solution

Khác với First-Fit (luôn bắt đầu tìm từ đầu danh sách), chiến lược Next-Fit ghi nhớ vị trí đã cấp phát lần trước và lần tìm kiếm tiếp theo bắt đầu ngay sau đó (kiểu vòng tròn / circular), tránh quét lại nhiều lần các khối nhỏ ở đầu danh sách.

Cho một vùng nhớ liên tục kích thước $N$ byte (địa chỉ $0..N-1$), ban đầu là một khối trống duy nhất. Có $Q$ thao tác lần lượt:

• ALLOC size: cấp phát $size$ byte liên tục bằng Next-Fit. Gọi $p$ là địa chỉ ngay sau vùng nhớ được cấp ở lần ALLOC thành công gần nhất (ban đầu $p=0$). Xét danh sách khối trống hiện tại theo thứ tự địa chỉ tăng dần; bắt đầu quét từ khối trống đầu tiên có địa chỉ bắt đầu $\ge p$ (nếu không có khối nào như vậy, coi như quay vòng về khối đầu danh sách); quét vòng tròn qua tất cả khối trống, chọn khối đầu tiên gặp có kích thước $\ge size$; cấp phát từ đầu khối đó, cập nhật $p$ = địa chỉ ngay sau vùng vừa cấp. Nếu không có khối nào đủ lớn, in FAIL (giữ nguyên $p$). Mỗi lần ALLOC thành công được gán id tăng dần $1,2,3,\dots$ (không tính các lần FAIL).
• FREE id: giải phóng vùng nhớ đã cấp cho lần ALLOC thành công thứ $id$ (đảm bảo đang được cấp, chưa free trước đó), đưa vùng đó về danh sách khối trống, rồi hợp nhất (coalesce) ngay với khối trống liền kề bên trái và/hoặc bên phải (nếu "chạm" địa chỉ) thành một khối lớn hơn. FREE không tạo output.

Yêu cầu: với mỗi thao tác ALLOC theo đúng thứ tự, in địa chỉ được cấp phát hoặc FAIL.

Ví dụ: $N=30$. ALLOC 10 → $0$; ALLOC 10 → $10$; FREE 1 (trả lại $[0,10)$); ALLOC 10 → vì $p=20$ (sau lần cấp gần nhất tại địa chỉ $10$ kích thước $10$), Next-Fit tìm khối đầu tiên có start $\ge 20$, tức $[20,30)$, nên cấp tại $\mathbf{20}$ — không quay lại $[0,10)$ dù nó trống và đủ lớn; đây là điểm khác biệt so với First-Fit.