Это интерактивная задача.
Made in Heaven — довольно любопытный стенд. Конечно, это (возможно) самый сильный Стенд из всех существующих, но он также является ярым любителем головоломок. Например, недавно он задал Qtaro следующую задачу:
Made in Heaven имеет \(n\) скрытых целых чисел \(a_1, a_2, \dots, a_n\) (\(3 \le n \le 5000\), \(1 \le a_i \le 4\)). Qtaro должен определить все \(a_i\), задав Made in Heaven несколько вопросов следующего вида:
- В одном запросе Qtaro разрешается дать Made in Heaven три различных индекса \(i\), \(j\) и \(k\) (\(1 \leq i, j, k \leq n\)).
- Если \(a_i, a_j, a_k\) образуют стороны невырожденного треугольника \(^\dagger\), Made in Heaven выдаст площадь этого треугольника.
- В противном случае, Made in Heaven ответит \(0\).
Задав не более \(5500\) таких вопросов, Qtaro должен либо сказать Made in Heaven все значения \(a_i\), либо сообщить, что нет возможности однозначно определить их.
К сожалению, из-за перезагрузки вселенной, Qtaro не так умен, как Jotaro. Пожалуйста, помогите Qtaro решить задачу Made In Heaven.
—————————————————————— \(^\dagger\) Три целых положительных числа \(a, b, c\) образуют стороны невырожденного треугольника тогда и только тогда, когда выполняются все следующие три неравенства:
- \(a+b > c\),
- \(b+c > a\),
- \(c+a > b\).
Протокол взаимодействия
Взаимодействие начинается с чтения \(n\) (\(3 \le n \le 5000\)) — количества скрытых целых чисел.
Чтобы задать вопрос, соответствующий тройке \((i, j, k)\) (\(1 \leq i < j < k \leq n\)), выведите «? \(i\) \(j\) \(k\)» без кавычек. После этого вы должны прочитать одно целое число \(s\).
- Если \(s = 0\), то \(a_i\), \(a_j\) и \(a_k\) не являются сторонами невырожденного треугольника.
- Иначе, \(s = 16 \Delta^2\), где \(\Delta\) — площадь треугольника. Площадь предоставляется в таком формате для удобства, чтобы вам нужно было вводить только целые числа.
Если числа \(a_i\) не могут быть однозначно определены, выведите «! \(-1\)» без кавычек. Иначе, если вы определили все значения \(a_i\), выведите «! \(a_1\) \(a_2\) \(\dots\) \(a_n\)» в одну строку.
Интерактор неадаптивный. Скрытый массив \(a_1, a_2, \dots, a_n\) фиксируется заранее и не изменяется в процессе взаимодействия.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Для взлома используйте следующий формат.
Первая строка содержат одно целое число \(n\) (\(3 \le n \le 5000\)) – количество скрытых целых чисел.
Вторая строка содержат \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 4\)) – скрытый массив.
Примечание
В первом примере процесс взаимодействия происходит следующим образом:
| Stdin | Stdout | Объяснение |
| 3 | | Прочитаем \(n = 3\). Существует \(3\) скрытых целых чисел |
|
| ? 1 2 3 | | Попросим найти площадь, образованную \(a_1\), \(a_2\) и \(a_3\) |
|
| 63 | | Получено \(16\Delta^2 = 63\). Значит, площадь \(\Delta = \sqrt{\frac{63}{16}} \approx 1.984313\) |
|
| ! -1 | Ответим, что не существует однозначного массива, удовлетворяющего запросам. |
Из полученной площади можно сделать вывод, что числа, образующие треугольник, либо (\(4\), \(4\), \(1\)), либо (\(3\), \(2\), \(2\)) (в определенном порядке). Поскольку существует несколько массивов чисел, удовлетворяющих запросам, уникальный ответ не может быть найден.
Во втором примере процесс взаимодействия происходит следующим образом:
| Шаг | Stdin | Stdout | Объяснение |
| 1 | 6 | | Прочитаем \(n = 6\). Значит, есть \(6\) скрытых чисел |
| 2 | | ? 1 2 3 | Спросим площадь треугольника, образованного \(a_1\), \(a_2\) и \(a_3\) |
| 3 | 0 | | Они не образуют невырожденный треугольник |
| 4 | | ? 2 3 4 | Спросим площадь треугольника, образованного \(a_2\), \(a_3\) и \(a_4\) |
| 5 | 0 | | Они не образуют невырожденный треугольник |
| 6 | | ? 4 5 6 | Спросим площадь треугольника, образованного \(a_4\), \(a_5\) и \(a_6\) |
| 7 | 0 | | Они не образуют невырожденный треугольник |
|
| 8 | | ? 1 5 6 | Спросим площадь треугольника, образованного \(a_1\), \(a_5\) и \(a_6\) |
| 9 | 63 | | Получим \(16\Delta^2 = 63\). Тогда площадь \(\Delta = \sqrt{\frac{63}{16}} \approx 1.984313\) |
| 10 | | ? 3 5 6 | Спросим площадь треугольника, образованного \(a_3\), \(a_5\) и \(a_6\) |
| 11 | 15 | | Получим \(16\Delta^2 = 15\). Тогда площадь \(\Delta = \sqrt{\frac{15}{16}} \approx 0.968245\) |
| 12 | | ? 1 2 4 | Спросим площадь треугольника, образованного \(a_3\), \(a_5\) и \(a_6\) |
| 13 | 135 | | Получим \(16\Delta^2 = 135\). Тогда площадь \(\Delta = \sqrt{\frac{135}{16}} \approx 2.904738\) |
| 14 | | ! 3 2 1 4 2 2 | Однозначный ответ найден, и он равен \(a = [3, 2, 1, 4, 2, 2]\). |
Из шагов \(10\) и \(11\) мы можем сделать вывод, что мультимножество \(\left\{a_3, a_5, a_6\right\}\) должно равняться \(\left\{2, 2, 1\right\}\).
Из шагов \(8\) и \(9\), мультимножество \(\left\{a_1, a_5, a_6\right\}\) должно быть либо \(\left\{4, 4, 1\right\}\), либо \(\left\{3, 2, 2\right\}\).
Так как \(\left\{a_3, a_5, a_6\right\}\) и \(\left\{a_1, a_5, a_6\right\}\) пересекаются по \(a_5\) и \(a_6\), делаем вывод, что \(a_5 = a_6 = 2\), а также \(a_1 = 3\), \(a_3 = 1\).
Из шагов \(6\) и \(7\) известно, что \(a_5 = a_6 = 2\), а \(a_4\), \(a_5\) и \(a_6\) не могут образовать невырожденный треугольник, следовательно, \(a_4 = 4\).
При всей известной информации, только \(a_2 = 2\) удовлетворяет запросам, сделанным на шагах \(2\), \(3\), \(4\), \(5\), \(12\) и \(13\).
В третьем примере один массив, удовлетворяющий запросам, — \([1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\).