Koala đã tạo ra một trò chơi mới và thách đấu bạn! Cô ấy bắt đầu bằng cách đặt xuống \(N\) vật phẩm, được đánh số từ \(0\) đến \(N-1\). Sau đó, cô bí mật gán cho mỗi vật phẩm một giá trị nguyên từ \(1\) đến \(N\) sao cho không có hai vật phẩm nào nhận cùng một giá trị. Vật phẩm \(i\) có giá trị \(P_i\). Cô thách bạn xác định một số tính chất của dãy giá trị \(P = P_0,P_1,\ldots,P_{N-1}\).

Để làm điều đó, bạn sẽ yêu cầu Koala chơi một số vòng. Trong mỗi vòng, bạn có \(W\) viên đá xanh lam và Koala có \(W\) viên đá đỏ. Bạn đi trước bằng cách đặt một số (có thể là tất cả) đá của mình cạnh những vật phẩm tùy chọn. Sau khi nhìn thấy cách sắp xếp của bạn, Koala cũng đặt một số (có thể là tất cả) đá của cô ấy cạnh các vật phẩm. Koala giành được tất cả các vật phẩm có số đá đỏ đặt cạnh nhiều hơn số đá xanh lam. Koala luôn phân phối đá sao cho tổng giá trị các vật phẩm cô giành được là lớn nhất. Nếu có nhiều cách đạt tổng giá trị lớn nhất, cô chọn cách giành được tổng số vật phẩm lớn nhất. Nếu vẫn còn nhiều cách, cô chọn một cách bất kỳ trong số đó.

Koala rất lười và sẽ ngủ quên nếu bạn yêu cầu cô chơi quá nhiều vòng. Nhiệm vụ của bạn là nhận biết các tính chất trong dãy \(P\) của Koala bằng cách chơi càng ít vòng càng tốt.

Chi tiết cài đặt

Thí sinh được khuyến nghị dùng mã mẫu của ngôn ngữ mình chọn làm điểm bắt đầu. Thí sinh phải cài đặt cả bốn hàm sau, kể cả khi chỉ làm một số subtasks; những hàm không dùng đến có thể để trống. Chương trình không được đọc từ đầu vào chuẩn, ghi ra đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào.

Trong mỗi hàm, tham số N là số vật phẩm và W là số đá mà cả bạn lẫn Koala có trong mỗi vòng.

int minValue(int N, int W);

• Trả về số hiệu \(i\) của vật phẩm có giá trị nhỏ nhất, tức là \(P_i = 1\).

int maxValue(int N, int W);

• Trả về số hiệu \(i\) của vật phẩm có giá trị lớn nhất, tức là \(P_i = N\).

int greaterValue(int N, int W);

• So sánh giá trị của vật phẩm \(0\) và \(1\), rồi trả về số hiệu của vật phẩm có giá trị lớn hơn. Cụ thể, trả về \(0\) nếu \(P_0 > P_1\), ngược lại trả về \(1\).

void allValues(int N, int W, int *P);

• Xác định toàn bộ dãy và ghi vào mảng P: với mọi \(0 \le i \le N-1\), P[i] phải chứa giá trị \(P_i\) của vật phẩm \(i\).
• Hàm không trả về giá trị.

Trong mỗi testcase, trình chấm gọi chính xác một trong bốn hàm trên một hoặc nhiều lần. Mỗi lời gọi hàm được coi là một ván chơi riêng. Hàm nào được gọi và số lần tối đa hàm đó có thể được gọi phụ thuộc vào subtask. Có thể giả sử Koala đã cố định dãy \(P\) trước mỗi lời gọi hàm và dãy không thay đổi trong suốt lời gọi đó. Cô ấy có thể thay đổi dãy trước lời gọi hàm tiếp theo.

Mỗi hàm do thí sinh cài đặt có thể gọi hàm sau để lấy thông tin về dãy của Koala:

void playRound(int *B, int *R);

• Hàm này yêu cầu Koala chơi một vòng với bạn và không trả về giá trị.
• Mảng B mô tả số đá xanh lam bạn đặt cạnh từng vật phẩm. Với mọi \(0 \le i \le N-1\), B[i] viên đá xanh lam được đặt cạnh vật phẩm \(i\). Mỗi B[i] phải là số nguyên không âm và B[0] + B[1] + ... + B[N-1] không được vượt quá \(W\).
• Trình chấm điền vào mảng R để mô tả câu trả lời của Koala. Với mọi \(0 \le i \le N-1\), Koala đặt R[i] viên đá đỏ cạnh vật phẩm \(i\).
• Mỗi subtask quy định một giới hạn cứng cho số lần gọi playRound trong mỗi ván. Dùng ít lời gọi hơn giới hạn này có thể đem lại điểm cao hơn.

Phân nhóm

Gọi \(C_{max}\) là số lần gọi playRound lớn nhất trong tất cả các ván của một testcase, và \(C\) là số lần gọi playRound trong ván duy nhất của testcase thuộc Subtask 5.

Trong công thức trên, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Trong mỗi testcase, chương trình phải luôn chạy trong giới hạn thời gian và bộ nhớ. Điều này bao gồm cả thời gian và bộ nhớ mà trình chấm sử dụng khi thiết lập, kết thúc và trả lời các lời gọi playRound. Khi ước lượng phần chi phí này, có thể giả sử trình chấm dùng để chấm có chức năng giống hệt và cách cài đặt tương tự trình chấm mẫu được cung cấp.

Nếu gọi playRound với mảng B không hợp lệ, hoặc số lời gọi playRound vượt giới hạn cứng của bất kỳ ván nào trong testcase, toàn bộ testcase bị chấm Not Correct và nhận \(0\) điểm.

Nếu một hàm không xác định đúng tính chất được yêu cầu của dãy \(P\) trong một ván bất kỳ của testcase, toàn bộ testcase bị chấm Not Correct và nhận \(0\) điểm.

Cả Subtask 4 và Subtask 5 đều yêu cầu cài đặt allValues, nhưng có giá trị \(W\) khác nhau. Có thể dùng điều này để phân biệt hai subtasks trong chương trình.

Bạn được nộp bài tối đa \(60\) lần và khoảng cách giữa hai lần nộp liên tiếp phải ít nhất \(2\) phút.

Ví dụ

Xét dãy \(P\) sau:

Dưới đây là một số lời gọi mẫu đến playRound và một câu trả lời hợp lệ của trình chấm cho mỗi lời gọi. Có thể có nhiều hơn một câu trả lời hợp lệ cho một lời gọi playRound.

Phản hồi cho từng hàm mà trình chấm gọi dưới đây (đúng một hàm trong mỗi testcase) được cung cấp theo thứ tự dưới dạng "Sample Data" khi nộp bài. Trong mỗi testcase này, được gọi playRound nhiều nhất \(3200\) lần.

Trình chấm mẫu

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

• Dòng \(1\): hai số nguyên \(F\), \(G\).
• Các dòng từ \(2\) đến \(G+1\): mỗi dòng chứa hai số nguyên \(N\), \(W\), theo sau bởi \(N\) số nguyên \(P_0,P_1,\ldots,P_{N-1}\) mô tả một ván.

Số nguyên \(F\) xác định hàm mà trình chấm mẫu sẽ gọi:

Số nguyên \(G\) xác định số lần gọi hàm đã chọn. Mỗi dòng sau đó mô tả một ván với dãy của Koala.

Với mỗi lời gọi hàm, trình chấm mẫu ghi hai dòng ra đầu ra chuẩn. Dòng đầu chứa số lần gọi playRound.

• Nếu \(F=4\), dòng thứ hai chứa nội dung mà hàm allValues đã ghi vào mảng P.
• Nếu \(F=1\), \(2\) hoặc \(3\), dòng thứ hai chứa một số nguyên duy nhất là giá trị trả về của hàm tương ứng.

Ví dụ, testcase thứ tư trong "Sample Data", gọi allValues với \(N=6\) và \(W=12\), có thể được mô tả bằng tệp đầu vào mẫu sau:

4 1
6 12 5 3 2 1 6 4

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2017: Koala Game.