Страница: 1 Отображать по:
#1745
Ездящий город
  
ограничение по времени на тест
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
#1750
Подпалиндромы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.

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

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

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

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

Выведите одно число — количество подстрок данной строки, являющихся палиндромами

Примеры
Входные данные
aaa
Выходные данные
6
Входные данные
aba
Выходные данные
4
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест