Заочная олимпиада 2006 - Сложные Ханойские Башни

Задача B. Сложные Ханойские Башни ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Э. Люка, И. Олейников	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	2 Мб
Выходной файл:	output.txt
Максимальный балл:	100

Условие

Согласно древней легенде в индийском городе Бенареса существует "Пирамида Браминов". Она состоит из N золотых колец разного диаметра и K алмазных стержней, на которые в день основания мира были надеты эти кольца. Жрецы храма должны непрерывно перекладывать кольца, соблюдая следующие правила:

1) Кольцо большего диаметра нельзя положить на кольцо меньшего диаметра

2) За один раз можно переместить только одно кольцо, являющиеся верхним на одном из стержней

Когда все кольца окажутся на K-том стержне по легенде произойдет конец света. Сначала все кольца лежат на 1-ом стержне. Так как жрецы хотят быстрее попасть на небо они просят вас написать программу, которая по числам N и K определит такой алгоритм перекладывания колец, что если К = 3, то число затраченных действий будет равно 2^N-1, иначе число действий должно быть меньше чем минимум из чисел N³ и N²K.

Формат входного файла

Во входном файле содержится два числа N и K.

Формат выходного файла

Выходной файл должен содержать число M - количество перекладываний, за которым следует M пар чисел i j, которые обозначают, что верхний диск с i-того стержня должен быть перемещен на j-тый. Если решений несколько выведите любое из них. Если решений не существует выведите −1.

Ограничения

1 ≤ N ≤ 31, 2 ≤ K ≤ 33, M ≤ 2¹⁵-1.

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`3 3`	`7 1 3 1 2 3 2 1 3 2 1 2 3 1 3`