Женская логика
Задачу добавил: alef
Успешно сдано решений: 4
Жена старшего сына Дарья привезла с собой целый обоз приданого. И хочет теперь его аккуратно сложить в специальной комнате-кладовке. Все вещи упакованы в коробки, но коробки эти разного размера. Будем ради простоты считать, что все коробки имеют форму куба и могут быть охарактеризованы параметром Dj – длиной стороны.
Дарья решила поступить просто – сложить все коробки в стопки в кладовке. Действует она по следующим правилам. Первую коробку она кладет на пол слева от дверного проема (см. рис.) – это будет основание первой стопки. Очередную коробку она может положить
а) как самую верхнюю в стопке, в которую она поместила предыдущую коробку – в том случае, если ее длина стороны не превосходит длины стороны коробки, являющейся в этой стопке верхней, и не превосходит высоты от верхней коробки до потолка;
б) если длина стороны превосходит длину стороны коробки, которая является верхней в стопке, переходит к рассмотрению одной из соседних стопок. Соседние стопки Дарья просматривает в таком порядке – стопка, которая следует за рассмотренной в предыдущем пункте по часовой стрелке (если таковая имеется), затем стопка, которая предшествует ей при движении по часовой стрелке (если таковая имеется). Если в эти стопки поместить новую коробку не удалось, она переходит к рассмотрению стопки, которая отстоит на одну от рассмотренной в пункте а) при движении по часовой стрелке и т.д. Возможный порядок рассмотрения стопок приведен на рисунке. Цифрой 0 обозначена стопка, рассмотренная Дарьей в пункте а). Отметим, что пунктирная линия считается границей.
в) если после рассмотрения всех стопок подходящего места для коробки так и не нашлось, Дарья пытается положить ее на пол вплотную к последней из сложенных стопок при движении по часовой стрелке. Когда возникает необходимость, Дарья делает поворот, и кладет коробку уже вдоль другой стены (при этом может оставаться свободное пространство между коробками, как например, показано на рисунке). Дверной проем загораживать нельзя – т.е. никакая коробка не должна пересекать область, ограниченную пунктирной линией (на верхнем рисунке).
Если очередную коробку в кладовку поместить нельзя, Дарья выносит ее из кладовки и переходит к следующей коробке. Разумеется, длина стороны коробки не должна превосходить ширины дверного проема, иначе ее просто нельзя внести в кладовку.
Дарья интересуется, сможет ли она таким путем уложить все свои коробки в кладовке. Ваша задача – написать программу, определяющую это.
Формат входного файла input.txt
Первая строка – целые числа N (1 <= N <= 10000), L (1 <= L <= 1000), W (1 <= W <= 1000), R (1 <= R <= W/2, L/2, H), H (10 <= H <=1000) через пробел.
N – количество коробок, которые надо уложить
Назначение L, W, R очевидно из рисунка.
H – высота комнаты
Вторая строка – N целых чисел D1, D2, …, DN через пробел (1 <= Dj <= 10000, j = 1, 2, …, N) – длины сторон коробок в том порядке, в котором Дарья будет пытаться их укладывать.
Формат выходного файла output.txt
Первая строка – слово YES, если Дарье удастся уложить все свои коробки в кладовой, слово NO, через пробел – количество коробок, которые не поместились в комнату, далее через пробел их номера – в той последовательности, в которой Дарья пыталась поместить их в комнату
Вторая строка – целое число M сформированных в кладовке стопок
Каждая из следующих M строк содержит список номеров коробок (через пробел), составляющих стопку с соответствующим номером. Коробки перечисляются от основания стопки к верху. (Если M = 0, вторая строка будет последней).
Пример входного файла
25 6 10 3 10
3 2 2 4 2 2 2 1 3 3 1 2 2 2 2 2 1 2 1 2 3 2 1 2 1
Пример выходного файла
NO 3 4 21 24
6
1 2 3 5
6 7 8
9 10 11 17
12 13 14 15 16
18 19
20 22 23 25