spoj
Задача
B
Наименование
LUNAR BASE

Условие

ГРУПА A, ЗАДАЧА B. ЛУННА БАЗА
---
Компанията за космическо развитие “Спейс Инвейдърс ЕООД” планира изграждането на първата си база на Луната. Тя ще има форма на прав тунел, който ще започва от вече фиксирана начална позиция и ще бъде на D метра под равнището ѝ. Посоката, в която ще се строи базата също е известна. 

Това позволява да представим картата на терена, като списък от височини (в метри), спрямо началната позиция (която е на височина 0 метра). Всеки елемент от списъка представлява осреднената височина на участък с дължина 100 метра от терена.
 
Скоро ще изпратят строителен дрон “СД101”, който ще се приземи на началната позиция. Мисията на строителният дрон е да изравни терена от картата, на D метра дълбочина. 

СД101 има три основни режима на работа:
1.	Режим на копаене, в който събира строителен материал от терена, с което намалява височината му със зададено количество метри.
2.	Режим на строене, в който “повдига” терена със зададено количество метри, използвайки изкопания материал от 1 (сумата от метрите от режим „повдигане“ трябва да е по-малък или равен на метрите от предходни команди „копаене“). 
3.	Режим на придвижване. 

Тези режими съответстват на следните команди, които се изпращат към дрона в поредици (програми):
- DIG d	= Изкопава участък от 100 метра дължина напред и d метра надолу и акумулира d единици строителен материал
- BUILD b = Повдига с b  метра нагоре участък от 100 метра дължина напред, за което използва b единици строителен материал
- MOVE x =Премества дрона x метра напред по посоката на тунела

След като изпълни DIG или BUILD команда, СД101 застава на края на обработения участък (премества се 100 метра напред). С командата “DIG 0”, дронът се премества 100 метра напред, без да променя средната височина на терена.

От технически съображения, инженерите на Спейс Инвейдърс решили, че всяка програма, която се изпраща към дрона, трябва да съдържа най-много една MOVE команда. Също така е важно, първата програма да се напише така, че след нейното изпълнение, да остане максимално количество строителен материал. Ако има различни варианти да се постигне това количество, се избира вариант с максимална дължина.

Напишете генератор на първата програма за СД101, който по зададена карта на терена и дълбочина D на базата да изведе съответната поредица от команди.

Вход:
На първия ред е зададена стойността на D (дълбочината на базата). На втория ред има списък A от N цели числа, разделени с интервал, описващи картата на терена.

Изход:
Поредица от команди за СД101, разделени с празен ред. Ако не е възможно да се генерира програма, даваща неотрицателно количество материал, то трябва да се изведе един ред със съобщението: NO RESOURCES.

Ограничения:
0 ≤ D ≤ 100 000	= Дълбочината, на която ще се строи базата
0 < N ≤ 50 000	= Броят числа, задаващи картата на терена
-100 000 ≤ Ai ≤ 100 000	= Всеки елемент от картата на терена
0 < x ≤ 5 000 000 = Параметърът на команда MOVE
0 ≤ d ≤ 200 000 = Параметърът на команда DIG
0 < b ≤ 200 000	= Параметърът на команда BUILD

Примерен вход 1: 
150
-450 -250 350 250 50 -150 150 -350 -50

Примерен изход 1:
MOVE 200
DIG 500
DIG 400
DIG 200
DIG 0
DIG 300

Примерен вход 2:  
100
0 -300 0 100 -200 0

Примерен изход 2:
DIG 100
MOVE 100
DIG 100
DIG 200
BUILD 100
DIG 100

Примерен вход 3  
0
-100 -100 -100

Примерен изход 3:
NO RESOURCES

« Предходна страница Решение Въпрос