A và B được chọn vào đội tuyển Nhật Bản tham dự Olympic Tin học Quốc tế. Để nâng cao kỹ năng xử lý thông tin, họ sẽ chơi “trò chơi người đưa tin” với chủ tịch K của Ủy ban Olympic Tin học Nhật Bản. Luật chơi được giải thích dưới đây.

A và B bị cách ly trong các phòng như hình. Trong phòng của A, B và chủ tịch K đều có điện thoại nội bộ, nhưng chỉ chủ tịch K có thể gọi đi. Mọi phương tiện liên lạc khác đều bị cắt, và A cùng B không được ra khỏi phòng nếu không có chỉ thị.

Các nhãn trong hình, từ trái sang phải: phòng của A, hành lang dài, phòng của chủ tịch K, hành lang dài, phòng của B.

Khi trò chơi bắt đầu, chủ tịch K gọi điện cho A và cho biết một số nguyên dương $X$. Mục tiêu là để A truyền chính xác giá trị $X$ cho B mà A và B không liên lạc trực tiếp với nhau.

Trong phòng chủ tịch K có một bàn cờ $4\times 4$. Ô ở hàng $i$, cột $j$ được ký hiệu là $(i,j)$ ($1\le i\le 4$, $1\le j\le 4$). Ô $(1,1)$ là góc trên bên trái, $(1,4)$ là góc trên bên phải, $(4,1)$ là góc dưới bên trái và $(4,4)$ là góc dưới bên phải. Khi trò chơi bắt đầu, một quân cờ được đặt vào một ô bất kỳ. Sau đó, chủ tịch K sẽ không thay đổi ô đặt quân cờ.

Tiếp theo, chủ tịch K liên tục gọi điện triệu tập A hoặc B đến phòng mình. Mỗi lần đến phòng chủ tịch K, A hoặc B phải di chuyển quân cờ sang một ô liền kề ở trên, dưới, trái hoặc phải. Sau khi di chuyển quân cờ, người đó trở về phòng mình. Khi B đến phòng chủ tịch K, nếu đã biết giá trị $X$, B có thể trả lời cho chủ tịch K thay vì di chuyển quân cờ. Nếu trả lời đúng giá trị $X$ thì được chấp nhận, nếu không thì bị coi là sai.

Thời điểm chủ tịch K triệu tập A hoặc B không đều đặn, và A cùng B không biết thứ tự mà chủ tịch K triệu tập hai người. Tuy nhiên, chủ tịch K đã quyết định thứ tự đó khi trò chơi bắt đầu, và được đảm bảo rằng ông không triệu tập cùng một người quá 100 lần liên tiếp. Nếu sau khi chủ tịch K đã triệu tập A và B tổng cộng $10\,000$ lần, người vừa được triệu tập đã trở về phòng mình mà B vẫn chưa trả lời giá trị $X$, trò chơi kết thúc và bị coi là sai.

Nhiệm vụ

Hãy cài đặt chiến lược của A và B, viết chương trình có thể trả lời đúng trong “trò chơi người đưa tin” được mô tả trên.

Chi tiết cài đặt

Bạn phải nộp hai tệp viết bằng cùng một ngôn ngữ lập trình.

Tệp thứ nhất có tên playerA.c hoặc playerA.cpp. Tệp này cài đặt chiến lược của A và phải cài đặt các thủ tục sau.

void InitA(int T, int X)

Thủ tục này được gọi đúng một lần lúc đầu. Tham số T là số thứ tự nhiệm vụ con $T$. Tham số X là số nguyên dương $X$ mà A phải truyền cho B.

int GameA(int I, int J)

Thủ tục này được gọi tương ứng với mỗi lần A đến phòng chủ tịch K. Các tham số I, J là cặp số nguyên $(I,J)$ biểu diễn ô đặt quân cờ khi A đến phòng. Chúng thỏa mãn $1\le I\le 4$ và $1\le J\le 4$.

Thủ tục phải trả về một trong các số nguyên $-1,-2,-3,-4$. Nếu trả về giá trị khác, chương trình bị đánh giá Wrong Answer [1] và bị kết thúc. Các giá trị này biểu diễn hành động của A như sau.

• $-1$: di chuyển quân cờ lên ô phía trên $(I-1,J)$.
• $-2$: di chuyển quân cờ xuống ô phía dưới $(I+1,J)$.
• $-3$: di chuyển quân cờ sang ô bên trái $(I,J-1)$.
• $-4$: di chuyển quân cờ sang ô bên phải $(I,J+1)$.

Nếu chỉ định một nước đi đưa quân cờ ra ngoài bàn cờ, chương trình bị đánh giá Wrong Answer [2] và bị kết thúc.

Tệp thứ hai có tên playerB.c hoặc playerB.cpp. Tệp này cài đặt chiến lược của B và phải cài đặt các thủ tục sau.

void InitB(int T)

Thủ tục này được gọi đúng một lần lúc đầu. Tham số T là số thứ tự nhiệm vụ con $T$.

int GameB(int I, int J)

Thủ tục này được gọi tương ứng với mỗi lần B đến phòng chủ tịch K. Các tham số I, J là cặp số nguyên $(I,J)$ biểu diễn ô đặt quân cờ khi B đến phòng. Chúng thỏa mãn $1\le I\le 4$ và $1\le J\le 4$.

Thủ tục phải trả về một trong các số nguyên $-1,-2,-3,-4$, hoặc một số nguyên dương $Y$. Nếu trả về giá trị khác, chương trình bị đánh giá Wrong Answer [3] và bị kết thúc. Các giá trị này biểu diễn hành động của B như sau.

• $-1$: di chuyển quân cờ lên ô phía trên $(I-1,J)$.
• $-2$: di chuyển quân cờ xuống ô phía dưới $(I+1,J)$.
• $-3$: di chuyển quân cờ sang ô bên trái $(I,J-1)$.
• $-4$: di chuyển quân cờ sang ô bên phải $(I,J+1)$.

Nếu chỉ định một nước đi đưa quân cờ ra ngoài bàn cờ, chương trình bị đánh giá Wrong Answer [4] và bị kết thúc.

• Số nguyên dương $Y$: trả lời cho chủ tịch K rằng giá trị $X$ là $Y$. Khi đó, nếu $X=Y$ thì được chấp nhận; nếu không thì bị đánh giá Wrong Answer [5] và chương trình bị kết thúc.

Không có thủ tục nào trong hai thủ tục GameA và GameB được gọi quá 100 lần liên tiếp. Nếu sau tổng cộng $10\,000$ lần gọi GameA và GameB mà GameB vẫn chưa trả về một số nguyên dương, chương trình bị đánh giá Wrong Answer [6] và bị kết thúc.

Bạn có thể tự do cài đặt các thủ tục khác để sử dụng nội bộ hoặc khai báo biến toàn cục. Tuy nhiên, hai chương trình nộp sẽ được liên kết cùng chương trình chấm thành một tệp thực thi, nên phải khai báo tất cả biến toàn cục và thủ tục nội bộ trong mỗi tệp bằng static để tránh xung đột với các tệp khác. Khi chấm, chương trình này được thực thi thành hai tiến trình, một cho phía A và một cho phía B, nên hai phía không thể dùng chung biến toàn cục trong chương trình.

Bài nộp của bạn không được trao đổi dữ liệu với đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào khác bằng bất kỳ cách nào.

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

Chương trình chấm mẫu để kiểm thử chương trình của bạn có trong tệp nén tải được từ trang web cuộc thi. Tệp nén này cũng chứa các tệp mẫu cho những tệp cần nộp.

Chương trình chấm mẫu gồm một tệp duy nhất, là grader.c hoặc grader.cpp. Để kiểm thử, hãy chạy các lệnh sau.

• Với C

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

• Với C++

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

Nếu biên dịch thành công, tệp thực thi grader được tạo ra.

Lưu ý rằng chương trình chấm thực tế khác với chương trình chấm mẫu. Chương trình chấm mẫu chạy dưới dạng một tiến trình duy nhất. Chương trình này đọ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

Chương trình chấm mẫu đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa các số nguyên $T,X,I_0,J_0$, cách nhau bởi dấu cách, biểu diễn số thứ tự nhiệm vụ con $T$, số nguyên $X$ mà A phải truyền cho B và vị trí ban đầu $(I_0,J_0)$ của quân cờ.
• Dòng thứ hai chứa một xâu gồm hai loại ký tự A, B và có độ dài đúng $10\,000$. Nếu ký tự thứ $k$ ($1\le k\le 10\,000$) là A hoặc B, thủ tục được gọi thứ $k$ sau khi InitA và InitB được gọi sẽ tương ứng là GameA hoặc GameB.

Dữ liệu ra

Nếu chương trình kết thúc bình thường, chương trình chấm mẫu ghi một dòng chứa thông tin sau ra đầu ra chuẩn.

• Nếu được chấp nhận, ghi “Accepted” (dấu ngoặc kép thực tế không được ghi; điều này cũng áp dụng bên dưới).
• Nếu bị đánh giá sai, ghi loại lỗi bằng số được mô tả trong phần “Chi tiết cài đặt”, chẳng hạn “Wrong Answer [1]”. Riêng với Wrong Answer [5], giá trị đúng $X$ và số nguyên dương $Y$ mà GameB trả về cũng được ghi, chẳng hạn “Wrong Answer [5] : X = 2, Y = 3”.

Giới hạn

Tất cả dữ liệu đầu vào thỏa mãn điều kiện sau.

• $1\le X\le 1\,000\,000\,000$.

Nhiệm vụ con

Nhiệm vụ con 1 [20 điểm]

• $T=1$.
• A là người đầu tiên được triệu tập đến phòng chủ tịch K, sau đó A và B được triệu tập luân phiên. Nghĩa là sau khi InitA và InitB được gọi, các thủ tục được gọi theo thứ tự GameA, GameB, GameA, GameB, ...

Nhiệm vụ con 2 [20 điểm]

• $T=2$.
• Vị trí ban đầu của quân cờ là $(I_0,J_0)=(1,1)$. Nghĩa là sau khi InitA và InitB được gọi, lần gọi GameA hoặc GameB đầu tiên có tham số $I=1,J=1$.

Nhiệm vụ con 3 [60 điểm]

• $T=3$.

Ví dụ trao đổi

Dưới đây là ví dụ dữ liệu mà chương trình chấm mẫu đọc và các lời gọi thủ tục tương ứng.

Dữ liệu vào 1

2 6 1 1
ABBAABAAABBBBBABBAABBBABBBBAAAAABABAABAABBBBABAAAA

Phần còn lại của dòng thứ hai được lược bỏ trong ví dụ gốc.

Các lời gọi thủ tục

Lưu ý rằng ví dụ này không nhất thiết mô tả một cách trao đổi có ý nghĩa.