Темы
    Информатика(2609 задач)
---> 8 задач <---
Источники --> Личные олимпиады --> Жаутыковские олимпиады
    2011(8 задач)
Страница: 1 2 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Формат входного файла

В первой строке задается $N$ — количество звезд на небе (3 $\le$  $N$ $\le$ 300000). В каждой из следу- ющих $N$ строк заданы целые $X$, $Y$ (|$X$, $Y$| $\le$ $10^9$) — координаты соответствующей звезды.

Формат выходного файла

Выведите ответ к задаче.

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

Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: $Y$ [$i_1$, $i_2$, $i_3$, $i_4$] = min($X$[$j_1$, $j_2$, $j_3$, $j_4$]), где 1 $\le$ $i_k$ $\le$ $N$ − $M$ + 1, $i_k$ $\le$ $j_k$ $\le$ $i_k$ + $M$ − 1, а $M$ -  заданное число.

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

В первой строке входного файла задаются $N$ и $M$ ($1$ $\le$ $M$ $\le$ $N$). Остальные строки файла содержат элементы массива $X$. Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению $10^9$. Они расположены в таком порядке, что считать их можно с помощью псевдокода:

for i = 1 to N:
for j = 1 to N:
for k = 1 to N:
for l = 1 to N:
read X[i, j, k, l]
Выходные данные

Выведите искомый массив $Y$ в том же формате, в котором был дан массив $X$.

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

Дана сетка с $N$ + 1 рядами и $M$ + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку ($N$, $M$). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем $T$ раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку ($N$, $M$). Так как это число может быть очень большим, выведите остаток от его деления на $Z$.

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

В первой строке входного файла задается 5 целых чисел: $N$, $M$, $K$, $T$ и $Z$ ($1$ $\le$ $N$,$M$ $\le$ 300000, 0 $\le$ $K$, $T$ $\le$ 20, 1 $\le$ $Z$ $\le$ $10^9$). В каждой из следующих $K$ строк расположены координаты соответствующей клетки с ловушкой $X$, $Y$ (0 $\le$ $X$ $\le$ $N$, 0 $\le$ $Y$ $\le$ $M$). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и ($N$, $M$) ловушек нет.

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

Выведите требуемое число.

Примеры
Входные данные
1 1 1 0 100
0 1
Выходные данные
1
Входные данные
2 2 0 0 10
Выходные данные
6
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Джек нашел $N$ камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий  2 и так далее, самый тяжелый получил номер $N$.

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

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

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

Первая строка содержит целое число $N$ (1 $\le$ $N$ $\le$ 100000).

Каждая из следующих $N$ строк содержит по два целых числа: $R$ (1 $\le$ $R$ $\le$ $N$) и $S$ (1 $\le$ $S$ $\le$ 2). $R$  номер камня, который будет положен на чашу $S$. Все $R$ будут различны.

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

Выведите $N$ строк  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры
Входные данные
5
1 2
3 1
2 1
4 2
5 1
Выходные данные
<
>
>
?
>
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите $N$-й элемент этой последовательности.

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

Одно целое число $N$ (1 $\le$ $N$ $\le$ 10100).

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

Выведите одно целое число - $N$-й элемент последовательности.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
4
Выходные данные
5

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