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

03/03/2020 by Владислав Гринькив

Задача

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

На занятие кружка пришли $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

Код

#include <iostream>
using namespace std;
struct archerProfile {
  unsigned long x;
  unsigned long r;
  unsigned int c;
}archer[1000];
int main(){ 
  int n;
  int commands = 1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> archer[i].x >> archer[i].r >> archer[i].c;
  }
  for (int i = 0; i < n - 1; i++) {
    unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;
    if (distanceBetweenArchers > archer[i].c * archer[i].r) {
      commands += 1;
    }
  }
  cout << commands;
  return 0;
}

#include <iostream>

using namespace std;

struct archerProfile {

unsigned long x;

unsigned long r;

unsigned int c;

}archer[1000];

int main(){

int n;

int commands = 1;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> archer[i].x >> archer[i].r >> archer[i].c;

}

for (int i = 0; i < n - 1; i++) {

unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;

if (distanceBetweenArchers > archer[i].c * archer[i].r) {

commands += 1;

}

cout << commands;

return 0;

}

Решение

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

Ссылки

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

Related Images:

e-olymp 1206. f91

29/01/2020 by Владислав Гринькив

Задача

МакКарти — известный теоретик компьютерных наук. В одной из своих работ он определил рекурсивную функцию $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

Код

#include <iostream>
using namespace std;
long f91(long n) {
  if(n <= 100){
    return 91;
  }
  else {
    return n - 10;
  }
}
int main() {
  long n;
  cin >> n;
  cout << f91(n);
  return 0;
}

#include <iostream>

using namespace std;

long f91(long n) {

if(n <= 100){

return 91;

}

else {

return n - 10;

}

int main() {

long n;

cin >> n;

cout << f91(n);

return 0;

}

Решение

Для решения задачи создадим функцию $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

Related Images:

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

18/01/2020 by Владислав Гринькив

Задача

Найти количество нулей в конце записи факториала числа $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

Код

#include <iostream> 
using namespace std;
int main() { 
    long long n, m = 5, s = 0; 
    cin >> n; 
    while(n >= m){
        s = s + (n / m); 
        m = m * 5;
    }
    cout << s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, m = 5, s = 0;

cin >> n;

while(n >= m){

s = s + (n / m);

m = m * 5;

}

cout << s;

return 0;

}

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 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

Related Images:

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

04/01/2020 by Владислав Гринькив

Задача

Вычислить значение $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

Код

#include <iostream>
using namespace std;

long pow(long a, long b) {
  if(b == 0){
    return 1;
  }
  if(b % 2 == 0){
    return pow(a * a, b / 2);
  }
  return a * pow(a, b - 1);
}

int main() {
  long a, b;
  cin >> a >> b;
  cout << pow(a,b);
  return 0;
}

#include <iostream>

using namespace std;

long pow(long a, long b) {

if(b == 0){

return 1;

}

if(b % 2 == 0){

return pow(a * a, b / 2);

}

return a * pow(a, b - 1);

}

int main() {

long a, b;

cin >> a >> b;

cout << pow(a,b);

return 0;

}

Решение

Для решения задачи создадим функцию «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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Владислав Гринькив

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

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

e-olymp 1206. f91

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

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

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

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

Задача

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

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

Тесты

Код

Решение

Примечание

Ссылки

Related Images: