eolymp
bolt
Try our new interface for solving problems
Məsələlər

Взвешивания 2

Взвешивания 2

Дано \textit{\textbf{N}} шаров, из них \textit{\textbf{N}}\textbf{ -- 2} шара имеют одинаковый вес, а два --- одинаковый между собой несколько больший вес. Требуется за минимальное количество взвешиваний на рычажных весах определить, какие два шара являются тяжёлыми. Операция взвешивания заключается в том, что на каждую из двух чаш весов кладётся одинаковое количество шаров. Если какая-то чаша перевесила --- или оба тяжёлых шара среди положенных на неё, или на ней один тяжёлый шар, а второй тяжёлый шар среди не лежащих на весах шаров. Если весы оказались в равновесии --- или чаши весов содержат по одному тяжёлому шару, или оба тяжёлых шара среди не лежащих на весах шаров. После каждого взвешивания можно принять решение о том, какие шары будут участвовать в следующем взвешивании. \InputFile В первой строке входного файла записано одно целое число \textit{\textbf{N}} (от \textbf{3} до \textbf{13}). \OutputFile В первой строке \textit{\textbf{выходного файла }}выведите последовательность правил и результатов взвешиваний. Правило взвешивания задаётся возможно пустой последовательностью символов '\textbf{<}', '\textbf{>}' и '\textbf{=}' (результаты предыдущих взвешиваний), за которыми следует знак вопроса, последовательность номеров шаров на левой чаше весов, знак '\textbf{/}' и последовательность номеров шаров на правой чаше весов. Числа отделяются от других чисел и символов одним знаком пробела, после последнего числа пробела быть не должно. Результат взвешивания задаётся возможно пустой последовательностью символов '\textbf{<}', '\textbf{>}' и '\textbf{=}' (результаты взвешиваний), за которыми следует двоеточие и номера тяжёлых шариков. Например, запись '\textbf{<<=? 1 2 / 3 4}' означает, что если результаты первых трёх взвешиваний (описанных также правилами в какой-то другой строке) были соответственно "левая чаша легче", "левая чаша легче" и "чаши в равновесии", а в четвёртом взвешивании на левую чашу весов нужно положить шары с номерами \textbf{1} и \textbf{2}, а на правую \textbf{3} и \textbf{4}. Если левая чаша будет весить меньше, то дальше будет применяться взвешивание из правила, начинающегося символами '\textbf{<<=}' или будет получен результат взвешивания, описанный строкой '<<=<:'. Если левая чаша будет весить больше, то далее будет применяться правило '<<=>?' или вывод '<<=>:'. Если чаши уравновесятся, то будет использоваться правило '<<==?' или вывод '<<==:'.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
3
Çıxış verilənləri #1
? 1 / 2
<: 2 3
>: 1 3
=: 1 2