Đội ngũ Code Jam vừa mua một vườn cây là một ma trận đất chưa được chuẩn bị gồm 1000 hàng và 1000 cột. Chúng tôi định trồng đủ loại cây ở đây — AVL, nhị phân, đỏ-đen, splay, v.v. — nên cần chuẩn bị một số ô bằng cách đào hố:

• Để có đủ cây dùng cho các bài toán về cây hằng năm, phải có ít nhất \(A\) ô đã được chuẩn bị.

• Để chăm sóc cây đúng cách, tập hợp tất cả các ô đã được chuẩn bị phải tạo thành một hình chữ nhật duy nhất song song với lưới, và mọi ô bên trong hình chữ nhật đó đều phải được chuẩn bị.

Các điều kiện trên cũng có nghĩa là không ô nào bên ngoài hình chữ nhật được phép đã chuẩn bị. Chúng tôi muốn khu vườn trông thật gọn gàng!

Ví dụ, khi \(A=11\), mặc dù mười một ô đã chuẩn bị trong hình bên trái phía dưới tạo thành một hình chữ nhật \(3\times4\) (3 hàng và 4 cột), ô ở chính giữa hình chữ nhật vẫn chưa được chuẩn bị. Vì không phải mọi ô trong hình chữ nhật \(3\times4\) đều đã chuẩn bị, công việc trong vườn vẫn chưa hoàn tất. Tuy nhiên, chỉ cần chuẩn bị thêm ô chính giữa thì hình chữ nhật có diện tích ít nhất 11 sẽ được lấp đầy và khu vườn sẵn sàng.

Xét một ví dụ khác ở phía dưới, lần này \(A=6\). Hình ở giữa có một ô được chuẩn bị nằm ngoài hình chữ nhật \(3\times2\). Vì thế, dù hình ngoài cùng bên phải đã chuẩn bị một hình chữ nhật diện tích 6, toàn bộ tập ô đã chuẩn bị vẫn không tạo thành một hình chữ nhật do có ô thừa bên trái. Khu vườn do đó chưa sẵn sàng.

Đào đất là việc nặng nhọc đối với con người, nên chúng tôi đã mượn chú chuột Go từ đội ngũ Google Go và huấn luyện nó giúp chuẩn bị các ô. Ta có thể triển khai chuột bằng cách đưa cho nó tọa độ một ô mục tiêu trong ma trận, miễn là ô đó không nằm trên bất kỳ biên nào của ma trận. Tuy nhiên, quá trình huấn luyện chưa hoàn hảo: chuột sẽ chọn đều giả ngẫu nhiên một trong chín ô thuộc khối \(3\times3\) có tâm là ô mục tiêu, rồi chuẩn bị ô được chọn. Nếu chọn trúng một ô đã chuẩn bị, nó sẽ vô ích chuẩn bị lại ô đó.

Ta chỉ có thể triển khai chuột tối đa 1000 lần trước khi nó quá mệt để đào tiếp, nên cần tìm một chiến lược triển khai phù hợp. Sau mỗi lần triển khai, bạn sẽ được cho biết ô mà chuột thực sự chuẩn bị và có thể dùng thông tin đó trước lần triển khai tiếp theo nếu cần. Bạn không phải khai báo trước kích thước hay vị trí của hình chữ nhật.

Dữ liệu vào

Đây là một bài tương tác, nên khái niệm dữ liệu vào và dữ liệu ra khác với các bài Code Jam thông thường. Chương trình của bạn tương tác với một tiến trình riêng vừa cung cấp thông tin vừa đánh giá phản hồi. Mọi thông tin đi vào chương trình qua đầu vào chuẩn; mọi nội dung cần giao tiếp phải được gửi qua đầu ra chuẩn. Nhiều ngôn ngữ lập trình mặc định lưu đệm đầu ra, vì vậy phải bảo đảm dữ liệu thực sự được gửi đi — chẳng hạn bằng cách flush bộ đệm — trước khi dừng lại chờ phản hồi. Xem FAQ để biết ý nghĩa của việc flush bộ đệm. Mọi thứ chương trình ghi ra đầu lỗi chuẩn đều bị bỏ qua, nhưng vẫn có thể tốn bộ nhớ, nên đừng ghi tràn. Một công cụ kiểm thử cục bộ bằng Python được cung cấp ở cuối đề để hỗ trợ gỡ lỗi. Ngoài ra, phần phân tích bài Number Guessing, một bài tương tác Code Jam trước đây, có lời giải mẫu bằng mọi ngôn ngữ được hỗ trợ.

Ban đầu, chương trình đọc một dòng chứa số nguyên \(T\), là số lượng test. Sau đó chương trình xử lý lần lượt \(T\) test.

Với mỗi test, chương trình đọc một dòng chứa số nguyên \(A\), là diện tích hình chữ nhật đã chuẩn bị tối thiểu cần đạt. Sau đó chương trình thực hiện tối đa 1000 lượt trao đổi với bộ chấm.

Dữ liệu ra

Chương trình gửi các tọa độ triển khai qua đầu ra chuẩn và đọc phản hồi của bộ chấm qua đầu vào chuẩn theo giao thức dưới đây.

Giao thức tương tác

Trong mỗi lượt trao đổi, chương trình ghi ra đầu ra chuẩn một dòng gồm hai số nguyên I J: chỉ số hàng và cột của ô mà bạn muốn triển khai chuột tới. Cả hai số phải nằm trong đoạn từ 2 đến 999 và được viết ở hệ thập phân, không có số 0 ở đầu. Nếu định dạng đầu ra sai, chẳng hạn giá trị vượt phạm vi, chương trình sẽ thất bại; bộ chấm gửi một dòng -1 -1 để báo test đã thất bại rồi không gửi thêm gì vào luồng đầu vào. Nếu định dạng hợp lệ, để phản hồi lần triển khai, bộ chấm ghi một dòng gồm hai số nguyên I' J' vào luồng đầu vào và chương trình phải đọc chúng từ đầu vào chuẩn.

Nếu lần triển khai vừa rồi khiến tập ô đã chuẩn bị trở thành một hình chữ nhật có diện tích ít nhất \(A\), bạn nhận được I' = J' = 0, báo hiệu test kết thúc. Nếu chưa, I' và J' là hàng và cột của ô mà chuột thực sự chuẩn bị, thỏa mãn \(|I'-I|\le1\) và \(|J'-J|\le1\). Khi đó bạn có thể bắt đầu lượt trao đổi tiếp theo.

Nếu chương trình làm sai, chẳng hạn xuất sai định dạng hoặc giá trị vượt phạm vi, bộ chấm gửi I' = J' = -1 như đã nói ở trên rồi ngừng gửi dữ liệu. Nếu vẫn tiếp tục chờ bộ chấm sau khi đọc -1 -1, chương trình sẽ hết thời gian. Bạn có trách nhiệm kết thúc chương trình kịp lúc để nhận phán quyết thích hợp như Wrong Answer hay Runtime Error thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình vượt tổng thời gian, vượt bộ nhớ hoặc gặp lỗi thực thi, bạn sẽ nhận phán quyết tương ứng.

Nếu giải xong test trong không quá 1000 lần triển khai, bạn nhận thông báo I' = J' = 0 rồi tiếp tục giải test kế tiếp. Nếu sau 1000 lượt trao đổi test vẫn chưa được giải, bộ chấm gửi I' = J' = -1 rồi ngừng gửi dữ liệu.

Không được gửi thêm thông tin cho bộ chấm sau khi đã giải xong tất cả các test. Nói cách khác, nếu chương trình tiếp tục ghi ra đầu ra chuẩn sau khi nhận I' = J' = 0 ở test cuối cùng, bạn sẽ nhận phán quyết Wrong Answer.

Trong một test cố định, các ô mà chuột chọn từ mỗi khối \(3\times3\) là giả ngẫu nhiên và độc lập với nhau, nhưng chúng được xác định bằng cùng một seed trong mọi lần chạy lại test đó. Vì vậy, một lời giải cho kết quả sai ở một test sẽ luôn sai ở test ấy trong mọi lần thử. Các test khác nhau sử dụng các seed khác nhau.

Ràng buộc

• \(1\le T\le20\).
• Mỗi test có tối đa 1000 lần triển khai.

Phân nhóm

Test Set 1 (công khai): \(A=20\).

Test Set 2 (ẩn): \(A=200\).

Ví dụ

  t = readline_int()         // reads 2 into t
  a = readline_int()         // reads 3 into a
  printline 10 10 to stdout  // sends out cell 10 10 to prepare
  flush stdout
  x, y = readline_two_int()  // reads 10 11, since cell 10 11 is prepared
  printline 10 10 to stdout  // sends out cell 10 10 again to prepare
  flush stdout
  x, y = readline_two_int()  // reads 10 10, since cell 10 10 is prepared
  printline 10 12 to stdout  // sends out cell 10 12 to prepare
  flush stdout
  x, y = readline_two_int()  // reads 10 11, since cell 10 11 is prepared again
  printline 10 10 to stdout  // sends out cell 10 10 to prepare
  flush stdout
  x, y = readline_two_int()  // reads 11 10, since cell 11 10 is prepared
  printline 11 10 to stdout  // sends out cell 11 10 to prepare
  flush stdout
  x, y = readline_two_int()  // reads 0 0; since cell 11 11 is prepared, a rectangle of size 4

  a = readline_int()         // reads 3 into a
  printline 10 10 to stdout  // sends out cell 10 10 to prepare
  x, y = readline_two_int()  // does not flush stdout; hangs on the judge

  a = readline_int()         // reads 3 into a
  printline 1 1 to stdout    // sends out cell 1 1 to prepare
  x, y = readline_two_int()  // reads -1 -1, since 1 is outside the range [2, 999]
  printline 10 10 to stdout  // sends a cell location anyway
  x, y = readline_two_int()  // hangs since the judge stops sending info to stdin

  a = readline_int()         // reads 3 into a
  printline 1 1 to stdout    // sends out cell 1 1 to prepare
  x, y = readline_two_int()  // reads -1 -1, since 1 is outside the range [2, 999]
  exit                       // receives a Wrong Answer judgment

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để chạy cục bộ hoặc trên nền tảng của Google. Khi kiểm thử cục bộ, cần chạy công cụ song song với chương trình; có thể dùng interactive runner của Google cho việc đó. Hãy đọc hướng dẫn trong phần chú thích của tệp ấy và phần Interactive Problems trong FAQ để biết thêm thông tin.

Hướng dẫn sử dụng nằm trong các chú thích bên trong công cụ và bạn được khuyến khích tự bổ sung test. Lưu ý rằng công cụ chỉ nhằm mô phỏng hệ thống chấm, không phải hệ thống chấm thật và có thể hành xử 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 kiểm tra phần Coding trong FAQ để bảo đảm bạn dùng cùng trình biên dịch với hệ thống.

Tải công cụ kiểm thử từ kho lưu trữ chính thức.

Nguồn

Google Code Jam 2018, Vòng loại, bài Go, Gopher!.

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