ЗАДАЧИ
problems.ru 		О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Все источники >> Книги, журналы >> Прасолов В.В., Задачи по планиметрии >> глава 30. Проективные преобразования >> параграф 2. Проективные преобразования плоскости
Фильтр
Сложность с по   Класс с по  
Выбрано 2 задачи
Версия для печати
Убрать все задачи

Имя входного файла:

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

Вниз   Решение

Можно ли составить магический квадрат из первых 36 простых чисел?
Магический квадрат – это квадратная таблица, заполненная числами, в которой суммы чисел во всех строках и столбцах равны.

Вверх   Решение

Задачи

Страница: << 1 2 3 [Всего задач: 13]      

  с решениями  

Задача 58429

Тема:   [ Проективные преобразования плоскости ]
Сложность: 7
Классы: 10,11

Даны две параллельные прямые a, b и точка O. Тогда для каждой точки M можно выполнить следующее построение. Проведем через M произвольную прямую l, не проходящую через O и пересекающую прямые a и b. Точки пересечения обозначим соответственно через A и B, и пусть M' — точка пересечения прямой OM с прямой, параллельной OB и проходящей через A.
а) Докажите, что точка M' не зависит от выбора прямой l.
б) Докажите, что преобразование плоскости, переводящее точку M в точку M', является проективным.
Прислать комментарий     Решение

Задача 58430

Тема:   [ Проективные преобразования плоскости ]
Сложность: 7
Классы: 10,11

Докажите, что преобразование координатной плоскости, которое каждую точку с координатами (x, y) отображает в точку с координатами $ \left(\vphantom{\frac{1}{x},\frac{y}{x}}\right.$$ {\frac{1}{x}}$,$ {\frac{y}{x}}$$ \left.\vphantom{\frac{1}{x},\frac{y}{x}}\right)$, является проективным.
Прислать комментарий     Решение

Задача 58431

Тема:   [ Проективные преобразования плоскости ]
Сложность: 7
Классы: 10,11

Пусть O — центр линзы, $ \pi$ — некоторая плоскость, проходящая через ее оптическую ось a и f — прямые пересечения плоскости $ \pi$ с плоскостью линзы и с фокальной плоскостью соответственно (a| f ). В школьном курсе физики показано, что если пренебречь толщиной линзы, то изображение M' точки M, лежащей в плоскости $ \pi$, строится следующим образом (рис.). Проведем через точку M произвольную прямую l; пусть A — точка пересечения прямых a и l, B — точка пересечения прямой f с прямой, проходящей через O параллельно l. Тогда M' есть точка пересечения прямых AB и OM. Докажите, что преобразование плоскости $ \pi$, сопоставляющее каждой точке ее изображение, является проективным.
Таким образом, через увеличительное стекло мы видим образ нашего мира при проективном преобразовании.


Прислать комментарий     Решение

Страница: << 1 2 3 [Всего задач: 13]      

  с решениями  

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .