Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Женская логика

Задачу добавил: 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

Сдать задачу

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