e-olymp 93. Truck driving

Task

Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a dedicated straight road between each pair of cities in that country. Amount of consumed fuel is the distance between two cities which is computed from their coordinates. There is a gas station in each city, so Umidsh can refuel the gas container of his truck. Your job is to compute the minimum necessary volume of gas container of Umidsh’s Truck.

Input data

The first line of input contains an integer, the number of test cases. Following, there are data for test cases. Each test case begins with a line containing one integer, $C$ $(2 ≤ C ≤ 200)$, which is the number of cities. The next $C$ lines each contain two integers $x$, $y$ $(0 ≤ x, y≤ 1000)$ representing the coordinate of one city. First city is the source city and second is the destination city of Umidsh.

Output data

There should be one line for each test case in output. Each line should contain one floating point number which is the minimum necessary volume of truck’s gas container, printed to three decimals.

Tests

Input Output
$2$
$2$
$0$ $0$
$3$ $4$
$3$
$17$ $4$
$19$ $4$
$18$ $5$
$5.000$
$1.414$
$1$
$3$
$4$ $5$
$4$ $6$
$4$ $7$
$1.000$
$2$
$4$
$0$ $1$
$0$ $-1$
$1$ $0$
$-1$ $0$
$3$
$8$ $9$
$0$ $1$
$14$ $14$
$1.414$
$11.314$
$3$
$2$
$1$ $1$
$1$ $2$
$5$
$8$ $6$
$3$ $3$
$4$ $1$
$7$ $7$
$5$ $0$
$3$
$1$ $1$
$1$ $3$
$2$ $5$
$1.000$
$5.657$
$2.000$

Code

Solution

We can interpretate the set of the cities as weighted graph, which vertices represent cities and weight of each edge between two vertices is the gas volume required for passing the distance between corresponding cities.
The volume of truck’s gas container depends on the gas volume required for arrival to the each next station of the Umidsh’s way. The maximum between gas volume required to get to the city $A$ and gas volume required to pass the way from the city $A$ to the city $B$ represents the minimum necessary gas volume required to get to the city $B$ through the city $A$. So the volume of truck’s gas container would turn to minimum, when the maximum gas volume required for passing the distance between each two stations of his way would turn to minimum. Thus we could use modified Dijkstra’s algorithm to find the biggest value among the weights of an edges between each two stations of the way between vertice 0 and vertice 1.

References

The task at E-Olymp
My solution at ideone

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». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. С помощью поиска в глубину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в глубину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае -нет.

Ссылки

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

e-olymp 1868. Функция

Условие задачи
Вычислите функцию:

[latex]f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}[/latex]

Входные данные
Одно натуральное число [latex] n \; [/latex] [latex](1 \leq n \leq 10^{12}) [/latex].

Выходные данные
Значение [latex] f(n) [/latex], взятое по модулю [latex] 2^{32} [/latex].
Continue reading

A1038. Дейкстра?

Задача: Имеется [latex]n [/latex] городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка  [latex]n [/latex], элемент [latex]a_{ij} [/latex] которой равен некоторому отрицательному числу, если город [latex]i [/latex] не соединен напрямую дорогой с городом [latex]j [/latex] и равен длине дороги в противном случае latex [/latex].

  1. Для 1-го города найти кратчайшие маршруты в остальные города.
  2. В предположении, что каждый город соединен напрямую с каждым, найти кратчайший маршрут, начинающийся в 1-м городе и проходящий через все остальные города.

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

4
-1 2 4 -1
2 -1 1 6
4 1 -1 1
-1 6 1 -1

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

1 > 2 = 2

1 > 3 = 3

1 > 4 = 4

Длина кратчайшей цепи, проходящей через все вершины 4

Ссылка на ideone: http://ideone.com/iXjoLZ

Решение:

Алгоритм: Для решения задачи применим алгоритм Дейкстры. Применяя этот алгоритм мы считаем что у нас нету ребер с отрицательным весом. Если вес ребра отрицательный, то его просто не существует (по условию задачи). Вводим матрицу смежности графа и проверяем является ли граф полным (для задания 2). Если граф является полным, то ищем для каждой вершины инцидентное ребро с минимальным весом и суммируем (задание 2). В цикле каждой вершине присваиваем минимально расстояние до нее от первой вершины и записываем в массив (задание 1).

e-olymp 1947. Конденсация графа

Условие задачи:

Для заданного ориентированного графа найти количество ребер в его конденсации.

Конденсацией орграфа G называют такой орграф G’, вершинами которого служат компоненты сильной связности G, а дуга в G’ присутствует только если существует хотя бы одно ребро между вершинами, входящими в соответствующие компоненты связности.

Конденсация графа не содержит кратных ребер.

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

Первая строка содержит два натуральных числа n и m (n10000, m100000) — количество вершин и ребер графа соответственно. Каждая из следующих m строк содержит описание ребра графа. Ребро номер i описывается двумя натуральными числами [latex]b_{i}[/latex], [latex]e_{i}[/latex](1 ≤ [latex]b_{i}[/latex], [latex]e_{i}[/latex] ≤ n) — номерами начальной и конечной вершины соответственно. В графе могут присутствовать кратные ребра и петли.

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

Количество ребер в конденсации графа.

Тесты:

Входные данные Выходные данные
4 4 2
2 1
3 2
2 3
4 3
6 9 1
1 2
2 4
4 1
4 2
3 2
2 6
3 5
5 3
6 2

Описание решения задачи:

Компонентой сильной связности называется такое подмножество вершин C, что любые две вершины этого подмножества достижимы друг из друга. Отсюда следует, что конденсация это граф, получаемый из исходного графа сжатием каждой компоненты сильной связности в одну вершину. Отсюда имеем структуру [latex]vertex[/latex]. Основным фундаментом данного алгоритма является следующая теорема: Пусть [latex]C[/latex] и [latex]{C}'[/latex] — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро ([latex]C[/latex],[latex]C'[/latex]). Тогда время выхода из [latex]C[/latex] будет больше, чем время выхода из [latex]{C}'[/latex]. Базируясь на этом, выполним серию обходов в глубину с помощью функции [latex]dfs[/latex] _ [latex]g[/latex], посещая весь граф. С визитом всех вершин графа,запоминаем для каждой время выхода, записывая это в созданный [latex]list[/latex]. Далее строится транспонированный граф. Запускаем серию обходов в глубину(функция [latex]dfs[/latex] _ [latex]tg[/latex]) этого графа в порядке, определяемом списком [latex]list[/latex] (а именно, в обратном порядке, т.е. в порядке уменьшения времени выхода). Каждое множество вершин, достигнутое в результате рекурсивного запуска обхода, и будет очередной компонентой сильной связности. Окрасим все вершины каждой сильной компоненты связности в один уникальный цвет, для этого зададим в структуре параметр [latex]colour[/latex]. Число цветов окраски будет равно количеству компонент сильной связности. Далее перебираем все ребра исходного графа. Если ребро соединяет вершины разного цвета, то оно принадлежит конденсации графа. Для каждого ребра ([latex]a[/latex], [latex]b[/latex]), для которого [latex]components[a].colour[/latex] [latex]≠[/latex] [latex]components[b].colour[/latex], занесем во множество [latex]ribs[/latex] данную пару. Количество элементов во множестве [latex]ribs[/latex] будет равняться числу ребер в конденсации графа.

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

e-olimp 4852. Кратчайшее расстояние

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]x[/latex]  [latex]\left ( 1\leq n\leq 1000,1\leq x\leq n \right )[/latex] — количество вершин в графе и стартовая вершина соответственно. Далее в [latex]n[/latex] строках по [latex]n[/latex] чисел — матрица смежности графа: в [latex]i[/latex]-ой строке на [latex]j[/latex]-ом месте стоит [latex]1[/latex], если вершины [latex]i[/latex] и [latex]j[/latex] соединены ребром, и [latex]0[/latex], если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].

Тесты 

 Входные данные  Выходные данные
3 1
0 1 0
0 0 0
0 0 0
 0 1 -1
6 5
0 1 1 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 1 1 0 0
0 1 0 0 0 0
2 2 1 1 0 -1
3 1
0 1 0
1 0 1
0 1 0
0 1 2

 

Реализация

Засчитанное решение на e-olimp.com

Код на ideone.com

Решение

Для решения данной задачи необходимо применить  алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем  вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид  [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.