Bạn không cần biết bất kỳ điều gì về luật cờ vua để giải bài này.

Có \(N\) quân vua trên một bàn cờ vô hạn, tức một lưới hai chiều, nằm tại các ô có tọa độ \((X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)\). Bạn không biết \(N\) cũng như tọa độ của các quân vua, nhưng biết các điều sau:

• \(N\) ít nhất là 1 và nhiều nhất là \(N_{\max}\).
• Không tọa độ \(X\) hoặc \(Y\) nào của một quân vua có trị tuyệt đối vượt quá \(M\).
• \(N\) quân vua nằm ở \(N\) ô khác nhau.

Các quân vua muốn gặp nhau tại một ô duy nhất. Nếu chọn ô \((X,Y)\) làm nơi họp, quân vua thứ \(i\) cần số nước đi bằng giá trị lớn nhất trong hai độ chênh tuyệt đối giữa tọa độ của nó và tọa độ nơi họp:

Vì vậy, tổng số nước đi của mọi quân vua là tổng các giá trị trên với mọi \(i\). Cách cụ thể các quân vua di chuyển trên bàn cờ không liên quan tới bài toán; chỉ ô xuất phát, ô đích và số nước đi luôn tính được bằng công thức trên mới quan trọng.

Bài toán có hai giai đoạn. Trong giai đoạn đầu, bạn có thể lặp lại thao tác sau: đề xuất một nơi họp \((A,B)\), trong đó cả \(A\) và \(B\) đều thuộc đoạn \([-10M,10M]\), rồi để bộ chấm cho biết tổng số nước các quân vua cần đi tới đó:

Bạn được trao đổi với bộ chấm theo cách này nhiều nhất \(R\) lần, và được tự chọn \(A,B\) trong mỗi lần. Các quân vua không thực sự di chuyển, nên các vị trí \((X_i,Y_i)\) giữ nguyên trong mọi yêu cầu của cùng một bộ test.

Trong giai đoạn thứ hai, vai trò đảo lại: bộ chấm đưa cho bạn tọa độ một ô họp \((C,D)\), với cả \(C\) và \(D\) thuộc đoạn \([-10M,10M]\), và bạn phải trả lời tổng số nước các quân vua cần đi tới đó, giả sử chúng vẫn ở đúng các vị trí của giai đoạn đầu. Có nhiều nhất \(R\) lần trao đổi như vậy và bạn phải trả lời đúng mọi yêu cầu của bộ chấm.

Dữ liệu vào

Chương trình nhận dữ liệu từ bộ chấm theo giao thức tương tác bên dưới.

Dữ liệu ra

Chương trình gửi truy vấn và câu trả lời tới bộ chấm theo giao thức tương tác bên dưới.

Giao thức tương tác

Ban đầu, đọc một dòng chứa bốn số nguyên \(T,N_{\max},M,R\), lần lượt là số bộ test, số quân vua tối đa, trị tuyệt đối tối đa của bất kỳ tọa độ nào của một quân vua, và số yêu cầu tối đa trong mỗi giai đoạn. Các giá trị \(M\) và \(R\) là cố định và chỉ được đưa vào dữ liệu đầu vào để tiện sử dụng; xem phần Ràng buộc. Sau đó xử lý lần lượt \(T\) bộ test.

Mỗi bộ test gồm hai giai đoạn. Trong lần trao đổi thứ \(i\) của giai đoạn đầu:

• Chương trình gửi một dòng chứa hai số nguyên \(A_i\) và \(B_i\), là tọa độ \(x\) và \(y\) của một ô. Cả \(A_i\) và \(B_i\) phải thuộc đoạn \([-10M,10M]\).
• Bộ chấm trả lời một dòng chứa một số nguyên: tổng số nước các quân vua cần đi từ các vị trí chưa biết của chúng tới ô bạn vừa gửi.

Bạn được khởi tạo nhiều nhất \(R\) lần trao đổi trong giai đoạn này. Nếu thực hiện quá \(R\) lần, hoặc gửi một yêu cầu mà bộ chấm không phân tích được hay có tọa độ ngoài giới hạn, bộ chấm trả lời một dòng chỉ chứa chuỗi ERROR.

Để kết thúc giai đoạn đầu và chuyển sang giai đoạn thứ hai, gửi một dòng chứa chuỗi READY, không phân biệt chữ hoa chữ thường. Bộ chấm sẽ đáp lại bằng yêu cầu đầu tiên của giai đoạn thứ hai.

Trong lần trao đổi thứ \(i\) của giai đoạn thứ hai:

• Bộ chấm gửi một dòng chứa hai số nguyên \(C_i\) và \(D_i\), là tọa độ \(x\) và \(y\) của một ô. Mỗi giá trị đều thuộc đoạn \([-10M,10M]\).
• Chương trình phải trả lời một dòng chứa một số nguyên: tổng số nước các quân vua cần đi tới ô đã cho.

Bộ chấm bảo đảm gửi ít nhất 1 và nhiều nhất \(R\) yêu cầu như vậy. Nếu câu trả lời sai hoặc không thể phân tích, bộ chấm trả về ERROR như trên. Nếu bạn trả lời đúng tất cả các yêu cầu, bộ chấm gửi một dòng chỉ chứa DONE; lúc đó chương trình phải bắt đầu bộ test tiếp theo, hoặc kết thúc không lỗi nếu đã xử lý đủ \(T\) bộ test.

Sau khi gửi một dòng ERROR, bộ chấm không gửi thêm bất kỳ đầu ra nào. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận ERROR, chương trình sẽ hết thời gian và nhận Time Limit Exceeded. Bạn có trách nhiệm cho chương trình thoát kịp thời để nhận Wrong Answer thay vì Time Limit Exceeded. Nếu chương trình gặp lỗi chạy, nó sẽ nhận phán quyết tương ứng.

Số lượng và vị trí các quân vua, cũng như số lượng và vị trí các yêu cầu mà bộ chấm sẽ gửi trong các giai đoạn thứ hai, đều được chọn trước khi bất kỳ lần trao đổi nào diễn ra.

Ràng buộc

• \(1\le T\le 15\).
• \(M=10^6\).
• \(-M\le X_i\le M\) với mọi \(i\).
• \(-M\le Y_i\le M\) với mọi \(i\).
• Các cặp \((X_i,Y_i)\) đôi một khác nhau.
• \(-10M\le C_i\le 10M\) với mọi \(i\).
• \(-10M\le D_i\le 10M\) với mọi \(i\).
• \(R=1000\).

Phân nhóm

• Test Set 1 (hiển thị): \(N_{\max}=1\).
• Test Set 2 (ẩn): \(N_{\max}=10\).

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử đi kèm để chạy cục bộ hoặc trên nền tảng chính thức. Khi chạy cục bộ, cần chạy công cụ song song với chương trình của bạn; có thể dùng interactive runner. Hãy đọc hướng dẫn trong phần bình luận của tệp đó và phần Bài tương tác trong FAQ.

Hướng dẫn riêng của công cụ cũng nằm trong các bình luận bên trong công cụ. Bạn nên bổ sung các bộ test của mình. Dù công cụ đượ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ụ nhưng không vượt qua 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 chính thức.

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

Ví dụ

  // Suppose that the judge has decided that in the first test case, the king
  // is at the coordinates (1, -2), and the requests will be (5, -1) and
  // (7, 7).
  t, nmax, m, r = readline_int_list()   // Reads 10 1 1000000 1000
  // Our solution decides (for whatever reason) to check (3, 3) first.
  printline 3 3 to stdout
  flush stdout
  result = readline_int()               // Reads 5
  // Our solution now decides (for whatever reason) to check (2, 0).
  printline 2 0 to stdout
  flush stdout
  result = readline_int()               // Reads 2
  // Our solution concludes that the king is at (3, -2), which is consistent
  // with the observed information so far, but unfortunately not correct.
  // Our solution moves on to the request phase.
  printline READY to stdout
  request_line = readline()             // Reads 5 -1
  printline 2 to stdout                 // Wrong answer!
  request_line = readline()             // Reads ERROR
  exit                                  // exits to avoid an ambiguous TLE error

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Board Meeting.

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