solution

Đề bài: [Lập trình Web & Backend] Mô phỏng LRU: hit hay miss

LRU Cache

Cache LRU (Least Recently Used) có sức chứa C. Khi truy cập một key:

Nếu key đã có → HIT, đưa key lên "mới dùng nhất".
Nếu chưa có → MISS, thêm key (mới dùng nhất). Nếu vượt C thì loại bỏ key ít dùng gần đây nhất.

Yêu cầu

Dòng 1: C (sức chứa). Dòng 2: số truy vấn Q. Q dòng tiếp theo: mỗi dòng một key (chuỗi). In ra Q dòng, mỗi dòng HIT hoặc MISS tương ứng.

Ví dụ

Input:

2
3
a
b
a

a→MISS, b→MISS, a→HIT (a vẫn còn).

Định dạng đầu vào:
Dòng 1: C. Dòng 2: Q. Q dòng tiếp: mỗi dòng một key.
Ràng buộc đầu vào:
1 ≤ C ≤ 1000, 1 ≤ Q ≤ 10000. Key là chuỗi không chứa khoảng trắng.
Định dạng đầu ra:
Q dòng: HIT hoặc MISS cho từng truy vấn.

Ví dụ:

Đầu vào:

2
3
a
b
a

Đầu ra:

MISS
MISS
HIT

Giải thích:

a và b nạp mới (MISS), sức chứa 2 nên a còn trong cache, truy cập lại là HIT.

Đang tải editor...