Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Маршрут кладоискателя#50577

Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M (1 \le N, M \le 100, N \times M \le 100))\), в одной клетке которого находится клад, в K
клетках находятся входы в лабиринт).

Требуется вывести искомый путь.

Формат входных данных
Первая строка содержит 2 числа N<=100 и M<=100, задающие размеры лабиринта. Далее следует описание лабиринта: N
строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В (N+2)-й строке находится число \(K (1 \le K \le N \times M)\) - количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа \(x_i\) и \(y_i\), означающие, что i-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце \((1 \le x_i \le N, 1\le y_i \le M)\). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

Формат выходных данных
В первой строке вывести одно число - длину кратчайшего маршрута. В следующих строках необходимо вывести кратчайший маршрут. Каждую клетку маршрута (включая начальную и конечную) вывести на отдельной строке в формате \(x_i\) \(y_i\), где \(x_i\) - строка клетки, а \(y_i\) - столбец клетки.

Если существует несколько путей минимальной длины, выведите любой. Если до сокровища невозможно добраться, в единственной строке выведите -1.

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	4 1 1 2 1 2 2 3 2 3 3
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

Алгоритм Флойда Обход в ширину

✓ 5✗ 21 100средняяВойти и решать

Транзитный путь#38585

Вам дано дерево с N вершинами. Здесь дерево - это разновидность графа, а точнее, связный неориентированный граф с N−1 ребром, где N - количество его вершин. I-е ребро (\(1<=i<=N-1\)) соединяет вершины a_i и b_i и имеет длину c_i.
Вам также дано Q запросов и целое число K. Для каждого j-го запроса (\(1<=j<=Q\)) найдите длину кратчайшего пути от вершины x_j к вершине y_j через вершину K.

Входные данные
В первой строке записано целое число N (\(3<=N<=10^5\)). В следующих N строках записаны вершины a_i и b_i (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\)) и длина между ними c_i(\(1<=c_i<=10^9\), \(1<=i<=N-1\))
Далее идут два числа Q и K (\(1<=Q<=10^5\), \(1<=K<=N\)). В последних Q строках записаны целые числа x_j, y_j(\(x_j \neq y_j\),\(x_j \neq K\), \(y_j \neq K\) \(1<=j<=Q\), ).
Заданный граф является деревом.

Выходные данные
Выведите ответы на запросы в Q строках. В j-й строке выведите ответ на j-й запрос.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1 2 1 1 3 1 2 4 1 3 5 1 3 1 2 4 2 3 4 5	3 2 4	Кратчайшие пути для трех запросов следующие: Запрос 1: Вершина 2 → Вершина 1 → Вершина 2 → Вершина 4: Длина 1 + 1 + 1 = 3 Запрос 2: Вершина 2 → Вершина 1 → Вершина 3: Длина 1 + 1 = 2 Запрос 3: Вершина 4 → Вершина 2 → Вершина 1 → Вершина 3 → Вершина 5: Длина 1 + 1 + 1 + 1 = 4
2	7 1 2 1 1 3 3 1 4 5 1 5 7 1 6 9 1 7 11 3 2 1 3 4 5 6 7	5 14 22	Путь для каждого запроса должен проходить через вершину K = 2.
3	10 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 1 1 9 10	17000000000

Алгоритмы на графах Кратчайшие пути в графе Обход в ширину

✓ 7✗ 31 000средняяВойти и решать

Мишина машина (В', В)#23371

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

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

Он начинает путь в любом из городов страны и затем путешествует по дорогам между городами. По каждой дороге Миша может проехать сколько угодно раз но ему платят за посещение любой ямы только один раз.

Помогите Мише найти самый выгодный маршрут.

Формат входных данных

В первой строке содержатся два целых числа n и m количество городов и дорог соединяющих города в стране соответственно (1 <= n <= 10⁵, 0<= m <= 10⁵)

В следующих m строках содержится по три целых числа, разделенных пробелами номера, - городов, соединенных очередной дорогой и количество ям на этой дороге соответственно. Количество ям на каждой дороге неотрицательное число не превосходящее 10⁶.

Гарантируется, что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов. Вершины нумеруются с единицы.

Формат выходных данных

Выведите одно число максимальное количество монет которое Миша сможет получить.

Ввод	Вывод
4 4 1 2 1 2 3 1 1 4 1 4 3 0	3
4 2 1 3 5 2 4 4	5

Замечание

Все дороги двусторонние; проехав в любую сторону по дороге, Миша посещает все ямы на этой дороге. Обратите внимание, что между некоторыми парами городов может не существовать пути по имеющимся дорогам.

Кратчайшие пути в графе Обход в ширину Способы задания графа

✓ 22✗ 49900средняяВойти и решать

66169#66169

Одна очень известная компания Я&Ко захотела создать сеть доставок из ресторанов и кафе по всему городу, притом доставку производили бы мини-поезда. Главной проблемой стала логистика – как добраться из точки отправления в точку назначения самым быстрым способом. Но так как мини-поезда представляли собой только прототип, то в них был очень плохо проработан аккумулятор, что заставило компанию подумать про эту проблему тщательнее.
Я&Ко решили проложить рельсы между всеми точками доставки и по некоторым рельсам пустить зарядку, чтобы мини-поезда могли ехать и заряжаться. Компания решила устроить среди всех программистов, кто сможет решить их задачу, соревнование. Далее выбрать победителя, но как, пока неизвестно.
Задача состоит в следующем – есть известная карта маршрутов в городе, которая представлена в виде направленного взвешенного графа с возможными циклами. На каждом ребре графа даны значения времени перемещения между связанными вершинами и заряжает рельс или нет на этом маршруте.
За 1 минуту по рельсам зарядки мини-поезд заряжается на 10%. Если он зарядился, но всё ещё в пути на зарядных рельсах, то его заряд составляет 100%.
Для простоты расчёта количество минут мини-поезда после съезда с рельсов округляется вверх к ближайшему целому (например, поезд максимально может проехать 30 минут, что означает его 100% заряда, на рельс он заехал, когда у него осталось заряда на 10 минут, пусть время в пути по рельсу составило 4 минуты, значит зарядился он на 40%, что составляет 12 минут, потому после съезда с зарядного рельса у него останется запас хода на 10 + 12 = 22 минуты.
Задача – найти минимальное время, за которое мини-поезд сможет доехать до клиента со стартовой точки, если точно известно, что он это сделать сможет.

Входные данные
на первой строке подаются два целых числа (1 <= N,M <= 1000), где N – количество вершин графа, M - количество рёбер.
на второй строке подаётся целое число T (1 <= T <= 100), где T – время, которое может проехать полностью заряженный мини-поезд;
на третьей строке подаются через пробел два целых числа – номер стартовой вершины и номер конечной вершины;
далее на M строках подаются рёбра графа через пробел с указанием зарядный рельс на данном пути или нет (0 – не зарядный, 1 – зарядный) (<откуда> <куда> <время в пути> <признак зарядного рельса>).
Выходные данные
выведите на первой строке количество минут, которое понадобится мини-поезду, чтобы полностью доехать до клиента (конечной точки) в виде одного целого числа.

Примечание
•робот изначально заряжен на 100%.

Алгоритм Дейкстры

✓ 1✗ 51 000средняяВойти и решать

Нечестная игра#50448

На клетчатой доске размером \(n \times m\), состоящей из \(n\) строк и \(m\) столбцов, в клетке \((r, c)\), то есть на пересечении \(r\)-й сверху строки и \(c\)-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.

Каждый ход устроен следующим образом.

Компьютер называет целое число \(k > 0\).
Вы ровно \(k\) раз некоторым образом выбираете одну из еще не удаленных клеток, соседних по стороне (имеющих общую сторону) с той, в которой фишка находится в текущий момент, и перемещаете фишку в эту клетку. Вы можете перемещать фишку на клетку, в которой она уже была. Если не существует еще не удаленных клеток, соседних по стороне с текущей, перемещение не производится.
Компьютер называет координаты \((i, j)\) произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.

Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки \((i, j)\) существует последовательность перемещений фишки, при которой в данный момент фишка находится в точности в клетке \((i, j)\), вы можете сообщить компьютеру, что игра завершена, и вы победили.

Разумеется, компьютер следит за соблюдением правил, поэтому если вы сообщаете ему о своей победе при удалении клетки, на которой фишка не могла в этот момент находиться, вы автоматически проигрываете.

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

Формат входных данных
В единственной строке ввода даны четыре целых числа \(n\), \(m\), \(r\) и \(c\) — размеры доски и координаты изначального расположения фишки (\(1 \le r \le n \le 1000\); \(1 \le c \le m \le 1000\)).

Во второй строке ввода дано максимальное количество баллов, которое можно получить за соответствующую группу тестов. Ваше решение это значение может игнорировать.

В следующих \(n \cdot m\) строках даны ходы, которые последовательно собирается сделать компьютер. Описание \(t\)-го хода задается тремя целыми числами \(k_t\), \(i_t\) и \(j_t\) — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить (\(1 \le k_t \le 10^9\); \(1 \le i_t \le n\); \(1 \le j_t \le m\)).

Гарантируется, что все удаляемые клетки различны, то есть никакая клетка не удаляется дважды.

Формат выходных данных
Выведите одно целое число от \(1\) до \(n \cdot m\) — номер хода, после которого вы сообщите компьютеру о своей победе.

Замечание

В первом примере можно, например, первым ходом передвинуть фишку из \((1, 1)\) в \((1, 2)\), а вторым — из \((1, 2)\) в \((2, 2)\) и затем в \((2, 1)\), тем самым поместив ее на удаляемую клетку.

графы Задачи на моделирование Обход в ширину

✓ 4✗ 291 000средняяВойти и решать

Количество кратчайших путей#49684

В Сильвертауне есть N районов с номерами от 1 до N и M дорог с номерами от 1 до M. Используя дорогу i, вы можете добраться из района A_i в район B_i или наоборот за один час.
Сколько существует путей, по которым можно добраться из района 1 в район N как можно быстрее?
Поскольку число может быть огромным, выведите его по модулю 10⁹+7

Формат входных данных
Первая строка содержит два целых числа N и M. Далее идет M строк, в каждой из которых записано по 2 числа: A_i и B_i.

Ограничения

2 ≤ N ≤ 2×10⁵
0 ≤ M ≤ 2×10⁵
1 ≤ Ai < Bi ≤ N
Пары (Ai,Bi) уникальны.
Все значения во входных данных целые числа.

Формат выходных данных
Выведите ответ на задачу.

Обход в ширину

✓ 57✗ 155900средняяВойти и решать

Найти Дэйва#38831

Беззработный Дэйв от скуки соорудил в собственной гостиной лабиринт из картонных коробок. Лабиринт содержит K входов. Когда его подружка Энни вернулась, лабиринт невероятным образом разросся изнутри, а сам горе-изобретатель там заблудился и не может выбраться.
Единственное, что нашла Энни в комнате это карту лабиринта, который имеет размеры NхM клеток. На карте было обозначено место, в котором находится Дэйв (как так вышло никто не знает). Клетки лабиринта либо пустые, по которым можно пройти, либо в них находится стена и по ним проходить нельзя. У клетки может быть до 4-х смежных клеток, в которую можно пройти из текущей.
Энни пригласила вас помочь ей определить, с какого входа нужно начать свой путь, чтобы побыстрее дойти до Дейва. Если таких входов несколько, Энни пойдет со входа с наименьшим номером.

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

Программа получает на вход несколько строк. В первой строке - 2 числа N и M (1<= N, M <= 100, NxM <= 100), размеры лабиринта. Далее следует N строк по M символов в каждой - описание лабиринта. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с Дэйвом.
В (N+2)-й строке находится число K (1<=K<=NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. В i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1<=xi<=N,1<=yi<=M).
Координаты входов попарно различны, все входы расположены в пустых клетках. Ни один из входов не находится в клетке с Дэйвом.

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

Выведите одно число - номер входа (нумерация начинается с 1). Если до Дэйва невозможно добраться, выведите -1.

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	1
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

Обход в ширину

✓ 13✗ 291 000средняяВойти и решать

Удаление клеток#38830

Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

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

В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.

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

Вывести одно число.

Примеры

№	Входные данные	Выходные данные
1	5 10 ##..#####. .#.#.#.... ###..##.#. ..##.....# .###.#####	5

Обход в глубину Обход в ширину

✓ 62✗ 170800средняяВойти и решать

Метро Давилона#38655

Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из N станций и M железнодорожных линий. Станции пронумерованы от 1 до N. Каждой линией управляет компания. У каждой компании есть идентификационный номер. I-я (1<=i<=M) линия соединяет станцию pi и qi двунаправленно. Промежуточной станции нет. Этой линией управляет компания ci . Можно делать пересадки на станции, где доступно несколько линий. Система оплаты проезда, используемая в этой системе метро, немного странная. Когда пассажир использует только те линии, которые обслуживаются одной и той же компанией, тариф составляет 1 сантик (валюта Давилона). Каждый раз, когда пассажир переходит на линию, которой управляет компания, отличная от текущей линии, с пассажира взимается дополнительная плата за проезд в размере 1 сантик. В случае, если пассажир, перешедший с линии компании А на линию другой компании, снова переходит на линию компании А, дополнительный тариф взимается снова. Незнайка сейчас на станции 1 и хочет добраться до станции N на метро. Найдите минимально необходимый тариф.

Входные данные
В первой строке задается два целых числа N (2<=N<=10⁵) и M (0<=M<=2*10⁵). В каждой из следующих M строк записаны по 3 числа: pi, qi и ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10⁶, pi ≠ qi.

Выходные данные
Выведите минимальный требуемый тариф. Если добраться до станции N на метро невозможно, выведите -1.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 2 1 2 3 1 3 1 2	1	Используйте линии компании 1: 1 → 2 → 3. Стоимость проезда 1 сантик.
2	8 11 1 3 1 1 4 2 2 3 1 2 5 1 3 4 3 3 6 3 3 7 3 4 8 4 5 6 1 6 7 5 7 8 5	2	Сначала используйте линии компании 1: 1 → 3 → 2 → 5 → 6. Затем используйте линии компании 5: 6 → 7 → 8. Стоимость проезда 2 сантика.
3	2 0	-1

Алгоритмы на графах Кратчайшие пути в графе

✓ 5✗ 651 000средняяВойти и решать

Два коня#38628

На стандартной шахматной доске (8х8) живут 2 шахматных коня: Красный и Зеленый. Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день: у Зеленого коня День Рождения. Зеленый конь решил отпраздновать это событие вместе с Красным. Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке. Заметим, что Красный и Зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы насладиться праздником?

Входные данные
На вход программы поступают координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами - маленькая латинская буква (от a до h) и цифра (от 1 до 8), задающие столбец и строку соответственно).

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

Примеры

№	Входные данные	Выходные данные
1	a1 a3	1

Обход в ширину

✓ 90✗ 110800средняяВойти и решать

Табличка#38625

Дана таблица, состоящая из N строк и M столбцов. В каждой клетке таблицы записано одно из чисел: 0 или 1. Расстоянием между клетками (x₁, y₁) и (x₂, y₂) назовем сумму |x1-x2|+|y1-y2|. Вам необходимо построить таблицу, в клетке (i, j) которой будет записано минимальное расстояние между клеткой (i, j) начальной таблицы и клеткой, в которой записана 1. Гарантируется, что хотя бы одна 1 в таблице есть.

Формат входных данных
В первой строке вводятся два натуральных числа N и M, не превосходящих 500. Далее идут N строк по M чисел - элементы таблицы.

Формат выходных данных
Требуется вывести N строк по M чисел - элементы искомой таблицы.

Обход в ширину

✓ 65✗ 67800средняяВойти и решать

Квас#38313

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

Планируется построить всего один завод в каком-нибудь городе, и развозить продукцию по остальным городам. Перевозка одной бочки в соседний город стоит один тугрик (местная валюта).

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

Входные данные
Первая строка входных данных содержит число N – количество городов ( N ≤ 10) и еще N чисел – количество кваса, требуемое ежедневно 1-м, 2-м, …, N -м городом (города нумеруются подряд вдоль кольцевой дороги).

Выходные данные
Выведите одно число – номер города, в котором следует построить завод. Если подходящих городов окажется несколько – выведите номер любого из них.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 5 3 10	3
2	6 4 4 1 5 1 3	2	На острове 6 городов, потребность каждого города указана в кружочках, номер города рядом с кружочком. Если построить завод во 2-м городе (он выделен серым), то потребуется заплатить 4 + 1 (стоимость перевозки в 1-й и 3-й города) + 52 + 32 (в 4-й и 6-й) + 13 (в 5-й см. рисунок). Во 2-й вообще ничего не везем. Это будет 24 тугрика. Легко проверить, что если построить завод в других городах, сумма будет больше. Например, если построить в 4-м городе, то сумма составит 1 + 1 + 32 + 42 + 43 = 28 тугриков.

Обход в ширину Перебор

✓ 59✗ 108900средняяВойти и решать

Нью-Кэпитал#38273

В стране из предыдущей задачи много специалистов не только по защите детей, но и про проектированию городов. Поэтому, чтобы решить проблему пробок в перенаселенной столице раз и навсегда, было решено построить новую столицу и перенести все правительство туда. Сказано — сделано.

Улицы в новой столице образуют правильную прямоугольную сетку, в которой все улицы пересекаются ровно через одну местную единицу длины. Вертикально идущие улицы называются улицами, а горизонтально идущие — аллеями. Всего в городе получилось 2000 улиц и 2000 аллей, поэтому, чтобы не придумывать много новых названий, их все просто пронумеровали. Улицы пронумеровали с запада на восток числами от −1000 до 999, а аллеи — с юга на север, тоже числами от −1000 до 999. Центром города считаются кварталы на пересечении улиц и аллей с номерами от −100 до 100.

Чтобы увеличить пропускную способность дорог в городе, было решено сделать все улицы и аллеи односторонними. По улицам с четными номерами разрешается ехать только с севера на юг, а по улицам с нечетными номерами — только с юга на север. Аналогично, по аллеям с четными номерами можно ехать только с востока на запад, а с нечетными — только с запада на восток.

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

Входные данные
В первой строке даны два числа x1 и y1 — номер улицы и номер аллеи, на пересечении которых находится мэрия. В второй строке даны два числа x2 и y2 — номер улицы и номер аллеи, на пересечении которых находится дом мэра. Все числа целые и не превосходят по модулю 100.

Выходные данные
Выведите одно число: длину кратчайшего пути от мэрии до дома мэра на автомобиле.-

Примеры

№	Входные данные	Выходные данные
1	0 0 1 1	4
2	3 5 2 4	4

Обход в ширину Разбор случаев

✓ 30✗ 901 000средняяВойти и решать

Преобразуем четырехзначные#37016

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

1. Можно увеличить первую цифру числа на 1, если она не равна 9.
2. Можно уменьшить последнюю цифру на 1, если она не равна 1.
3. Можно циклически сдвинуть все цифры на одну вправо.
4. Можно циклически сдвинуть все цифры на одну влево.

Например, применяя эти правила к числу 1234 можно получить числа 2234, 1233, 4123 и 2341 соответственно. Точные правила игры Витя пока не придумал, но пока его интересует вопрос, как получить из одного числа другое за минимальное количество операций.

Входные данные: на вход подаются два различных четырехзначных числа, каждое из которых не содержит нулей. Каждое число с новой строки

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

Примеры

№	Входные данные	Выходные данные
1	1234 4321	1234 2234 3234 4323 4322 4321

Обход в ширину

✓ 80✗ 109800средняяВойти и решать

Эвакуация#34976

Одна из Сверхсекретных организаций, чье название мы не имеем право разглашать, представляет собой сеть из N подземных бункеров, соединенных равными по длине туннелями, по которым из любого бункера можно добраться до любого другого (не обязательно напрямую). Связь с внешним миром осуществляется через специальные засекреченные выходы, которые расположены в некоторых из бункеров.

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

Формат входных данных
В первых двух строках вводятся два натуральных числа N, K (\(1 <= N <= 100000\), \(1 <= K <= N\)) — количество бункеров и количество выходов соответственно. В третьей строке через пробел записаны K различных чисел от 1 до N, обозначающих номера бункеров, в которых расположены выходы. В четвертой строке идёт число M (\(1 <= M <= 100000\)) — количество туннелей. В следующих M строках вводятся пары чисел – номера бункеров, соединенных туннелем.
По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

Формат выходных данных
Выведите N чисел, разделенных пробелом — для каждого из бункеров минимальное время, необходимое чтобы добраться до выхода. Считайте, что время перемещения по одному туннелю равно 1.

Обход в ширину

✓ 273✗ 691800средняяВойти и решать

0-1 BFS: Начало (C++)#33468

По заданному изображению неориентированного графа (имеет ребра весом 0 и 1), выведите список кратчайших расстояний от вершины 0 до всех остальных.

Входные данные
Дано изображение неориентированного графа с ребрами 0 и 1.

Выходные данные
В ответе выведите список кратчайших путей от вершины 0.

0-1 BFS

✓ 60✗ 35800средняяВойти и решать

Кратчайший путь (AB)#33466

Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.

Формат входных данных
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа N и K (1<=N<=100000, 0<=K<=300000), где K – количество дорог. Каждая из следующих K строк содержит описание дороги с двусторонним движением – три целых числа ai, bi и li (1aibiN, 1li106). Это означает, что имеется дорога длины li, которая ведет из города ai в город bi. В последней строке находятся два числа А и В – номера городов, между которыми надо посчитать кратчайшее расстояние (1<=A,B<=N )

Формат выходных данных
Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города А до города В доехать невозможно, выведите –1.

Алгоритм Дейкстры

✓ 92✗ 888900средняяВойти и решать

Файловый менеджер#33310

Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер Fur Manager, который отображает список имен файлов проекта в некотором порядке.

В текущей версии Fur Manager’a для перемещения по списку имен файлов есть следующие возможности:

можно нажать клавишу вниз, при этом курсор перемещается на следующий файл в списке, для последнего файла следующим считается первый;

можно нажать клавишу вверх, при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний;

можно нажать клавишу Alt и, удерживая ее, набрать последовательность латинских букв. После этого клавишу Alt следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается c заданной последовательности символов. Ближайший файл — это файл, на который можно переместиться за наименьшее количество нажатий клавиши вниз. Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор останется на месте.

Первая и вторая из описанных возможностей файлового менеджера требуют по одному нажатию клавиши, а третья — одного нажатия (нажатие клавиши Alt) плюс количество нажатий, равное длине набранной последовательности латинских букв.

Файлы пронумерованы от 1 до N в порядке их следования. После загрузки Fur Manager’а курсор находится на первом файле.

Петя знает, что ему сначала придется редактировать файл с номером a₁, затем с номером a₂ и так далее, а последним — файл с номером a_k. В последовательности a₁, a₂, ..., a_k один и тот же номер может встречаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.

Требуется написать программу, которая выдает искомую последовательность нажатий клавиш.

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

В первой строке входных данных содержится целое число N (1 ≤ N ≤ 1000) — количество файлов в проекте.

В следующих N строках записаны имена файлов, по одному в каждой строке. Файлы перечислены в том порядке, в котором они отображаются файловым менеджером. Имена состоят только из строчных латинских букв. Длина каждого имени не превосходит 2000 символов. Все имена файлов различны.

Далее в следующей строке записано целое число k (1 ≤ k ≤ 10).

Последняя строка входных данных содержит k целых чисел a₁, a₂, ..., a_k (1 ≤ a_i ≤ N) — номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a₁, a₂, ..., a_k.

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

Выведите описание искомой последовательности нажатий клавиш в виде k блоков информации:

первый блок информации описывает перемещение от файла с номером 1 к файлу с номером a₁;

второй блок информации описывает перемещение от файла с номером a1 к файлу с номером a₂;

…

k-ый блок информации описывает перемещение от файла с номером a_k–1 к файлу с номером a_k.

Каждый блок информации выглядит следующим образом.

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

Следующие L строк блока описывают нажимаемые клавиши. Каждая из строк содержит описание одной клавиши:

если нажимается клавиша вниз, то в строке записывается слово down;

если нажимается клавиша вверх, то в строке записывается слово up;

если нажимается клавиша Alt, то в строке записывается слово Alt;

при нажатии клавиши с латинской буквой выводится соответствующая ей латинская буква.

Если существует несколько оптимальных способов перемещения, то требуется вывести любой из них.

Ввод	Вывод
6 a b c d e f 4 4 3 1 6	2 Alt d 1 up 2 Alt a 1 up

Алгоритм Дейкстры Быстрая сортировка Способы задания графа

✓ 2✗ 31 000средняяВойти и решать

33228#33228

В одной из деревень Центрального района решили построить новую школу, но никак не могут выбрать, в какой именно. Решили сделать так: подсчитать для каждой деревни суммарное расстояние, которое будут проходить все школьники Центрального района, если школа будет построена в этой деревне, и выбрать место, для которого эта сумма будет минимальной. В распоряжении администрации есть карта дорог Центрального района. Напишите программу, которая поможет выбрать место для школы. Если какой-то населенный пункт не имеет связи с другим населенным пунктом, где предполагается разместить школу, считайте, что доставка каждого ученика вертолётом "стоит" 10000 единиц расстояния.

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

В первой строке вводится количество деревень N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог: положительное число означает расстояние между деревнями, ноль говорит о том, что дороги нет. В последней строке вводится N чисел - количество школьников в каждой деревне.

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

Программа должна вывести два числа: сначала номер деревни, где нужно построить школу, а затем (через пробел) – общее расстояние, которое будут проходить все школьники Центрального района, если школа будет построена в этой деревне.

Ввод	Вывод
4 0 11 8 4 11 0 2 5 8 2 0 13 4 5 13 0 15 26 30 12	2 255

Алгоритм Флойда кратчайшие пути

✓ 11✗ 66800средняяВойти и решать

Космическое путешествие#32966

В MMORPG "Космические торговцы online" скорость перемещения игрока между звёздами ограничена одним парсеком в секунду. С такой скоростью можно быстро добраться до ближайших звёзд, но на путешествие с одного края галактики до другого может потребоваться несколько часов. Для ускорения таких долгих путешествий создатели игры сделали несколько "кротовых нор" — туннелей, соединяющих две точки в пространстве, которые позволяют мгновенно перемещаться между этими точками туда и обратно.

Напишите программу, которая вычисляет минимальное время путешествия, используя информацию о "кротовых норах".

В первой строке ввода содержится целое число N (1 ≤ N ≤ 100). Далее следует строка, содержащая 6 целых чисел — координаты начальной (x_s,y_s,z_s) и конечной (x_t,y_t,z_t) точки путешествия. Далее следует N строк, содержащих 6 целых чисел — координаты концов "кротовых нор". Все координаты измеряются в парсеках и находятся в диапазоне от 0 до 10000, и нет точек с совпадающими координатами.

Вывести минимальное время путешествия в секундах с точностью не менее 10⁻⁶.
Примеры

№	Входные данные	Выходные данные
1	1 0 0 0 100 100 0 1 1 1 50 100 10	52.722246

Алгоритм Флойда

✓ 82✗ 193900средняяВойти и решать