e-olimp 1658. Факториал

Задача

Вычислите факториал числа.

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

Одно целое число [latex]n[/latex] ([latex] 0 \leqslant n \leqslant 20[/latex]).

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

Выведите значение [latex]n! = 1 · 2 · 3 · … · n.[/latex]

Тесты

Входные данные Выходные данные
3 6
0 1
20 2432902008176640000

Код № 1

Решение № 1

Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.

Код № 2

Решение № 2

Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).

Ссылки

Условие задачи на E-Olymp
Код задачи № 1 на Ideone
Код задачи № 2 на Ideone

e-olymp 9405. Профессор и шары

Условие задачи

Для праздника Профессор купил голубые, красные и жёлтые воздушные шары. Всего $n$ штук. Жёлтых и голубых вместе — $a$. Красных и голубых — $b$ штук.

Сколько голубых, красных и жёлтых шаров купил Профессор?

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

Три натуральных числа $n$, $a$, $b$.

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

В одной строке выведите количество голубых, красных и жёлтых шаров, которые купил Профессор.

Тесты

Входные данные Выходные данные
1 10 6 8 4 4 2
2 12 8 10 6 4 2
3 14 10 12 8 4 2
4 16 14 12 10 2 4

Программный код

Решение

Для решения задачи необходимо вывести формулу для вычисления количества жёлтых ($y$), синих ($u$) и красных ($r$) шаров. Из условия имеем, что:

$$\left.\begin{matrix}
&u&+&y&=a&\\
&r&+&u&=b&\\
&r&+&u&+&y&=n&
\end{matrix}\right\}$$

Выразим $r$ и $y$ через $u$:

$$\left.\begin{matrix}
r=&b&-&u&\\
y=&a&-&u&
\end{matrix}\right\}$$

Подставим эти значения в формулу $r+u+y=n$:

$n=b-u+u+a-u$

$u$ и $-u$ взаимоуничтожатся и мы получим, что:

$n=a+b-u$

Теперь выведем формулу для вычисления количества синих шаров:

$u=b+a-n$

Ссылки

e-olymp 9080. Три богатыря

Задача

Три богатыря шли из Бразилии в Киевскую Русь. Шли они со скоростью [latex]n[/latex] метров в минуту и должны пройти расстояние [latex]r[/latex] километров. Сколько дней им понадобится для преодоления пути?

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

Два натуральных числа [latex]n[/latex] и [latex]r[/latex] [latex]\left(n, r \leqslant10^{4}\right)[/latex]

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

Выведите количество дней, за которое богатыри проделают свой нелегкий путь.

Тесты

Входные данные Выходные данные
1 1 10 7
2 2 8 3
3 4 70 13
4 5 68 10
5 3 12 3

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

Решение

Ответом к задаче будет количество дней, за которое богатыри проделают путь. То есть нам просто надо поделить путь на скорость. Но загвоздка задачи состоит в том, что скорость дана в метрах в минуту, а нам надо перевести в километры в сутки. В одних сутках [latex]1440[/latex] минут, в километре [latex]1000[/latex] метров. Выполнив математические преобразования, получаем, что надо заданное значение скорости умножить на [latex]1.44[/latex]. Выводим результат деления пути на скорость, умноженную на [latex]1.44[/latex]. Так как получится нецелый результат, округляем значение в сторону большего с помощью функции Math.ceil().

Ссылки

e-olymp 8659. Байтик та шахи

Задача

Вкотре запізнившись на урок, Байтик, проходячи повз ігрову кімнату, помітив шахову дошку. Порахував усі клітинки на ній, і йому стало цікаво: скільки різних квадратів зі стороною $k(1 \leqslant k \leqslant n)$ можна розмістити на дошці розміру $n$.

Вхідні дані

Натуральне число $n$ $( n\leqslant 10000)$ розмір шахової дошки.

Вихідні дані

Єдине число – кількість різних квадратів, які можна розмістити на шаховій дошці.

Тести

Входные данные Выходные данные
1 3 14
2 10 385
3 99 328350
4 999 332833500
5 10000 333383335000

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

Рішення

Вирішити цю задачу можна за допомогою квадратного пірамідального числа — числа, яке висловлює кількість квадратів з різними сторонами в сітці $n$*$n$. Загальна формула для пірамідального числа порядку $n$: $\sum\limits_{k = 1}^{n} k^{2} = \frac{n(n+1)(2n+1)}{6}$. Використаємо виведену формулу для лінійного обчислення, щоб не використовувати цикли і зменшити час роботи програми.

Посилання

e-olymp 399. Последствия гриппа в Простоквашино

Задача

”Дорогой дядя Фёдор!

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

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

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

Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

Всегда твой верный друг – кот Матроскин.”

Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

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

В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

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

Вывести в $n$ строках по одному числу – ответ на соответствующее задание Шарика.

Тесты

Входные данные Выходные данные
1 3
2
3
4
1
0
2
2 5
3
11
7
43
27
0
0
0
0
0
3 6
2
28
42
14
64
0
1
2674440
24466267020
429
55534064877048198
1

Код

Решение

Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$

e-olymp 9410. Студенческая любовь

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношенияКоэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

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

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

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

Выведите одно число — ответ на задачу.

Тесты

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

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

1
2
-3 -5
3 5
0
2 1
5
-2
0
3 5
-5 -2 -1 0 4
5 4 0 0 -1
4
4 9
1000 -22 333 -56 1 2 -77 -650 10
-7 166 -333 90 -565 12 788 -800 111
523

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

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

Условие задачи e-olymp

Код решения ideone

e-olymp 4439. Возведение в степень

Задача

Вычислить значение $a^b$.

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

Два натуральных числа $a$ и $b$.

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

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 100 1
 2 2 10 1024
 3 3 7 2187
 4 8 9 134217728
 5 10 10 10000000000
 6 100 9 1000000000000000000

Код

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

e-olymp 8916. Первые парные

Первые парные

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

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

Натуральное число [latex] n [/latex].

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

В одной строке через пробел [latex] n [/latex] первых четных натуральных чисел.

Тесты

Входные данные Выходные данные
1 3 2 4 6
2 8 2 4 6 8 10 12 14 16
3 5 2 4 6 8 10

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

 

Решение

Решением этой задачи является вывод через пробел удвоенных чисел от 1 до [latex] n [/latex].

Ссылки

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

Цифра 3

Условие задачи:

На входе программы имеется натуральное число [latex] n (n < 99) [/latex]. Нужно вывести третью цифру (разряд сотен) числа [latex] n [/latex].

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

Натуральное число [latex] n (n < 99) [/latex].

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

Цифра разряда сотен числа [latex] n [/latex].

Тесты:

Ввод Вывод
1 512 5
2 7826 8
3 90285 2
4 12479056 0
5 18942793357 3

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

Решение:

Для нахождения третьей цифры с конца данного числа, выполним ряд следующих действий:

  • разделим данное натуральное число на [latex] 100 [/latex] и получаем количество сотен в числе: либо однозначное число (цифру), либо многозначное;
  • так как мы хотим получить простую сотню (однозначное число), мы находим остаток от полученного числа при делении на [latex] 10 [/latex].

Ссылки:

Задача на E-Olymp

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

Засчитанное решение на E-Olymp

e-olymp 8891. Ровно одно условие из двух

Задача

Для заданного целого числа $n$ вывести YES, если выполняется ровно одно из следующих условий и NO в противном случае.

  • число $n$ четное.
  • число $n$ отрицательное и кратное трем.

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

Одно целое число $n$.

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

Вывести YES или NO в зависимости от выполнения условий.

Тесты

ВВОД ВЫВОД
 22  YES
 7  NO
 -30  NO
 -9  YES
 0  YES

Код

 

Решение

Если оба условия выполняются или оба не выполняются, то нужно вывести «NO», а иначе  — «YES».

  • В первом случае проверяем четность числа $n$.
  • Во втором случае проверяем кратность трем и является ли $n$ отрицательным.
  • В обеих случаях исключаем варианты, когда оба условия могли бы выполнятся, то есть исключаем отрицательные числа и кратность трем для первого, и четность числа для второго случая.

Ссылки

e-olymp
ideone