| Автор: | Городская олимпиада школьников Санкт-Петербурга по информатике 2006 | Ограничение времени: | 1 сек | |
| Входной файл: | parcel.in | Ограничение памяти: | 64 Мб | |
| Выходной файл: | parcel.out |
Почтовый поезд уже готов к отправлению, и тут рядом с платформой останавливается дилижанс, из которого выскакивает сам начальник почтового отделения. Он подбегает к поезду и вручает Бобу посылку. Боб заходит внутрь вагона и обнаруживает, что места на такую большую посылку уже точно не осталось. Свободна только одна маленькая полочка под самым потолком. Но начальник уверяет, что эту посылку просто необходимо доставить. Похоже, придется переставлять коробки с одной полки на другую. А ведь времени осталось так мало!
Согласно инструкции, Боб может действовать следующим образом: за одно действие он может взять коробку с некоторой полки и перенести ее на другую полку.
Для каждой полки известен максимальный вес коробки, которую можно на ней разместить. При этом, поскольку времени очень мало, Бобу нужно постараться освободить полку для вновь прибывшей посылки, совершив минимальное количество действий.
К сожалению, Боб не очень быстро соображает, так что вы очень поможете ему, если напишете программу, которая найдет для него нужный порядок действий.
На первой строке записано целое число n — количество полок в вагоне.
На второй строке содержатся n целых чисел ci, разделенных пробелами. i-е из них задает максимальный вес предмета, который можно поставить на полку номер i.
На третьей строке задано n − 1 натуральное число wi — веса коробок, стоящих на соответствующих полках (последняя полка изначально пуста).
В последней строке задан вес a новой посылки, которую требуется поставить.
На первой строке выходного файла запишите минимальное число действий m, которое придется совершить Бобу.
На второй строке выведите описания этих действий — m − 1 натуральное число, задающие, предмет с какой полки перемещается на ту, которая свободна в текущий момент времени (последним действием ставится привезенная посылка). Если поставить посылку невозможно ни при какой последовательности действий, выходной файл должен содержать число −1.
| № | Входной файл (parcel.in) |
Выходной файл (parcel.out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|