АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

911. Взвешивание-2

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Дано 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

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XIV Межвузовская олимпиада 2011 /
910. I - Мaршрутизация 911. 912. X - Взвешивание
 
время генерации 0.141 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.