Zillionim

Đề bài

Zillionim là trò chơi theo lượt cho hai người. Ban đầu, \(10^{12}\) đồng xu được xếp nối tiếp thành một hàng, đánh số từ \(1\) đến \(10^{12}\) từ trái sang phải. Mỗi lượt, người chơi phải chọn và loại bỏ \(10^{10}\) đồng xu liên tiếp. Hai đồng xu vốn không liên tiếp sẽ không trở thành liên tiếp, ngay cả khi mọi đồng xu ở giữa đã bị loại bỏ.

Đến lượt mình, người chơi thực hiện một nước hợp lệ nếu có thể, rồi tới lượt đối thủ. Người không thể thực hiện nước hợp lệ trong lượt của mình sẽ thua (và đối thủ thắng).

Vì các kỹ sư vẫn đang huấn luyện mô hình máy học chơi Zillionim, chúng tôi đã tạo một AI đơn giản chơi bằng nước đi ngẫu nhiên. AI luôn đi trước. Mỗi lượt, AI xác định mọi nước hợp lệ rồi chọn đều ngẫu nhiên một nước.

Bạn có thể đánh bại AI này... ít nhất trong phần lớn số ván không?

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là bài tương tác. Bạn cần bảo đảm đã đọc phần Bài toán tương tác trong mục Câu hỏi thường gặp.

Ban đầu, chương trình đọc một dòng chứa hai số nguyên \(T\), số bộ test, và \(W\), số ván tối thiểu cần thắng để lời giải được xem là đúng. Sau đó, bạn xử lý \(T\) bộ test, mỗi bộ là một ván Zillionim.

Mỗi bộ test được xử lý bằng các lần trao đổi với bộ chấm cho đến khi một người thắng. Trong mỗi lần trao đổi, bộ chấm trước tiên xuất một dòng chứa số nguyên \(P\), được hiểu như sau:

• Nếu \(1 \le P \le 10^{12}-10^{10}+1\), AI đã loại bỏ các đồng xu \(P,P+1,\ldots,P+10^{10}-1\), và đến lượt bạn. Nghĩa là bạn còn ít nhất một nước hợp lệ. AI luôn đi hợp lệ.
• Nếu \(P=-2\), nước gần nhất của bạn đã giúp bạn thắng ván hiện tại.
• Nếu \(P=-3\), AI vừa đi và thắng ván hiện tại. Trong trường hợp này, bộ chấm không gửi nước cuối của AI.
• Nếu \(P=-1\), thông tin cuối bạn gửi sai định dạng hoặc là nước không hợp lệ (ngoài phạm vi hoặc cố loại bỏ đồng xu không còn tồn tại), nên bạn nhận Wrong Answer vì chơi sai (xem thêm bên dưới).

Sau khi nhận \(P\) dương, bạn phải gửi một dòng chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^{12}-10^{10}+1\)), biểu thị việc loại bỏ các đồng xu \(Q,Q+1,\ldots,Q+10^{10}-1\). Tất cả chúng phải chưa bị loại bỏ trong ván hiện tại.

Sau khi bộ chấm gửi -2 hoặc -3, nếu đó là ván cuối thì bộ chấm và chương trình đều kết thúc. Nếu không, bộ chấm gửi dữ liệu của lần trao đổi đầu tiên trong ván kế tiếp. Bộ chấm chỉ kiểm tra số ván thắng/thua sau khi mọi ván được xử lý đúng. Ví dụ, nếu thắng \(T-1\) ván rồi gửi dữ liệu sai trong ván cuối, bạn vẫn nhận Wrong Answer, bất kể \(W\).

Sau khi nhận -1, chương trình phải kết thúc để nhận Wrong Answer. Nếu vẫn chờ bộ chấm, chương trình sẽ hết thời gian và nhận Time Limit Exceeded. Bạn có trách nhiệm để chương trình thoát bình thường và đúng hạn, nhằm nhận Wrong Answer thay vì Runtime Error hoặc Time Limit Exceeded.

Hạt giống sinh số ngẫu nhiên được định trước (và khác nhau) cho từng ván. Vì vậy, hai bài nộp thực hiện chính xác cùng chuỗi nước trong một ván sẽ nhận chính xác cùng chuỗi nước từ AI trong ván ấy. Cách AI chơi trong một ván cũng không phụ thuộc, kể cả theo nghĩa sinh giả ngẫu nhiên, vào các nước trong những ván trước thuộc cùng bộ test.

Ràng buộc

• \(T=500\).
• \(-3 \le P \le 10^{12}-10^{10}+1\).
• \(P \ne 0\).
• \(P\) biểu thị nước đi hợp lệ hoặc thông tin hợp lệ về trạng thái ván, như giải thích ở trên.

Phân nhóm

Bộ test 1 (Hiển thị)

\(W=300\).

Bộ test 2 (Hiển thị)

\(W=475\).

Bộ test 3 (Hiển thị)

\(W=499\).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ này để kiểm tra cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm tra cục bộ, cần chạy công cụ song song với chương trình; có thể dùng trình chạy tương tác của chúng tôi. Hãy đọc hướng dẫn trong chú thích của tệp đó và phần Bài toán tương tác trong mục Câu hỏi thường gặp.

Hướng dẫn sử dụng nằm trong chú thích của công cụ. Chúng tôi khuyến khích bạn tự thêm ca kiểm thử. Dù nhằm mô phỏng hệ thống chấm, công cụ này KHÔNG PHẢI hệ thống chấm thật và có thể hoạt động khác. Nếu chương trình vượt qua công cụ nhưng thất bại trên bộ chấm thật, hãy xem phần Lập trình trong Câu hỏi thường gặp để bảo đảm bạn dùng cùng trình biên dịch với chúng tôi.

Tải công cụ kiểm thử

Ví dụ

t, w = readline_int_list()   // đọc 500 vào t và 300 vào w
p = readline_int()           // đọc 23; bắt đầu ván 1. AI lấy xu 23 đến 32.
printline 38 to stdout       // ta lấy xu 38 đến 47
flush stdout
p = readline_int()           // đọc 3. AI lấy xu 3 đến 12.
printline 13 to stdout       // ta lấy xu 13 đến 22 (nước duy nhất còn lại!)
flush stdout
p = readline_int()           // đọc -2. Ta thắng ván 1 vì AI hết nước.
p = readline_int()           // đọc 32; bắt đầu ván 2. AI lấy xu 32 đến 41.
printline 13 to stdout       // ta lấy xu 13 đến 22
flush stdout
p = readline_int()           // đọc -3. Không biết nước của AI, nhưng ta hết nước và thua ván 2.
p = readline_int()           // đọc 10; bắt đầu ván 3. AI lấy xu 10 đến 19.
printline 0 to stdout        // chọn chỉ số sai (đánh số xu bắt đầu từ 1!)
flush stdout
p = readline_int()           // đọc -1 — ta đã mắc lỗi!
exit                         // thoát để tránh lỗi TLE không rõ nguyên nhân

Nguồn

Google Code Jam 2019, Vòng 3, bài Zillionim.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.