Задача №113944. Угадай-ка!
Это интерактивная задача.
В выходной Алексей вместе со своими одноклассниками решил посетить парк аттракционов. Поскольку Алексею очень нравится решать головоломки и получать за это призы, его заинтересовал новый павильон «Угадай-ка!», где посетителям предлагается сыграть в следующую игру.
На столе в павильоне есть клетчатое прямоугольное поле размера \(n \times m\), каждая клетка раскрашена в один из \(k\) разных цветов, и есть колода из \(n \cdot m\) карт с написанными на них числами от 1 до \(n \cdot m\). Ведущий игры в павильоне загадывает одну из карт колоды, а посетитель должен её отгадать. Чтобы отгадать неизвестную ему карту, посетитель задаёт ведущему один или несколько запросов следующим образом:
- Посетитель по своему усмотрению раскладывает на поле все карты номерами вверх, ровно по одной карте в каждой клетке поля
- Ведущий смотрит на поле и говорит посетителю цвет клетки, на которой лежит загаданная карта
Всего посетителю разрешено разложить карты и получить ответ ведущего не более \(99\) раз, после чего он должен правильно назвать номер загаданной карты. Гарантируется, что ответы ведущего не противоречивы, то есть всегда существует по крайней мере одна карта, для которой все данные ведущим ответы верны.
Напишите программу, которая поможет Алексею получить приз!
Ваша программа будет общаться с тестирующей системой по протоколу, описанному ниже.
При запуске решения на вход подаются три целых положительных числа \(n\), \(m\) и \(k\) (\(1 \leq n, m \leq 10\), \(2 \leq k \leq n \cdot m\)) — размеры игрового поля и количество цветов, в которые раскрашено поле. В каждой из следующих \(n\) строк передаётся по \(m\) целых чисел через пробел, каждое от \(1\) до \(k\) — раскраска клеток игрового поля. Гарантируется, что для каждого из \(k\) цветов на поле есть по крайней мере одна клетка, раскрашенная в этот цвет.
Вам разрешается задать ведущему не более \(99\) запросов , чтобы угадать загаданную ведущим карту.
Чтобы задать запрос, выведите строку « ? », после чего выведите \(n\) строк по \(m\) целых чисел в каждой — номера карт, раскладываемых вами в соответствующие клетки поля. Каждое число должно быть от 1 до \(n \cdot m\), номера карт не должны повторяться.
В ответ на каждый запрос вводится целое число \(c\) — цвет клетки, в которую вы положили загаданную карту, или число \(-1\) в случае, если программа превысила ограничение по числу запросов. Обратите внимание, в случае считывания числа \(-1\) вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некорректным!
Как только вы найдете ответ, выведите строку « Ready! ». В следующей строке выведите целое число \(x\) (\(1 \leq x \leq n \cdot m\)) — номер загаданной ведущим карты. После этого ваша программа должна завершиться.
Для установки правильности вашей программы жюри может запускать её произвольное количество раз для одного и того же игрового поля с разными загаданными картами.
В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.
В примере поле 2 на 3 раскрашено в 3 цвета. Ответ на первый запрос — цвет 1, следовательно, ведущий загадал карту c номером \(1\) или с номером \(3\). Ответ на второй запрос — цвет 2, это говорит о том, что ведущий загадал карту с номером \(3\) или \(4\). Следовательно, была загадана карта с номером 3. Обратите внимание, что при проверке вашей программы на этом тесте в тестирующей системе может быть загадана другая карта.
В точности соблюдайте формат выходных данных. После каждого вывода обязательно выводите один перевод строки и сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
2 3 3 1 2 1 2 3 3 1 2
? 1 2 3 4 5 6 ? 2 4 6 3 1 5 Ready! 3