Темы
    Информатика(2609 задач)
---> 9 задач <---
Страница: 1 2 >> Отображать по:
ограничение по времени на тест
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;
ограничение по памяти на тест
64 megabytes
Дано выражение p1/p2/.../pn. Требуется определить, сколько различных значений и целых значений оно может принимать при всевозможных расстановках скобок.

Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида $a_1$ + $a_2$ +...+ $a_n$ и $a_1$ . $a_2$ . ... . $a_n$ не зависит от порядка выполнения в них действий и, следовательно, не меняется при произвольной расстановке в этих выражениях скобок.

В отличие от сложения и умножения, деление – операция не ассоциативная. Так, значение выражения вида $a_1$/$a_2$/ ... /$a_n$ может меняться при расстановке в нем скобок.

Рассмотрим выражение вида

$p_1$/$p_2$/ ... /$p_n$,

где все $p_i$ – простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений. Например, выражение 3/2/2 после расстановки скобок может принять два значения: 3/4 = (3/2)/2 и 3 = 3/(2/2).

В первой строке вводится число $n$ ( 1$ \le$n$ \le$200). Следующая строка содержат $n$ натуральных чисел – $p_1$, $p_2$,..., $p_n$. Все числа $p_i$ простые и не превосходят $10^4$.

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

В первой строке выведите количество возможных значений, которые может принять выражение $p_1$/$p_2$/ ... /$p_n$ при заданных $p_i$ после расстановки в нем скобок. Во второй строке выведите количество целых чисел среди этих значений.

Примеры
Входные данные
3
3 2 2
Выходные данные
2
1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дан полный граф, в котором все ребра покрашены в белый или черный цвет. Необходимо построить минимальное контролирующее в белом или черном графе.

В одном магическом королевстве есть $N$ городов, каждые два из которых соединены дорогой. Эти дороги были построены в давние времена Светлыми и Темными силами. Дороги, которые были построены Светлыми силами, вымощены белыми камнями, а те, что построены Темными – черными. Поскольку магические чары охраняют дороги, ни одно доброе существо не может пройти по дороге, вымощенной черными камнями, и ни одно злое – по белой дороге.

Когда-то давно люди решили избрать своих правителей и изгнали верховных магов из королевства. Однако недавно верховные маги Светлых и Темных сил договорились вернуть королевство под свой контроль. Для этого они хотят направить в некоторые города королевства магов, которые возьмут эти и смежные с ними города под свой контроль.

Точнее, если светлый маг будет направлен в некоторый город, то он возьмет под свой контроль этот город и все города, которые напрямую соединены с ним белыми дорогами. Аналогично, черный маг помимо города, в который он направлен, будет контролировать все города, напрямую соединенные с ним черными дорогами. Для захвата королевства требуется установить контроль над всеми городами.

Однако, при разработке плана захвата обнаружилось две трудности. Во-первых, выяснилось, что маг согласен принять участие в операции только если все маги, которые будут направлены в королевство, будут представлять ту же силу, что и он. То есть либо все участвующие в захвате маги должны быть светлыми, либо все они должны быть темными. Во-вторых, общее число магов, которые могут быть направлены в королевство не должно превышать K. Единственная надежда верховных магов заключается в том, что K достаточно велико, $2^K$ >= $N$.

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

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

В первой строке вводятся целые числа $N$ и $K$ ( $2 \le N \le 256$, $2^K$ $\ge$ $N$, $K \le N$).

Следующие $N$ строк содержат по $N$ целых чисел каждая. На $i$-ой позиции $i$-ой из этих строк расположено число 0, которое означает, что город не соединен дорогой сам с собой. Для всех $j \neq i$ число на $j$-ой позиции $i$-ой из этих строк равно 1, если $i$-ый город соединен с $j$-ым белой дорогой, и равно 2, если они соединены черной дорогой. Числа в строках разделены пробелами.

Гарантируется, что входные данные корректны, то есть если $i$-ый город соединен с $j$-ым белой дорогой, то и $j$-ый соединен с $i$-ым белой дорогой, аналогично в случае черных дорог.

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

Если захватить королевство при заданных условиях невозможно, выведите единственное число 0. В противном случае в первой строке выведите 1, если удастся захватить королевство с использованием светлых магов, и 2, если требуется использовать черных магов. В следующей строке выведите число L$ \le$K – количество использованных магов. Третья строка должна содержать $L$ целых чисел – номера городов, в которые следует направить магов. Заметьте, что вам не требуется минимизировать $L$. Если решений несколько, выведите любое.

Примеры
Входные данные
8 3
0 1 1 1 1 2 2 2
1 0 1 1 2 1 2 2
1 1 0 1 2 2 1 2
1 1 1 0 2 2 2 1
1 2 2 2 0 2 1 1
2 1 2 2 2 0 2 1
2 2 1 2 1 2 0 2
2 2 2 1 1 1 2 0
Выходные данные
1
3
1 5 2 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дан точечный источник света и многоугольник. Необходимо пройти от заданной точки до ближайшей освещенной точки, не проходя через дом.

В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с $N$ вершинами. Сам Петя находится в точке с координатами ($x$, $y$).

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

Петя может перемещаться по плоскости со скоростью $v$. Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).

Выясните, какое минимальное время требуется Пете, чтобы оказаться в освещенной точке.

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

В первой строке вводятся координаты Пети – два неотрицательных вещественных числа, не превышающих 1000, и его скорость v – вещественное число, 10-2$ \le$ v$ \le$ $10^4$.

Вторая строка содержит $N$ – число вершин в многоугольнике, задающем Петин дом ( 3$ \le$N$ \le$100). Далее в $N$ строках вводится по два вещественных числа – координаты вершин многоугольника в порядке их обхода против часовой стрелки. Все координаты неотрицательны и не превышают 1000.

Гарантируется, что входные данные корректны, в частности, многоугольник выпуклый, и никакие три его последовательные вершины не лежат на одной прямой. Также гарантируется, что и Петя, и лампочка находятся снаружи от многоугольника, в частности, не находятся на его границе. Расстояние от точки, где находится Петя, до многоугольника и от начала координат до многоугольника не меньше 10-2, расстояние от Пети до начала координат не меньше 10-2.

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

Выведите минимальное время, за которое Петя сможет попасть в освещенную точку. Ваш ответ должен отличаться от правильного не более чем на 10-4.

Примеры
Входные данные
3.5 3.5 1.0
4
2.0 0.0
4.0 2.0
2.0 4.0
0.0 2.0
Выходные данные
3.58113883008418967000
#520
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Даны размеры контейнера (в трех измерениях) и двух коробок. Необходимо определить, помещаются ли коробки в контейнер, если верх обязательно должен совпадать и боковые грани должны быть параллельны граням контейнера.

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

Ящики и контейнер имеют вид прямоугольных параллелепипедов. Длина, ширина и высота первого ящика – $l_1$, $w_1$ и $h_1$, соответствующие размеры второго ящика – $l_2$, $w_2$ и $h_2$. Контейнер имеет длину, ширину и высоту $l_c$, $w_c$ и $h_c$.

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

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

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

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

Первая строка входных данных содержит $l_1$, $w_1$ и $h_1$, вторая – $l_2$, $w_2$ и $h_2$, третья – $l_c$, $w_c$ и $h_c$. Все размеры – целые положительные числа, не превышающие 1000. Числа в строках разделены пробелами.

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

Выведите YES, если ящики можно упаковать в контейнер, и NO в противном случае.

Пояснения к примерам

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

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

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