Задача №115172. Хорошие раскраски -- 4
Саша предложил Ильдару сыграть в игру. Ильдару эта идея не понравилась, но отказать Саше он не смог, а потому попросил вас написать программу, которая будет играть вместо него.
Игра начинается с того, что Саша достает клетчатый лист размером \(n \times n\) клеток и закрашивает какие-то \(2n\) клеток в цвета \(1,2,\ldots, 2n\), соответственно. За один ход Ильдар может указать на какую-то еще не закрашенную клетку и попросить Сашу закрасить эту клетку. Саша красит эту клетку в один из \(2n\) цветов по своему выбору. Ильдар может сделать не более \(10\) ходов, после чего ему требуется отыскать хорошую четверку клеток. Четверка клеток называется хорошей если выполняются следующие условия:
- Никакие две клетки из четверки не раскрашены в один и тот же цвет;
- Центры клеток образуют прямоугольник, стороны которого параллельны линиям сетки.
С момента запуска программы вам на входе будет доступно число \(t\) (\(1 \leq t \leq 200\)) — количество независимых игр, которые должна отыграть ваша программа.
В начале каждой игры в первой строке будет доступно число \(n\) (\(3 \leq n \leq 1000\)) — размер поля. В последующих \(2n\) строках будут указаны позиции клеток, которые изначально раскрасил Саша. В \(i\)-й из строк указана пара чисел \((x_i, y_i)\) (\(1 \leq x_i, y_i \leq n\)) — позиция клетки, раскрашенной в цвет под номером \(i\).
После того как вы считаете эти данные, можно будет совершить не более \(10\) ходов. Чтобы сделать ход, выведите « ? \(x\) \(y\)» (\(1 \leq x,y \leq n\)). В ответ на это программа жюри в единственной строке выведет единственное число от \(1\) до \(2n\) — цвет клетки \((x,y)\).
После совершения ходов (не обязательно делать все \(10\) ходов и не обязательно делать хотя бы \(1\) ход) выведите строку в формате « ! \(x_1\) \(x_2\) \(y_1\) \(y_2\)» (\(1 \leq x_1, x_2, y_1, y_2 \leq n\)). Если клетки \((x_1, y_1)\), \((x_1, y_2)\), \((x_2, y_1)\), \((x_2, y_2)\) раскрашены в различные цвета, то программа жюри выведет « OK », после чего ваша программа должна сразу перейти к обработке следующей игры. В ином случае, если какие-то из указанных клеток раскрашены в один цвет или одна из клеток еще не раскрашена, то программа жюри выведет вам « ERROR », при считывании этой строки ваша программа должна немедленно завершить свое исполнение.
Обратите внимание, что в данной задаче интерактор является адаптивным, то есть состояние раскраски всегда соответствует уже сделанным запросам, но в остальном может меняться в процессе работы .
Визуализация примера:
Для корректной работы программы после каждой операции вывода запроса или вывода ответа требуется выводить символ перевода строки, а также очищать буфер вывода. Функция print в Python или вывод endl в С++ делают это автоматически. Также можно делать следующие операции:
- В языке Pascal: flush(output) ;
- В С/С++: fflush(stdout) или cout.flush() ;
- В Java: System.out.flush() ;
- В Python: sys.stdout.flush() из библиотеки sys ;
- В C # : Console.Out.Flush() ;
STUPID 1 3 1 1 2 3 1 4 5 6 1 1 2 1 3 2 1 2 3 3 1 3 2
YES max-questions: 1