Digit Blocks

Bạn sẽ xây \(N\) tháp, mỗi tháp gồm \(B\) khối lập phương, mỗi lần đặt một khối. Tháp được xây từ dưới lên: khối thứ \(i\) đặt vào một tháp sẽ là khối thứ \(i\) tính từ đáy. Bạn phải chọn vị trí cho mỗi khối trước khi thấy các khối sắp tới; đã đặt thì không được di chuyển.

Mỗi khối in một chữ số thập phân, các mặt chữ số cùng hướng ra trước. Phông chữ không cho phép xoay để đổi chữ số; chẳng hạn không thể xoay \(6\) thành \(9\).

Ví dụ, \(N=B=3\) và trạng thái hiện tại ở Hình 1. Nếu khối \(6\) xuất hiện, có thể đặt lên tháp đang có hai khối (Hình 2) hoặc bắt đầu tháp thứ ba (Hình 3); không thể đặt lên tháp đầu vì nó đã đủ \(B\) khối.

Khi xây xong, đọc số \(B\) chữ số trên mỗi tháp từ trên xuống; khối đặt cuối là chữ số có nghĩa lớn nhất. Các số có thể có tùy ý số \(0\) ở đầu. Cộng \(N\) số để được điểm. Ở Hình 4, ba số là \(123,345,96\), điểm \(123+345+96=564\).

Chữ số mỗi khối được sinh đều ngẫu nhiên, độc lập với mọi thông tin khác. Tổng điểm trên \(T\) bộ phải ít nhất \(P\).

Giao thức tương tác

Các mục Dữ liệu vào và Dữ liệu ra dưới đây quy định đầy đủ cuộc đối thoại giữa chương trình và bộ chấm.

Dữ liệu vào

Đây là bài tương tác; hãy bảo đảm bạn đã đọc hướng dẫn chung dành cho bài tương tác. Ban đầu bộ chấm gửi một dòng chứa \(T,N,B,P\), lần lượt là số bộ test, số tháp, số khối trong mỗi tháp và tổng điểm tối thiểu cần đạt để vượt phân nhóm. Sau đó mỗi bộ gồm \(NB\) lượt trao đổi, mỗi lượt tương ứng với việc đặt một khối. Trước tiên bộ chấm in một dòng chứa chữ số \(D\) trên khối cần đặt; chương trình trả một dòng chứa số \(i\in[1,N]\), là tháp nhận khối.

Sau lượt cuối của mỗi bộ trừ bộ cuối, bộ chấm lập tức bắt đầu bộ kế. Sau lượt cuối của bộ cuối, nó in 1 nếu tổng điểm ít nhất \(P\), -1 nếu không.

Dữ liệu ra

Trong mỗi lượt, in số hiệu một tháp chưa đủ \(B\) khối và xả bộ đệm. Nếu dòng sai định dạng, số hiệu tháp ngoài phạm vi hoặc tháp đã đủ \(B\) khối, bộ chấm in -1 rồi không xuất thêm gì. Sau bất kỳ -1 nào vì những lý do trên, chương trình phải tự thoát kịp thời; nếu tiếp tục chờ bộ chấm, chương trình sẽ bị treo thay vì nhận phán quyết cho đáp án sai. Các lỗi chạy chương trình khác vẫn nhận phán quyết tương ứng.

Mỗi chữ số được sinh đều, độc lập theo từng khối, từng bộ và từng lượt nộp. Vì vậy, ngay cả hai lượt nộp cùng mã nguồn cũng có thể nhận các chữ số khác nhau.

Ràng buộc

• \(T=50\), \(N=20\), \(B=15\); \(D\in[0,9]\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(P=860939810732536850\approx8{,}6\cdot10^{17}\). Ngưỡng xấp xỉ \(90\%\) của \(T\cdot S\), trong đó \(S=19131995794056374{,}42\ldots\approx1{,}9\cdot10^{16}\) là điểm kỳ vọng cao nhất có thể trên một bộ nếu thời gian không giới hạn. Giá trị chính xác của \(S\) nằm ở dòng 13–14 của công cụ kiểm thử gốc.
• Test Set 2 (Visible Verdict): \(P=937467793908762347\approx9{,}37\cdot10^{17}\), xấp xỉ \(98\%\) của \(T\cdot S\).

Công cụ kiểm thử

Kho chính thức cung cấp công cụ mô phỏng để chạy cục bộ hoặc trên nền tảng gốc. Khi chạy cục bộ, cần chạy công cụ song song với lời giải, chẳng hạn qua interactive runner; hướng dẫn sử dụng nằm trong phần chú thích của công cụ và hướng dẫn chung cho bài tương tác. Bạn được khuyến khích tự thêm bộ test. Công cụ không phải bộ chấm thật và có thể hành xử khác; nếu mã vượt công cụ nhưng không vượt hệ thống gốc, tài liệu chính thức còn yêu cầu kiểm tra rằng trình biên dịch đang dùng giống với trình biên dịch của hệ thống. Bản LQDOJ dùng interactor đi kèm gói bài.

Ví dụ

Nguồn

Google Code Jam 2021, Vòng 1B, bài Digit Blocks.

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