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

Лифт

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

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

Когда ремонт закончен, необходимо вывезти строительный мусор, ставшие лишними вещи...

Все от чего требовалось освободить квартиру, отнесли к лифту и положили возле него группами, которые мы будем условно называть «кучи». Получилось так, что в каждой (кроме, быть может, последней) куче содержится от M до 2*M предметов (предмет – это и коробка, и пакет, и сверток, и любая другая «упаковочная» единица). В случае, если в куче содержится ровно 2*M предметов, будем называть ее полностью заполненной.

Для определенности перенумеруем кучи числами от 1 до N, и для кучи № J будем считать соседними кучи № J–1 и № J+1. У куч № 1 и № N будет только по одной соседней.

Загрузка предметов в лифт происходит по следующим правилам.

Каждый раз в лифт загружают предметы только из одной кучи.

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

Если куча загружена в лифт полностью, лифт отправляется на первый этаж, разгружается и возвращается.

Если же в куче еще остались предметы, то делают следующее. Если хотя бы одна из соседних куч еще не заполнена полностью (т.е. в ней предметов меньше 2*M), то предмет, который уже не может быть загружен в лифт в настоящий момент, перекладывается в эту кучу. При этом он оказывается верхним в этой куче (т.е. при загрузке этой кучи в лифт его поместят туда первым). То же самое проделывается со следующим предметом – если его нельзя поместить в лифт, его перекладывают в незаполненную соседнюю кучу.

Если не заполнены полностью обе соседние кучи, то сначала дополняют ту, в которой предметов меньше (при равенстве количества предметов – кучу с меньшим номером). Анализ количества предметов в соседних кучах производится на каждом шаге.

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

  1. В куче осталось M или более предметов. Тогда она по-прежнему рассматривается как куча с прежним номером.
  2. В куче осталось менее M предметов. Если же такая куча (с меньшим, чем M количеством предметов) уже имеется, то эта – вновь оставшаяся куча – добавляется к ней (как понятно, в этом случае общее количество предметов в объединяемых кучах не может превысить 2*M). Если других куч, содержащих менее M предметов, нет, то она также рассматривается как куча с прежним номером.

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

Кучи можно загружать в лифт в любом порядке.

Ваша задача – определить минимально возможное количество поездок лифта и соответствующий порядок загрузки куч

Примечание. Соседними считаются только кучи с номерами, отличающимися на 1. Если куча с некоторым номером «исчезает», то ее соседи не становятся соседями друг друга.

Формат входного файла
Первая строка – целые числа N, M и W через пробел
N – исходное количество куч (1<=N<=10);
M – минимальное количество предметов в любой из исходных куч (возможно, за исключением последней) (1<=M<=10)
W – максимально возможная загрузка лифта (в килограммах) (1<=W<=1000)
Следующие N строк содержат информацию о кучах (строка № 2 – о куче № 1, строка № 3 – о куче № 2, строка № J+1 – о куче № J, и т.д.).
Каждая строка содержит не более 2*M (и не менее M – возможно, за исключением последней) целых чисел через пробел – массы предметов (в килограммах), составляющих кучу. Первой в строке указана масса предмета, лежащего в самом низу кучи. Масса любого предмета не меньше 1 кг и не больше W кг

Формат выходного файла
Первая строка – целое число – минимально возможное количество поездок лифта
Вторая строка – целые числа через пробел – номера куч в той последовательности, в которой они должны загружаться в лифт (с учетом вновь формируемых куч)

Пример входного файла
2 2 200
80 100 50
50 150

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

Сдать задачу

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