e-olymp 88. Месть Ли Чака

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

Входные данные

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

Выходные данные

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные Выходные данные
$531$ $348$ $1645$ $911$
$1784353$ $453345$ $463973$ $214457$
$39252362$ $345673$ $786536$ $302328$
$68790234$ $679643$ $789057$ $281232$
$324$ $8564$ $45074547$ $32984424$

Код программы

Решение задачи

Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. Обозначим начальное местоположение Гайбраша — $g,$ Ли Чака — $l.$, выход $e.$
Безопасный для Гайбраша маршрут существует тогда и только тогда, когда существует путь $\omega,$ такой, что для $\forall v \in \omega \ \rho \left(g, v \right ) + 1 < \rho(l, v).$ С помощью поиска в ширину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в ширину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае — нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 130. Прямоугольник

Задача

Заданы координаты трёх вершин прямоугольника. Найдите координаты четвертой вершины.

Входные данные

В единственной строке записано шесть чисел — координаты трёх точек.

Выходные данные

Два числа, координаты искомой вершины прямоугольника. Все входные и выходные данные — целые числа, не превышающие по модулю [latex]100[/latex].

Тесты

Входные данные Выходные данные
[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]1[/latex] [latex]2[/latex] [latex]1[/latex] [latex]2[/latex] [latex]0[/latex]
[latex]1\, 4\, 4\, 0\, 0\, 2[/latex] [latex]5\, 2[/latex]
[latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex]
[latex]2[/latex] [latex]-1[/latex] [latex]3[/latex] [latex]1[/latex] [latex]-2[/latex] [latex]1[/latex] [latex]-1[/latex] [latex]3[/latex]
[latex]8\, 0\, 1\, 6\, 0\, 4[/latex] [latex]9\, 2[/latex]

Код программы

Решение задачи

Прямоугольник

Прямоугольник

Координаты четвертой вершины будут равны сумме координат прилежащих вершин минус координаты противоположной вершины, т. е: [latex]x_4=x_1+x_3-x_2[/latex] и [latex]y_4=y_1+y_3-y_2[/latex]. Но мы не знаем какая из входных вершин противоположна четвертой, а какие — прилежащие. Так как наша фигура это прямоугольник, то противоположная вершина будет при угле [latex]90^{\circ}[/latex]. Произведение перпендикулярных векторов дает [latex]0[/latex]. Перебрав три варианта произведения векторов, заданных входными вершинами, находим вершину при угле [latex]90^{\circ}[/latex]. Остальные две, соответственно, будут прилежащими. Находим координаты четвертой вершины по формуле, заданной выше.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 27. Циклические сдвиги

Задача

Циклический сдвиг

Запишем целое десятичное число $n$ в двоичной системе счисления и образуем все левые циклические сдвиги числа $n$, у которых первая цифра числа переносится в конец.

Например, если $n = 11$, то в двоичной системе это $1011_2$, его циклические сдвиги: $0111_2$, $1110_2$, $1101_2$, $1011_2$. Максимальное значение $m$ у всех полученных таким образом чисел будет иметь число $1110_2 = 14_{10}$.

Для заданного числа $n$ определить максимальное значение $m$.

Входные данные: одно число $n (1 ≤ n ≤ 2\cdot 10^9)$.

Выходные данные: искомое число $m$.

Тесты

Входные данные Выходные данные
11 14
23 30
256 256
257 384
34132 43664

Код программы

Решение задачи

  1. Сначала мы находим степень двойки, большую данного числа;
  2. Далее мы циклически сдвигаем влево данное число на один бит и из полученных чисел выбираем наибольшее.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 1507. История Лаурела-Харди

Задача

Лаурел и Харди — два известных киногероя $50$-ых. Они известны своей разницей в весе, как можно увидеть на картинке. Если Вы еще не разобрались, кто из них кто, то я добавлю, что Лаурел легче. В свои юношеские годы Лаурел и Харди любили играть со странными качелями, и когда качели находились в равновесии, то Харди всегда был у земли. Мы рассмотрим двумерную версию качель.

Качели, которыми пользовались Лаурел и Харди, представляют собой часть окружности радиуса $r$, как показано на картинке (они закрашены серым и имеют вид буквы $D$). Харди сел на точку $B$ (самая правая точка качель), а Лаурел сел на точку $A$ (самая левая точка отрезка $AB$). $d = EF$ — расстояние между центром отрезка $AB$ и дуги $AFB$. То есть $E$ — середина отрезка $AB$, а $F$ — середина дуги $AFB$. $MN$ — основа качель, является горизонтальной прямой. $BD = h_1$ — расстояние от Харди до земли. Вам необходимо найти расстояние от Лаурела до земли (обозначаемое $h_2 = AC$).

Входные данные

Первая строка содержит количество тестов $N (0 < N ≤ 1000)$. Каждая из следующих $N$ строк представляет собой отдельный тест, который имеет следующий формат:

Каждая строка содержит три целых числа $r (10 ≤ r ≤ 100)$, $d (5 ≤ d ≤ r)$, $h_1 (5 ≤ h_1 ≤ d)$. Значение этих чисел приведено выше.

Выходные данные

Для каждого теста в отдельной строке вывести его номер и действительной число — значение $h_2$. Это число должно содержать четыре десятичных знака. Формат вывода приведен в примере.

Тесты

Входные данные Выходные данные
2
10 10 10
10 7 6
Case 1: 10.0000
Case 2: 8.0342
3
12 7 7
11 11 8
54 12 6
Case 1: 7.0000
Case 2: 14.0000
Case 3: 19.7383
5
94 21 12
23 9 8
5 4 3
2 2 1
43 26 20
Case 1: 32.1226
Case 2: 10.0439
Case 3: 5.0440
Case 4: 3.0000
Case 5: 32.4231

Код программы

Решение

Для лучшего понимания решения данной задачи, я построил к ней чертеж, который вы можете видеть сверху. Но прежде чем приступить непосредственно к объяснению решения, я хотел бы обратить внимание на то, что мой рисунок (даже без дополнительных построений) немного отличается от данного нам в условии. Эти различия преднамеренны и метод решения справедлив для обоих рисунков.

В $10$ строке введем число $N$ из входного потока, а в $12$ — запустим цикл, который будет работать $N$ раз. Далее за каждый проход цикла будем читать по $3$ следующих числа из входного потока и выводить на экран номер текущего теста. Перед тем, как идти дальше, разберемся в рисунке. Так как по условию отрезок $EF$ делит сегмент $AFB$ пополам, то по свойствам хорд и дуг окружности, он является частью радиуса $r$ нашей окружности с центром в точке $O$ и перпендикулярен хорде $AB$, что и показано на чертеже. Кроме того, я дорисовал радиусы $OA$ и $OB$ окружности к соответствующим точкам и начертил отрезок $BH$, как продолжение $AB$, от точки $B$ до прямой $MN$. Также, я построил прямоугольный треугольник $\triangle OGB$, в котором катет $OG = r-BD$.
Достроив все необходимые отрезки, легко заметить, что мы имеем прямоугольный треугольник $\triangle ACH$ с катетом $AC$, длину которого нам и нужно найти по условию задачи. Предлагаю сделать это, воспользовавшись формулой $AC = AH \cdot \sin(\angle AHC)$. Найдем значения сомножителей.

Из рисунка очевидно, что $\angle AHC = \angle BHD = \angle EBG = \angle OBG-\angle OBE.$
Сначала найдем $\angle OBG$. Для этого рассмотрим треугольник $\triangle OGB$. Длины его гипотенузы и противолежащего к искомому углу катета нам уже известны, так что можем сразу найти $\angle OBG = \arcsin \frac{OG}{OB}$.
Теперь найдем $\angle OBE$. Рассмотрим прямоугольный треугольник $\triangle OEB$. В нем противолежащий искомому углу катет $OE = r-d$, а гипотенуза $OB = r$. Значит, $\angle OBE = \arcsin \frac{OE}{OB}$.
В итоге остаётся только найти разницу этих углов, которая и будет являться величиной искомого $\angle AHC$. В коде же значение этого угла считается в $17$ строке и присваивается переменной $a$.

Стоит заметить, что если $\angle OBG-\angle OBE = 0$, то длины отрезков $AC$ и $BD$, очевидно, совпадают. В таком случае можем сразу вывести на экран $h_2 = h_1$, как мы и поступили в $19$ строке, и перейти к нахождению $AC$ уже для следующего тестового случая.

Если же величина $\angle AHC$ отлична от $0$, то нам все еще предстоит посчитать длину гипотенузы $AH$ треугольника $\triangle ACH$. Она состоит из хорды $AB$ и отрезка $BH$.
Сперва найдем длину хорды. Известно, что $OF$ делит ее на $2$ одинаковых по длине отрезка, значит, следует опять рассмотреть треугольник $\triangle OEB$. Длину его гипотенузы и одного из катетов мы уже находили, так что просто применим теорему Пифагора и найдем $EB = \sqrt{OB^2-OE^2}$. Тогда $AB = 2 \cdot EB$.
Для нахождения длины $BH$, рассмотрим треугольник $\triangle BDH$, в котором этот отрезок является гипотенузой. Длину катета $BD$ и величину угла $\angle BHD$ мы уже знаем, значит, можем применить формулу $BH = \frac{BD}{\sin(\angle BHD)}$.
Сложим найденные значения длин хорды $AB$ и отрезка $BH$, чтобы получить $AH$. В коде эта длина находится в $17$ строке и присваивается переменной $b$.

Теперь остается только подставить найденные значения в ранее приведенную формулу и получить наконец длину $h_2$, которую выведем на экран в $23$ строке.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++

e-olymp 480. Возведение в степень — 2

Задача

Для заданных $A$, $B$ и $M$ вычислить $A^B \mod M$.

Входные данные

Во входном файле даны три натуральных числа $A$, $B$, $M$ $(1 ≤ A, \, B ≤ 10^{18}, \, 2 ≤ M ≤ 2 \cdot 10^9)$, записанные в одной строке через пробел.

Выходные данные

В выходной файл выведите одно число, равное $A^B \mod M$.

Тесты

Входные данные Выходные данные
$531$ $348$ $1645$ $911$
$1784353$ $453345$ $463973$ $214457$
$39252362$ $345673$ $786536$ $302328$
$68790234$ $679643$ $789057$ $281232$
$324$ $8564$ $45074547$ $32984424$

Код программы

Решение задачи

По свойствам операций со сравнениями по модулю:
$$C \equiv C \mod K \pmod K$$
$$CD \equiv (C \mod K) \cdot (D \mod K) \pmod K$$
$$C \equiv D \pmod K \Rightarrow C^n \equiv D^n \pmod K$$
Отсюда выводим рекуррентную формулу бинарного возведения в степень по модулю:
$$
A^B \mod M =
\begin{cases}
1 \text{ при } B = 0\\\
\left ( \left (A \mod M \right ) \left ( (A \mod M)^{B-1} \mod M \right )\right )\mod M \\\\ \text{ при } B \equiv 1 \pmod 2\\\
\left ( \left (A \mod M \right)^2 \right)^{\frac{B}{2}} \mod M \text{ при } B \equiv 0 \pmod 2 \wedge B \neq 0
\end{cases}
$$

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olimp 197. Отрезок и окружности

Задача

На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны $1,2,3\dots.$ Также на плоскости задан отрезок, концы которого находятся в точках $(X_{1}, Y_{1})$ и $(X_{2}, Y_{2}).$ Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

Входные данные

Первая строка входного файла содержит 4 целых числа $X_{1}, Y_{1}, X_{2}, Y_{2}.$ Эти числа не превосходят $10^{3}$ по абсолютной величине. Заданный отрезок имеет ненулевую длину.

Выходные данные

В выходной файл выведите ответ на задачу.

Тесты

Входные данные Выходные данные
-1 -1 1 1 2
-1 1 1 1 1
1 1 2 1 1
-5 -5 5 -5 5
-10 10 -10 10 28

Код программы

Решение

Для начала рассмотрим первое условие. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до начала координат возрастает. Для такого отрезка ответ очевиден — это количество целых чисел между расстояниями от начала координат до обоих концов отрезка. Условие из шестнадцатой строчки кода получилось путем приведения подобных и раскрытия скобок следующих неравенств: $x_{1}^{2}+y_{1}^{2}-x_{2}^{2}-y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0$ и $-x_{1}^{2}-y_{1}^{2}+x_{2}^{2}+y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0.$

Иначе сведем данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к $(0,0)$ точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.

Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее. Также мы добавляем маленькую константу
$\varepsilon = 10^{-8}$ к большему расстоянию до конца отрезка и отнимаем из меньшего, чтобы избежать случая нахождения какой-либо точки отрезка на окружности. В противном случае решение задачи будет работать не корректно.

Ссылки

Условие задачи на e-olymp
Код решения

e-olimp 146. Квадраты — 2

Задача

В белом квадрате $N$ раз выполнили одну и ту же операцию: один из наименьших белых квадратов разбили на 4 одинаковых квадрата и 2 из них закрасили черным цветом. Для данного $N$ вычислить, сколько процентов занимает площадь черной фигуры.

Входные данные

Во входном файле одно число $N.$ $1\leq N\leq 100.$

Выходные данные

В выходной файл нужно записать ответ, вычисленный с точностью 5 знаков после запятой по правилам математических округлений.

Тесты

Входные данные Выходные данные
1 50.00000
3 65.62500
10 66.66660
50 66.66667

Код программы

Решение

При $N=1$ площадь черной фигуры составляет $50\%$. При $N=2$ площадь фигуры равна $50\% + 50\% \cdot \frac{1}{4}$. При $N=3$ площадь черной фигуры составляет $50\% + 50\% \cdot \frac{1}{4}+50\% \cdot \frac{1}{16}$. Очевидно, что перед нами геометрическая прогрессия. Процент, занимаемый площадью черной фигуры, будем искать через сумму геометрической прогресcии: $S_{n}=\frac{b_{1}(1-q^{N})}{1-q}$, где ,$q=\frac{b_{2}}{b_{1}}=\frac{12.5}{50}=0.25,$ $N-$ кол-во операций.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 2364. Часы

Задача

Ослик Иа-Иа и часы

Ослик Иа-Иа и часы

На очередной день рождения ослику Иа-Иа подарили наручные стрелочные часы. Теперь у него появилось новое развлечение — смотреть на бег стрелок. На то, как минутная догоняет часовую, обходит и тут же продолжает бежать за ней. Вот и в этот раз Кенга застала ослика за этим занятием. Она присоединилась к наблюдением и через некоторое время ей стало интересно, сколько уже моментов, когда минутная стрелка обгоняет часовую, видел Иа-Иа. Для этого она спросила у ослика во сколько он начал смотреть на часы, записала это и текущее время и побежала к Сове с этим вопросом. Но Сова оказалось очень занята и поэтому попросила вас помочь. Как известно, за один день часовая стрелка делает два оборота, а минутная целых [latex]24[/latex]. Continue reading

e-olymp 542. Поставка содовой воды

Задача

Тим ужасно любит содовую воду, иногда он ею никак не может напиться. Еще более досадным является тот факт, что у него постоянно нет денег. Поэтому единственным легальным способом их получения является продажа пустых бутылок из-под соды. Иногда в добавок к его лично выпитым бутылкам добавляются те, которые Тим иногда находит на улице. Однажды Тима настолько замучила жажда, что он решил пить до тех пор пока мог себе это позволить.

Входные данные

Три целых неотрицательных числа $e$, $f$, $c$, где $e$ $\left(e < 1000\right)$ — количество пустых бутылок, имеющихся у Тима в начале дня, $f$ $\left(f < 1000\right)$ — количество пустых бутылок, найденных в течение дня, и $c$ $\left(1 < c < 2000\right)$ — количество пустых бутылок, необходимых для покупки новой бутылки.

Выходные данные

Сколько бутылок содовой воды смог выпить Тим, когда его замучила жажда?

Тесты

Входные данные Выходные данные
[latex]9[/latex] [latex]0[/latex] [latex]3[/latex] [latex]4[/latex]
[latex]5[/latex] [latex]5[/latex] [latex]2[/latex] [latex]9[/latex]
[latex]0[/latex] [latex]8[/latex] [latex]4[/latex] [latex]2[/latex]
[latex]22[/latex] [latex]0[/latex] [latex]4[/latex] [latex]7[/latex]

Код программы

Решение

Можно считать, что изначально у Тима имеется $e+f$ пустых бутылок. Допустим, у него есть хотя бы $c$ бутылок, необходимых для покупки новой, Тим идет и меняет их на одну полную бутылку. Затем выпивает её, после чего общее количество пустых у него уменьшается на $c — 1$. То есть за $e + f$ пустых бутылок он сможет выпить $\frac{e + f}{c — 1}$ бутылок содовой воды. Нам также следует добавить к $c — 1$ маленькую константу $a = 0.0001$, чтобы в случае, когда количество бутылок кратно $c — 1$, Тиму нельзя было взять новую бутылку с недостающим количеством пустых бутылок для этого. Следовательно, он должен выпить на одну бутылку меньше. В результате выводим целое число бутылок содовой воды, которые Тим смог выпить, когда его замучила жажда.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 61. Уборка снега

Задача

Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?

При этом известно, что:

  • Снегоход может очищать только одну проезжую полосу дороги за один проход.
  • Все дороги прямые с одной полосой движения в каждом направлении.
  • Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
  • Во время очистки снега снегоход двигается со скоростью 20 км/час, и со скоростью 50 км/час по уже очищенной дороге.
  • Возможность проехать все дороги всегда существует.

Входные данные

Первая строка содержит два числа $x$ и $y$ ($-30000 \leq x, y \leq 30000$) — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.

Выходные данные

Время в часах и минутах, необходимое для очистки всех дорог и возврата в ангар. Время следует округлить до ближайшей минуты

Тесты

Входные данные Выходные данные
$0$ $0$
$0$ $0$ $-1000$ $2000$
$0$ $0$ $1000$ $2000$
$0:27$
$0$ $1000$
$0$ $0$ $0$ $3000$
$0$ $0$ $1000$ $1000$
$0$ $0$ $3000$ $0$
$3000$ $0$ $3000$ $3000$
$3000$ $3000$ $0$ $3000$
$0$ $3000$ $1000$ $2000$
$3000$ $0$ $2000$ $1000$
$3000$ $3000$ $2000$ $2000$
$1:46$
$-500$ $0$
$-1000$ $0$ $0$ $0$
$0$ $0$ $1000$ $0$
$-1000$ $1000$ $0$ $0$
$-1000$ $1000$ $0$ $2000$
$0$ $2000$ $1000$ $1000$
$1000$ $1000$ $0$ $1000$
$0$ $1000$ $0$ $0$
$0:49$
$1000$ $500$
$-1000$ $0$ $1000$ $0$
$-1000$ $1000$ $1000$ $1000$
$-1000$ $0$ $-1000$ $1000$
$1000$ $0$ $1000$ $1000$
$-1000$ $0$ $1000$ $1000$
$1000$ $0$ $-1000$ $1000$
$-1000$ $1000$ $0$ $2000$
$0$ $2000$ $1000$ $1000$
$1:20$
$500$ $-500$
$0$ $0$ $1000$ $-1000$
$1000$ $-1000$ $2000$ $0$
$2000$ $0$ $3000$ $-1000$
$3000$ $-1000$ $4000$ $0$
$4000$ $0$ $5000$ $-1000$
$5000$ $-1000$ $6000$ $0$
$0$ $0$ $8000$ $0$
$1:39$

Код программы

Решение задачи

Пусть граф $G = \left \langle V, U \right \rangle$ — граф, ребра которого — указанные в задаче дороги, а вершины — перекрестки. Граф $G$ — ориентированный, при чем, в силу того, что все дороги имеют двустороннее движение, из того, что $\left ( v_i, v_j \right ) \in U$ следует, что $\left ( v_j, v_i \right ) \in U.$ Из этого следует, что полустепень захода каждой вершины равна ее полустепени исхода, из чего, по критерию существования Эйлерова цикла, граф $G$ содержит Эйлеров цикл, т.е. существует путь, такой, что снегоход сможет очистить все дороги, пройдя по каждой ровно один раз в каждую сторону, следовательно длина такого пути будет равна удвоенной длине дорог. Снегоход всегда двигается со скоростью $V = 20 \text{км/час} = \frac{1000}{3} \text{м/мин}.$ По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах: $t = \frac{2L}{V} = \frac{3L}{500},$ где $L$ — длина всех дорог.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.

Ссылки

Условие задачи на e-olymp

Решение задачи на e-olymp

Код решения