Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Stones
Задания по информатике

Підпис:  Задача Каменоломни (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

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"