|
Склад
(Время: 1 сек. Память: 16 Мб Сложность: 58%)
На роботизированном складе имеется n отсеков, в которые робот может размещать грузы. Отсек с номером i имеет вместимость ci. Груз с номером i имеет размер si, поступает на склад в момент времени ai и забирается со склада в момент времени di. Вместимость отсека и размер груза имеют одну и ту же размерность. Если в отсеке с вместимостью c находится несколько грузов с суммарным размером d, то свободное место в этом отсеке равно c – d.
Когда груз с номером i поступает на склад, робот сначала пытается найти отсек, в котором достаточно свободного места для размещения этого груза. Если отсеков, в которых достаточно свободного места, несколько, то робот помещает груз в тот из них, в котором свободного места меньше. Если и таких отсеков несколько, то робот выбирает отсек с минимальным номером.
Если отсеков с достаточным количеством свободного места нет, робот пытается переместить грузы, уже расположенные в отсеках. Для этого он пытается найти такой отсек и такой груз в нем, что перемещение его в другой отсек обеспечивает достаточное количество свободного места для размещения поступившего груза. Если таких вариантов перемещения грузов несколько, то выбирается тот вариант, в котором потребуется перемещение груза с минимальным размером. Если и таких вариантов несколько, то выбирается вариант перемещения, при котором в отсеке, из которого перемещается груз, свободное место после перемещения этого груза будет минимально, а при прочих равных условиях — тот вариант, при котором в отсеке, куда осуществляется перемещение, свободное место после этого перемещения будет также минимально. Если и после этого остается более одного варианта, то выбирается тот вариант, при котором номер перемещаемого груза минимален и номер отсека, в который он перемещается, – также минимален. Если варианта с перемещением одного груза найти не удалось, то груз не принимается на склад.
Требуется написать программу, которая по списку грузов, поступающих для размещения на складе, выводит последовательность действий, выполняемых роботом.
Входные данные
Первая строка входного файла содержит два целых числа: n — количество отсеков, и m — количество грузов (1 ≤ n ≤ 10, 1 ≤ m ≤100). Вторая строка содержит n целых чисел ci, определяющих вместимости отсеков (1 ≤ ci ≤ 109). Последующие m строк описывают грузы: каждый груз описывается тремя целыми числами: своим размером si, временем поступления на склад ai и временем, когда его забирают со склада di (1 ≤ si ≤ 109, 1 ≤ ai < di ≤ 1000, все времена во входном файле различны, грузы упорядочены по возрастанию времени поступления на склад). Все числа в строках разделены пробелом.
Выходные данные
Выведите последовательность действий робота в том порядке, в котором они выполняются. Следуйте формату выходного файла, приведенного в примере. Возможны следующие сообщения:
- put cargo X to cell Y - разместить груз с номером X в отсеке с номером Y;
- move cargo X from cell Y to cell Z - переместить груз с номером X из отсека с номером Y в отсек с номером Z;
- take cargo X from cell Y - взять груз с номером X из отсека с номером Y.
- cargo X cannot be stored - груз X невозможно переместить
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 1
3
3 1 2 |
put cargo 1 to cell 1
take cargo 1 from cell 1
|
| 2 | 3 5
3 2 10
1 1 6
3 2 8
9 3 5
2 4 9
12 7 10 |
put cargo 1 to cell 2
put cargo 2 to cell 1
put cargo 3 to cell 3
move cargo 1 from cell 2 to cell 3
put cargo 4 to cell 2
take cargo 3 from cell 3
take cargo 1 from cell 3
cargo 5 cannot be stored
take cargo 2 from cell 1
take cargo 4 from cell 2
|
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
