Mọi vụ đột nhập, dù chỉ là giả định, đều cần một kế hoạch tẩu thoát tốt. Vì thế, bạn đã thuê một trợ lý để giúp mình thoát khỏi kho dưới nước phát hiện hôm qua.

Để kế hoạch thành công, việc liên lạc với trợ lý rất quan trọng. Cụ thể, bạn cần gửi một trong \(N\) thông điệp khác nhau, được đánh số từ \(1\) đến \(N\). Đáng tiếc là khi ở trong chiếc tàu ngầm mới tinh, bạn chỉ có thể phát hai loại tín hiệu. Vì vậy, bạn phải mã hóa thông điệp thành một dãy các tín hiệu này.

Tuy nhiên, phát tín hiệu là một quá trình phức tạp, liên quan đến ống phóng ngư lôi, một ứng dụng bất ngờ và tao nhã của thuật toán Dijkstra, cùng một gói mì spaghetti cỡ gia đình. Quá trình ấy có thể thất bại và phát nhầm tín hiệu. Bạn chỉ có thể chắc chắn rằng điều này không bao giờ xảy ra hai lần liên tiếp. Ngoài ra, bạn luôn biết tín hiệu nào thực sự đã được phát và có thể điều chỉnh hành động tiếp theo.

Hiển nhiên, tín hiệu trong hình được hiểu là bit \(1\).

Bạn nhận ra rằng trong những điều kiện này, có thể không truyền được một thông điệp một cách hoàn toàn không mơ hồ. Vì vậy, bạn chấp nhận việc trợ lý xác định nhiều nhất hai thông điệp mà bạn có thể muốn gửi, miễn là thông điệp ban đầu nằm trong số đó. Là một lập trình viên tài năng, bạn muốn viết chương trình vừa giúp mình quyết định nên phát tín hiệu nào, vừa giúp trợ lý xác định hai thông điệp có thể có.

Phát tín hiệu từ tàu ngầm có thể gây nghi ngờ — nó gây nhiễu vô tuyến nghiêm trọng và làm các loài vật địa phương vô cùng hoảng loạn — nên bạn chỉ được phát tối đa \(250\) tín hiệu. Trợ lý cũng cần phản ứng nhanh: họ phải nhận ra lúc nào việc liên lạc đã kết thúc mà không chờ thêm tín hiệu!

Giao tiếp

Đây là bài giao tiếp, trong đó chương trình của bạn được chạy nhiều lần cho mỗi bộ dữ liệu. Bạn phải cài đặt hai hàm sau. Trong mỗi lần chạy chương trình, chỉ một trong hai hàm được gọi, nhưng có thể được gọi nhiều lần với các tham số khác nhau:

void encode(int N, int X);
std::pair<int, int> decode(int N);

Các hàm do trình chấm cung cấp là:

int send(int s);
int receive();

• encode(N, X): \(N\) là số thông điệp khác nhau và \(X\) là thông điệp cần truyền, với \(1\le X\le N\). Trong mỗi lời gọi encode, bạn được gọi send(s) tối đa \(250\) lần. Tham số \(s\) phải bằng \(0\) hoặc \(1\), biểu thị tín hiệu muốn gửi. Giá trị trả về cho biết tín hiệu thực sự đã được gửi. Giá trị này có thể khác \(s\), nhưng trong hai lời gọi send liên tiếp thuộc cùng một lời gọi encode, điều đó xảy ra nhiều nhất một lần.
• decode(N): \(N\) giống với giá trị trong lời gọi encode tương ứng. Mỗi lời gọi encode có một lời gọi decode tương ứng. Trong decode, hàm receive() trả về tín hiệu tiếp theo thực sự đã được gửi trong lời gọi encode tương ứng. Cuối cùng, decode phải trả về một cặp số nguyên \((a,b)\), với \(1\le a,b\le N\), sao cho \(X=a\) hoặc \(X=b\). Được phép có \(a=b\).

Bạn bị chấm sai bộ dữ liệu nếu trong decode gọi receive nhiều lần hơn số lần send đã được gọi trong encode tương ứng. Bạn được phép gọi receive ít hơn số lần đó. Chỉ được gọi send trong encode và receive trong decode.

Nếu một lời gọi không thỏa mãn các điều kiện trên, chương trình bị kết thúc ngay và nhận kết quả Not correct cho bộ dữ liệu tương ứng. Bạn không được ghi ra đầu ra chuẩn hoặc đọc từ đầu vào chuẩn; nếu vi phạm, bạn có thể nhận kết quả Security violation!.

Mã nguồn phải chứa #include "communication.h". Bạn cài đặt encode và decode, không viết hàm main. Không thể dựa vào bộ nhớ dùng chung giữa phía mã hóa và phía giải mã, vì chúng được gọi trong những lần chạy chương trình khác nhau.

Lưu ý kỹ thuật

1. Không có bảo đảm rằng các lời gọi decode xuất hiện theo cùng thứ tự với các lời gọi encode tương ứng.
2. Giới hạn thời gian và thời gian chạy hiển thị trong CMS chính thức được tính theo thời gian trung bình của các lời gọi trong một lần chạy chương trình. Cụ thể, nếu một lần chạy có \(K\) lời gọi encode hoặc \(K\) lời gọi decode, tổng thời gian của lần chạy ấy không được vượt quá \(K\cdot0.005\) giây. Mỗi lần chạy được bảo đảm có ít nhất \(50\) lời gọi encode hoặc decode.
3. Giới hạn bộ nhớ được tính theo lượng bộ nhớ lớn nhất sử dụng tại bất kỳ thời điểm nào trong quá trình chạy.

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

Gói đính kèm của bài trên CMS chính thức có communication.h, trình chấm mẫu sample_grader.cpp và chương trình mẫu communication_sample.cpp. Bạn có thể liên kết bài làm với trình chấm mẫu; hướng dẫn nằm trong sample_grader.cpp. Chẳng hạn, đặt communication.cpp, communication.h và sample_grader.cpp trong cùng thư mục rồi chạy:

g++ -std=c++17 sample_grader.cpp communication.cpp
./a.out

Để đơn giản, trình chấm mẫu không chạy chương trình hai lần mà gọi cả encode và decode, mỗi hàm đúng một lần, trong cùng một lần chạy. Vì vậy, hành vi này khác với trình chấm thật.

Trình chấm mẫu trước tiên đọc hai số nguyên \(N\) và \(X\), với \(1\le X\le N\), từ đầu vào chuẩn. Sau đó, nó gọi encode(N, X) và ghi nhật ký mọi lời gọi send ra đầu ra chuẩn. Với mỗi lời gọi send, bạn nhập giá trị trả về cho lời gọi đó qua đầu vào chuẩn.

Tiếp theo, trình chấm gọi decode(N) và ghi nhật ký mọi lời gọi receive. Khi kết thúc, nó in một trong các thông báo sau:

• Invalid input.: dữ liệu nhập cho trình chấm không đúng định dạng trên.
• Invalid send.: gọi send trong decode, hoặc gọi send với tham số khác \(0\) và \(1\).
• Invalid reply to send.: giá trị trả về được nhập cho send không phải \(0\) hoặc \(1\), hoặc khác tham số của send hai lần liên tiếp.
• Looks (and smells) fishy.: gọi send quá \(250\) lần.
• Invalid receive.: gọi receive trong encode.
• Assistant waiting for Godot.: gọi receive nhiều lần hơn send.
• Invalid answer.: decode không trả về một cặp số nguyên trong đoạn từ \(1\) đến \(N\).
• Wrong answer.: cặp do decode trả về không chứa thông điệp ban đầu \(X\).
• Correct: w signal(s) sent.: cặp do decode trả về chứa \(X\) và đã có \(w\) lần gọi send.

Các thông báo trên giữ nguyên cách viết trong PDF chính thức. Trình chấm thật chỉ in Not correct khi có bất kỳ lỗi nào ở trên, hoặc Correct: w signal(s) sent.. Trình chấm thật còn có tính thích ứng: các tham số \(N\), \(X\) và các giá trị trả về của send có thể phụ thuộc vào hành vi của chương trình trong lần chạy hiện tại cũng như những lần chạy khác. Cả trình chấm mẫu và trình chấm thật đều tự động kết thúc chương trình khi có lỗi. Việc đọc và ghi các luồng chuẩn ở phần chạy thử do trình chấm mẫu thực hiện.

Ràng buộc

• \(3\le N\le10^9\).
• \(1\le X\le N\).
• Giới hạn thời gian: trung bình \(0.005\) giây cho mỗi lời gọi, theo cách tính ở phần lưu ý kỹ thuật.
• Giới hạn bộ nhớ: \(8\) MiB.

Phân nhóm

1. \(15\) điểm: \(N=3\).
2. Tối đa \(85\) điểm: không có ràng buộc thêm. Điểm phụ thuộc vào số tín hiệu lớn nhất \(w_{\max}\) đã gửi trong tất cả các thông điệp của các bộ dữ liệu thuộc phân nhóm này.

Điểm của phân nhóm \(2\) được xác định bởi hàm tuyến tính từng đoạn trong hình sau, rồi làm tròn đến số nguyên gần nhất duy nhất. Trục đứng score biểu diễn số điểm; trục ngang là \(w_{\max}\).

Cụ thể, trước khi làm tròn, số điểm là:

Các mốc của đồ thị là \((100,85)\), \((110,65)\), \((140,35)\), \((200,15)\) và \((250,5)\). Để đạt điểm tối đa, không được gọi send quá \(100\) lần cho bất kỳ thông điệp nào trong phân nhóm \(2\).

Ví dụ giao tiếp

Xét \(N=1337\) và \(X=42\). Đầu tiên, trình chấm gọi encode(1337, 42). Một quá trình giao tiếp có thể diễn ra như sau; mũi tên chỉ giá trị trả về:

send(1) -> 0
send(0) -> 0
send(1) -> 1
send(1) -> 0

Lần đầu phát nhầm tín hiệu. Lần thứ hai phát đúng, như đã được bảo đảm. Lần thứ ba tiếp tục phát đúng, còn lần thứ tư phát nhầm.

Sau đó, trong một lần chạy mới của chương trình, trình chấm gọi decode(1337). Một quá trình giao tiếp có thể là:

receive() -> 0
receive() -> 0
receive() -> 1
return {1337, 42}

Lời gọi receive đầu tiên trả về \(0\), là giá trị thực sự được trả về bởi lần gọi send đầu tiên, dù khác tham số đã truyền vào lần gọi ấy. Hai lời gọi tiếp theo lần lượt nhận các giá trị trả về của lần gọi send thứ hai và thứ ba. Cặp trả về chứa \(42\), nên câu trả lời đúng và được chấp nhận. Chương trình còn được phép gọi receive thêm một lần nữa.