solution

Hệ thống buddy quản lý một vùng nhớ kích thước $2^k$ byte bằng cách chia đôi đệ quy: một khối kích thước $2^{e}$ có thể tách thành hai khối "buddy" kích thước $2^{e-1}$ đặt liên tiếp. Khi cấp phát $size$ byte, kích thước thực tế được làm tròn lên thành lũy thừa của $2$ nhỏ nhất $\ge size$ (gọi bậc $e = \log_2$ của kích thước đó). Ban đầu chỉ có một khối trống duy nhất, bậc $k$, tại địa chỉ $0$.

Có $Q$ thao tác:

• ALLOC size: tính bậc cần thiết $e$ (nhỏ nhất sao cho $2^e \ge size$). Tìm khối trống bậc $f \ge e$ nhỏ nhất hiện có (nếu nhiều khối cùng bậc $f$, chọn khối địa chỉ nhỏ nhất); nếu $f=e$ thì cấp phát luôn khối đó; nếu $f>e$, tách khối liên tục thành hai nửa bậc $f-1$: giữ nửa địa chỉ thấp hơn để tiếp tục tách (nếu cần), đưa nửa còn lại vào danh sách khối trống bậc $f-1$, lặp lại tới khi đạt bậc $e$, rồi cấp phát khối địa chỉ thấp đó. Nếu không có khối trống bậc $\ge e$ nào (kể cả xét hết tới bậc $k$), in FAIL. Mỗi lần ALLOC thành công được gán id tăng dần $1,2,3,\dots$.
• FREE id: giải phóng khối đã cấp cho lần ALLOC thành công thứ $id$. Đưa khối về danh sách trống ở đúng bậc của nó, sau đó hợp nhất liên tiếp với "buddy" của nó (địa chỉ buddy = địa chỉ hiện tại XOR $2^{bậc}$) nếu buddy đó cũng đang trống và cùng bậc — hợp nhất thành khối bậc cao hơn $1$, tiếp tục thử hợp nhất lên các bậc cao hơn cho tới khi không thể hoặc đạt bậc $k$. FREE không tạo output.

Yêu cầu: với mỗi ALLOC, in địa chỉ cấp phát hoặc FAIL.

Ví dụ: $k=4$ (vùng nhớ $16$ byte). ALLOC 3 (cần bậc $2$, tức $4$ byte): tách $16 \to 8+8$, tách tiếp $8 \to 4+4$, cấp tại địa chỉ $\mathbf{0}$ (còn dư khối trống bậc $2$ tại địa chỉ $4$ và bậc $3$ tại địa chỉ $8$).