Anna và Bruno thích bói toán và thường cùng nhau thử nhiều cách bói khác nhau. Hôm nay, họ sẽ thực hiện \(Q\) lượt bói bằng những lá bài ghi số \(0\) hoặc \(1\). Mỗi lượt diễn ra như sau:

1. Họ chuẩn bị nhiều lá bài, mỗi lá ghi số \(0\) hoặc \(1\), xáo trộn rồi xếp thành một chồng bài.
2. Anna rút lần lượt từng lá, tổng cộng \(N=900\) lá. Cả Anna và Bruno đều biết \(N\). Mỗi khi rút được một lá, Anna quyết định bỏ lá đó hoặc đặt nó lên bàn. Nếu đặt lên bàn, Anna được chèn lá bài vào bất kỳ vị trí nào trong dãy bài đang có. Cụ thể, nếu trên bàn đang có \(l\) lá, Anna chọn số nguyên \(x\) với \(0 \le x \le l\) và chèn lá mới ngay bên phải lá thứ \(x\) tính từ trái sang phải. Khi \(x=0\), lá mới được chèn vào đầu bên trái của dãy.
3. Sau khi rút và xử lý đủ \(N\) lá, phần việc của Anna kết thúc. Kết quả bói là số lá ghi số \(1\) trong toàn bộ \(N\) lá Anna đã rút, kể cả những lá đã bỏ đi.
4. Bruno chỉ nhìn dãy bài cuối cùng trên bàn để đoán kết quả bói. Nếu đoán đúng, lượt bói thành công.

Càng đặt ít lá bài lên bàn, cách bói càng được đánh giá cao. Hãy cài đặt chiến lược của Anna và Bruno để thành công trong cả \(Q\) lượt. Trong bài này, Anna đặt càng ít lá lên bàn thì bạn càng được nhiều điểm.

Chi tiết cài đặt

Bạn phải nộp hai tệp: Anna.cpp và Bruno.cpp.

Tệp Anna.cpp cài đặt chiến lược của Anna, phải nạp Anna.h bằng chỉ thị #include và cài đặt hàm sau:

void Anna(int N)

Hàm này được gọi tổng cộng \(Q\) lần. Lần gọi thứ \(i\) (\(1 \le i \le Q\)) tương ứng với phần việc của Anna trong lượt bói thứ \(i\). Tham số N là số lá bài Anna phải rút.

Trong mỗi lần thực hiện Anna, bạn phải gọi hàm sau đúng \(N+1\) lần:

int DrawCard(int x)

Hàm này cho phép Anna nhận lá bài tiếp theo đồng thời quyết định cách xử lý lá bài vừa rút trước đó. Giá trị trả về của lần gọi thứ \(j\) (\(1 \le j \le N\)) là số ghi trên lá bài thứ \(j\). Tham số của lần gọi thứ \(k\) (\(2 \le k \le N+1\)) chỉ định cách xử lý lá bài thứ \(k-1\).

• Lần gọi thứ \(j\) (\(1 \le j \le N\)) trả về \(0\) hoặc \(1\), là số ghi trên lá bài thứ \(j\) Anna rút được.
• Lần gọi thứ \(N+1\) trả về \(-1\), báo rằng Anna đã rút đủ bài.
• Trong lần gọi đầu tiên, bắt buộc phải có \(x=-1\). Nếu không, chương trình bị chấm Wrong Answer [1].
• Trong lần gọi thứ \(k\) (\(2 \le k \le N+1\)), nếu \(x=-1\) thì bỏ lá bài thứ \(k-1\). Nếu \(x \ge 0\), chèn lá đó ngay bên phải lá thứ \(x\) tính từ trái sang phải trong dãy hiện tại; riêng \(x=0\) nghĩa là chèn vào đầu bên trái. Gọi \(l\) là số lá hiện có trên bàn, tham số phải thỏa mãn \(-1 \le x \le l\). Nếu không, chương trình bị chấm Wrong Answer [2].
• Nếu số lần gọi DrawCard không đúng bằng \(N+1\) khi Anna kết thúc, chương trình bị chấm Wrong Answer [3].

Tệp Bruno.cpp cài đặt chiến lược của Bruno, phải nạp Bruno.h bằng chỉ thị #include và cài đặt hàm sau:

int Bruno(int N, int L, std::vector<int> C)

Hàm này được gọi đúng một lần sau mỗi lần gọi Anna, tổng cộng \(Q\) lần. Lần gọi thứ \(i\) (\(1 \le i \le Q\)) tương ứng với phần việc của Bruno trong lượt bói thứ \(i\). Hàm phải trả về số lá ghi số \(1\) trong tất cả các lá Anna đã rút.

• N là số lá bài Anna đã rút.
• L là số lá bài đang nằm trên bàn.
• C là mảng có độ dài L. Phần tử C[l-1] là số ghi trên lá thứ \(l\) tính từ trái sang phải trên bàn, với \(1 \le l \le L\).
• Nếu giá trị trả về không bằng số lá ghi số \(1\) mà Anna đã rút, chương trình bị chấm Wrong Answer [4].

Lưu ý quan trọng

Bạn được cài đặt các hàm phụ và khai báo biến toàn cục. Hai tệp nộp sẽ được liên kết cùng bộ chấm thành một tệp thực thi. Để tránh xung đột tên giữa các tệp, mọi biến toàn cục và hàm nội bộ phải được khai báo trong một không gian tên không có tên, tức namespace { ... }.

Khi chấm thật, tệp thực thi được chạy thành hai tiến trình, một phía Anna và một phía Bruno. Hai phía không thể chia sẻ biến toàn cục.

Chương trình bạn nộp không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Bộ chấm thật không thích nghi: dãy số trên các lá bài đã được cố định trước khi chương trình chạy, không thay đổi dựa trên hành động của chương trình.

Biên dịch và chạy thử

Gói tệp tải từ trang kỳ thi chứa bộ chấm mẫu và các tệp mã nguồn mẫu. Bộ chấm mẫu nằm trong grader.cpp.

Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng một thư mục, rồi biên dịch bằng lệnh:

g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Bạn cũng có thể chạy tệp compile.sh đi kèm gói tải:

./compile.sh

Nếu biên dịch thành công, tệp thực thi grader được tạo ra.

Bộ chấm thật khác với bộ chấm mẫu. Bộ chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Thông tin gỡ lỗi có thể được ghi ra đầu ra lỗi chuẩn. Việc bộ chấm mẫu đọc và ghi các luồng này không cho phép mã bạn nộp sử dụng chúng.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên \(Q,N\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên \(A_{i,1},A_{i,2},\ldots,A_{i,N}\), cách nhau bởi dấu cách.

\(A_{i,j}\) (\(1 \le i \le Q\), \(1 \le j \le N\)) là số ghi trên lá bài thứ \(j\) mà Anna rút trong lượt bói thứ \(i\).

Dữ liệu ra

Bộ chấm mẫu thông báo kết quả theo các dạng sau; dấu ngoặc kép không được in:

• Nếu chương trình đúng, bộ chấm in số lá bài trên bàn lớn nhất trong tất cả các lượt, chẳng hạn Accepted: 100. Số sau dấu hai chấm là số lá bài, không phải số điểm.
• Nếu chương trình sai, bộ chấm in loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình đồng thời vi phạm nhiều điều kiện, bộ chấm mẫu chỉ báo một loại lỗi trong số đó. Bộ chấm mẫu có thể dừng chương trình ngay khi phát hiện lỗi.

Ràng buộc

• \(1 \le Q \le 100\).
• \(N=900\).
• \(A_{i,j}\) là \(0\) hoặc \(1\) với \(1 \le i \le Q\), \(1 \le j \le N\).

Chấm điểm

Nếu chương trình bị chấm một trong các lỗi Wrong Answer [1] đến Wrong Answer [4], quá thời gian, quá bộ nhớ hoặc lỗi khi chạy ở bất kỳ bộ dữ liệu nào, bạn nhận \(0\) điểm cho toàn bộ bài.

Nếu chương trình đúng ở tất cả các bộ dữ liệu, gọi \(L\) là giá trị lớn nhất của số lần gọi DrawCard với tham số \(x \ge 0\) trong một lần gọi Anna, xét trên mọi lượt bói của mọi bộ dữ liệu. Đây cũng là số lá bài trên bàn lớn nhất. Điểm được tính như sau:

• Nếu \(L>500\): nhận \(3\) điểm.
• Nếu \(14<L \le 500\): nhận \(\left\lfloor 100\left(\frac{2.5}{L-11.5}\right)^{0.35}\right\rfloor\) điểm.
• Nếu \(L \le 14\): nhận \(100\) điểm.

Ví dụ giao tiếp

Dưới đây là dữ liệu vào của bộ chấm mẫu và một chuỗi lời gọi hàm tương ứng. Phần Output biểu diễn các lời gọi và giá trị trả về, không phải văn bản mà chương trình nộp phải in. Các lời gọi DrawCard được thụt vào bên dưới lần gọi Anna đang thực hiện.

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

2 5
0 1 0 0 1
1 1 0 1 0

Dữ liệu ra của trình chấm mẫu:

Anna(5)
  DrawCard(-1) -> 0
  DrawCard(0) -> 1
  DrawCard(-1) -> 0
  DrawCard(1) -> 0
  DrawCard(-1) -> 1
  DrawCard(1) -> -1
Bruno(5, 3, [0, 1, 0]) -> 2
Anna(5)
  DrawCard(-1) -> 1
  DrawCard(0) -> 1
  DrawCard(1) -> 0
  DrawCard(2) -> 1
  DrawCard(-1) -> 0
  DrawCard(1) -> -1
Bruno(5, 4, [1, 0, 1, 0]) -> 3

Giải thích

Ví dụ có \(Q=2\) lượt bói, mỗi lượt Anna rút \(N=5\) lá. Trong lượt thứ nhất, Anna thực hiện như sau:

1. Rút một lá bài ghi số \(0\).
2. Chọn đặt lá đó lên bàn, chèn vào đầu bên trái. Dãy trên bàn trở thành \(0\). Sau đó rút lá tiếp theo, ghi số \(1\).
3. Bỏ lá vừa rút. Sau đó rút lá tiếp theo, ghi số \(0\).
4. Chọn đặt lá đó lên bàn, chèn ngay bên phải lá thứ nhất tính từ trái sang phải. Dãy trên bàn trở thành \(0,0\). Sau đó rút lá tiếp theo, ghi số \(0\).
5. Bỏ lá vừa rút. Sau đó rút lá tiếp theo, ghi số \(1\).
6. Chọn đặt lá đó lên bàn, chèn ngay bên phải lá thứ nhất tính từ trái sang phải. Dãy trên bàn trở thành \(0,1,0\).

Bruno biết \(N\) và nhìn thấy dãy \(0,1,0\). Bruno đoán rằng có \(2\) lá ghi số \(1\) trong các lá Anna đã rút. Đáp án đúng nên lượt bói thành công. Số lá Anna đặt lên bàn trong lượt này là \(L=3\).

Trong lượt bói thứ hai, Anna đặt \(L=4\) lá lên bàn.

Ví dụ này không thỏa mãn ràng buộc của bài, vì \(N=5\) thay vì \(900\). Tệp sample-01-in.txt trong gói tải tương ứng với ví dụ trên. Tệp sample-02-in.txt đi kèm là một dữ liệu mẫu thỏa mãn các ràng buộc.

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ nhất. Tham khảo thêm gói bộ chấm mẫu, thông báo triển khai và thông tin chấm điểm. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.