Лифт
Задачу добавил: alef
Успешно сдано решений: 7
Когда все необходимое для ремонта было куплено и доставлено к подъезду, материалы стали выгружать из машины, относить к лифту и укладывать возле него группами, которые мы будем условно называть «кучи». Получилось так, что в каждой (кроме, быть может, последней) куче содержится от M до 2*M–1 предметов (предмет – это и рулон обоев, и пачка клея, и упаковка плитки, и любая другая «упаковочная» единица). В случае, если в куче содержится ровно 2*M–1 предметов, будем называть ее полностью заполненной. Для определенности перенумеруем кучи числами от 1 до N, и для кучи № J будем считать соседними кучи № J–1 и № J+1. У куч № 1 и № N будет только по одной соседней. Загрузка предметов в лифт происходит по следующим правилам. Каждый раз в лифт загружают предметы только из одной кучи. При погрузке в лифт предметы берут из кучи в том порядке, в котором они сложены. Их помещают в лифт до тех пор, пока не закончится куча или пока это не приводит к перегрузке лифта. Если куча загружена в лифт полностью, лифт отправляется на этаж, разгружается и возвращается. Если же в куче еще остались предметы, то делают следующее. Если хотя бы одна из соседних куч еще не заполнена полностью (т.е. в ней предметов меньше 2*M–1), то предмет, который уже не может быть загружен в лифт в настоящий момент, перекладывается в эту кучу. При этом он оказывается верхним в этой куче (т.е. при загрузке этой кучи в лифт его поместят туда первым). То же самое проделывается со следующим предметом – если его нельзя поместить в лифт, его перекладывают в незаполненную соседнюю кучу. Если не заполнены полностью обе соседние кучи, то сначала дополняют ту, в которой предметов меньше (при равенстве количества предметов – кучу с меньшим номером), потом – если одна из куч оказывается полностью заполненной, а предметы еще остаются – дополняют другую. Если соседние кучи отсутствуют или если в результате всех вышеописанных действий в куче, из которой загружали предметы в лифт, все равно еще остаются какие либо предметы, то возможны два варианта. 1. В куче осталось M или более предметов. Тогда она по-прежнему рассматривается как куча с прежним номером. 2. В куче осталось менее M предметов. Если других куч, содержащих менее M предметов, нет, то ей присваивается очередной номер (при возникновении остатка впервые это будет номер N+1). Если же такая куча (с меньшим, чем M количеством предметов) уже имеется, то эта – вновь оставшаяся куча – добавляется к ней (как понятно, в этом случае общее количество предметов в объединяемых кучах не может превысить 2*M–1). Кучи можно загружать в лифт в любом порядке. Ваша задача – определить минимально возможное количество поездок лифта и соответствующий порядок загрузки куч Примечание. Для вновь сформированных (так же как и для исходных) куч соседними считаются кучи с номерами, отличающимися на 1. Так, для кучи с номером N+1 куча с номером N будет соседней. Формат входного файла Первая строка – целые числа N, M и W через пробел N – исходное количество куч (1<=N<=20); M – минимальное количество предметов в любой из исходных куч (возможно, за исключением последней) (1<=M<=10) W – максимально возможная загрузка лифта (в килограммах) Следующие N строк содержат информацию о кучах (строка № 2 – о куче № 1, строка № 3 – о куче № 2, строка № J+1 – о куче № J, и т.д.). Каждая строка содержит не более 2*M–1 целых чисел через пробел – массы предметов (в килограммах), составляющих кучу. Первой в строке указана масса предмета, лежащего в самом низу кучи. Формат выходного файла Первая строка – целое число – минимально возможное количество поездок лифта Вторая строка – целые числа через пробел – номера куч в той последовательности, в которой они должны загружаться в лифт (с учетом вновь формируемых куч) Пример входного файла Пример выходного файла