Bottle Sort
(Время: 5 сек. Память: 256 Мб Сложность: 99%)
Аня любит играть на планшете в игру на переливание жидкостей. При переливании можно смешивать только одинаковые цвета. Причём если две или более доли одного цвета из одной колбы можно перелить сразу, то это будет считаться за один ход. В пустую колбу можно переливать любой цвет. Переливать можно максимум столько долей, сколько свободных долей в наполняемой колбе. Цель игры – отсортировать разноцветные жидкости по бутылкам так, чтобы в каждой был только один цвет.
Помогите Ане пройти 99 уровней этой игры.
Входные данные
В первой строке входного файла INPUT.TXT находятся три натуральных числа N, K, H – количество заполненных колб, количество пустых колб, высота каждой колбы в долях (2 ≤ N, H ≤ 9; 0 < K < 3). Далее в N строках написано по H натуральных чисел ci – цвета (1 ≤ ci ≤ N). Описание цветов идёт снизу вверх.
Выходные данные
В выходной файл OUTPUT.TXT выведите в первой строке наименьшее количество переливаний. Далее в каждой строке вывести само переливание в виде пары чисел: ai bi, где ai – номер колбы из которой переливают в колбу с номером bi.
Гарантируется, что решение существует. Если решений несколько, то выведите любое.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 1 3
1 1 2
3 1 2
2 3 3 | 5
1 4
2 4
2 1
3 2
4 3 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
