408265: GYM103074 F Зов Древних

F. Зов Древнихограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Это интерактивная задача.

Окутанный фантасмагоричными предзнаменованиями Вася взирает на безлунное небо. «Если бы я мог стать столь же чрезвычайно сияющим» — подумал Вася вглядевшись в звезду, и тут же получил зловещее предупреждение из древних глубин космоса. И тогда он понял, что сосредоточив свое невежественное сознание на некоторых звездах, можно услышать кошмарный зов неизвестного Древнего Бога.

Вспомнив знания, полученные из Некрономикона, Вася установил, что каждый из Древних имеет свой радиус влияния, и звезды находящиеся внутри радиуса отвечают зовом тому, кто в них вглядывается. Три Бога отравляют реальность своим противоестественным существованием: Азазот, с радиусом влияния 30 световых лет, Йог-Сотот с радиусом 20 и Шаб-Ниггурат с радиусом 10. Небо представляет собой координатную плоскость 100 на 100 световых лет, и на каждой целочисленной координате находится звезда. Вася может всматриваться в звезду с определенными координатами и понимать, находится ли она в радиусе влияния Древнего.

В данный момент пробудился только один Древний, то есть только вокруг него звезды отвечают на взор. Вася должен понять, какой из Древних пробудился и сказать его радиус, но сделать все это не более чем за N действий, иначе Вася сойдет с ума от переполняющего чудовищного познания.

Выходные данные

Выведите строку вида «! R», где R — радиус влияния пробужденного Древнего.

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

Чтобы узнать находится ли звезда (X, Y) внутри зоны влияния Древнего, выведите в стандартный поток строку вида «? X Y», где X, Y — целые числа (0 ≤ X, Y ≤ 100). После этого выведите перевод строки и выполните операцию flush.

В ответ на запрос придет одно целое число: единица, если звезда находится внутри зоны влияния Древнего и ноль, если нет.

Чтобы вывести ответ на задачу, выведите строку вида «! R», где R — радиус влияния пробужденного Древнего.

Если вы сделаете более N запросов вида «? X Y» или сделаете некорректный запрос, решение получит вердикт «Неправильный ответ».

Если в какой-то момент ваша программа ничего не будет выводить или вы забудете выполнить операцию flush после вывода вопроса или ответа, решение получит вердикт «Решение зависло».

Чтобы выполнить операцию flush, можно использовать (сразу после вывода запроса и перевода строки):

• fflush(stdout) в C++;
• System.out.flush() в Java;
• stdout.flush() в Python;
• flush(output) в Pascal;

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача	Баллы	Ограничения	Необходимые подзадачи	Информация о проверке
[0.5ex] 1	25	N = 10202		полная
2	25	103 ≤ N ≤ 5·103	1	полная
3	25	300 ≤ N ≤ 500	1,2	полная
4	25	N = 101	1,2,3	полная

ПримерВходные данные

1
0

Выходные данные

? 8 12
? 95 87 
! 10