A và B được chọn vào đội tuyển Nhật Bản dự thi Olympic Tin học Quốc tế. Để rèn luyện khả năng xử lý thông tin, họ chơi trò truyền tin với chủ tịch K.

A, B và K ở ba phòng riêng biệt. Mỗi phòng có điện thoại nội bộ, nhưng chỉ K được gọi điện. A và B không có cách liên lạc nào khác và chỉ được rời phòng khi K gọi. Khi bắt đầu trò chơi, K thông báo riêng cho A một số nguyên dương \(X\). Mục tiêu của A và B là khiến B xác định đúng \(X\) mà không liên lạc trực tiếp với nhau.

Trong phòng K có một bàn cờ \(4 \times 4\). Ô \((i,j)\) nằm ở hàng \(i\) từ trên xuống, cột \(j\) từ trái sang, với \(1 \le i,j \le 4\). Các ô \((1,1)\), \((1,4)\), \((4,1)\) và \((4,4)\) lần lượt là bốn góc trên trái, trên phải, dưới trái và dưới phải. Ban đầu, một quân cờ được đặt ở một ô bất kỳ. K không di chuyển quân cờ trong suốt trò chơi.

K liên tục gọi A hoặc B đến phòng mình. Mỗi lần đến, người được gọi phải di chuyển quân cờ sang một ô kề cạnh ở phía trên, dưới, trái hoặc phải, rồi trở về phòng. Riêng B, nếu đã xác định được \(X\), có thể trả lời K thay cho việc di chuyển. Nếu câu trả lời đúng, hai người thắng; nếu sai, họ thua ngay.

Thứ tự gọi được K chọn trước khi trò chơi bắt đầu, nhưng A và B không biết thứ tự đó, cũng không biết đối phương đã được gọi bao nhiêu lần giữa hai lượt của mình. Bảo đảm K không gọi cùng một người quá \(100\) lần liên tiếp. Nếu sau tổng cộng \(10\,000\) lượt gọi, người được gọi đã di chuyển xong mà B vẫn chưa trả lời, trò chơi kết thúc với kết quả sai.

Yêu cầu

Cài đặt hai chương trình mô tả chiến lược của A và B để B luôn xác định đúng \(X\) trong giới hạn lượt gọi.

Giao diện của phía A

Nộp tệp playerA.c hoặc playerA.cpp, định nghĩa đúng hai hàm:

void InitA(int T, int X);
int GameA(int I, int J);

• InitA(T, X) được gọi đúng một lần lúc khởi tạo. T là số hiệu bài toán con; X là số nguyên dương cần truyền cho B. Hàm không trả về giá trị.
• GameA(I, J) được gọi mỗi khi A đến phòng K. I và J là hàng và cột hiện tại của quân cờ, với \(1 \le I,J \le 4\). Hàm phải trả về một trong bốn số nguyên -1, -2, -3, -4, biểu thị một bước di chuyển.

Giao diện của phía B

Nộp tệp playerB.c hoặc playerB.cpp, định nghĩa đúng hai hàm:

void InitB(int T);
int GameB(int I, int J);

• InitB(T) được gọi đúng một lần lúc khởi tạo. T là số hiệu bài toán con. Phía B không được cung cấp X. Hàm không trả về giá trị.
• GameB(I, J) được gọi mỗi khi B đến phòng K. I và J là hàng và cột hiện tại của quân cờ, với \(1 \le I,J \le 4\). Hàm phải trả về một trong bốn số -1, -2, -3, -4 để di chuyển, hoặc một số nguyên dương Y để trả lời rằng \(X=Y\).

Các giá trị trả về biểu thị di chuyển có cùng ý nghĩa ở cả hai phía:

Mỗi lượt phải thực hiện đúng một bước di chuyển hợp lệ, trừ lượt B trả lời. Không được đứng yên hoặc đưa quân cờ ra ngoài bàn. Số nguyên dương do GameB trả về là đáp án gửi cho K và làm trò chơi kết thúc ngay, không phải một thông điệp gửi cho A.

Thứ tự gọi và cách ly hai phía

Hai tệp phải dùng cùng một ngôn ngữ. Trình chấm cung cấp main và khai báo trực tiếp bốn hàm trên; không có header giao tiếp riêng phải đưa vào mã dự thi.

Khi khởi tạo, grader mẫu gọi InitA(T, X), rồi InitB(T). Sau khi hoàn thành khởi tạo, các lời gọi GameA và GameB diễn ra theo thứ tự K đã chọn. Mỗi lời gọi nhận vị trí quân cờ sau tất cả những bước di chuyển trước đó. Mỗi bên chỉ quan sát được tham số của các lời gọi dành cho mình và có thể giữ trạng thái riêng qua các lượt gọi.

Không hàm nào trong hai hàm GameA, GameB được gọi quá \(100\) lần liên tiếp. Tổng số lời gọi hai hàm không vượt quá \(10\,000\). B phải trả về đáp án dương trong một lời gọi GameB nằm trong giới hạn đó; trả lời ở lượt thứ \(10\,000\) vẫn hợp lệ.

Hai tệp được liên kết cùng trình chấm thành một tệp thực thi, nhưng khi chấm bài, phía A và phía B chạy trong hai tiến trình riêng biệt. Hai phía không chia sẻ biến toàn cục hay bộ nhớ. Bạn được viết các hàm phụ và biến toàn cục, nhưng mọi hàm phụ và biến toàn cục nội bộ trong mỗi tệp phải được khai báo static để tránh xung đột khi liên kết. Bốn hàm giao diện phải giữ nguyên khả năng được trình chấm gọi.

Mã dự thi không được tương tác với đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào bằng bất kỳ cách nào. Kênh truyền thông tin duy nhất giữa hai phía là vị trí quân cờ được quan sát và thay đổi qua những lời gọi nói trên; không có hàm gửi chuỗi, gửi bit hoặc gọi trực tiếp sang phía còn lại.

Dữ liệu vào

Dữ liệu dành cho mã dự thi được truyền qua InitA, InitB, GameA và GameB. Chỉ A được nhận \(X\); thứ tự gọi đầy đủ được giữ trong trình chấm.

Để thử chương trình, grader mẫu đọc đầu vào chuẩn theo định dạng:

• Dòng đầu tiên chứa bốn số nguyên \(T,X,I_0,J_0\), phân cách bằng dấu cách: số hiệu bài toán con, số cần truyền và vị trí ban đầu của quân cờ.
• Dòng thứ hai chứa một chuỗi dài đúng \(10\,000\) ký tự, chỉ gồm A và B. Ký tự thứ \(k\) cho biết lời gọi thứ \(k\) sau khi khởi tạo là GameA hay GameB.

Chuỗi gọi thỏa mãn giới hạn không có quá \(100\) ký tự giống nhau liên tiếp và các điều kiện của bài toán con tương ứng. Grader mẫu đọc dữ liệu, đóng luồng đầu vào, khởi tạo hai phía rồi lần lượt thực hiện các lời gọi. Nó dừng ngay khi có đáp án hoặc hành động không hợp lệ.

Dữ liệu ra

Mã dự thi thực hiện hành động bằng giá trị trả về từ GameA hoặc GameB; B báo đáp án bằng giá trị nguyên dương trả về từ GameB.

Grader mẫu ghi một dòng ra đầu ra chuẩn:

Grader mẫu kết thúc với mã thoát \(0\) khi chấp nhận, hoặc mã thoát bằng số lỗi khi chấm sai.

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

Biên dịch bằng một trong hai lệnh:

gcc -O2 -lm grader.c playerA.c playerB.c -o grader

g++ -O2 -lm grader.cpp playerA.cpp playerB.cpp -o grader

Chạy ./grader, cung cấp dữ liệu cho grader qua đầu vào chuẩn và nhận kết quả của grader qua đầu ra chuẩn. Grader mẫu chạy trong một tiến trình để thử các lời gọi. Khi chấm chính thức, hai phía chạy cách ly trong hai tiến trình như đã mô tả; chiến lược phải tuân thủ sự cách ly này cả khi thử bằng grader mẫu.

Giới hạn

• \(1 \le X \le 1\,000\,000\,000\).
• \(T \in \{1,2,3\}\).
• \(1 \le I_0,J_0 \le 4\).
• Không gọi cùng một phía quá \(100\) lần liên tiếp.
• Nhiều nhất \(10\,000\) lượt gọi GameA và GameB cộng lại.
• Thời gian: 1 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi hai chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm, tuân thủ giao diện, cách ly, giới hạn lượt gọi, thời gian và bộ nhớ.

• Bài toán con 1 (20 điểm): \(T=1\). A được gọi trước, sau đó hai bên được gọi luân phiên: lượt lẻ gọi GameA, lượt chẵn gọi GameB.
• Bài toán con 2 (20 điểm): \(T=2\). Vị trí ban đầu của quân cờ là \((I_0,J_0)=(1,1)\). Lời gọi đầu tiên có thể dành cho A hoặc B.
• Bài toán con 3 (60 điểm): \(T=3\). Không có giới hạn bổ sung.

Ví dụ tương tác

Xét một trò chơi có dòng đầu của dữ liệu dành cho grader là 2 6 1 1. Phần đầu của chuỗi quy định thứ tự gọi là:

ABBAABAAABBBBBABBAABBBABBBBAAAAABABAABAABBBBABAAAA

Bảng sau mô tả quá trình tương tác kết thúc ở lượt chơi thứ \(6\), trước khi cần dùng các ký tự còn lại của chuỗi dài \(10\,000\) ký tự:

Chuỗi hành động này minh họa giao diện tương tác và không quy định chiến lược phải sử dụng.