Vương quốc JOI là một hòn đảo được biển bao quanh, có dạng một bảng vuông gồm \(N\) hàng và \(N\) cột. Hướng dọc là Bắc-Nam, hướng ngang là Tây-Đông. Ô ở hàng thứ \(r+1\) tính từ phía Bắc và cột thứ \(c+1\) tính từ phía Tây được ký hiệu là \((r,c)\), với \(0\le r,c\le N-1\).

Nữ hoàng Anna muốn mời Bruno dự tiệc. Cô đã chọn \(K=7\) ô làm địa điểm dự kiến, đánh số từ \(0\) đến \(K-1\); địa điểm dự kiến thứ \(i\) là ô \((R_i,C_i)\). Không có địa điểm dự kiến nào tiếp giáp với biển. Địa điểm tổ chức chính thức chỉ được quyết định vào ngày diễn ra bữa tiệc.

Vào ngày hôm trước, Anna đặt một lá cờ ở mọi ô, mỗi lá cờ ghi một số nguyên từ \(1\) đến \(1\,000\,000\,000\), để giúp Bruno tìm đường.

Vào ngày diễn ra bữa tiệc, Bruno chỉ được thông báo chỉ số \(t\) (\(0\le t\le K-1\)) của địa điểm được chọn. Sau đó, cậu đáp trực thăng xuống một ô không tiếp giáp với biển và bắt đầu đi đến bữa tiệc.

Bruno không biết tọa độ hiện tại của mình, nhưng biết các hướng Bắc, Nam, Đông, Tây. Cậu chỉ nhìn thấy lá cờ ở ô hiện tại và tám ô xung quanh. Cụ thể, khi Bruno ở \((a,b)\), với \(1\le a,b\le N-2\), cậu nhìn thấy chín ô sau, theo thứ tự:

Bruno có thể thực hiện một trong năm hành động:

Bruno không được đến muộn, nên phải đến địa điểm tổ chức bằng số hành động ít nhất có thể. Với các điều kiện của bài toán, điều này bảo đảm cậu không bao giờ đi vào ô tiếp giáp với biển.

Việc viết các số lớn lên cờ rất phiền phức, nên Anna muốn giảm nhỏ nhất có thể giá trị lớn nhất được ghi trên các lá cờ. Hãy cài đặt chiến lược của Anna để ghi số lên cờ và chiến lược của Bruno để đi đến địa điểm tổ chức bằng số hành động ít nhất.

Chi tiết cài đặt

Cần nộp hai tệp Anna.cpp và Bruno.cpp.

Trong Anna.cpp, sử dụng #include "Anna.h" và cài đặt hàm:

void Anna(int N, int K, std::vector<int> R, std::vector<int> C);

Hàm này cài đặt cách Anna ghi số lên cờ và được gọi đúng một lần ở đầu mỗi tình huống:

• N là số hàng và số cột của bảng.
• K là số địa điểm dự kiến, bằng \(7\).
• R và C là hai mảng có độ dài K; R[i], C[i] là tọa độ địa điểm dự kiến thứ \(i\), với \(0\le i\le K-1\).
• Các tham số tuân theo mục Ràng buộc.

Trong mỗi lần gọi Anna, chương trình phải gọi hàm sau đúng \(N^2\) lần, mỗi ô đúng một lần:

void SetFlag(int r, int c, int value);

Hàm này ghi số value lên lá cờ ở ô (r,c).

Nếu một lời gọi SetFlag bị coi là sai, chương trình bị kết thúc ngay lập tức.

Trong Bruno.cpp, sử dụng #include "Bruno.h" và cài đặt hàm:

std::vector<int> Bruno(int K, std::vector<int> value);

Hàm này được gọi đúng một lần cho mỗi tình huống, sau khi Anna đã được gọi:

• K là số địa điểm dự kiến, bằng \(7\).
• value là mảng có độ dài \(9\), chứa các số ghi trên cờ ở ô hiện tại và tám ô xung quanh. Khi vị trí hiện tại là \((a,b)\), các phần tử value[0] đến value[8] tương ứng với chín ô theo đúng thứ tự đã liệt kê ở phần mô tả.
• Với mỗi \(t=0,1,\ldots,K-1\), hàm phải quyết định hành động tiếp theo nếu địa điểm tổ chức là địa điểm dự kiến thứ \(t\).
• Giá trị trả về là mảng có độ dài K. Phần tử thứ \(i+1\) của mảng, tức phần tử có chỉ số \(i\), là hành động khi \(t=i\).

Nếu có nhiều cách đi tối ưu đến một địa điểm, có thể trả về bất kỳ hành động tiếp theo nào thuộc một trong các cách đó.

Mỗi bộ kiểm thử gồm \(Q\) tình huống. Anna và Bruno được gọi luân phiên, mỗi hàm tổng cộng \(Q\) lần, chứ không phải mô phỏng liên tiếp toàn bộ hành trình của Bruno trong một tình huống.

Lưu ý

Có thể cài đặt hàm phụ trợ hoặc khai báo biến toàn cục. Hai tệp nộp được liên kết cùng trình chấm thành một tệp thực thi; mọi biến toàn cục và hàm nội bộ phải nằm trong không gian tên vô danh để tránh xung đột giữa các tệp. Khi chấm, tệp thực thi được chạy thành hai tiến trình, một cho Anna và một cho Bruno. Hai tiến trình không thể chia sẻ biến toàn cục.

Chương trình không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Trình tự chấm

Các tình huống được đánh số từ \(0\) đến \(Q-1\). Trong mỗi tình huống, các giá trị sau được cố định: kích thước bảng \(N\), số địa điểm dự kiến \(K=7\), các ô \((R_0,C_0),\ldots,(R_{K-1},C_{K-1})\), và vị trí hiện tại \((a,b)\) của Bruno. Các giá trị này thỏa mãn mục Ràng buộc.

Với từng tình huống \(k=0,1,\ldots,Q-1\) theo thứ tự:

1. Gọi Anna với các tham số của tình huống \(k\) như mô tả trong phần cài đặt, để ghi số lên các lá cờ.
2. Gọi Bruno với các tham số của tình huống \(k\) như mô tả trong phần cài đặt, để quyết định các hành động tiếp theo.

Nếu có lỗi Wrong Answer trong quá trình này, chương trình bị kết thúc ngay và bộ kiểm thử đó được coi là sai.

Biên dịch và chạy thử

Gói tệp hỗ trợ trong phần đính kèm chứa trình chấm mẫu grader.cpp và mã nguồn mẫu của các tệp cần nộp. Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng thư mục và chạy:

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp

Nếu biên dịch thành công, tệp thực thi grader được tạo ra. Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Đầu vào của trình chấm mẫu có dạng:

Q
(Dữ liệu cho tình huống 0)
...
(Dữ liệu cho tình huống Q-1)

Dữ liệu cho mỗi tình huống có dạng:

N K
R_0 C_0
...
R_{K-1} C_{K-1}
a b

Mọi giá trị đầu vào đều là số nguyên. Riêng khi dùng trình chấm mẫu, có thể chọn \(3\le N\le 100\) và \(1\le K\le 7\). Các khoảng này khác với ràng buộc của dữ liệu chấm thật.

Dữ liệu ra

Khi chương trình kết thúc thành công, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn:

• Nếu đúng, ghi số lớn nhất được Anna viết lên cờ, chẳng hạn Accepted : Maximum value = 12.
• Nếu sai, ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu đồng thời vi phạm nhiều loại lỗi, trình chấm mẫu chỉ thông báo một trong các loại đó.

Ràng buộc

• \(1\le Q\le 300\).
• \(5\le N\le 100\).
• \(K=7\).
• \(1\le R_i\le N-2\) với mọi \(0\le i\le K-1\).
• \(1\le C_i\le N-2\) với mọi \(0\le i\le K-1\).
• \((R_i,C_i)\ne(R_j,C_j)\) với mọi \(0\le i<j\le K-1\).
• \(1\le a\le N-2\).
• \(1\le b\le N-2\).

Phân nhóm

Nếu có bất kỳ bộ kiểm thử nào bị chấm Wrong Answer, điểm của toàn bộ bài là \(0\).

Nếu chương trình đúng trên tất cả các bộ kiểm thử, gọi \(L\) là số nguyên lớn nhất được ghi trên các lá cờ trong toàn bộ các bộ kiểm thử. Điểm được tính như sau:

• Nếu \(70\,001\le L\le 1\,000\,000\,000\): \(7\) điểm.
• Nếu \(10\,001\le L\le 70\,000\): \(13\) điểm.
• Nếu \(2001\le L\le 10\,000\): \(19\) điểm.
• Nếu \(21\le L\le 2000\): \(\left\lfloor 50-12.5\log_{10}\left(\frac{L}{20}\right)\right\rfloor\) điểm, tức làm tròn xuống số nguyên gần nhất.

Nếu \(L\le 20\), dùng bảng sau:

Ví dụ giao tiếp

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

1
5 7
1 1
1 2
2 1
2 2
2 3
3 2
3 3
1 1

Các số Anna ghi trên cờ

Trong ví dụ này, giả sử Anna ghi các số sau lên \(25\) lá cờ. Các hàng/cột được liệt kê theo thứ tự từ Bắc xuống Nam và từ Tây sang Đông.

Lời gọi và giá trị trả về

Giải thích

Trong ví dụ này, \((a,b)=(1,1)\). Với các địa điểm dự kiến \(0,1,2,3\), hành động tiếp theo phải như sau:

• Chọn địa điểm \(0\): bữa tiệc ở \((1,1)\), nên phải thực hiện hành động \(4\).
• Chọn địa điểm \(1\): bữa tiệc ở \((1,2)\), nên phải thực hiện hành động \(0\).
• Chọn địa điểm \(2\): bữa tiệc ở \((2,1)\), nên phải thực hiện hành động \(2\).
• Chọn địa điểm \(3\): bữa tiệc ở \((2,2)\), nên có thể thực hiện hành động \(0\) hoặc \(2\).

Ví dụ trả về [4,0,2,2,2,0,0]. Có thể có nhiều cách đi tối ưu; chẳng hạn trả về [4,0,2,0,2,0,2] cũng được coi là đúng.

Ví dụ 2

Dữ liệu vào của trình chấm mẫu:

1
100 7
3 21
16 9
44 36
44 78
45 78
67 59
90 22
84 59

Giải thích

Chẳng hạn, hàm Bruno trả về [3,1,1,0,0,3,2] thì được coi là đúng.

Nguồn

JOI 2020/2021, Spring Training Camp, Contest 4. Tác giả: 米田優峻 và 米田寛峻. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.