Trò chơi sử dụng một hộp đen hình vuông đặt nằm trên bàn. Mỗi cạnh trong bốn cạnh của hộp có \(n\) lỗ, tổng cộng \(4n\) lỗ, để ném một viên bi vào. Viên bi cuối cùng sẽ đi ra qua một trong \(4n\) lỗ, có thể chính là lỗ mà nó đã đi vào.

Bên trong hộp là một lưới \(n\times n\). Các lỗ nằm ở hai đầu của mỗi hàng và mỗi cột. Mỗi ô hoặc để trống, hoặc chứa một bộ đổi hướng. Bộ đổi hướng làm viên bi đổi hướng chuyển động một góc \(90^\circ\).

Hình trên minh họa một hộp \(5\times5\). Nhãn Hole chỉ một lỗ; nhãn Deflectors chỉ các bộ đổi hướng.

Viên bi chuyển động thẳng cho đến khi gặp một bộ đổi hướng hoặc ra khỏi hộp. Khi gặp bộ đổi hướng, viên bi đổi hướng chuyển động, sau đó bộ đổi hướng quay \(90^\circ\), chuyển giữa hai trạng thái / và \.

Ở hình a, viên bi được ném qua một lỗ, gặp bộ đổi hướng và đổi hướng chuyển động. Sau lần ném này, bộ đổi hướng đã chuyển trạng thái. Ở hình b, một viên bi mới được ném vào cùng lỗ, gặp bộ đổi hướng đó và rẽ theo hướng ngược với viên bi đầu tiên. Hình c cho thấy bộ đổi hướng lại chuyển trạng thái sau lần va chạm tiếp theo. Bộ đổi hướng chuyển trạng thái mỗi lần bị viên bi chạm vào.

Mỗi lần bị chạm, bộ đổi hướng phát ra một tiếng bíp. Đếm số tiếng bíp cho biết số lần viên bi đổi hướng. Có thể chứng minh rằng viên bi luôn ra khỏi hộp. Hộp có một nút đưa tất cả bộ đổi hướng về trạng thái ban đầu và một nút chuyển trạng thái đồng thời tất cả bộ đổi hướng.

Đây là bài tương tác thông qua thư viện. Hệ thống chấm giữ kín cấu hình của hộp. Bạn cần viết chương trình khảo sát hộp bằng các hàm được cung cấp và trả về cấu hình ban đầu mà bạn suy ra được. Phiên bản này chuyển bài chỉ nộp kết quả của IOI 2006 thành bài nộp mã nguồn C++; không cần nộp tệp ZIP kết quả hay kết nối tới một dịch vụ bên ngoài.

Yêu cầu cài đặt

Nộp một tệp mã nguồn C++, khai báo #include "cppbblib.h" và cài đặt hàm:

std::vector<std::string> solve_blackbox(int box_id);

Mỗi lần chạy, hệ thống gọi hàm này đúng một lần cho một hộp có số hiệu \(1\le box\_id\le15\). Các hộp được chấm trong những tiến trình độc lập. Không cài đặt hàm main, không đọc đầu vào chuẩn và không ghi đầu ra chuẩn; hệ thống sử dụng các luồng này để liên lạc với thư viện chấm.

Đầu tiên, gọi Initialize(box_id) đúng một lần để nhận kích thước \(n\). Sau đó có thể gọi các hàm khảo sát. Khi đã hoàn tất, trả về một vector gồm đúng \(n\) chuỗi, mỗi chuỗi có đúng \(n\) ký tự. Các chuỗi mô tả các hàng từ trên xuống dưới; ký tự trong mỗi chuỗi tương ứng với các cột từ trái sang phải:

• .: khẳng định ô ban đầu trống.
• /: khẳng định ô ban đầu có bộ đổi hướng /.
• \: khẳng định ô ban đầu có bộ đổi hướng \.
• ?: chưa xác định được trạng thái ban đầu của ô.

Không thêm tiêu đề #FILE, dòng kích thước hay dấu cách vào các chuỗi trả về. Trả về khỏi solve_blackbox kết thúc việc khảo sát; không gọi Finalize hoặc tự kết thúc tiến trình bằng exit.

Các hàm thư viện

Tệp cppbblib.h cung cấp các hàm sau:

int Initialize(int box);
int throwBall(int holeIn, int sideIn, int &holeOut, int &sideOut);
void ResetBox();
void ToggleDeflectors();
long long HowManyThrows();

• Initialize(box) phải được gọi đúng một lần, trước các hàm khảo sát khác, với box bằng tham số box_id. Hàm trả về \(n\), với \(1\le n\le30\).
• throwBall(holeIn, sideIn, holeOut, sideOut) ném một viên bi vào hộp, trả về số lần viên bi chạm bộ đổi hướng và ghi lỗ ra, cạnh ra vào hai tham số tham chiếu. Cạnh \(1\) là trên, \(2\) là phải, \(3\) là dưới, \(4\) là trái. Trên cạnh trên/dưới, lỗ được đánh số từ trái sang phải; trên cạnh trái/phải, lỗ được đánh số từ trên xuống dưới. Mọi số hiệu lỗ nằm trong \([1,n]\).
• ResetBox() khôi phục tất cả bộ đổi hướng về trạng thái ban đầu của hộp.
• ToggleDeflectors() chuyển đồng thời mọi bộ đổi hướng ở trạng thái hiện tại: / thành \ và ngược lại. Ô trống không thay đổi.
• HowManyThrows() trả về số lần gọi throwBall đã hoàn tất kể từ Initialize. ResetBox và ToggleDeflectors không đặt lại bộ đếm này.

Thư viện cũng cung cấp phiên bản throwBall nhận con trỏ int* thay cho hai tham số tham chiếu. Hai phiên bản có cùng ý nghĩa. Trạng thái sau một lần ném được giữ lại cho thao tác tiếp theo. Một bộ đổi hướng chuyển trạng thái sau mỗi lần bị chạm, kể cả khi bị chạm nhiều lần trong cùng một lượt ném.

Số lần chạm được trả về bằng số nguyên có dấu \(32\) bit; giao thức hỗ trợ tối đa \(2^{24}-1\) lần chạm cho một lượt ném. Không có hạn mức riêng cho số lần gọi hàm, nhưng toàn bộ chương trình phải chạy trong giới hạn thời gian và bộ nhớ của bài. Gọi hàm với tham số không hợp lệ hoặc sai thứ tự không được chấp nhận.

Bộ chấm thử

Tệp đính kèm chứa cppbblib.h, bộ chấm thử sample_grader.cpp, lời giải khung và hộp mẫu blackbox.in. Bộ chấm thử đọc một hộp tự tạo từ đầu vào chuẩn và gọi solve_blackbox(0). Lời giải vẫn gọi Initialize(box_id); chỉ bộ chấm thử sử dụng số hiệu \(0\), còn các lần chấm trên hệ thống dùng số hiệu từ \(1\) đến \(15\).

Định dạng hộp tự tạo:

• Dòng đầu chứa \(n\).
• Dòng thứ hai chứa số bộ đổi hướng \(d\).
• Mỗi dòng trong \(d\) dòng tiếp theo chứa cột, hàng, rồi ký tự / hoặc \, phân cách bởi dấu cách. Hàng và cột được đánh số từ \(1\). Các ô không được liệt kê là ô trống; nếu một tọa độ được liệt kê nhiều lần, bản ghi cuối quyết định hướng của bộ đổi hướng.

Đây chỉ là đầu vào của bộ chấm thử, không phải đầu vào mà lời giải được phép đọc khi nộp bài. Cấu hình của \(15\) hộp chấm không được cung cấp cho lời giải.

Ví dụ thử nghiệm

5
3
2 3 \
4 2 /
4 4 /

Chấm điểm

Phiên bản LQDOJ áp dụng điểm theo tỉ lệ ô xác định đúng, thay cho cách chuẩn hóa theo kết quả của người chơi khác trong kỳ thi IOI 2006 gốc. Mỗi hộp có trọng số bằng nhau, chiếm \(100/15\) điểm trong tổng số \(100\) điểm.

Gọi \(B\) là số ô được khẳng định bằng ., / hoặc \; ô trống xác định đúng cũng được tính. Nếu có bất kỳ khẳng định nào sai so với trạng thái ban đầu, cả hộp nhận \(0\) điểm. Kết quả sai số hàng, sai độ dài hàng hoặc chứa ký tự không hợp lệ cũng không được chấp nhận.

Nếu mọi khẳng định đều đúng, phần trăm điểm của hộp là:

Trả về toàn bộ ô là ? cho \(0\) điểm; xác định đúng mọi ô cho đủ điểm. Tổng điểm là tổng của \(p/15\) trên \(15\) hộp, không làm tròn điểm từng hộp về số nguyên. Một hộp bị lỗi không ngăn hệ thống chấm các hộp còn lại.

Trong kỳ thi sử dụng định dạng này, hệ thống lấy điểm cao nhất của từng hộp trên tất cả các lần nộp của bạn, rồi cộng lại. Cả cách chấm theo tỉ lệ ô và cách tổng hợp điểm này là quy tắc của phiên bản chuyển thể, không phải quy tắc lịch sử IOI 2006.

Nguồn

IOI 2006 - Blackbox, bản tiếng Anh 1.6. Chuẩn hóa theo tỉ lệ ô như bản chuyển thể của Pavel Kunyavskiy trên Codeforces; phiên bản này dùng giao diện hàm C++ thay cho nộp tệp kết quả.