| Codeforces Round 415 (Div. 1) |
|---|
| Закончено |
Это интерактивная задача. В формате выходных данных вы найдёте информацию о том, как сбрасывать буфер вывода (делать операцию flush).
В воскресенье хакер Леха забрал Нуру из дома, где она живёт, и поехал с ней в один из самых роскошных ресторанов Вичкополиса. По приезду они оставили машину на огромной стоянке близ ресторана и поспешили внутрь здания.
В ресторане вежливый официант сразу же принес Лехе и Нуре меню, состоящее из n блюд. Интересно, что в меню все блюда пронумерованы целыми числами от 1 до n. Немного подумав, девушка заказала ровно k различных блюд из имеющихся в меню. Чтобы скоротать время ожидания, пока повара готовят заказанные Лехой и Нурой блюда, девушка предложила хакеру сыграть в игру, которая поможет им ближе узнать друг друга.
Суть игры очень проста: Нура хочет, чтобы Леха отгадал любые два блюда среди тех, которые она заказала. При этом она готова отвечать только на один тип вопросов. Леха может говорить Нуре два целых числа x и y (1 ≤ x, y ≤ n). Затем для числа x девушка выбирает блюдо с номером a такое, что, во-первых, блюдо a находится в списке заказанных Нурой (x может быть равно a), а, во-вторых, значение 
минимально. По аналогичным правилам девушка выбирает блюдо b для числа y. После этого Нура говорит Лехе «TAK», если 
, и «NIE» в противном случае. Однако в ресторане готовят быстро, поэтому у Лехи хватит времени, чтобы задать не более 60 вопросов. После этого он должен назвать номера двух любых блюд, заказанных Нурой.
Помогите Лехе справиться с этой задачей.
В единственной строке входного файла заданы два числа n и k (2 ≤ k ≤ n ≤ 105) — количество блюд в меню и количество блюд, заказанных Нурой.
Если вы хотите предоставить ответ, то выведите строку вида 2 x y (1 ≤ x, y ≤ n, x ≠ y), если считаете, что блюда с номерами x и y были среди заказанных Нурой. После этого сбросьте буфер вывода и завершите работу программы.
Вы, помогая Лехе, можете задавать Нуре запросы не более 60 раз. Каждый запрос должен быть выведен в одной строке и иметь вид 1 x y (1 ≤ x, y ≤ n). После каждого запроса обязательно требуется вывести перевод строки и сбросить буфер вывода (операция flush). После сброса буфера необходимо считать ответ на запрос из входных данных.
После каждого запроса программа жюри выведет одну строку в поток входных данных. Эта строка будет «TAK» или «NIE» (без кавычек) в зависимости от ответа девушки.
Для сброса буфера вывода (то есть для операции flush) сразу после вывода перевода строки можно сделать:
- fflush(stdout) в языке C++;
- System.out.flush() в Java;
- stdout.flush() в Python;
- flush(output) в Pascal;
- смотрите документацию для других языков.
Взломы
Чтобы совершить взлом, вам требуется указать два числа n и k (2 ≤ k ≤ n ≤ 105) в первой строке и, чтобы описать блюда, которые заказала Нура, k целых различных чисел a1, a2, ..., ak (1 ≤ ai ≤ n), записанных в порядке возрастания, во второй строке. Разумеется, у взламываемого решения не будет возможности прочитать номера загаданных блюд.
3 2
NIE
TAK
NIE
TAK
TAK
TAK
1 1 2
1 2 1
1 1 3
1 3 1
1 2 3
1 3 2
2 2 3
В примере в меню существует три блюда. Нура заказала блюда с номерами 2 и 3, которые придется отгадать Лехе. Если Нуре будут поступать запросы о первом блюде (x = 1), то Нура выберет второе (a = 2) как блюдо с наименьшим значением . Для второго (x = 2) и третьего (x = 3) блюд оптимальными будут они же, потому что в таком случае 
.
Пусть Леха спрашивает у Нуры про следующие пары блюд:
- x = 1, y = 2, тогда он получит ответ «NIE», потому что |1 - 2| > |2 - 2|
- x = 2, y = 1, тогда он получит ответ «TAK», потому что |2 - 2| ≤ |1 - 2|
- x = 1, y = 3, тогда он получит ответ «NIE», потому что |1 - 2| > |3 - 3|
- x = 3, y = 1, тогда он получит ответ «TAK», потому что |3 - 3| ≤ |1 - 2|
- x = 2, y = 3, тогда он получит ответ «TAK», потому что |2 - 2| ≤ |3 - 3|
- x = 3, y = 2, тогда он получит ответ «TAK», потому что |3 - 3| ≤ |2 - 2|
По имеющейся информации можно однозначно сказать, что Нура заказала блюда с номерами 2 и 3.
