---> 39 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
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

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

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

Сначала вводятся числа $N$ - количество вершин $N$-угольника (3 <= $N$ <= 1000) и $M$ - количество диагоналей, проведенных Васей. Далее на вход программы поступают $M$ пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри $N$-угольника. Вершины $N$-угольника нумеруются числами от 1 до $N$.

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

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

Примеры
Входные данные
3
0
Выходные данные
0
Входные данные
4 1
1 3
Выходные данные
0
Входные данные
6 2
1 3
5 3
Выходные данные
4 1 3 5 6
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

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

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

Первая строка содержит одно целое число n (0 ≤ n≤ 100 000) – количество черных узлов в начале. Каждая из следующих n строк содержит два целых числа – координаты очередного черного узла, по модулю не превосходящие 109.

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

Выведите число черных вершин после окончания всех перекрасок. Если процедура никогда не закончится, то выведите –1.

Примеры
Входные данные
10
-1 0
0 5
-4 -4
4 1
1 5
-2 -3
0 -2
1 -3
0 3
0 2
Выходные данные
10

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