|
Олимпиады прошлых лет
|
||||||||||||||||||||||||||||||||||||
|
I Всероссийская заочная олимпиада школьников по информатике, 2006/07 учебный год
Задача L. Переливания
| Имя входного файла: | l.in |
| Имя выходного файла: | l.out |
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
Есть три сосуда с водой. В одном из них A миллилитров воды, в другом - B миллилитров, в третьем - C. Разрешается следующая операция. Можно перелить воду из одного сосуда в другой так, чтобы в том сосуде, в который мы переливаем, количество воды после переливания было в два раза больше, чем до переливания. То есть, если до переливания в сосудах было A, B и C миллилитров соответственно, и мы переливаем, например, из второго сосуда в третий, то после переливания в сосудах должно оказаться A, B-C, 2С миллилитров соответственно (такое переливание можно делать только при условии, когда B≥C). Эту операцию можно повторять не более 10000 раз.
Напишите программу, которая определит, можем ли мы в результате освободить один из сосудов.
Формат входных данных
Во входном файле записаны неотрицательные целые числа A, B, C - количество воды в каждом из сосудов изначально. Числа A, B, C не превышают 1018.
Формат выходных данных
Если освободить один из сосудов можно, то выведите сначала количество операций, которое для этого понадобится, а дальше - сами операции. Каждая операция описывается двумя числами - номером сосуда, из которого мы переливаем, и номером сосуда, куда переливаем. Минимизировать количество операций переливания не требуется, но их количество не должно превышать 10000.
Если освободить сосуд невозможно (или на это требуется больше 10000 операций), выведите в выходной файл одно число -1 (минус один).
Примеры
| l.in | l.out |
1 2 10 |
2 3 1 2 1 |
0 1 0 |
0 |