printРабочее место участника

printЗадачи

253. Катание на автобусах

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В городе `n` автобусных остановок, через которые проходят `k` кольцевых автобусных маршрутов. Каждый маршрут задается списком номеров остановок, через которые он проходит, `i`-ый маршрут проходит по остановкам `a_{i,1},\ a_{i,2},\ …,\ a_{i,l_i}` (в этом порядке). По маршруту ходит ровно один автобус. В момент времени 0 этот автобус находится на остановке `a_{i,1}`. На то, чтобы доехать до следующей на своем маршруте остановки, автобус тратит ровно одну минуту. Временем стоянки автобуса на остановке можно пренебречь. Все маршруты кольцевые, то есть через минуту после остановки `a_{i,l_i}` автобус оказывается на остановке `a_{i,1}` и едет по маршруту еще раз.
Несколько человек в этом городе решили покататься на автобусах. При этом каждый из них составил план своего катания. План `j`-го человека состоит из остановки `b_j`, на которой человек начнет свое катание и последовательности чисел `c_{j,1},\ c_{j,2},\ \ …,\ c_{j,m_j}`. Эти числа означают следующее: в момент времени 0 человек придет на остановку `b_j` и дождется ближайшего автобуса (если в этот момент какой-то автобус находится на остановке `b_j`, человек сядет в него). На этом автобусе он проедет `c_{j,1}` остановок, после чего выйдет и дождется следующего автобуса на той остановке, где он окажется. На нем он проедет `c_{j,2}` остановок, снова выйдет и снова дождется следующего автобуса. И так далее. Если в какой-то момент к остановке подъедет сразу несколько автобусов, то человек сядет в автобус с минимальным номером маршрута. Когда человек выходит из автобуса на какой-то остановке, он может уехать с этой остановки не раньше, чем через минуту.
Для каждого человека определите, через сколько минут после начального момента и на какой остановке закончится его катание.
Ввод
Во входном файле записано сначала число `n`, затем число `k`. Далее записано `k` строк, задающих автобусные маршруты. Каждая строка начинается с числа `l_i`, задающего длину маршрута, затем идет список остановок, через которые проходит маршрут: `a_{i,1},\ a_{i,2},\ …,\ a_{i,l_i}`. Маршрут может несколько раз проходить через одну и ту же остановку.
Далее идет число `p` — количество людей, и затем `p` строк, задающих планы людей. Каждая строка содержит сначала числа `b_j` — номер начальной остановки и `m_j` — количество чисел в последовательности. Затем идут числа `c_{j,1},\ c_{j,2},\ \ …,\ c_{j,m_j}`.
Все числа во входном файле натуральные и не превышают 50.
Вывод
В выходной файл для каждого человека выведите два числа: время в минутах, когда закончится его катание, и номер остановки, на которой это произойдет. Если же человек не сможет реализовать свой план до конца (на какой-либо остановке он не дождется автобуса), выведите для него два нуля.

Пример ввода

6 4
4  1 2 3 5
2  3 4
5  5 2 1 3 2
2  4 3
3
1  4  1 2 3 4
2  1  1
6  3  1 2 3

Пример вывода

20 1
2 3
0 0
Источник: XII командный чемпионат школьников Санкт-Петербурга по программированию.
loading