|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1852. Кратчайший путь
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Студент Василий живёт в городе, где улицы образуют правильную сетку кварталов: все кварталы являются квадратами с длиной стороны, равной 100 метрам. Дом Василия располагается в юго-западном углу – точке с координатами (0, 0). Университет располагается в северо-восточном углу – точке с координатами (N, M).  Выйдя утром из дома, Василий идёт в университет. Он движется по улицам, но при этом некоторые кварталы может пересечь также по диагонали, ведущей из юго-западного угла квартала в северо-восточный. Напишите программу, которая вычислит длину кратчайшего маршрута от дома до университета. Входные данные В первой строке находятся два целых числа N и M (0 < N, M ≤ 109) – размер сетки кварталов с запада на восток (по горизонтали) и с юга на север (по вертикали) соответственно. Во второй строке находится целое число K (0 ≤ K ≤ 105) – количество кварталов, через которые можно пройти наискосок. Далее следуют K строк с парами целых положительных чисел x и y, разделённых пробелами – координаты северо-восточных углов таких кварталов (1 ≤ x ≤ N, 1 ≤ y ≤ M). Выходные данные Требуется вывести длину кратчайшего пути от дома Василия до университета в метрах, округлённую до ближайшего целого. Пример Входные данные 3 2 Выходные данные 383 |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Межвузовские олимпиады / | XXI межвузовская олимпиада - 2018 / |
| 1851. F - Треугольник Паскаля | 1852. | 1853. H - Двоичное дерево | 1854. I - Гири | 1855. J - Поисковый индекс |
| Задачи с соревнований и сборов / | Школьные олимпиады и курсы Вологодской области / | Импульс, смена 2019 / | Деревья отрезков / |
| 1986. 09 - Билеты на электричку | 1852. |
| время генерации 0.265 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |