Подразделы

Другие разделы

Дата и время

09/04/2025 18:25:43

Авторизация

Лето 9

A. Катание на автобусах B. Старая крепость C. Гистограмма D. Два коня E. Сапер F. Интересное число G. Треугольник Паскаля H. Два прямоугольника I. Цветные нули

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

Ограничения: время – 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