e-olymp 1326. В хоккей играют настоящие…

Задача

prb1326 Лесные жители решили провести хоккейный турнир между $N$ командами. Сколькими способами могут быть распределены комплекты золотых, серебряных и бронзовых медалей, если одно призовое место может занять только одна команда?

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

В единственной строке расположено единственное натуральное число $N$, не превышающее 100.

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

Единственное число — искомое количество способов.

Тесты

Ввод Вывод
1 1 1
2 2 2
3 3 6
4 5 60
5 56 166320
6 100 970200

Код

Решение

Чтобы рассчитать количество способов воспользуемся формулой размещения из комбинаторики $A_N^k = \frac{N!}{(N−k)!}$, где $k = 3$, так как существует всего 3 призовых места и следовательно комплекты медалей можно распределить $N$$(N — 1)$$(N — 2)$ способами, при $N >= 3$. При $N < 3$ существует всего $N$ способов распределения, так как команд меньше чем призовых мест.

Ссылки

e-olymp
ideone

e-olymp 1289. Ланч

Задача

Влад хочет взять с собой для ланча пару фруктов. У него есть $a$ различных бананов, $b$ различных яблок и $c$ различных груш. Сколькими способами он может выбрать 2 разных фрукта из имеющихся у него?

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

В одной строке заданы три неотрицательных числа: $a$, $b$, $c$. Все числа не превышают [latex]10^6[/latex].

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

Вывести количество способов, которыми можно выбрать 2 фрукта разного вида.

 

Тесты

Вход Выход
2 3 4 26
6 2 4 44
0 4 8 32
1052 886 225 1368122
772 621 124 652144

Код программы

Решение

Пусть у нас $1$ банан и $b$ различных яблок. Мы можем взять $1$ банан  и одно яблоко $b$ способами. Так как бананов $a$, по одному яблоку и банану можем взять [latex](a \cdot b)[/latex] способами. Аналогично, так как груш $с$,  то есть [latex](a \cdot с)[/latex] способов взять по одному банану и одну грушу, и [latex](c \cdot b)[/latex] способов взять по одному яблоку и одну грушу. То есть всего [latex](a \cdot b + b \cdot c + c \cdot a) [/latex].

Ссылки

e-olymp

ideone

e-olymp 97. Числа Белла

Задача

Число Белла [latex]B_n[/latex] равно количеству разбиений множества из [latex]n[/latex] элементов на произвольное количество непересекающихся непустых подмножеств. Например, [latex]B_3 = 5[/latex], так как существует [latex]5[/latex] возможных разбиений множества [latex]\lbrace a, b, c\rbrace[/latex]: [latex]\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace[/latex]. Дополнительно считаем, что [latex]B_0 = 1[/latex].
Рассмотрим определитель [latex]D_n[/latex]:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа [latex]p[/latex] найти наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

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

Каждая строка ввода содержит два целых числа [latex]n[/latex] и [latex]p[/latex] ( [latex]\;0\leq\; n,\;p \;\leq\; 10000[/latex] ). Известно, что [latex]p[/latex] – простое.

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

Для каждой пары входных значений [latex]n[/latex] и [latex]p[/latex] в отдельной строке выведите наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Тесты

Входные данные Выходные данные
1 5
3 2
4 2
4 3
10000 3
0
2
5
2
24962375
18 2
465 1009
9998 9221
548 11
134
0
778
14412
1093 1093
1103 1723
3931 617
4868 6113
9534 71
1
0
10635
0
639989
617 17
42 11
0 5
11295
63
0

Код программы

 

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i! $$

Воспользуемся этим свойством для решения данной задачи. Найдём степень числа [latex]p[/latex] в разложении  на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число [latex]k[/latex].

Ссылки

Условия задачи на e-olymp
Код задачи на ideone
Число Белла на wikipedia

e-olymp 239. Треугольники

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные Выходные данные
5
2 -1
3 0
0 4
-3 0
-2 1
6
5
0 0
2 4
6 6
10 34
-42 -48
10
4
0 0
0 1
1 0
1 1
0
8
0 0
2 2
1 1
3 3
0 1
2 1
1 0
1 2
24
5
0 0
0 1
-1 0
-1 -1
3 -3
3

 

Решение задачи

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex].  Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

Условие задачи на сайте  E-Olymp

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

e-olymp 1503. Вписанные треугольники

Задача

Пример первого теста на графике

На границе окружности с центром в начале координат и радиусом $r$ заданы $n$ различных точек. Поскольку все точки расположены на одной окружности, то любые три из них не коллинеарны, и поэтому образуют треугольник. Вам необходимо вычислить суммарную площадь всех этих $C_{n}^3$ треугольников.

Входные данные
Состоит из не более чем $16$ тестов. Каждый тест начинается двумя целыми числами $n \left(0 ≤ n ≤ 500\right)$ и $r \left(0 < r ≤ 100\right)$. Через $n$ обозначено количество точек, а через $r$ радиус окружности. Центр окружности находится в центре координат. Дальше следуют $n$ строк, каждая из которых содержит действительное число $θ \left(0 ≤ θ < 360 \right)$, которое определяет угол в градусах между точкой и направлением $x$-оси. Например, если $θ$ равно $30$ градусов, то соответствующая точка имеет декартовы координаты $\left(r \cdot \cos(30°), r \cdot \sin(30°) \right)$. Последняя строка содержит $n = r = 0$ и не обрабатывается.

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

Тесты

Входные данные Выходные данные
5 10
10
100
300
310
320
3 20
10
100
300
0 0
286
320
3 5
25
176
243
0 0
25
4 20
30
80
130
330
0 0
822
2 7
30
230
0 0
0

Код программы

Решение задачи

Радианная мера точек заносится в массив, после чего массив сортируется по возрастанию с помощью функции  sort().

В переменную res  изначально заносится площадь, равная площади кругов радиуса $r$,
то есть значение $C_{n}^3 \cdot \pi \cdot r^2 = n(n-1)(n-2)(n-2)\pi \cdot \frac{r^2} {6}$. Значение $\frac{r^2} {2}$ присваивается переменной r2, а sq – площадь одного круга, то есть $\pi \cdot r^2$.

Перебираются пары точек, а затем вычисляется угол.
Если угол меньше, то проходимся по меньшему сегменту, площадь которого равна $\pi r^2-0.5r^2(\alpha-\sin \alpha)$, $\alpha = 2\pi -\alpha$. В ином случае мы проходим по большему сегменту.
В любом случае переменной s  присваивается площадь сегмента, который мы проходим от $P_{i}$ к $P_{j}$ при движении против часовой стрелки.

Количество точек, лежащих на сегменте, равно $n-(j-i+1)$.
Значит, из переменной res необходимо вычесть площадь сегмента s такое количество раз, которому равно количество точек, то есть pts .

Количество точек, которые лежат на сегменте площади s , равно $n-2-  $  pts.
Площадь противоположного сегмента равна разности площади круга и сегмента. Для получения ответа вычитаем площадь противоположного сегмента из переменной res такое количество раз, которое равно значению переменной  pts и выводим полученное значение.

Ссылки

Условие задачи на e-olymp.com
Решение задачи ideone.com

A1029

Задача о восьми мирных ладьях

Задача о восьми мирных ладьях

Условие

Получить все расстановки   [latex]8[/latex]   ладей на шахматной доске, при которых ни одна ладья не угрожает другой.


Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска   [latex]8 \times 8[/latex].

Ладья находится под боем, если другая ладья находится с ней на одной строке или в одном столбце. Следовательно, фиксируя, скажем, столбцы, можно разместить ладьи по строкам таким образом, чтобы ни одна пара не находилась под боем.

Заведем массив на восемь элементов и занумеруем его таким образом, чтобы значение   [latex]j[/latex]   по индексу   [latex]i[/latex]   соответствовало строке [  [latex]j[/latex],   в которой находится ладья в   [latex]i[/latex]-м столбце.

Теперь легко видеть, что положение на доске определяется перестановкой чисел   [latex]1,..,8[/latex].   Как известно, число различных перестановок длины [latex]n[/latex]   —   [latex]P_{n}=n![/latex]. Следовательно, всего существует   [latex]8!=40320[/latex]   различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья


Детали реализации

Для получения перестановок использована функция стандартной библиотеки [latex]next\_permutation()[/latex]

В силу большого объёма выходного файла (5.5 мб) он доступен отдельно, по ссылке: https://www.dropbox.com/s/yyaz7vq08jczsnl/out?dl=0