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 1462. Хитрая сортировка

Задача

Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.

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

Первая строка содержит число [latex] n [/latex] ([latex] 1 \leqslant n \leqslant 100 [/latex]), а вторая — сами натуральные числа, не превышающие [latex] 32000 [/latex].

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

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

Тесты

Входные данные Выходные данные
1 7
12 15 43 13 20 1 15
20 1 12 13 43 15 15
2 10
82 22 19 90 34 17 588 921 200 121
90 200 121 921 22 82 34 17 588 19
3 4
162 9801 37 14
9801 162 14 37

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

 

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

Для решения этой задачи необходимо объявить массив, с размером [latex] n [/latex], который будет хранить все числа, введенные пользователем.
Сортировку будем проводить в циклах for для сравнения соседних чисел и смены их позиции с помощью функции swap. Если последняя цифра следующего числа меньше предыдущего, то эти числа меняются местами. Если их последние цифры одинаковые, то сравниваются сами числа.
В конце выводим массив array[n].

Ссылки

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

Решение на e-olymp

Решение на ideone.com

e-olymp 1462. Хитрая сортировка

Задача

Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.

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

Первая строка содержит число  $n \ (1 \leqslant n \leqslant 1000)$, а вторая — сами натуральные числа, не превышающие $32000$.

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

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

Тесты

Входные данные Выходные данные
1 7
12 15 43 13 20 1 15
12 33 14 44 64 77
2 4
345 112 999 29
112 345 29 999
3 9
78 33 13 0 12 89 20 78 9990
0 20 9990 12 13 33 78 78 89

Код

Решение

Воспользуемся алгоритмом пузырьковой сортировки, при которой соседние элементы сравниваются и меняются местами, если следующий элемент меньше предыдущего. Исходя из условия задачи отделяем и реализуем алгоритм непосредственно с последними цифрами чисел последовательности. В случае их равенства сортируем уже сами числа.

Ссылки

e-olymp 2663. Сортировка пузырьком

Условие

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

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

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$$9$.

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

Выведите одно число — количество обменов пузырьковой сортировки.

Тесты

Ввод Вывод
1 3
1 3 2
1
2 2
2 1
1
3 4
4 1 5 3
3
4 5
5 4 1 100000 7
4
5 6
6 5 4 3 2 1
15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

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

Ссылки

решение на e-olymp
код на ideone

e-olymp 1704. Умная черепашка

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

Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие 30.

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

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

Тесты

Ввод Вывод
1 4 5 10
2 3 14 105
3 11 17 5311735
4 20 21 68923264410
5 30 30 30067266499541040

Код программы (циклы)

Решение

Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$.  Для того, чтобы избежать больших чисел,  делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.

 

Код программы (динамическое программирование)

Решение

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

Ссылки (циклы)

Ссылки (динамическое программирование)

e-olymp 8963. Наименьшие влево

Условие

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

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

В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

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

Выведите элементы обновленного массива.

Тесты

Ввод Вывод
1 7
6 -3 -7 4 -7 -4 5
-7 -7 6 -3 4 -4 5
2 2
100 -100
-100 100
3 6
-2 -2 7 3 99 -2
-2 -2 -2 7 3 99
4 5
1 1 1 1 1
1 1 1 1 1

Решение

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

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

Ссылки

решение на E-olymp
код на ideone

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-olimp 7848. Переставить соседние

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

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

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

Вывести обновленный массив.

Тесты

Входные данные Выходные данные
7
3 5 -7 7 5 -9 -4
5 3 7 -7 -9 5 -4
8
-9 81 27 -38 2 6 -56 -21
81 -9 -38 27 6 2 -21 -56
2
25 -76
-76 25
3
55 44 33
44 55 33
1
99
99

Код

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

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

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

e-olymp 7847. Кількість різних елементів

Задача

Дано масив з N цілих чисел. Визначте, скільки в цьому масиві різних елементів.

Вхідні дані

В першому рядку записано число N. В наступному рядку записано N цілих чисел. Всі числа за модулем не перевищують 100.

Вихідні дані

Кількість різних елементів в масиві.

Тести

 

Вхідні дані Вихідні дані
1. 7
3 5 -7 7 5 -9 -4
6
2. 5
1 25 59 75 100
5
3. 6
1 2 3 1 2 4
4

Код 1

Решение

Ставим отметку числу как будто видим его впервые.
Далее задача пройти по всем предыдущим числам и проверить не встретится ли такое же число.
Если встретится, то отметку снимаем, а пройдя по всем предыдущим числам так и не встретив числа равного текущему, значит «видим его впервые» и отметка поставлена справедливо.
Считаем количество отметок.

Ссылки

Код 2

Решение

Сначала, количество различных чисел равно [latex]n[/latex]
Далее в цикле for отметим каждое число с потока.
Встретив число ранее отмеченное уменьшаем счетчик различных чисел.

Ссылки

 

 

 

 

e-olymp 8663. Задача про множення

Задача

На уроці математики Байтик навчився множити, і почав застосовувати цю операцію з різними числами. Наприклад, розкладав число на цифри і знаходив добуток цифр. І тут він задумався, який найбільший добуток цифр серед натуральних чисел, що не перевищує [latex]N[/latex]. Допоможіть розв’язати задачу.

Вхідні дані

Одне число [latex]N(1\leqslant N\leqslant 2\times 10^{9})[/latex].

Вихідні дані

Максимальний добуток цифр серед чисел, що не перевищують [latex]N[/latex].

Тести

Вхідні дані Вихідні дані
57 36
1000 729
7999 5103
28994 10368
4876 2268

 

Код програми

Алгоритм

Складність задачі полягає в обмеженості у часі.

  1. Знайдемо добуток цифр заданого числа.
  2.  Змінемо останню цифру на [latex]9[/latex] та віднімемо [latex]1[/latex] від попереднього розряду. Визначаємо поточний добуток цифр отриманого числа. Повторюємо цю операцію з наступними розрядами числа.
  3. Порівнюємо поточний добуток з максимальним.

Приклад:

Приклад розкладу числа на різних етапах алгоритму:

 

Посилання

Задача на 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 8674. Игра

Задача

Мурад и Ибрагим играют в следующую игру. Изначально дается число $1$. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от $2$ до $9$ включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа $n$. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинает первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.

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

Первая строка содержит одно число $t$ $(1 \leqslant t \leqslant 2500)$ — количество тестов. Каждая из следующих $t$ строк содержит одно целое число $n$ $(2 \leqslant n \leqslant 10^9)$.

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

Для каждого теста выведите в отдельной строке $1$, если Мурад выиграет игру, и $2$ иначе.

Тесты

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

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

1 4
9
10
1149729
999999999
1
2
2
1
2 3
6
163
1234567
1
2
2
3 3
42
100
1000
1
1
1

 

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

Решение с циклом для каждого отдельного теста:

 

Решение без цикла для каждого отдельного теста:

 

Решение

Для начала заметим, что победит тот игрок, чей ход выпадет на число из промежутка $[\frac{n}{9},n)$, так как любое число из этого промежутка можно умножить на соответствующее целое число из $[2,9]$ и получить число не меньшее чем $n$. Назовем такой промежуток «зеленой зоной» (в общем виде будет $[\frac{2n}{18^k},\frac{n}{18^{k-1}})$, $k \in \mathbb {N}$). Тогда очевидно, что проиграет тот игрок, чей ход выпадает на число из промежутка $[\frac{n}{18},\frac{n}{9})$, так как при умножении числа из этого промежутка на любое целое число из $[2,9]$, приводит к тому, что получается число из «зеленой зоны». Назовем такой промежуток «красной зоной» (в общем виде будет $[\frac{n}{18^k},\frac{2n}{18^k})$, $k \in \mathbb {N}$). Получаем, что промежуток $(0,n)$ делится на «красные» и «зеленые зоны». Тогда задача сводится к нахождению вида «зоны» в которой находится $1$.

Используя в реализации цикл для каждого отдельного теста, получить результат достаточно несложно. Однако, для заданного $n$ можно получить исход игры используя лишь линейные вычисления.

Рассмотрим цепочку неравенств (учитывая, что $2 \leqslant n$ ):  $$\lfloor \log _{18} n \rfloor \leqslant \log _{18} n \leqslant \lceil  \log _{18} n \rceil$$

$$ 18^{\lfloor \log _{18} n \rfloor} \leqslant n \leqslant 18^{\lceil  \log _{18} n \rceil}$$

$$\frac{1}{18^{\lceil  \log _{18} n \rceil}} \leqslant \frac{1}{n} \leqslant \frac{1}{18^{\lfloor \log _{18} n \rfloor}}$$

$$\frac{n}{18^{\lceil  \log _{18} n \rceil}} \leqslant 1 \leqslant \frac{n}{18^{\lfloor \log _{18} n \rfloor}}$$

Из общего вида «красной зоны» видно, что левый ее конец это число вида $\frac{n}{18^k}$, значит $\frac{n}{18^{\lceil  \log _{18} n \rceil}}$ является левым концом «красной зоны», обозначим его как $l$. Тогда, $2l$ будет правым концом «красной зоны» исходя из её общего вида. Из полученного неравенства видно, что $1$ лежит между левыми концами соседних «красных зон». Получаем, что если $2l \leqslant 1$, то единица лежит в «зеленой зоне», а иначе — в «красной».

Ссылки

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

Решение с циклом для каждого отдельного теста на ideone

Решение без цикла для каждого отдельного теста на ideone

e-olymp 2098. Переворачиватель

Условие

Заданы [latex]n[/latex] чисел. Выведите их в обратном порядке.

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

Сначала задано число [latex]n[/latex] ([latex]0 \lt n \lt 100[/latex]), за ним идут [latex]n[/latex] целых чисел.

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

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

Тесты

Ввод Вывод
1 7
2 4 1 3 5 3 1
1 3 5 3 1 4 2
2 1
5
5
3 10
1 1 1 9999 5 -1 7 3 0 9
9 0 3 7 -1 5 9999 1 1 1

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

Решение

Введём переменную [latex]n[/latex], затем создадим массив из [latex]n[/latex] элементов. С помощью цикла for от [latex]0[/latex] до [latex]n[/latex] запишем в него числа. Теперь с помощью другого цикла от [latex]n-1[/latex] до [latex]-1[/latex] выводим их в обратном порядке.

e-olymp 8945. *Рамка 4

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

Для заданных натуральных чисел $n$ и $m$ вывести прямоугольную рамку размером $n \times m$ из звездочек, заполненную пробелами как показано в примере.

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

Два натуральных числа $n$ и $m \; (n, m \leqslant 100)$.

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

Выведите прямоугольную рамку размером $n \times m$.

Тесты

Входные данные Выходные данные
1 4 7
2 2 8
3 3 3
4  3 2

 

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

Решение

Для получения рамки нужно заполнить первые и последние строки символом $*$ . Для этого в цикле будем проверять равенство  столбцов $0$,  $(m-1)$ и строк $0$ , $(n-1)$. В случае равенства выводить символ. Таким образом получим рамку.

Ссылки

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

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

e-olymp 8546. Найдите сумму

Задача

По заданному натуральному числу $n$ вычислите сумму

$\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+ … +\frac{1}{n\cdot(n+1)}$

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

Одно натуральное число $n$ ($n$ $⩽$ $1000$).

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

Выведите сумму с $6$ десятичными знаками.

Тесты

Входные данные Выходные данные
1 1 0.500000
2 5 0.833333
3 12 0.923077

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

Решение

Для вычисления данной суммы необходимо сложить $n$ слагаемых вида

$\frac{1}{i \cdot (i + 1)}$

начиная с $i = 1$ и с шагом в единицу до $i = n$.

Ссылки

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

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

e-olymp 8680. Чётные соседи

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

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

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

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

Входные данные Выходные данные
1 6
1 2 3 4 5 6
2
2 9
3 6 3 5 2 9 1 2 5
0
3 3
2 1 2
1
4 6
13 24 54 66 44 77
2
5 4
100 224 666 222
2

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

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

e-olymp 8544. Квадраты чисел

Задача

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

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

Одно натуральное число [latex]n[/latex] [latex](n \leqslant 10^9)[/latex]

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

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

Тесты

Входные данные Выходные данные
1 1
16 1 4 9 16
93 1 4 9 16 25 36 49 64 81
100 1 4 9 16 25 36 49 64 81 100

Код

Решение

Воспользуемся циклом, в котором заведем переменную [latex]i[/latex]  и будем перечислять числа [latex]1, 4, 9, …, i^2[/latex], пока [latex]i^2[/latex] не будет больше [latex]n[/latex]. Выводим последовательно квадраты натуральных чисел в одной строке.

Ссылки

Задача на e-olymp
Код решения на ideone

e-olymp 3873. Счастливый номер

Условие

Подавляющее большинство людей стараются найти закономерности, которые приносят удачу! Зуб акулы в ухе папуаса — к удачной рыбной ловле. Черная кошка, которая передумала перебегать вам дорогу — к отмене контрольной. Любимая игрушка у компьютера — к удаче в командном чемпионате по программированию.

Для большинства студентов несомненным является тот факт, что номер трамвайного билетика приносит удачу. А уж если такой билетик достался перед экзаменом, пятерка обеспечена! Главное тут — четко понимать, что такое счастливый билет. И почему, спрашивается, многие считают, что только номер автобусного или троллейбусного билета может приносить удачу своему владельцу?! Чем хуже, скажем, номер паспорта или номер кассового чека в гастрономе? Главное, чтобы номер был счастливым!

Витька всегда считал, что удачу приносят такие номера, в записи которых цифры идут в неубывающем порядке. Например, счастливыми являются номера $11111$ или $12345$. Даже номер $00000$ — тоже счастливый!

Интересно, сколько счастливых номеров существует для заданной длины записи числа? Напишите программу, которая это количество вычислит.

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

Входной файл содержит единственное целое число $N$, $(1 \leq N \leq 64)$, $N$ — длина числа, для которой нужно вычислить количество счастливых номеров.

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

Вывести одно число — количество счастливых номеров.

Тесты

Входные данные Выходные данные
1 2 55
2 4 715
3 3 220

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

Решение

Для того, чтобы решить эту задачу, я начертил таблички (рис. 1.1) для всех вариантов $2$ значного числа и $1$ значного (рис. 1.2). Для $3$ значного аналогично, только рядов будет $3$. Из комбинаторики мы помним формулу: $C_n^m=\frac{n!}{m!(n-m)!}$, из которой мы получим: $(n + 9)! \over {9! \times n!}$. Потому-что из картинки мы видим что при 1 значном числе количество вариантов равно $10$. В коде я сразу сокращал на $n!$, чтобы не получались огромные числа.

рис 1.1

рис 1.2

Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

e-olymp 8671. Представимые суммой квадратов

Задача

Найдите все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.

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

Одно натуральное число $n$ $( n \leqslant 10000)$.

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

Выведите в одной строке в возрастающем порядке все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.

Тесты

Входные данные  Выходные данные
1 5 5
2 10 5 10
3 13 5 10 13
4 20 5 10 13 17 20
5 30  5 10 13 17 20 25 26 29

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

Решение

Для решения задачи создадим функцию check(), которая будет выводить число, если его можно представить в виде суммы двух квадратов. В функции перебираем всевозможные варианты $i$ и считаем $j$ для каждого $i$ по формуле $j=\sqrt{n-i^2}$, до тех пор пока не найдем целое (не равное $i$ ) $j$ или же не переберем все $i$. Просматриваем до $ i \cdot i < n $,  потому что сумма двух квадратов не может превышать заданного числа. Формулу получили выразив $j$ из исходной формулы $(i^2+j^2=n)$.

Ссылки

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

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