Задача E. А она складывается?..

Задачу добавил: alef

Успешно сдано решений: 0

Так почти наверняка заготовка мембраны не будет полностью закрыта деталями! – воскликнул Кеша.

— Конечно. Но это была первая часть задачки. А вторая состоит в том, чтобы довести изготовление мембраны до конца, – заметил Виктор.

Рис. 1

Заготовка мембраны длиной N клеток и шириной M клеток, на которой уже размещены некоторые детали, может быть описана с помощью M чисел, каждое из которых не превосходит N. Каждое из чисел показывает, какое количество клеток в ряду уже заполнено (рис. 2). Ваша задача состоит в том, чтобы определить минимальное количество деталей вида, как на рис. 1, и их возможный набор, которыми можно заполнить свободные клетки так, чтобы внутри мембраны не оставалось пустот.

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

Рис. 2

Первая строка – целые числа N (1 <= N <= 20) и M (1 <= M <= 10) через пробел. N – длина мембраны в клетках, M – ширина мембраны в клетках.

Вторая строка – M целых чисел R1, R2, …, RM через пробел. Для всех J = 1, 2, …, M верно, что 0 <= RJ <= N. RJ – количество заполненных клеток в ряду № J (на рис.2  приведен пример частично заполненной заготовки для N = 14 и M = 6).

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

Первая строка – целое число K– минимально возможное количество деталей, которое требуется, чтобы полностью заполнить заготовку мембраны. Если это невозможно, следует вывести слово NO.

Следующие K строк присутствуют в выходном файле, если в первой строке указано положительное число деталей, и описывают детали в том порядке, в котором их нужно укладывать (сверху вниз, слева направо).

Каждая из этих строк содержит тип детали, за которым без пробелов следует ноль, один, два или три знака «+», показывающих поворот на 0⁰, 90⁰, 180⁰ и 270⁰ против часовой стрелки относительно исходного положения детали (рис. 1), и – через пробел – номер ряда мембраны, в котором будет находиться левый верхний угол прямоугольника из 6 клеток, объемлющего деталь. Нумерация рядов – сверху вниз, от 1 до M.

Если возможных вариантов заполнения мембраны несколько, выведите любой из них.

Пример входного файла

14 5

8 8 9 9 8

Рис. 3

Пример выходного файла

7

2++ 1

4 4

1 2

4 1

5 4

4+ 3

5+ 1

Пояснение к примеру.

На рис. 3 приведена частично заполненная мембрана (штриховка), и цифрами от 1 до 7 обозначены детали, которые могут быть на нее уложены для полного заполнения. Отдельно изображена деталь типа 5, которая укладывается последней. Крестиком помечен левый верхний угол прямоугольника, из 6 клеток, объемлющего деталь.

Сдать задачу

Задать вопрос жюри по этой задаче