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

Это коммуникационная задача.

Две программы, Алиса и Боб, играют в следующую кооперативную игру.

Даны целые числа $A$ и $B$, такие что $0 \le A, B < 2^{64}$. Изначально только Алиса знает $A$, и только Боб знает $B$. Пусть $C := \min(A, B)$. Цель состоит в том, чтобы и Алиса, и Боб смогли вывести $C$.

Для обмена информацией Алиса и Боб могут вызывать следующие функции:

  • send(x): Отправить 1-битное значение $x$ другой программе. Этот вызов не завершается, пока другая программа не вызовет receive().
  • receive(): Получить 1-битное значение от другой программы и вернуть его. Этот вызов не завершается, пока другая программа не вызовет send().

Суммарное количество вызовов send(), сделанных Алисой и Бобом вместе, не должно превышать $76$. То же самое относится и к receive().

После завершения обмена информацией каждая программа должна ровно один раз вызвать следующую функцию:

  • answer(x): Объявить, что значение $C$ равно $x$. Сразу после вызова этой функции программа должна завершиться.

Игра считается успешной, если и Алиса, и Боб правильно назовут $C$.

Напишите две программы — Алису и Боба, которые всегда добиваются успеха в игре.

Протокол взаимодействия

Это интерактивная коммуникационная задача (ваши программы и жюри взаимодействуют через стандартные потоки ввода и вывода). Ваша программа, играющая за Алису, и ваша программа, играющая за Боба, будут играть через программу жюри.

Запуск программы

Сначала ваша программа получает входные данные в следующем формате:

Player
X

Здесь Player — это строка Alice или Bob, а $X$ — целое число, удовлетворяющее условию $0 \le X < 2^{64}$.

  • Если Player равно Alice, то $A = X$. С этого момента ваша программа должна действовать как Алиса.
  • Если Player равно Bob, то $B = X$. С этого момента ваша программа должна действовать как Боб.

После этого вызывайте send, receive и в конце answer, как описано ниже.

send

Чтобы вызвать send(x), выведите:

send x

Здесь $x$ должно быть равно $0$ или $1$.

Этот вызов не завершается, пока другая программа не вызовет receive(). Вы получите вердикт Wrong Answer в любом из следующих случаев:

  • другая программа завершилась, пока вы ожидали,
  • другая программа тоже вызвала send(), пока вы ожидали,
  • суммарное количество вызовов send(), сделанных Алисой и Бобом, превысило $76$.

receive

Чтобы вызвать receive(), выведите:

receive

Затем считайте полученный бит $x$ из стандартного потока ввода:

x

Этот вызов не завершается, пока другая программа не вызовет send(). Вы получите вердикт Wrong Answer в любом из следующих случаев:

  • другая программа завершилась, пока вы ожидали,
  • другая программа тоже вызвала receive(), пока вы ожидали,
  • суммарное количество вызовов receive(), сделанных Алисой и Бобом, превысило $76$.

Если во время взаимодействия вы получите вердикт Wrong Answer, на вход будет подано число $-1$. Если вы считали $-1$, немедленно завершите программу, иначе вы можете получить вердикт Time Limit Exceeded.

answer

Чтобы вызвать answer(x), выведите:

answer x

Здесь $x$ должно быть равно $\min(A, B)$. После вызова этой функции немедленно завершите программу.

Примечание

  • После каждого вывода ваша программа должна сбрасывать буфер стандартного вывода (flush); в противном случае вы можете получить Time Limit Exceeded.
  • Программа жюри, ваша программа в роли Алисы и ваша программа в роли Боба работают одновременно. Ограничения по времени и памяти измеряются как сумма всех трёх процессов, поэтому оставляйте достаточный запас как по времени, так и по памяти.
    • Программа жюри потребляет до $50$ мс и $5$ МиБ.
  • Вам предстоит работать с целыми числами в диапазоне от $0$ до $2^{64} - 1$. Будьте осторожны с переполнением.

Примеры

Пример ввода 1

Alice
31
1

Пример вывода 1

send 0
receive
send 1
answer 25

Пример ввода 2

Bob
25
0
1

Пример вывода 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.