e-olymp 9066. Кружок стрельбы

Задача

После успешного обучения Атрея стрельбе из лука «Когтя» Фэй решила не останавливаться на достигнутом и открыть целый кружок стрельбы из лука.

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

У каждого из учеников есть свой волшебный лук, который характеризуется своей дальностью $r_i$ и силой $c_i$. Оба параметра — целые положительные числа. Когда ученик совершает выстрел из лука, магический снаряд начинает лететь вдоль координатной прямой в сторону увеличения координаты. Снаряд летит до тех пор, пока его сила положительна. В момент выстрела сила заряда равна силе лука, из которого совершается выстрел. Каждый раз, когда снаряд пролетает очередные $r_i$ единиц расстояния вдоль прямой, он теряет одну единицу силы.

Если ученик произвел выстрел, и снаряд, выпущенный им, достиг следующего по порядку вдоль прямой ученика, снаряд прекращает свой полет, а ученик, которого достиг снаряд, внезапно решает, что ему тоже надо произвести выстрел, и совершает его. Ученик совершит выстрел, даже если снаряд достиг его, имея силу $0$.

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

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

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

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 5
1 3 3
5 1 2
8 2 3
10 1 2
11 3 2
2
2 6
1 3 5
4 2 2
7 4 3
10 1 2
11 3 2
13 4 3
1

Код

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

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

e-olymp 1206. f91

Задача

МакКарти — известный теоретик компьютерных наук. В одной из своих работ он определил рекурсивную функцию $f_{91}$, которая определена для всякого натурального числа $n$ следующим образом:

Если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;

Если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.

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

Натуральное число $n$, не большее $1000000$.

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

Значение $f_{91}\left(n\right)$.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 5 91
 2 27 91
 3 91 91
 4 100 91
 5 102 92
 6 180 170

Код

Решение

Для решения задачи создадим функцию $f_{91}\left(n\right)$ которая в зависимости от значения $n$ будет выдавать нам разные значение, а имеено:
если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;
если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.
Так же, мы можем проследить законномерность того, что если $n\leqslant100$ функция $f_{91}\left(n\right)$ будет выдавть $91$, заметив это можно будет заменить сложную, но при этом красивую рекурсивную функцию на более простое и практичное решение и получить следущие соотношение:
$f_{91}\left(n\right) = \begin{cases} 91, & n\leqslant100;\\ n-10, & n\geqslant101; \end{cases}$

Ссылки

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

e-olymp 123. Количество нулей у факториала

Задача

Найти количество нулей в конце записи факториала числа $n$.

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

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

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

Количество нулей в конце записи $n!$

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 0
 2 7 1
 3 12 2
 4 100 24
 5 306 75
 6 5000 1249

Код

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

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

Код на Ideone

Засчитанное решение на e-olymp 

 

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