Задача №111236. aliens
Мирко большой фанат различных узоров на полях, в первую очередь странных кругов предположительно инопланетного происхождения. Одной летней ночью он решил создать свой собственный узор на поле своей бабушки. Так как Мирко патриот своей родной Хорватии, то он решил, что узор на поле будет в форме хорватского герба, который, как известно, представляет собой шахматную доску 5 на 5 c 13 красными и 12 белыми квадратами.
Поле бабушки Мирко разделено на \(N\) рядов по \(N\) клеток в каждом. Левый нижний угол поля обозначается координатами \((1, 1)\), правый верхний - координатами \((N, N)\).
Мирко решил выкосить траву только на тех участках, которые соответствуют красным полям на шахматной доске. Он выбрал нечетное число \(M \geq 3\) и так выкосил траву на поле, что каждый квадрат на шахматной доске соответствует квадрату размером \(M \times M\) клеток на поле, и шахматная доска целиком умещается на поле.
На рисунке (см. английскую версию условия) показан пример поля для \(N = 19\) и \(M = 3\). Клетки, на которых трава была выкошена, отмечены серым. Центр узора имеет координаты \((12, 9)\) и отмечен черной точкой
После того, как Мирко пошел спать, его творение привлекло внимание настоящих инопланетян! Они летают высоко вверху над полем в космическом корабле и исследуют узор с помощью прибора. Этот прибор может лишь определить, есть ли в определенной клетке трава или нет.
Пришельцы нашли одну клетку с выкошенной травой и теперь хотят найти центральную клетку узора Мирко. Они не знают размера узора \(M\).
Напишите программу, которая по размеру поля \(N\) (\(1 \leq N \leq 2\,000\,000\,000\)), координатам некоторой клетки с выкошенной травой \((X_0, Y_0)\) и способности взаимодействовать с инопланетным устройством, найдет центральную клетку узора Мирко
На каждом тесте устройство не может быть запущено более 300 раз
Это интерактивная задача. Ваша программа может взаимодействовать с устройством инопланетян, используя стандартный вывод и считывая данные, передаваемые устройством со стандартного ввода
- При запуске программы ей будут введены разделенные пробелом числа \(N\), \(X_0\), \(Y_0\).
- Для того, чтобы узнать есть ли трава в клетке \((X, Y)\) выведите на стандартный поток вывода строку "examine \(X\) \(Y\)". Если координаты \((X, Y)\) не будут находиться внутри поля или вы запустите устройство более 300 раз, то космический корабль потеряет управление и врежется в землю. Вы же в этом случае получите 0 баллов за тест.
- Устройство поместит в ваш стандартный поток ввода строку "true", если трава в указанной клетке выкошена и "false" в противном случае.
- Когда программа обнаружит центральную клетку, она должна вывести строку "solution \(X_c\) \(Y_c\)" на стандартный поток вывода. Выполнение вашей программы в этот момент будет автоматически завершено.
Для корректной работы вашей программы не забывайте вызывать функцию "flush" после каждого вывода данных. Её заменяет endl в С++, print в Python, writeln в Pascal.
> 20 4 9 < examine 2 9 > false < examine 3 9 > true < examine 6 9 > false < examine 5 9 > true < examine 4 3 > true < examine 2 3 > false < examine 3 3 > true < examine 3 1 > false < examine 3 2 > true < solution 10 9
