---> 6 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников
    2002(9 задач)
    2003(10 задач)
    2004(13 задач)
    2005(12 задач)
    2006(12 задач)
    2007(11 задач)
    2008-2009(19 задач)
    2009-2010(23 задач)
    2010-2011(19 задач)
    2011-2012(8 задач)
    2012-2013(21 задач)
    2013-2014(8 задач)
    2014-2015(8 задач)
Страница: 1 2 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

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

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

Во входном файле записаны сначала числа N ($2 \le N \le 100$) и E ($2 \le E \le N$). Затем записано число M ($0 \le M \le 100$), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki ($2 \le K \le N$) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

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

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

Примеры
Входные данные
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
Выходные данные
40
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

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

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

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

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

Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

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

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

Примеры
Входные данные
1 3 4
0 0 2 0
0 1 1 0
0 0 3 0
Выходные данные
6
Входные данные
0 5 5
0 1 0 0 0
0 1 0 1 0
0 0 3 1 0
1 0 1 1 0
2 0 0 0 0
Выходные данные
12
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Задан взвешенный граф, содержащий два типа вершин (деревни и города), а также начальная вершина (столица). Необходимо для каждого из городов определить кратчайший путь от столицы.

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

Напишите программу, которая посчитает, в каком порядке и через какое время каждый из гонцов доберётся до своего города. Считается, что гонец во время пути не спит и нигде не задерживается.

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

Во входном файле сначала записаны 3 числа N, M, K — количество населенных пунктов, количество дорог и количество городов (2N1000, 1M10000, 1KN). Далее записан номер столицы C (1CN). Следующие K чисел задают номера городов. Далее следуют M троек чисел Si, Ei, Ti, описывающих дороги: Si и Ei — номера населенных пунктов, которые соединяет данная дорога, а Ti — время для проезда по ней (1Ti100).

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

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

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

Примеры
Входные данные
5 4 5 1
1 2 3 4 5
1 2 1
2 3 10
3 4 100
4 5 100

Выходные данные
1 0
2 1
3 11
4 111
5 211
Входные данные
5 5 3 1
2 4 5
2 1 1
2 3 10
3 4 100
4 5 100
1 5 1

Выходные данные
5 1
2 1
4 101
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.

В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.

Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.

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

В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа Ki — количества этажей, на которых останавливается i-й лифт, за которым следует Ki натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤Ki≤1000, K1+K2+…+KL≤100000. Количество этажей в небоскребе не превосходит 1000000.

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

В выходной файл выведите одно число — минимальную стоимость подъема сейфа.

Группы тестов:

  • Группа 0 : Тесты из условия (тесты 1-3). 0 баллов.
  • Группа 1 : Количество этажей в доме не превосходит 100 (тесты 4-6). 30 баллов.
  • Группа 2 : Количество этажей в доме не превосходит 1000 (тесты 7-11). 30 баллов.
  • Группа 3 : K1+K2+…+KL≤1000 (тесты 12-32). 20 баллов.
  • Группа 4 : Дополнительных ограничений нет (тесты 33-50). 20 баллов.
Баллы за группу тестов выставляются только при корректной работе программы на всех тестах группы.

Примеры
Входные данные
10 1 1 1 1 1
2 3 7
Выходные данные
7
Входные данные
10 1 1 3 2 1
2 3 7
Выходные данные
9
Входные данные
20 100 0 1 1 2
2 5 7
2 8 17
Выходные данные
804
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с «Бегущим городом» назвать их «Ездящий город».

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

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

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

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

Сначала вводится число $N$ — общее количество контрольных пунктов (2≤$N$≤10000).

Далее вводится количество автобусных маршрутов $K$ (1≤$K$≤50000). Далее идет $K$ описаний автобусных маршрутов.

Каждый маршрут описывается четырьмя числами $A_i$, $B_i$, $C_i$, $D_i$, которые означают, что каждые $C_i$ минут (т.е. в моменты времени 0, $C_i$, 2*$C_i$, …) автобус выходит от контрольного пункта $A_i$ и через $D_i$ минут прибывает к контрольному пункту $B_i$. Все $C_i$ и $D_i$ — натуральные и не превышают 10000.

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

Далее вводится число $M$ — количество контрольных пунктов в маршрутном листе участника (2≤$M$≤50). Далее вводятся $M$ чисел $P_1$, $P_2$, …, $P_M$ — номера контрольных пунктов, которые нужно посетить (числа в этом списке могут повторяться). В момент времени 0 участник находится в пункте $P_1$. Временем прохождения маршрута считается момент времени, когда участник окажется в пункте $P_M$.

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

Выведите одно число — минимальное время, за которое участник может пройти маршрут. Если существующие автобусные рейсы не позволяют пройти маршрут, выведите одно число –1 (минус один).

Примеры
Входные данные
2 2
2 1 3 1
1 2 5 4
3
1 2 1
Выходные данные
7
Входные данные
3 4
2 1 30 10
1 2 50 40
2 3 45 10
3 1 55 10
3
1 2 1
Выходные данные
65
Входные данные
2 2
1 2 3 1
1 2 5 4
3
1 2 1
Выходные данные
-1

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест