Лифт
Задачу добавил: alef
Успешно сдано решений: 0
Когда ремонт закончен, необходимо вывезти строительный мусор, ставшие лишними вещи...
Все от чего требовалось освободить квартиру, отнесли к лифту и положили возле него группами, которые мы будем условно называть «кучи». Получилось так, что в каждой (кроме, быть может, последней) куче содержится от M до 2*M предметов (предмет – это и коробка, и пакет, и сверток, и любая другая «упаковочная» единица). В случае, если в куче содержится ровно 2*M предметов, будем называть ее полностью заполненной.
Для определенности перенумеруем кучи числами от 1 до N, и для кучи № J будем считать соседними кучи № J–1 и № J+1. У куч № 1 и № N будет только по одной соседней.
Загрузка предметов в лифт происходит по следующим правилам.
Каждый раз в лифт загружают предметы только из одной кучи.
При погрузке в лифт предметы берут из кучи в том порядке, в котором они сложены. Их помещают в лифт до тех пор, пока не закончится куча или пока это не приводит к перегрузке лифта.
Если куча загружена в лифт полностью, лифт отправляется на первый этаж, разгружается и возвращается.
Если же в куче еще остались предметы, то делают следующее. Если хотя бы одна из соседних куч еще не заполнена полностью (т.е. в ней предметов меньше 2*M), то предмет, который уже не может быть загружен в лифт в настоящий момент, перекладывается в эту кучу. При этом он оказывается верхним в этой куче (т.е. при загрузке этой кучи в лифт его поместят туда первым). То же самое проделывается со следующим предметом – если его нельзя поместить в лифт, его перекладывают в незаполненную соседнюю кучу.
Если не заполнены полностью обе соседние кучи, то сначала дополняют ту, в которой предметов меньше (при равенстве количества предметов – кучу с меньшим номером). Анализ количества предметов в соседних кучах производится на каждом шаге.
Если соседние кучи отсутствуют или если в результате всех вышеописанных действий в куче, из которой загружали предметы в лифт, все равно еще остаются какие либо предметы, то возможны два варианта.
- В куче осталось M или более предметов. Тогда она по-прежнему рассматривается как куча с прежним номером.
- В куче осталось менее 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