Amaru đang đi mua quà lưu niệm tại một cửa hàng ở nước ngoài. Cửa hàng có \(N\) loại quà lưu niệm, và mỗi loại có vô số quà sẵn có.

Mỗi loại quà lưu niệm có một mức giá cố định. Cụ thể, quà lưu niệm loại \(i\) (với \(0 \le i < N\)) có giá \(P[i]\) đồng xu, trong đó \(P[i]\) là một số nguyên dương.

Amaru biết rằng các loại quà lưu niệm đã được sắp xếp theo thứ tự giảm dần theo giá, và các giá đều phân biệt. Cụ thể, \(P[0] > P[1] > \cdots > P[N-1] > 0\). Hơn nữa, anh ấy đã biết được giá trị \(P[0]\). Đáng tiếc là Amaru không có thêm bất kỳ thông tin nào khác về giá của các loại quà.

Để mua quà, Amaru sẽ thực hiện một số giao dịch với người bán. Mỗi giao dịch gồm các bước sau:

1. Amaru đưa một số (dương) đồng xu cho người bán.
2. Người bán đặt số đồng xu này thành một đống trên bàn ở phòng phía sau, nơi Amaru không nhìn thấy.
3. Người bán xét lần lượt từng loại quà lưu niệm \(0, 1, \ldots, N-1\) theo đúng thứ tự đó. Mỗi loại được xét đúng một lần trong mỗi giao dịch.
   • Khi đang xét loại \(i\), nếu số đồng xu hiện có trong đống ít nhất là \(P[i]\), thì:
     • người bán lấy đi \(P[i]\) đồng xu khỏi đống, và
     • đặt một quà lưu niệm loại \(i\) lên bàn.
4. Người bán trả lại cho Amaru toàn bộ số đồng xu còn lại trong đống và tất cả quà lưu niệm trên bàn.

Lưu ý rằng trên bàn không có đồng xu hay quà lưu niệm nào trước khi mỗi giao dịch bắt đầu.

Nhiệm vụ của bạn là chỉ dẫn cho Amaru thực hiện một số giao dịch sao cho:

• ở mỗi giao dịch, anh ấy mua được ít nhất một quà lưu niệm, và
• tổng cộng anh ấy mua đúng \(i\) quà lưu niệm loại \(i\), với mọi \(i\) thỏa \(0 \le i < N\). Lưu ý rằng điều này có nghĩa là Amaru không được mua quà lưu niệm loại \(0\).

Amaru không cần tối thiểu hóa số giao dịch và có nguồn cung đồng xu không giới hạn.

Đây là bài toán giao tiếp (Communication, được quản lý bằng manager.cpp), tuy về mặt logic nó là một bài tương tác trong cùng tiến trình thông qua các hàm gọi lại (callback).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong tệp souvenirs.h:

void buy_souvenirs(int N, long long P0)

• \(N\): số loại quà lưu niệm.
• \(P0\): giá trị của \(P[0]\).
• Hàm này được gọi đúng một lần cho mỗi test.

Bên trong hàm trên, bạn có thể gọi hàm thư viện sau (do trình chấm cung cấp) để chỉ thị cho Amaru thực hiện một giao dịch:

std::pair<std::vector<int>, long long> transaction(long long M)

• \(M\): số đồng xu mà Amaru đưa cho người bán.
• Hàm trả về một cặp giá trị. Phần tử thứ nhất là một mảng \(L\) chứa các loại quà lưu niệm đã mua được (theo thứ tự tăng dần). Phần tử thứ hai là một số nguyên \(R\), là số đồng xu còn lại được trả về cho Amaru sau giao dịch.
• Yêu cầu \(P[0] > M \ge P[N-1]\). Điều kiện \(P[0] > M\) đảm bảo Amaru không mua quà loại \(0\), và \(M \ge P[N-1]\) đảm bảo Amaru mua được ít nhất một quà. Nếu các điều kiện này không được thỏa, lời giải sẽ nhận kết quả Output isn't correct: Invalid argument. Lưu ý rằng khác với \(P[0]\), giá trị \(P[N-1]\) không được cung cấp cho bạn.
• Hàm này có thể được gọi tối đa \(5000\) lần trong mỗi test.

Hành vi của trình chấm là không thích nghi (not adaptive). Điều đó có nghĩa là dãy giá \(P\) được cố định trước khi buy_souvenirs được gọi.

Ràng buộc

• \(2 \le N \le 100\)
• \(1 \le P[i] \le 10^{15}\) với mọi \(i\) thỏa \(0 \le i < N\).
• \(P[i] > P[i+1]\) với mọi \(i\) thỏa \(0 \le i < N-1\).

Phân nhóm

• Subtask 1 (4 điểm): \(N = 2\).
• Subtask 2 (3 điểm): \(P[i] = N - i\) với mọi \(i\) thỏa \(0 \le i < N\).
• Subtask 3 (14 điểm): \(P[i] \le P[i+1] + 2\) với mọi \(i\) thỏa \(0 \le i < N-1\).
• Subtask 4 (18 điểm): \(N = 3\).
• Subtask 5 (28 điểm): \(P[i+1] + P[i+2] \le P[i]\) với mọi \(i\) thỏa \(0 \le i < N-2\), và \(P[i] \le 2 \cdot P[i+1]\) với mọi \(i\) thỏa \(0 \le i < N-1\).
• Subtask 6 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

Xét lời gọi sau:

buy_souvenirs(3, 4)

Có \(N = 3\) loại quà lưu niệm và \(P[0] = 4\). Quan sát rằng chỉ có ba dãy giá \(P\) khả dĩ: \([4, 3, 2]\), \([4, 3, 1]\) và \([4, 2, 1]\).

Giả sử buy_souvenirs gọi transaction(2) và lời gọi này trả về \(([2], 1)\), nghĩa là Amaru mua được một quà loại \(2\) và người bán trả lại \(1\) đồng xu. Quan sát điều này cho phép ta suy ra \(P = [4, 3, 1]\), vì:

• Với \(P = [4, 3, 2]\), transaction(2) sẽ trả về \(([2], 0)\).
• Với \(P = [4, 2, 1]\), transaction(2) sẽ trả về \(([1], 0)\).

Sau đó, buy_souvenirs có thể gọi transaction(3), trả về \(([1], 0)\), nghĩa là Amaru mua được một quà loại \(1\) và người bán trả lại \(0\) đồng xu. Cho tới đây, anh ấy đã mua được tổng cộng một quà loại \(1\) và một quà loại \(2\).

Cuối cùng, buy_souvenirs có thể gọi transaction(1), trả về \(([2], 0)\), nghĩa là Amaru mua được một quà loại \(2\). Lưu ý rằng ta cũng có thể dùng transaction(2) ở bước này. Tại thời điểm này, Amaru đã có một quà loại \(1\) và hai quà loại \(2\) — đúng theo yêu cầu.

3
4 3 1

0 1 2

Chấm điểm

Trình chấm mẫu (sample grader) đọc dữ liệu vào theo định dạng:

• Dòng \(1\): \(N\)
• Dòng \(2\): \(P[0]\ P[1]\ \ldots\ P[N-1]\)

Trình chấm mẫu in ra:

• Dòng \(1\): \(Q[0]\ Q[1]\ \ldots\ Q[N-1]\)

trong đó \(Q[i]\) là tổng số quà lưu niệm loại \(i\) mà Amaru đã mua được, với mọi \(i\) thỏa \(0 \le i < N\).