Задача A. Факториал

Условие этой задачи очень простое. Найдите наименьшее $K$ такое, что $K!$ делится на $N$ без остатка. $K! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (K-1) \cdot K.$ В первой и единственной строке дано число $N$ $(1 \le N \le 10^{16}).$ Выведите ответ на задачу. Вход

4

Ответ

4

Вход

8

Ответ

4

$N \le 10 $ — $10\%$ тестов.
$N \le 100 $ — $20\%$ тестов.
$N \le 1000$ — $30\%$ тестов.
$N \le 10^6 $ — $40\%$ тестов.
$N \le 10^9 $ — $50\%$ тестов.

Задача B. Тима и точки

Один очень сильный мальчик по имени Тима поймал Вас на переулке Манхэттена. Единственный шанс уйти без повреждений — решить следующую задачу! Даны $N$ точек в пространстве. Требуется найти две самые удалённые точки. Расстояние между точками $(x_1; y_1; z_1)$ и $(x_2; y_2; z_2)$ равно $|x_1-x_2|+|y_1-y_2| + |z_1-z_2|$. Решите задачу и спасите себя! В первой строке задано целое число $N$ $(2 \le N \le 10^5)$ — количество точек. В следующих $N$ строках заданы сами точки — по три целых числа $x_i;$ $y_i;$ $z_i$ на каждой строке. Все координаты точек находятся в интервале $[-10^6 \ldots 10^6]$. Выведите ответ к задаче. Вход

4
 0  9 -8
-2  5  3
 6 -6  2
 7  1  6

Ответ

31

Ответ 31, потому что расстояние между 1-ой и 3-ей точками равно $|0-6| + |9-(-6)| + |-8-2| = 6 + 15 + 10 = 31;$
$2 \le N \le 10^4$ — для $30\%$ тестов.

Задача C. Горы

Даша записалась на кружок рисования и первым ее заданием стало нарисовать красивые горы Алматы. В Алматы имеется $N$ гор, и каждую можно представить в виде равнобедренного, прямоугольного треугольника с гипотенузой, расположенной на оси $x$ (смотрите рисунок). Даша ограничена в средствах, поэтому она хочет узнать точное количество краски, которое ей понадобится. Помогите Даше, найдите площадь гор, для того чтобы рассчитать количество необходимой краски. Первая строка входных данных содержит единственное число $N$ $(1 \le N \le 10^4),$ количество гор в городе Алматы. Следующие $N$ строк содержат по два числа $0 \le x_i \le 10^6,$ $1 \le h_i \le 10^4,$ $X$ координата центра $i$-ой горы и ее высота соответственно. Выведите единственное число — площадь гор занимаемых на рисунке Даши, ответ следует выводить с 4 знаками после точки. Вход

2
0 1
1 1

Ответ

1.7500

Вход

3
4 3
1 1
2 2

Ответ

10.7500

Вход

1
0 1

Ответ

1.0000

Следующий рисунок соответствует 2 тесту.

Задача D. На катке

Андрей очень любит кататься на коньках и в период зимних каникул его практически каждый день можно встретить там. Поэтому он очень обрадовался узнав, что его друзья решили отметить новый год совместным походом на каток. Однако, у родителей было свое условие если ребята хотят остаться допоздна — они должны взять с собой младших сестренок.
Танцы на катке проходят в парах. Всего на каток пойдут $N$ парней (включая Андрея) и каждый приведет с собой сестренку. Парни готовы танцевать только с девушками. Точно также, девушки готовы танцевать только с парнями. К тому же, девушки хотят танцевать только с парнями выше них. Последнее условие — ни один из парней не хочет танцевать со своей сестренкой.
По описанию роста парней и девушек, определите максимальное количество пар, которое может танцевать на катке одновременно. В первой строке входного файла единственное число $N$ — количество парней. Следующие $N$ строк содержат по два целых числа — рост парня и рост сестренки парня соответственно. Все числа во входном файле меньше $10^5.$ В единственной строке выходного файла выведите ответ на задачу — максимальное количество пар, которое можно составить не нарушая вышеизложенных условий. Вход

5
1 2
5 2
2 1
3 3
5 1

Ответ

4

Вход

5
2 2
1 2
2 1
1 2
4 4

Ответ

2

Вход

5
3 2
4 5
3 3
1 4
1 4

Ответ

2

$N \le 500$ — для $30\%$ тестов.

Задача E. Треугольники

Посчитайте количество различных треугольников с целыми сторонами, имеющих площадь равную $\sqrt S.$ Формула Герона для площади треугольника: $\sqrt{p(p-a)(p-b)(p-c)},$, где $p = (a+b+c)/2,$ $a,$ $b,$ $c$ — длины сторон треугольника. В первой строке входных данных задано целое число $1 \le T \le 4$ — количество тестов. В следующих $T$ строках заданы по одному целому числу $1 \le S \le 10^{18}.$ Выведите $T$ — строк, в каждой строке ответ на соответствующий тест. Вход

3
8
13
60

Ответ

1
0
0

$S \le 100 $— $10\%$ тестов;
$S \le 1000 $— $20\%$ тестов;
$S \le 10^6 $— $30\%$ тестов;
$S \le 10^9 $— $40\%$ тестов;
$S \le 10^{12} $— $50\%$ тестов.

Задача F. Приют для животных

Animal-planet построили новое здание для животных. Это здание состоит из $N$ последовательных подъездов, для каждого из которых известно количество этажей в нем. На каждом этаже каждого подъезда расположена ровно одна квартира. При этом количество этажей в разных подъездах может быть разным.
Некоторые животные Мадияра не могут жить ниже $K$-го этажа. Он хочет выкупить несколько последовательных квартир не ниже $K$-го этажа в нескольких последовательных подъездах для своей будущей квартиры. При этом в каждом подъезде он должен выкупить одинаковое количество квартир и квартиры в разных подъездах должны быть расположены на одинаковых этажах. В итоге все выкупленные квартиры должны образовывать прямоугольник $X \times Y$, где $X$ — количество задействованных подъездов, а $Y$ — количество квартир, выкупленных в каждом подъезде. выбранной квартиры назовем площадь этого прямоугольника.
Помогите Мадияру найти максимальный размер квартиры, которая его устроит. В первой строке входных данных задаются два натуральных числа $N$ и $K$ $(1 \le N \le 10^5,$ $1 \le K \le 10^9).$ В следующей строке задаются $N$ натуральных чисел — $i$-ое число количество этажей $i$-го подъезда. Количество этажей не превосходит $10^9.$ Выведите одно число — ответ к задаче. Вход

4 2
3 4 1 3

Ответ

4

$1 \le N \le 1000$ — для $40\%$ тестов.