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

Защищенное соединение#30707

В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании <<Laim.UR>> и <<Xenda>> решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании \(n\) городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.

Специалисты компаний определили \(m\) пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.

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

Теперь необходимо определить минимальную стоимость защищенного канала, соединяющего два дата-центра компаний.

Формат входных данных
В первой строке находятся целые числа \(n\) и \(m\) (\(2 \le n \le 5\,000\), \(1 \le m \le 10^5\)) — количество городов и количество пар городов, которые можно соединить сегментом канала связи.

Во второй строке находятся \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 2\)). Если \(a_i = 0\), то в \(i\)-м городе нет дата-центра ни одного из гигантов. Если \(a_i = 1\), то в \(i\)-м городе есть дата-центр <<Laim.UR>>, а если \(a_i = 2\), то в \(i\)-м городе находится дата-центр <<Xenda>>. Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка.

В каждой из следующих \(m\) строк находится по три целых числа — \(s_i\), \(t_i\) и \(c_i\), которые означают, что города \(s_i\) и \(t_i\) (\(1 \le s_i, t_i \le n\), \(s_i \ne t_i\)) можно соединить сегментом канала связи стоимостью \(c_i\) (\(1 \le c_i \le 10^5\)). Каждую пару городов можно соединить не более чем одним сегментом канала.

Формат выходных данных
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: \(x\), \(y\) и \(d\), означающие, что между городами \(x\) и \(y\) возможно провести канал связи суммарной стоимостью \(d\). В городе \(x\) должен находиться дата-центр <<Laim.UR>>, в городе \(y\) — дата-центр <<Xenda>>. Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите \(-1\).

В первом примере оптимально построить канал связи из двух сегментов: \(3-2\) и \(2-4\).

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

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

Заправки-2#30702

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

В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-й, потратив как можно меньшее денег.

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

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

В первой строке вводится число N (1<=N<=100), в следующей строке идет N чисел, i-е из которых задает стоимость бензина в i-м городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

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

Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

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

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

Хакер#27307

Однажды юный хакер Шалдыга Севин решил совершить дерзкое преступление - сменить имя своего друга Максима Никитина на сильвере, пока тот был в ЛКШ Зима (Ливневая Коробка Шредингера), чтобы Наталья Владимировна поставила ему двойку. Для этого Шалдыга решил заразить вирусом базу данных сильвера.

Однако юный хакер осознал одну проблему - он не знает, на каком именно компьютере лицея она хранится. Шалдыга не стал долго думать над этой проблемой и решил заразить все компьютеры в лицее (для надежности). Вирус работает так: раз в день он заражает все компьютеры, связанные с зараженными напрямую. Первый компьютер Шалдыге придется заразить лично, потому он может выбрать любой.

Хакер хочет узнать минимальное количество дней, которое понадобится для того, чтобы заразить все компьютеры лицея. Однако выяснилась еще одна проблема - эта задача легко решается с помощью БФСа, но написать его меньше чем за 15 дней невозможно, а Хакеру еще нужно сделать 200 номеров по математике. Поэтому Шалдыга попросил Вас сделать невозможное - написать программу, отвечающую на его вопрос, за время этого контеста.

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

В первой строке на вход подаются два числа N и M - количество компьютеров в лицее и соединений между ними соответственно. 1 <= N, M <= 100

В следущих M строках Вам даются описания соединений между компьютерами, а именно 2 чила U и V, которые означают, что компьютеры U и V соединены.

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

Выведите ответ на вопрос Шалдыги

Ввод	Вывод
6 9 1 2 1 3 2 4 2 6 3 4 3 5 4 5 4 6 5 6	2

(с) Григорьев Е., 2017

графы Обход в ширину

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

Рейсы во времени#27276

Между \(N\) населенными пунктами совершаются пассажирские рейсы на машинах времени.

В момент времени 0 вы находитесь в пункте \(A\). Вам дано расписание рейсов. Требуется оказаться в пункте \(B\) как можно раньше (то есть в наименьший возможный момент времени).

При этом разрешается делать пересадки с одного рейса на другой. Если вы прибываете в некоторый пункт в момент времени \(T\), то вы можете уехать из него любым рейсом, который отправляется из этого пункта в момент времени \(T\) или позднее (но не раньше).

Формат входных данных
Первая строка содержит число \(N\) — количество населенных пунктов (\(1 \le N \le 1000\)). Вторая строка содержит два числа \(A\) и \(B\) — номера начального и конечного пунктов. Третья строка содержит число \(K\) — количество рейсов (\(0 \le K \le 1000\)). Следующие \(K\) строк содержит описания рейсов, по одному на строке. Каждое описание представляет собой четверку целых чисел. Первое число каждой четверки задает номер пункта отправления, второе — время отправления, третье — пункт назначения, четвертое — время прибытия. Номера пунктов — натуральные числа из диапазона от 1 до \(N\). Пункт назначения и пункт отправления могут совпадать. Время измеряется в некоторых абсолютных единицах и задается целым числом, по модулю не превышающим \(10^9\). Поскольку рейсы совершаются на машинах времени, то время прибытия может быть как больше времени отправления, так и меньше, или равным ему.

Гарантируется, что входные данные таковы, что добраться из пункта \(A\) в пункт \(B\) всегда можно.

Формат выходных данных
Выведите минимальное время, когда вы сможете оказаться в пункте \(B\).

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

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

Авиаперелеты#27275

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

Теперь профессор хочет найти путь наименьшей стоимости, учитывая что до конференции осталось K ночей (то есть профессор может совершить не более K перелетов).

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

В первой строке находятся числа N (количество городов), M (количество авиарейсов), K (количество оставшихся ночей), S (номер города, в котором живет профессор), F (номер города, в котором проводится конференция).

Ограничения: 2≤N≤100, 1≤M≤10⁵, 1≤K≤100, 1≤S≤N, 1≤F≤N.

Далее идет M строк, задающих расписание авиарейсов. i-я строка содержит три натуральных числа: S_i, F_i и P_i, где S_i - номер города, из которого вылетает i-й рейс, F_i- номер го-рода, в который прилетает i-й рейс, P_i - стоимость перелета i-м рейсом. 1≤S_i≤N, 1≤F_i≤N, 1≤P_i≤106.

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

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

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

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

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

Лабиринт знаний#27272

В Летней Компьютерной Школе (ЛКШ) построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход – в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

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

Первая строка входных данных содержит целые числа N (1 <= N <= 2000) – количество комнат и M (1 <= M <= 10000) – количество дверей. В каждой из следующих M строк содержится описание двери – номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 2 1 2 3 1 2 7	7

Алгоритм Форда-Беллмана

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

Отрицательный цикл-2#27269

Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

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

В первой строке содержится число N (1 <= N <= 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер по модулю меньше 100000. Если ребра нет, соответствующее значение равно 100000.

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

В первой строке выведите "YES", если цикл существует, или "NO", в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковые – первую и последнюю), а в третьей строке – вершины, входящие в этот цикл, в порядке обхода. Если циклов несколько, то выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	3 100000 100000 -51 100 100000 100000 100000 -50 100000	YES 4 3 2 1 3

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

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

Pink Floyd#27233

Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.

Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

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

Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤10⁴, 2≤k≤10⁴). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами b_i, e_i и w_i - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤b_i,e_i≤n, −10⁵≤w_i≤10⁵). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку “infinitely kind”.

Ввод	Вывод
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 -10 1 3 1 2 4	6 5 6 5 7 2 3
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 10 1 3 1 2 4	infinitely kind

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

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

Столовая#27231

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

Помогите найти такое здание!

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

В первой строке находятся два числе N и M - количество зданий и количество дорог, соединяющих здания (1<=N<=100, 0 <=M<=(N(N−1))/2. Далее в M строках расположены описания дорог: 3 целых числа s_i, e_i, l_i - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1<=s_i,e_i<=N, 0<=l_i,=100, дороги двунаправленные).

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

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

Ввод	Вывод
3 2 1 2 1 2 3 2	2
3 1 1 2 10	1

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

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

Флойд - существование#27226

Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует ли кратчайший путь между ними или нет.

Комментарий: Кратчайший путь может не существовать по двум причинам:

Нет ни одного пути
Есть пути сколь угодно маленького веса

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

В первой строке входного файла записано единственное число: N (1 <=N <=100) — количество вершин графа. В следующих N строках по N чисел — матрица смежности графа (j-е число в i-й строке соответствует весу ребра из вершины i в вершину j): число 0 обозначает отсутствие ребра, а любое другое число — наличие ребра соответствующего веса. Все числа по модулю не превышают 100.

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

Выведите N строк по N чисел. j-е число в i-й строке должно соответствовать кратчайшему пути из вершины i в вершину j. Число должно быть равно 0, если пути не существует, 1, если существует кратчайший путь, и 2, если пути существуют, но бывают пути сколь угодно маленького веса.

Примеры

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

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

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

Транспортировка#27126

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. Нато, чтобы довезти кружки от завода-изготовителя до ЛКШ,остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.

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

Выведите одно число - максимальное количество кружек, которое можно привезти за первый рейс, потратив не более 24часов.

Алгоритм Дейкстры Бинарный поиск по ответу

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

Одуванчики#26996

У Ани есть поле размером N×M клеток. На этом поле Аня разводит одуванчики. Аня заметила, что если в некоторой клетке поля растёт одуванчик, то на следующий день в четырёх клетках рядом с ним (севернее, восточнее, южнее и западнее) вырастает по одуванчику. Однако за пределами поля одуванчики не вырастают.

Сейчас на поле растёт несколько одуванчиков (не меньше одного). Определите, через сколько дней всё поле будет в одуванчиках. Известно, что Аня хорошо заботится о выросших одуванчиках, поэтому ни один из них не погибнет.

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

На первой строке находятся числа N и M (1<=N, M <= 100) размеры поля. Далее идут N строк, каждая из которых по M элементов. Эти строки обозначают поле. Символ «.» в строке означает, что данная клетка поля пуста, а символ «*» что в клетке находится одуванчик. Других символов в строках быть не может.

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

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

Частичные решения, работающие при случаях, когда N = 1 или M = 1, получат не менее 30 баллов.

Ввод	Вывод
3 3 ... .*. ...	2
4 3 ... ... ... *..	5

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

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

1 - k BFS#21770

Дан ориентированный взвешенный граф. Необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм 1 - k BFS.

Входные данные
В первой строке даны 2 целых числа n и m, число вершин и ребер в графе соответственно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра (a, b, c >= 0).

Выходные данные
Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.

Примеры

№	Входные данные	Выходные данные
1	9 9 1 2 1 2 4 2 4 6 1 4 3 1 3 5 2 5 6 1 8 9 100 9 7 100 7 8 100	1 4 3 6 4 Impossible Impossible Impossible

0-1 BFS

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