Страница: 1 2 >> Отображать по:
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Группа людей называется современниками, если был такой момент, когда они могли собраться все вместе и обсуждать какой-нибудь важный вопрос. Для этого в тот момент, когда они собрались, каждому из них должно было уже исполниться 18 лет, но еще не исполниться 80 лет.

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

Будем считать, что в день своего 18-летия человек уже может принимать участие в такого рода собраниях, а в день 80-летия, равно как и в день своей смерти, — нет.

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

Сначала на вход программы поступает число N — количество людей (1N10000). Далее в N строках  вводится по шесть чисел — первые три задают дату (день, месяц, год) рождения, следующие три — дату смерти (она всегда не ранее даты рождения). День (в зависимости от месяца, а в феврале — еще и года) от 1 до 28, 29, 30 или 31, месяц — от 1 до 12, год — от 1 до 2005.

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

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

Никакое множество не должно быть указано дважды.

Если нет ни одного непустого максимального множества, выведите  одно число 0.

Гарантируется, что входные данные будут таковы, что размер  выходных данных  для правильного ответа не превысит 2 Мб.

Оценка задачи

1 балл получат программы, правильно решающие задачу для случая N100.

Примеры
Входные данные
3
2 5 1988 13 11 2005
1 1 1 1 1 30
1 1 1910 1 1 1990
Выходные данные
2 
3 
Входные данные
3
2 5 1968 13 11 2005
1 1 1 1 1 30
1 1 1910 1 1 1990
Выходные данные
2 
1 3 
Входные данные
3
2 5 1988 13 11 2005
1 1 1 1 1 10
2 1 1910 1 1 1928
Выходные данные
0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Заданы годы существования цивилизаций. Необходимо найти пару цивилизаций, которые существовали одновременно наибольшее количество лет.

Недавно Петя занялся изучением древних цивилизаций. Он нашел в энциклопедии даты рождения и гибели $N$ различных древних цивилизаций и теперь хочет узнать о влиянии культуры одних цивилизаций на культуру других.

Петя предположил, что между цивилизациями $A$ и $B$ происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.

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

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

В первой строке вводится число $N$ – количество цивилизаций, культура которых интересует Петю (1$ \le$N$ \le$100 000). Следующие N строк содержат описание цивилизаций – в каждой строке задаются два целых числа $S_i$ и $E_i$ – год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят $10^9$ по абсолютной величине, $S_i$ < $E_i$.

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

Выведите два числа – номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите единственное число 0.

Примеры
Входные данные
3
-600 -400
-450 -300
-400 -50
Выходные данные
1 2
Входные данные
2
10 20
15 21
Выходные данные
1 2
Входные данные
1
77777 77778
Выходные данные
0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
На плоскости заданы углы (фигура, образованная лучами, исходящими из одной точки). Требуется найти "выпуклую оболочку", которая также ограничена двумя лучами.

Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению выпуклое множество, содержащее заданное множество точек $X$, называется выпуклой оболочкой множества $X$.

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.

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

В первой строке вводится число $n$ - количество углов (1 <= $n$ <= 1000). Каждая из следующих n строк содержит описание одного угла. Угол задается координатами трех точек: вершины и двух отличных от вершины точек - по одной на каждом из лучей. Все координаты целые и не превышают $10^4$ по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.

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

Выведите границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходных данных не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все выводимые числа должны быть целыми и не превосходить $10^5$ по абсолютной величине. При проходе вдоль описанной границы выпуклая оболочка углов должна быть справа. На первой строке выведите $L$ - количество объектов в ответе. Следующие $L$ строк должны содержать описание объектов. Объекты описываются следующим образом:

*Отрезок: "segment $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) и ($x_2$, $y_2$) - концы отрезка, отрезок считается направленным от ($x_1$, $y_1$) к ($x_2$, $y_2$).
*Луч, направленный от начала: "outray $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) - начало луча, а ($x_2$, $y_2$) - произвольная точка на луче, отличная от начала.
*Луч, направленный к началу: "inray $x_1$ $y_1$ $x_2$ $y_2$", где ($x_2$, $y_2$) - начало луча, а ($x_1$, $y_1$) - произвольная точка на луче, отличная от начала.
*Прямая: "line $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) и ($x_2$, $y_2$) - две точки на прямой, причем при движении вдоль прямой в ее направлении точка ($x_1$, $y_1$) следует ранее точки ($x_2$, $y_2$).
*Если выпуклой оболочкой является вся плоскость, то выведите $L$ = 0.

Примеры
Входные данные
2
3 1 4 1 4 4
2 2 4 3 3 4
Выходные данные
3
inray 4 1 3 1
segment 3 1 2 2
outray 2 2 3 5
Входные данные
2
0 0 1 0 0 1
0 0 -1 0 0 1
Выходные данные
1
line 0 0 -1 0
Входные данные
2
0 0 1 0 0 1
0 0 -1 0 0 -1
Выходные данные
0
Для N человек известно 3 параметра: время надувания шарика, сколько шариков можно надуть до отдыха и время отдыха. Требуется определить, за какое минимальное время эти люди надуют N шариков.

Организаторы детского праздника планируют надуть для него $M$ воздушных шариков. С этой целью они пригласили $N$ добровольных помощников, $i$-й среди которых надувает шарик за $T_i$ минут, однако каждый раз после надувания $Z_i$ шариков устает и отдыхает $Y_i$ минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

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

В первой строке входных данных задаются числа $M$ и $N$ (0 <= $M$ <= 15000, 1 <= $N$ <= 1000). Следующие $N$ строк содержат по три целых числа - $T_i$, $Z_i$ и $Y_i$ соответственно (1 <= $T_i$, $Y_i$ <= 100, 1 <= $Z_i$ <= 1000).

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

Выведите в первой строке число $T$ - время, за которое будут надуты все шарики. Во второй строке выведите $N$ чисел - количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.

Примеры
Входные данные
2 2
1 1 1
1 1 1
Выходные данные
1
1 1 
Входные данные
3 2
2 2 5
1 1 10
Выходные данные
4
2 1 
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 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

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