Все источники
>>
Олимпиады и турниры
>>
Всероссийская олимпиада по математике
>>
1992-1993
>>
Региональный этап
>>
9 класс
Фильтр
Выбрано 3 задачи Убрать все задачи
|
Имя входного файла: |
stalker.in |
|
Имя выходного файла: |
stalker.out |
|
Максимальное время работы на одном тесте: |
2 секунды |
|
Максимальный объем используемой памяти: |
128 мегабайт |
В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.
Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.
Формат входных данных
В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.
В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число ri - количество дорог, обозначенных на i-ой карте. Затем идут ri строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r1 + r2 + ... + rK ≤ 300 000).
Формат выходных данных
В выходной файл необходимо вывести одно число - минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число -1.
Примеры
|
stalker.in |
stalker.out |
stalker.in |
stalker.out |
|
|
5 3 1 3 4 3 1 2 1 3 2 4 1 4 5 |
2 |
5 3 2 3 2 4 5 1 2 1 2 1 3 5 4 |
-1 |
РешениеНайдите наибольшее число, у которого каждая цифра, начиная с третьей, равна сумме двух предыдущих цифр.
РешениеНа доске написано число 0. Два игрока по очереди приписывают справа к выражению на доске: первый – знак + или - , второй – одно из натуральных чисел от 1 до 1993. Игроки делают по 1993 хода, причем второй записывает каждое из чисел от 1 до 1993 ровно по одному разу. В конце игры второй игрок получает выигрыш, равный модулю алгебраической суммы, написанной на доске. Какой наибольший выигрыш он может себе гарантировать?
Решение
Задачи
Задача 109548 (#93.4.9.6) |
|
|
Три прямоугольных треугольника расположены в одной полуплоскости относительно данной прямой l так, что один из катетов каждого треугольника лежит на этой прямой. Известно, что существует прямая, параллельная l, пересекающая треугольники по равным отрезкам. Докажите, что если расположить треугольники в одной полуплоскости относительно прямой l так, чтобы другие их катеты лежали на прямой l, то также найдётся прямая, параллельная l , пересекающая их по равным отрезкам.
|
|
Решение |
Задача 108230 (#93.4.9.7) |
|
|
На диагонали AC ромба ABCD взята произвольная точка E, отличная от точек A и C, а на прямых AB и BC
– точки N и M соответственно, причём
AE = NE и CE = ME. Пусть K – точка пересечения прямых AM и CN. Докажите, что точки K, E и D лежат на одной прямой.
|
|
|
Решение |
Задача 109550 (#93.4.9.8) |
|
|
|
|
|
Решение |
Страница: << 1 2 [Всего задач: 8]
