ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2063. Чёрные и белые

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Рассмотрим игру. В ряд лежат n шариков двух цветов: черные и белые. Позиции в ряду пронумерованы от 1 до n. Вам известно только общее количество шариков (n); точное их расположение и даже количество белых шариков неизвестно.
Вы можете делать запросы вида v u, где 1 ≤ v, un. Если на позиции v находится чёрный шарик, а на позиции u — белый, то эти шарики поменяют местами (иначе не произойдёт ничего). При этом вам не сообщают, поменяли шарики местами или нет.
После некоторого (возможно, нулевого) числа таких запросов вы должны сделать «утверждение». «Утверждение» — это тоже две позиции v, u. Вам нужно угадать две такие позиции в ряду, что там лежат шарики одного и того же цвета.
Ваша задача — выдать последовательность запросов, за которой следует ровно одно «утверждение».
В одном тесте может быть много игр. Более того, во всех тестах, кроме первого, ровно 99 игр, причём в первой игре n = 2, во второй игре n = 3 и т. д.. В последней игре n = 100.
Первый тест совпадает с примером из условия. На нём проверяется только формат вывода.
На всех тестах, начиная со второго, чтобы пройти тест, ваша программа должна угадать хотя бы в 80 играх из 99.
Обратите внимание, что, хоть ваша программа и не должна выигрывать все 99 игр, мы не гарантируем, что тесты случайные.

Исходные данные

В первой строке ввода записано одно число m — количество игр в этом тесте. Для всех тестов, кроме первого, m=99.
В следующих строках заданы начальные расстановки шаров в ряду. Во всех тестах, кроме первого, расстановки зашифрованы. Вы не должны пытаться расшифровывать эти данные (и не обязаны их считывать), однако наличие во вводе этой информации позволяет нам гарантировать, что в этой задаче заранее определённые тесты, которые не подстраиваются под вашу стратегию.

Результат

Выведите ровно m описаний игр.
Одно описание игры состоит из k + 1 строк, где k — количество сделанных вашей программой запросов.
В первых k строках выводятся эти запросы (в порядке применения) в формате ? v u (1 ≤ v, un, vu).
В последней строке описания выводится ! v u (1 ≤ v, un, vu) — ваше «утверждение».
Общее количество выведенных строк (суммарно по всем играм внутри одного теста) не должно превышать 5 · 105.

Пример

исходные данныерезультат
2
01
101
? 1 2
? 2 1
? 1 2
! 2 1
? 1 2
? 3 1
! 1 2

Замечания

В примере из условия белые шарики обозначены как 0, чёрные — как 1. Рассмотрим его подробнее.
Первая игра: 01 → 01 → 10 → 01 — мы не угадали.
Вторая игра: 101 → 011 → 110 — мы угадали.
Так, на этом тесте мы угадали в одной игре из двух.
Автор задачи: Алексей Данилюк
Источник задачи: Уральская региональная командная олимпиада по программированию 2015