Universal Cup Judging System

Universal Cup

Límite de tiempo: 0.5 s Límite de memoria: 1024 MB Puntuación total: 100 Comunicación
Estadísticas

Đây là một bài toán truyền thông (communication).

Hai chương trình, Alice và Bob, cùng chơi trò chơi hợp tác sau đây.

Cho hai số nguyên $A$ và $B$ thỏa mãn $0 \le A, B < 2^{64}$. Ban đầu, chỉ Alice biết $A$, và chỉ Bob biết $B$. Đặt $C := \min(A, B)$. Mục tiêu là cả Alice và Bob đều có thể đưa ra $C$.

Để trao đổi thông tin, Alice và Bob có thể gọi các hàm sau:

  • send(x): Gửi một giá trị 1-bit $x$ cho chương trình kia. Lời gọi này sẽ không trả về cho đến khi chương trình kia gọi receive().
  • receive(): Nhận một giá trị 1-bit từ chương trình kia và trả về giá trị đó. Lời gọi này sẽ không trả về cho đến khi chương trình kia gọi send().

Tổng số lần gọi send() của cả Alice và Bob cộng lại không được vượt quá $76$. Điều tương tự cũng áp dụng cho receive().

Sau khi quá trình truyền thông kết thúc, mỗi chương trình phải gọi hàm sau đúng một lần:

  • answer(x): Tuyên bố giá trị của $C$ là $x$. Ngay sau khi gọi hàm này, chương trình phải kết thúc.

Trò chơi thành công nếu cả Alice và Bob đều trả lời đúng $C$.

Hãy viết hai chương trình, Alice và Bob, luôn thành công trong trò chơi.

Giao thức tương tác

Đây là bài toán truyền thông tương tác (các chương trình của bạn và máy chấm giao tiếp qua luồng vào/ra chuẩn). Chương trình đóng vai Alice và chương trình đóng vai Bob của bạn sẽ chơi trò chơi thông qua máy chấm.

Khởi động chương trình

Chương trình của bạn trước tiên nhận dữ liệu vào theo định dạng sau:

Player
X

Ở đây, Player là xâu Alice hoặc Bob, và $X$ là một số nguyên thỏa mãn $0 \le X < 2^{64}$.

  • Nếu Player là Alice, thì $A = X$. Từ thời điểm này trở đi, chương trình của bạn phải hoạt động như Alice.
  • Nếu Player là Bob, thì $B = X$. Từ thời điểm này trở đi, chương trình của bạn phải hoạt động như Bob.

Sau đó, hãy gọi send, receive, và cuối cùng là answer như mô tả dưới đây.

send

Để gọi send(x), hãy in ra:

send x

Ở đây, $x$ phải bằng $0$ hoặc $1$.

Lời gọi này không trả về cho đến khi chương trình kia gọi receive(). Bạn sẽ bị chấm là Wrong Answer nếu bất kỳ điều nào sau đây xảy ra:

  • chương trình kia kết thúc trong khi bạn đang đợi,
  • chương trình kia cũng gọi send() trong khi bạn đang đợi,
  • tổng số lần gọi send() của Alice và Bob vượt quá $76$.

receive

Để gọi receive(), hãy in ra:

receive

Sau đó đọc bit nhận được $x$ từ đầu vào chuẩn:

x

Lời gọi này không trả về cho đến khi chương trình kia gọi send(). Bạn sẽ bị chấm là Wrong Answer nếu bất kỳ điều nào sau đây xảy ra:

  • chương trình kia kết thúc trong khi bạn đang đợi,
  • chương trình kia cũng gọi receive() trong khi bạn đang đợi,
  • tổng số lần gọi receive() của Alice và Bob vượt quá $76$.

Nếu bạn bị chấm là Wrong Answer trong quá trình tương tác, dữ liệu vào được cung cấp sẽ là $-1$. Nếu đọc thấy $-1$, hãy kết thúc chương trình ngay lập tức, nếu không bạn có thể nhận Time Limit Exceeded.

answer

Để gọi answer(x), hãy in ra:

answer x

Ở đây, $x$ phải bằng $\min(A, B)$. Sau khi gọi hàm này, hãy kết thúc chương trình ngay lập tức.

Ghi chú

  • Sau mỗi lần in ra, chương trình của bạn phải làm rỗng bộ đệm đầu ra chuẩn (flush); nếu không, bạn có thể nhận Time Limit Exceeded.
  • Chương trình chấm, chương trình đóng vai Alice của bạn và chương trình đóng vai Bob của bạn chạy đồng thời. Giới hạn thời gian và bộ nhớ được tính bằng tổng của cả ba chương trình, vì vậy hãy chừa đủ khoảng trống cho cả thời gian lẫn bộ nhớ.
    • Chương trình chấm tiêu thụ tối đa khoảng $50$ ms và $5$ MiB.
  • Bạn sẽ xử lý các số nguyên trong phạm vi từ $0$ đến $2^{64} - 1$. Hãy cẩn thận với hiện tượng tràn số (overflow).

Ví dụ

Dữ liệu vào mẫu 1

Alice
31
1

Kết quả mẫu 1

send 0
receive
send 1
answer 25

Dữ liệu vào mẫu 2

Bob
25
0
1

Kết quả mẫu 2

receive
send 1
receive
answer 25

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.