Đề bài

Odin có một số chiếc nhẫn phép thuật có khả năng tự tạo ra bản sao. Mỗi chiếc "nhẫn X ngày" cứ sau mỗi \(X\) ngày kể từ ngày nó xuất hiện lại tạo ra thêm một chiếc nhẫn X ngày. Có sáu loại nhẫn: nhẫn 1 ngày, nhẫn 2 ngày, ..., cho đến nhẫn 6 ngày.

Ví dụ, một chiếc nhẫn 3 ngày xuất hiện vào ngày 0 sẽ không làm gì cho đến ngày 3, khi nó tạo ra thêm một chiếc nhẫn 3 ngày. Sau đó, vào ngày 6, mỗi chiếc trong hai chiếc nhẫn này sẽ tạo ra thêm một chiếc nhẫn 3 ngày, và quá trình cứ tiếp tục như vậy.

Bạn biết rằng Odin không có chiếc nhẫn nào trước ngày 0. Vào ngày 0, một số chiếc nhẫn xuất hiện. Cuối ngày 0, với mỗi \(1 \le i \le 6\), Odin có \(R_i\) chiếc nhẫn \(i\) ngày. Bạn biết rằng \(0 \le R_i \le 100\) với mọi \(i\), và có ít nhất một giá trị \(R_i\) dương.

May mắn thay, bạn còn có thể sử dụng giếng tri thức bí mật. Mỗi lần sử dụng, bạn có thể biết tổng số nhẫn Odin có vào cuối một ngày cụ thể từ ngày 1 đến ngày 500, kể cả hai đầu mút. Vì ngay cả chiếc giếng cũng chỉ chứa được hữu hạn thông tin, nó sẽ trả lời theo modulo \(2^{63}\)! Ngoài ra, bạn chỉ được sử dụng giếng tối đa W lần.

Mục tiêu của bạn là xác định Odin có bao nhiêu chiếc nhẫn thuộc mỗi loại vào cuối ngày 0 — tức là tìm tất cả các giá trị \(R_i\).

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à một bài toán tương tác. Bạn cần bảo đảm rằng mình đã đọ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 phải đọc một dòng chứa hai số nguyên T, số lượng bộ test, và W, số lần được phép sử dụng giếng tri thức trong mỗi bộ test. Sau đó, bạn cần xử lý T bộ test.

Trong mỗi bộ test, chương trình thực hiện tối đa W + 1 lượt trao đổi với bộ chấm. Bạn có thể thực hiện tối đa W lượt trao đổi có dạng sau:

• Chương trình in một dòng chứa một số nguyên duy nhất \(D\) trong đoạn từ 1 đến 500, kể cả hai đầu mút.
• Bộ chấm trả lời bằng một dòng chứa một số nguyên duy nhất: tổng số nhẫn Odin có vào cuối ngày \(D\), theo modulo \(2^{63}\). Nếu bạn gửi dữ liệu không hợp lệ (chẳng hạn một số nằm ngoài phạm vi hoặc một dòng sai định dạng), bộ chấm sẽ trả lời -1.

Sau từ 0 đến W lượt trao đổi như trên, bạn phải thực hiện thêm một lượt trao đổi có dạng sau:

• Chương trình in một dòng chứa sáu số nguyên \(R_1\), \(R_2\), \(R_3\), \(R_4\), \(R_5\), \(R_6\), trong đó \(R_i\) biểu thị số nhẫn \(i\) ngày Odin có vào cuối ngày 0.
• Bộ chấm trả lời bằng một dòng chứa một số nguyên duy nhất: 1 nếu câu trả lời của bạn đúng, và -1 nếu câu trả lời sai (hoặc nếu bạn đã gửi một dòng sai định dạng).

Sau khi bộ chấm gửi -1 vào luồng vào của chương trình (do dữ liệu không hợp lệ hoặc câu trả lời không đúng), bộ chấm sẽ không gửi thêm bất kỳ dữ liệu nào. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận -1, chương trình sẽ hết thời gian và nhận lỗi Time Limit Exceeded. Lưu ý rằng bạn có trách nhiệm kết thúc chương trình kịp thời để nhận phán quyết Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình vượt quá giới hạn bộ nhớ hoặc gặp lỗi thực thi, bạn sẽ nhận phán quyết tương ứng.

Ràng buộc

\(1 \le \mathbf{T} \le 50\).

Phân nhóm

Test set 1 (Hiển thị)

\(\mathbf{W} = 6\).

Test set 2 (Ẩn)

\(\mathbf{W} = 2\).

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ụ kiểm thử này để kiểm tra cục bộ hoặc trên nền tảng của ban tổ chức. Để kiểm tra cục bộ, bạn cần chạy công cụ song song với chương trình của mình; có thể dùng trình chạy tương tác của ban tổ chức cho việc đó. Để biết thêm thông tin, hãy đọc hướng dẫn trong các chú thích của tệp ấy và xem 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 công cụ kiểm thử được viết trong các chú thích bên trong công cụ. Bạn nên bổ sung các bộ test của riêng mình. Xin lưu ý rằng tuy công cụ kiểm thử được thiết kế để mô phỏng hệ thống chấm, nó 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ụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy xem phần Lập trình trong mục Câu hỏi thường gặp để bảo đảm rằng bạn đang dùng cùng trình biên dịch với ban tổ chức.

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

Ví dụ

  t, w = readline_int_list()   // Đọc 50 vào t và 6 vào w
  printline 3 to stdout        // Hỏi về ngày 3.
  flush stdout
  n = readline_int()           // Đọc 15 vào n.
  printline 1 to stdout        // Hỏi về ngày 1.
  flush stdout
  n = readline_int()           // Đọc 7 vào n.
  printline 1 1 1 3 0 0 to stdout
  flush stdout                 // Đưa ra một dự đoán dù vẫn có thể truy vấn giếng
                               // thêm tối đa bốn lần nữa.
  verdict = readline_int()     // Đọc -1 vào verdict (bộ chấm đã quyết định rằng
                               // lời giải của chúng ta không đúng)
  exit                         // Thoát để tránh lỗi TLE không rõ nguyên nhân

Nguồn

Google Code Jam 2019, Vòng 1B, bài Draupnir.

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