Это коммуникационная задача.
Две программы, Алиса и Боб, играют в следующую кооперативную игру.
Даны целые числа $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