Дано N шаров,
из них N – 2 шара имеют одинаковый вес, а два — одинаковый
между собой несколько больший вес. Требуется за минимальное количество
взвешиваний на рычажных весах определить, какие два шара являются тяжёлыми.
Операция взвешивания заключается в том, что на каждую из двух чаш весов
кладётся одинаковое количество шаров. Если какая-то чаша перевесила — или оба
тяжёлых шара среди положенных на неё, или на ней один тяжёлый шар, а второй
тяжёлый шар среди не лежащих на весах шаров. Если весы оказались в равновесии —
или чаши весов содержат по одному тяжёлому шару, или оба тяжёлых шара среди не
лежащих на весах шаров. После каждого взвешивания можно принять решение о том,
какие шары будут участвовать в следующем взвешивании.
В первой строке входного файла записано одно целое
число N (от 3 до 13).
В первой строке выходного файла выведите последовательность
правил и результатов взвешиваний.
Правило взвешивания задаётся возможно пустой
последовательностью символов '<', '>' и '=' (результаты предыдущих
взвешиваний), за которыми следует знак вопроса, последовательность номеров
шаров на левой чаше весов, знак '/' и последовательность номеров шаров на
правой чаше весов. Числа отделяются от других чисел и символов одним знаком
пробела, после последнего числа пробела быть не должно.
Результат взвешивания задаётся возможно пустой
последовательностью символов '<', '>' и '=' (результаты взвешиваний), за
которыми следует двоеточие и номера тяжёлых шариков.
Например, запись '<<=? 1 2 / 3 4' означает, что если результаты первых трёх взвешиваний (описанных
также правилами в какой-то другой строке) были соответственно "левая чаша
легче", "левая чаша легче" и "чаши в равновесии", а в
четвёртом взвешивании на левую чашу весов нужно положить шары с номерами 1 и 2,
а на правую 3 и 4. Если левая чаша будет весить меньше, то дальше будет
применяться взвешивание из правила, начинающегося символами '<<=<?' или будет получен результат взвешивания, описанный
строкой '<<=<:'. Если левая чаша будет весить больше, то далее будет
применяться правило '<<=>?' или вывод '<<=>:'.
Если чаши уравновесятся, то будет использоваться правило '<<==?' или вывод '<<==:'.
Пример
|
Поток ввода
|
Поток вывода
|
|
3
|
?
1 / 2
<:
2 3
>:
1 3
=:
1 2
|
|
4
|
?
1 / 2
<?
2 / 3
<>:
2 4
<=:
2 3
>?
1 / 3
>>:
1 4
>=:
1 3
=?
1 / 3
=<:
3 4
=>:
1 2
|
