Алгосия и Байтек оказались в очень необычной ситуации. У каждого из них есть своя собственная бинарная строка длины $n$. Они хотели бы обменяться этими строками как можно быстрее.
Ситуация осложняется тем, что в данный момент они находятся на чемпионате по игре «Камень, ножницы, бумага». Этот конкурс недавно претерпел технологическую революцию. Чтобы избежать любых попыток общения между участниками и полностью сосредоточиться на случайности стратегий игроков, организаторы решили полностью изолировать участников друг от друга и поставить между ними компьютерную систему. Каждый из участников объявляет свой ход, и только после этого раскрываются результаты раунда.
Правила матча в «Камень, ножницы, бумагу» следующие:
- Матч состоит из раундов.
- Во время одного раунда каждый из игроков выбирает один из трех символов: бумага, камень или ножницы.
- Затем эти символы сравниваются. Если игроки выбрали один и тот же символ, раунд заканчивается вничью, и никто не получает очка. В противном случае игрок с более сильным символом получает 1 очко (бумага побеждает камень, камень побеждает ножницы, а ножницы побеждают бумагу).
- Игрок, который первым наберет на 2 очка больше, чем противник, выигрывает матч.
- Раунды продолжаются до тех пор, пока кто-то из игроков не выиграет матч.
Алгосии и Байтеку важно узнать строки друг друга до окончания матча. Они также хотели бы сыграть как можно меньше раундов, чтобы не испытывать терпение наблюдателей и болельщиков. Напишите программу, которая им в этом поможет. Вам необходимо решить эту задачу для $t$ независимых тестовых случаев.
Протокол взаимодействия
Это интерактивная задача. Ваша программа будет запущена в двух экземплярах — один для Алгосии, другой для Байтека. Каждый экземпляр в первой строке входных данных получит слово Algosia или Bajtek, которое определяет, за действия какого из персонажей отвечает данная копия программы.
Формат входных данных в обоих случаях выглядит идентично. Первая строка входных данных содержит слово Algosia или Bajtek. Вторая строка содержит два числа $n$ и $t$ ($1 \le n \le 5000, 1 \le t \le 5$), определяющие длину бинарных строк, которые хотят передать друг другу Алгосия и Байтек, и количество тестовых случаев соответственно. Затем $t$ раз происходит взаимодействие между программами.
В первой строке каждого тестового случая обе программы получат строку длины $n$, состоящую только из символов 0 и 1. После считывания своих строк Алгосия и Байтек начинают игру. Во время одного раунда игрок сначала выводит строку, содержащую его ход, обозначенный одним символом $c \in \{P, K, N\}$, а затем считывает со стандартного ввода строку, содержащую символ, обозначающий ход другого игрока в том же формате. Максимальное количество раундов в одном тестовом случае составляет 20000. Превышение этого лимита приведет к вердикту «неправильный ответ».
Чтобы завершить тестовый случай, необходимо вывести строку, содержащую символ ! (восклицательный знак), пробел и следующую за ним строку длины $n$, состоящую только из символов 0 и 1. Для Алгосии это должна быть строка Байтека, а для Байтека — строка Алгосии. После вывода результата программа должна сразу перейти к следующему тестовому случаю (то есть считать строку, которую нужно передать) или завершить работу, если это был последний тестовый случай.
После вывода ответа необходимо очистить буфер вывода, например, с помощью вызова cout.flush() или fflush(stdout).
Примеры
Входные данные 1
Algosia 5 1 10010 P K
Выходные данные 1
P K ! 00011
Примечание
- Во всех тестах выполняется $t = 5, n = 5000$.
- Если после раунда у одного из игроков на 2 очка больше, чем у противника, программа немедленно завершается с вердиктом «неправильный ответ».
- Обе программы запускаются одновременно. Время работы программы измеряется как реальное время от начала до завершения работы интерактора.
- Преимущество в очках не переносится между тестовыми случаями. В начале каждого случая оба игрока начинают с 0 очков (независимо от того, с каким результатом закончился предыдущий случай).
Подзадачи
Набор тестов состоит из одной группы, за которую можно получить максимум 10 баллов. Пусть $m$ обозначает максимальное количество сыгранных раундов по всем тестовым случаям одного теста. Результат за данный тест определяется по следующим правилам:
| $m \le$ | Количество баллов |
|---|---|
| 20000 | 1 |
| 16250 | 2 |
| 10000 | 3 |
| 8750 | 4 |
| 6250 | 5 |
| 5500 | 6 |
| 5250 | 7 |
| 5125 | 8 |
| 5050 | 9 |
| 5000 | 10 |
Итоговый результат за задачу — это минимальный результат по всем тестам.
Детали реализации
В разделе файлов доступен интерактор pknsoc.cpp. Он идентичен интерактору, используемому для проверки решений на SIO2. Его следует запускать командой:
python3 pknrun.py [решение] < [тест] > [вывод]
при этом файлы pknsoc.cpp и oi.h должны находиться в одной папке. Формат, в котором интерактор принимает входные данные, описан в комментариях к файлу pknsoc.cpp.
Примечание
Общение между программами иным способом, кроме как через ход игры (например, путем отправки хода с задержкой и считывания времени другой программой), запрещено. В случае обнаружения жюри попытки общения между программами недозволенным способом, решение может быть удалено, а в серьезных случаях может быть принято решение о дисквалификации с конкурса.