Страница: 1 Отображать по:
#1761
Катание на автобусах
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Заданы кольцевые маршруты автобусов. На проезд между остановками автобус тратит 1 минуту. Для людей заданы списки, в которых содержится число остановок, которое они проезжают, прежде чем выйти из автобуса. Когда человек выходит, он ждет ближайшего автобуса, садится на него и едет следующее по его списку число остановок, до тех пор, пока список его поездок не окончится. Необходимо определить для каждого человека, где и когда он закончит поездку.

В городе \(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
#1762
Старая крепость
  
Из окружности вырезано некоторое количество фрагментов. Требуется найти минимальную выпуклую оболочку (провести между оставшимися фрагментами хорды).

В одной далекой стране ученые обнаружили странное скопление камней. Изучив его, ученые пришли к выводу, что это части старой крепостной стены, имевшей форму окружности. К сожалению, время и вандалы разрушили некоторые части стены.

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

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

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

Во входном файле задано два натуральных числа: число фрагментов \(n\) (1 ≤ \(n\) ≤ 180) и радиус крепости \(r\) (1 ≤ \(r\) ≤ 100). Далее следует n пар целых чисел, описывающих сохранившиеся фрагменты стены: \(a_i\), \(b_i\) – углы в градусах, соответствующие началу и концу фрагмента. Углы отмеряются от направления на север из центра крепости, против часовой стрелки (0 ≤ \(a_i\), \(b_i\)< 360, \(a_i\) ≠ \(b_i\)). Каждый фрагмент от начального угла к конечному также проходится против часовой стрелки. Фрагменты не имеют общих точек.

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

Выведите минимальную возможную длину забора. Ответ должен отличаться от правильного не более, чем на \(10^{-3}\).

Примеры
Входные данные
1 100
0 90
Выходные данные
298.5009889168
#1763
Гистограмма
  
Задан текст, требуется вывести вертикальную гистограмму для различных букв текста с помощью символов #.

Вовочка ломает систему безопасности Пентагона. Для этого ему понадобилось узнать, какие символы в секретных зашифрованных посланиях употребляются чаще других. Для удобства изучения Вовочка хочет получить графическое представление встречаемости символов. Поэтому он хочет построить гистограмму количества символов в сообщении. Гистограмма – это график, в котором каждому символу, встречающемуся в сообщении хотя бы один раз, соответствует столбик, высота которого пропорциональна количеству этих символов в сообщении.

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

Входной файл содержит зашифрованный текст сообщения. Он содержит строчные и прописные латинские буквы, цифры, знаки препинания («.», «!», «?», «:», «-», «,», «;», «(», «)»), пробелы и переводы строк. Размер входного файла не превышает \(10^4\) байт. Текст содержит хотя бы один непробельный символ. Все строки входного файла не длиннее 200 символов.

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

Для каждого символа c кроме пробелов и переводов строк выведите столбик из символов «#», количество которых должно быть равно количеству символов c в данном тексте. Под каждым столбиком напишите символ, соответствующий ему. Отформатируйте гистограмму так, чтобы нижние концы столбиков были на одной строке, первая строка и первый столбец были непустыми. Не отделяйте столбики друг от друга. Отсортируйте столбики в порядке увеличения кодов символов.

Пример

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

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

Hello, world!
     #   
     ##  
#########
!,Hdelorw
Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.
         #              
         #              
         #              
         #              
         #              
         #         #    
         #  #      #    
      #  # ###  ####    
      ## ###### ####    
      ##############    
      ##############  ##
#  #  ############## ###
########################
,.;ADTabdeghilmnorstuvwy
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест