Задача Каменоломни
(STONES)
В
стране Qwerty все постройки строятся исключительно из камня. Для каждой
строительной фирмы камень добывается в собственной каменоломне и обработка
может производиться на одной из фабрик,
количество которых совпадает с количеством каменоломен. К этим объектам ведет
единственная прямая дорога по краю скалы, по одной стороне от которой находится
обрыв, а по другой указанные объекты. Владельцы строительных фирм столкнулись с
множеством транспортных проблем (заторы и пробки) на единственной дороге и
решили построить альтернативные дороги для доставки камня на
фабрики. Поскольку стоимость доставки и обработки одинакова для всех фабрик и
не зависит от расстояния, то чтобы не допустить пробок в будущем, владельцы
решили строить дороги непересекающимися между собой и с основной дорогой.
Ваша задача написать программу, которая по заданному
расположению 
каменоломен и 
фабрик предложит один из вариантов прокладки
непересекающихся дорог.
Формат ввода/вывода:
Напишите программу STONES, которая читает входные данные
из файла STONES.DAT и записывает результат в файл STONES.SOL.
Файл STONES.DAT содержит целое число и последовательность из 
нулей и единиц разделенных пробелами, которая
описывает расположение каменоломен и камнеобрабатывающих фабрик относительно
дороги слева направо (см. рисунок): 
– каменоломня, 
– фабрика.
Если построение невозможно, то
файл STONES.SOL должен содержать слово “NO” (без кавычек). В противном
случае файл STONES.SOL должен содержать пар целых чисел, разделенных пробелом. Каждая
пара чисел – это номер каменоломни и номер фабрики, которые должны быть
соединены дорогой. Каменоломни
нумеруются целыми
числами от до слева направо. Фабрики нумеруются таким же образом. Если существует
несколько вариантов решения, выведите любой из них.
Ограничения: 
.
Пример: (см. рисунок)
|
STONES.DAT: 3 0 1 0 0 1 1 |
STONES.SOL: 2 1 1 3 3 2 |