Задача №3880. Переливание
На досуге вы любите почитать сборники занимательных задач по математике. Недавно вы наткнулись в одном из таких сборников на следующую задачу:
Есть бесконечный резервуар с водой и два пустых сосуда объёмом 5 и 12 литров. Можно наливать воду из резервуара в любой сосуд до его заполнения, переливать воду из —одного сосуда в другой до заполнения второго или опустошения первого (смотря что будет раньше) и выливать воду из сосуда на землю до полного опустошения сосуда. Как таким образом можно отмерить 3 литра?
Вы решили написать программу, которая будет решать подобные задачи для произвольных объёмов сосудов.
Во входном файле находятся три целых числа — \(V_1\), \(V_2\) и \(V\) — объёмы двух сосудов и объем воды, который нужно отмерить. Гарантируется, что \(1\leq V_1,V_2\leq 32767\) и \(0\leq V\leq \max(V_1,V_2)\).
В первую строку выходного файла выведите одно число — количество действий в вашем решении. Далее выведите соответствующее количество строк, описывающих действия в вашем решении. Для каждого действия выведите два числа:
- если это действие — переливание из одного сосуда в другой, то первое число должно быть номером сосуда, откуда надо переливать воду, а второе — номером сосуда, куда переливать;
- если это действие — набор воды из резервуара, то первое число должно быть нулём, а второе — номером сосуда, куда наливать;
- если это действие — выливание воды “на землю”, то первое число должно быть номером сосуда, а второе — нулём.
После выполнения всех операций хотя бы в одном сосуде должна находиться вода в объёме \(V\).
Если существует несколько решений, то вы можете вывести любое. Ваше решение не обязано быть оптимальным, единственное ограничение — размер выходного файла не должен превосходить 3 Мб.
Если решений не существует, выведите одно число -1.
5 12 3
10 0 1 1 2 2 1 1 2 0 1 1 0 0 1 1 2 0 1 1 2