2 тур - з 24.10 по 30.10.2016
точка входу для відправлення розв'язків http://134.249.159.199//cgi-bin/new-client?contest_id=34
Задача 1. Задача про зайця (20 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 1с.
У невеличкій посадці живе заєць. Вискочивши з нори і бігаючи по снігу, він залишив сліди. Визначити де знаходиться заєць.
Вхідні дані
Карта руху зайця задана N (1≤N≤100) рядками, які містять послідовність великих латинських літер перша буква звідки наступні куди.
Вихідні дані
Виведіть послідовність літер в стовпчик в порядку зростання, які вказують можливе місце розташування зайця, якщо карта не може бути рухом зайця вивести NO SOLUTION.
Приклад
Приклад вхідних даних
|
Приклад вихідних даних
|
10
B C D K M A
C D K L
D L R
K L Q N M
M N A
A P N
N P
Q P R L
L R
R P
|
B
L
|
Задача 2. Школа (100 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 1с.
В Луцьку побудували нову школу. Школа містила N кабінетів, пронумерованих від 1 до N, між деякими з них є двері. Коли учень проходить через двері, він отримує певну кількість знань. Вхід в школу знаходиться в кабінеті 1, а вихід в N. Кожний учень проходить школу рівно один раз і поступає в певний вищий навчальний заклад в залежності від набраних балів (при вході в школу цей бал рівний нулю). Ваша задача показати найкращий результат.
Вхідні дані
Перший рядок вхідного файлу містить цілі числа N (1≤ N≤2000) – кількість кабінетів та M (1≤M≤10000) кількість дверей. В кожному з наступних M рядків міститься опис дверей: номер кабінету, з якого та в який вони ведуть, а також ціле число, яке визначає кількість знань отриманих при проходженні через двері (це число по модулю не перевищує 10000). Двері можуть вести з кабінету в той самий кабінет між двома кабінетами може бути більше ніж одні двері.
Вихідні дані
В вихідний файл виведіть "yes" – якщо можна отримати необмежено великий запас знань, "no" – якщо школу пройти неможна, і максимальну кількість знань іншому випадку.
Приклад
Input.txt
|
Output.txt
|
2 2
1 2 5
1 2 -5
|
5
|
|