Только один день (40 баллов)
Автор задачи: Рогачева Е.В.
Задачу добавил: alef
Успешно сдано решений: 11
Успешный маршрут - дело хорошее, но МM - город большой, а магазины иной раз расположены достаточно далеко друг от друга. В распоряжении NN всего один день, так что нужно, чтобы он успел посетить все магазины в течение дня, и, к тому же, купил книжку.
Попробуйте отыскать именно такой маршрут для NN и выведите номера магазинов в порядке их посещения. Если составить такой маршрут невозможно, в выходном файле следует вывести "NO".
Формат входного файла input.txt
Первая строка содержит целое число K (3<=K<=20) - количество магазинов, а также два вещественных числа, записанных с точностью два знака после запятой - время начала и время окончания путешествия NN в формате часы:минуты
Каждая из следующих K строк содержит информацию в формате: первое число - вещественное с точностью два знака после запятой - цена книги в магазине с соответствующим номером, затем записаны K целых чисел - время в минутах, которое требуется, чтобы добраться от данного магазина до другого.
Замечания. Время начала путешествия NN - это время, когда он оказывается в первом магазине из списка посещаемых, время окончания - время, не позже которого он должен оказаться в последнем магазине.
Во второй строке содержится информация для магазина №1, в третьей - для магазина № 2 и т.д.
Все числа (во всех строках) отделены друг от друга пробелами.
Формат выходного файла output.txt
Одна строка, содержащая K целых чисел через пробел, - номера магазинов в порядке их посещения.
Если маршрут найти невозможно, вывести слово NO.