Hệ thống Buddy (Buddy System) cấp phát bộ nhớ. Tổng bộ nhớ có kích thước 2^M đơn vị (một khối duy nhất ban đầu). Khi cần cấp phát một vùng kích thước s, hệ thống làm tròn s lên luỹ thừa của 2 nhỏ nhất ≥ s (gọi là kích thước khối cần là 2^k).
Cấp phát: tìm khối tự do nhỏ nhất có kích thước ≥ 2^k. Nếu khối tìm được lớn hơn 2^k, chia đôi liên tiếp (mỗi lần tách thành 2 khối "buddy" bằng nhau) cho đến khi được đúng kích thước 2^k, rồi cấp khối đầu (địa chỉ thấp hơn). Nếu không có khối nào đủ lớn, yêu cầu thất bại.
Cho danh sách Q yêu cầu cấp phát (chỉ cấp phát, không giải phóng). Với mỗi yêu cầu in ra bậc k của khối được cấp (số mũ, tức khối có kích thước 2^k), hoặc -1 nếu thất bại. In mỗi kết quả trên một dòng.
Ví dụ: M=3 (tổng 8). Yêu cầu s=1 -> cần 2^0, tách 8->4+4->2+2->1+1, cấp khối 1 (k=0). s=3 -> cần 2^2=4, có khối 4 còn lại, cấp (k=2).
Dòng đầu: M (tổng bộ nhớ = 2^M) và Q (số yêu cầu). Dòng tiếp: Q số nguyên là kích thước các yêu cầu cấp phát.
1 ≤ M ≤ 30; 1 ≤ Q ≤ 100000; 1 ≤ s ≤ 2^M.
Q dòng, mỗi dòng là bậc k của khối được cấp (kích thước 2^k) hoặc -1 nếu thất bại.
Ví dụ:
Đầu vào:
3 2
1 3
Đầu ra:
0
2
Giải thích:
Đang tải editor...