Задача C. Спичечные блоки

Автор:А. Баранов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Пусть имеется n спичек равной длины. Из указанных спичек необходимо собрать набор прямоугольных блоков, каждый из которых представляет собой двумерную матрицу квадратных ячеек (см. рисунок). При этом каждое ребро в таком блоке соответствует ровно одной спичке. Таким образом, полученный блок однозначно определяется своей конфигурацией [A × B], где A и B — размеры его сторон. Блоки, совпадающие с точностью до поворота, считаются одинаковыми, т.е. [A × B] = [B × A].

Требуется вывести все уникальные комбинации прямоугольных блоков, которые можно составить из заданного числа спичек. При этом каждая такая комбинация должна включать в себя все имеющиеся спички. Комбинации, различающиеся только лишь порядком следования составляющих их блоков, полагаются тождественными и не должны встречаться более одного раза.

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

Входной файл "input.txt" содержит исходное число спичек n.

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

Выходной файл "output.txt" должен содержать все найденные комбинации, представленные в следующем формате: вначале указывается число блоков в текущей комбинации k; далее следует ровно k пар натуральных чисел, определяющих конфигурации имеющихся блоков.

В случае, если подходящие комбинации не были найдены, в выходной файл записывается единственный символ пробела (ASCII 32).

Ограничения

0 < n ≤ 128

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

Входной файл (input.txt) Выходной файл (output.txt)
1
23
5 1 1 1 1 1 1 1 1 1 2
3 1 1 1 2 2 2
2 1 1 1 6
2 1 2 1 5
2 1 3 1 4
2
3
 

0.114s 0.014s 17