e-olymp 908. Те, что делятся на 6

Задача: Те, что делятся на 6

Для [latex]N[/latex] целых чисел определить сумму и количество положительных чисел, которые делятся на 6 без остатка.

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

В первой строке задано количество чисел [latex]N[/latex]$\left(1 \leq N \leq 100\right)$, в следующей строке через пробел заданы сами числа, значения которых по модулю не превышают $10000$.

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

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

Тесты

Ввод Вывод

3

12 15 18

2 30
4

-10 -15 42 -24

1 42
2

6 0

1 6
3

-6 -12 -32

0 0

Решение

Заводим 2 переменные: сумму и количество. Каждый раз, когда мы читаем число, проверяем положительно ли оно и делится ли на 6 (Обычно желательно сначала проверять наимение вероятное условие, т.к. программа реже будет лишний раз проверять второе условие и, как следствие, сделает меньше действий, но в этой задачи это особой роли не играет из-за малого ввода), если оба условия выполняются, добавляем к счетчику 1, а к сумме введенное число. По окончанию ввода выводим сумму и количество через пробел.

Ссылки

e-olymp 8653. Прибавить вычесть и умножить

Задача

Пусть x — переменная, изначально равная 0. Промоделируйте выполнение следующих операций над ней:

  • add a: прибавить значение a к x;
  • subtract a: вычесть значение a из x;
  • multiply a: умножить x на a;

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

Каждая строка содержит операцию и значение. Промоделируйте все операции. Значение переменной x при выполнении каждой операции не превышает по модулю $10^9$.

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

Выведите результирующее значение переменной x.

Тесты

Ввод Вывод
1 add 2
subtract 5
subtract 1
multiply -3
12
2 subtract 5
multiply -5
add 5
30
3 add 6
add 543
multiply 23
12627
4 multiply 45678
add 3
3
5 subtract 58
add 38
multiply -1
add 100
120

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

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

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

Ссылки

e-olymp 8519. Сумма четных цифр

Задача взята с сайта e-olymp.

Задача

Задано длинное число. Найти сумму его четных цифр.

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

Одно натуральное число $n  (n ≤ 10^{100} )$.

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

Вывести сумму четных цифр числа $n$.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2345 6
2 3458937487534533459 32
3 888888888888888888888888888888 240

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

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

Переменная c — является переменной типа char, что означает, что cin в этом случае будет считывать по одному символу с потока. По этой причине, чтобы решить данную задачу, нужно считывать заданное число с помощью cin в цикле while до тех пор, пока происходит ввод данных с клавиатуры.  Проверяя каждую цифру введенного числа на четность, будем прибавлять четные к переменной sum.
Для работы с символом  c как с числом, будем писать c - '0'.

Ссылки

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

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

Сумма делителей — 2

Задача

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

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

Одно целое число $n \left(1 \leqslant n < 10^{15}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные Выходные данные
$100000000000031$ $100000000000032$
$10000019$ $10000020$
$400001520001444$ $700002730002667$
$9$ $13$
$304250263527210$ $1281001468723200$
$94083986096100$ $457766517350961$
$1234567898765$ $1517681442816$
$100000000000000$ $249992370597277$
$562949953421312$ $1125899906842623$
$81795$ $161280$
$9999999999999$ $14903272088640$
$997$ $998$
$1325$ $1674$
$2468013$ $3290688$
$951641320$ $2447078400$
$71675429738641$ $71695352830464$
$1100000000033$ $1200000000048$
$6300088$ $11859480$
$98$ $171$
$9102837465$ $15799834440$

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

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

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$
Для того, чтобы не вычислять $p_k^{\alpha_k+1}$, перепишем данную формулу в следующем виде:
$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$

Ссылки

Код решения

Сумма делителей

Задача

Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $n.$
Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу.

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

Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные Выходные данные
$12$ $28$
$239$ $240$
$1234$ $1854$
$6$ $12$
$1000000007$ $1000000008$
$44100$ $160797$
$223092870$ $836075520$
$2147483648$ $4294967295$
$678906$ $1471002$
$1111111$ $1116000$
$9876543210$ $27278469036$
$99460729$ $99470703$
$5988$ $14000$
$1$ $1$
$1348781387$ $1617960960$
$135792$ $406224$
$5402250$ $17041284$
$375844500$ $1259767236$
$1000000000$ $2497558338$
$2357947691$ $2593742460$

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

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

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$

Ссылки

Код решения

e-olymp 1128. Проблема Лонги

Задача

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:
Дано целое число [latex]n[/latex] [latex](1 < n < 231)[/latex], Вы должны вычислить [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].
"О, я знаю, я знаю!" — воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.

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

Каждая строка содержит одно число [latex]n[/latex].

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

Для каждого значения [latex]n[/latex] следует вывести в отдельной строке сумму [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].

Тесты

Входные данные Выходные данные
[latex]2[/latex] [latex]6[/latex] $3$
$15$
[latex]1[/latex] [latex]50[/latex] [latex]100[/latex] $1$
$195$
$520$
[latex]7[/latex] [latex]4791[/latex] [latex]12345678[/latex] [latex]478900[/latex] $13$
$15965$
$170994915$
$4980040$
[latex]123[/latex] [latex]7777[/latex] [latex]157423949[/latex] [latex]904573[/latex] $2147483648$ $405$
$54873$
$613124817$
$1809145$
$35433480192$

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

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

Согласно свойству НОД, если некоторые числа [latex]a_1[/latex] и [latex]a_2[/latex] взаимно просты, то [latex]\gcd \left(a_1 \cdot a_2, c\right) = \gcd \left(a_1, c\right) \cdot \gcd \left(a_2, c\right)[/latex], где [latex]c[/latex] — некоторая константа. Если же вместо [latex]c[/latex] взять [latex]i[/latex] ([latex] 1 ≤ i ≤ a_1 \cdot a_2[/latex]) и просуммировать по [latex]i[/latex] обе части равенства, получим:
[latex]\sum\limits_{i=1}^{a_1 \cdot a_2} \gcd \left(a_1 \cdot a_2, i\right) = \sum\limits_{i=1}^{a_1 \cdot a_2} \left(\gcd \left(a_1, i\right) \cdot \gcd \left(a_2, i\right)\right) = \sum\limits_{i=1}^{a_1} \gcd \left(a_1, i\right) \cdot \sum\limits_{i=1}^{a_2} \gcd \left(a_2, i\right)[/latex].
Значит мы можем данное число представить как произведение простых в некоторых степенях. Эти числа, очевидно, будут взаимно простыми, из чего следует возможность применения данного свойства и последующего суммирования по [latex]i[/latex].
Теперь докажем, что для любого простого числа [latex]p[/latex] в степени [latex]a\geqslant 1[/latex] верно следующее равенство:
[latex]\sum\limits_{i=1}^{p^a} \gcd\left(p^a, i\right) = \left(a + 1\right)\cdot p^a — a \cdot p^{a-1} [/latex].
Обозначим $\sum\limits_{i=1}^{r} \gcd\left(r, i\right)$ как $g\left(r\right)$.
База индукции:
[latex]a = 1[/latex]:
$$g\left(p\right) = \gcd\left(p, 1\right) + \gcd\left(p, 2\right) + \ldots + \gcd\left(p, p\right) = \left(p — 1 \right) + p = 2 \cdot p — 1.$$
Если [latex]a = 2[/latex]:
$$g\left(p^{2}\right) = \gcd\left(p^{2}, 1\right) + \gcd\left(p^{2}, 2\right) + \ldots + \gcd\left(p^{2}, p\right) + \gcd\left(p^{2}, p + 1\right) + \ldots + \\ + \gcd\left(p^{2}, 2 \cdot p\right) + \ldots + \gcd\left(p^{2}, p^{2}\right) = 1 + 1 + \ldots + p + 1 + \ldots + p + \ldots + p^{2} = \\ = \left( p^{2} — p \right) + p \cdot \left( p — 1 \right) + p^{2} = 3 \cdot p^{2} — 2\cdot p.$$
Для любых $a \geqslant 2$:
$$g\left(p^{a}\right) = \sum\limits_{j=1}^{p^{a-1}} \gcd\left(p^a, j\right) + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a, j\right) + p^{a} =g\left(p^{a — 1}\right) + p^{a} + \\ + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right).$$
Причем:
$$\sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right) = \sum\limits_{j=1}^{p^{a} — p^{a-1} — 1} \gcd\left(p^{a — 1}, j\right) = \\ = \sum\limits_{j=1}^{p^{a} — p^{a-1}} \gcd\left(p^{a — 1}, j\right) — p^{a — 1} = \left( p — 1\right)\cdot g\left(p^{a-1}\right) — p^{a-1}.$$
Откуда следует:
$$g\left(p^{a}\right) = p^{a} — p^{a-1} + p\cdot g\left(p^{a-1}\right).$$
Предположение индукции:
Пусть [latex]a = b[/latex]:
$$g\left(p^{b}\right) = \left(b + 1\right) \cdot p^b — b \cdot p^{b-1}.$$
Шаг индукции:
Пусть [latex]a = b + 1[/latex]:
$$g\left(p^{b + 1}\right) = p^{b + 1} — p^{b} + p\cdot g\left(p^{b}\right) = p^{b + 1} — p^{b} + p\cdot \left[\left(b+1\right) \cdot p^{b} + b\cdot p^{b-1}\right] = \\ = \left(b + 2\right)\cdot p^{b+1} — \left(b + 1\right)\cdot p^{b}.$$

Ссылки

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

e-olymp 520. Сумма всех

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]2[/latex] [latex]4[/latex] [latex]6[/latex]
2 [latex]3[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]9[/latex]
4 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex] [latex]10[/latex]
5 [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]

 

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

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

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 1000. Задача a + b

Задача

Вычислите сумму [latex]\textbf {a + b}[/latex].

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

В каждой строке задано два целых числа [latex]\textbf{a}[/latex] и [latex]\textbf{b}[/latex] ([latex] \bigl| \textbf {a} \bigr|, \bigl| \textbf {b} \bigr| \textbf {≤ 30000}[/latex]).

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

Для каждого теста выведите сумму [latex]\textbf {a + b}[/latex] в отдельной строке.

Тесты

Входные данные Выходные данные
$4$ $8$
$5$ $0$
$-6$ $8$
$12$
$5$
$2$
$-3$ $3$ $0$
$12$ $8$
$10$ $10$
$20$
$20$
$30000$ $30000$
$3000$ $3000$
$300$ $300$
$30$ $30$
$3$ $3$
$60000$
$6000$
$600$
$60$
$6$
$10$ $23$
$613$ $2$
$-200$ $300$
$33$
$615$
$100$

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

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

Пока вводятся пары чисел, они считываются и на экран выводится их сумма, затем курсор переходит на новую строку.

Ссылки

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

e-olymp 542. Поставка содовой воды

Задача

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

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

Три целых неотрицательных числа [latex]e[/latex], [latex]f[/latex], [latex]c[/latex], где [latex]e[/latex] ([latex]e < 1000[/latex]) — количество пустых бутылок, имеющихся у Тима в начале дня, [latex]f[/latex] ([latex]f < 1000[/latex]) — количество пустых бутылок, найденных в течение дня, и [latex]c[/latex] ([latex]1 < c < 2000[/latex]) — количество пустых бутылок, необходимых для покупки новой бутылки.

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

Сколько бутылок содовой воды смог выпить Тим, когда его замучила жажда?

Тесты

Входные данные Выходные данные
[latex]9[/latex] [latex]0[/latex] [latex]3[/latex] [latex]4[/latex]
[latex]5[/latex] [latex]5[/latex] [latex]2[/latex] [latex]9[/latex]
[latex]0[/latex] [latex]8[/latex] [latex]4[/latex] [latex]2[/latex]
[latex]22[/latex] [latex]0[/latex] [latex]4[/latex] [latex]7[/latex]

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

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

Можно считать, что изначально у Тима имеется [latex]e+f[/latex] пустых бутылок. Допустим, у него есть хотя бы [latex]c[/latex] бутылок, необходимых для покупки новой, Тим идет и меняет их на одну полную бутылку. Затем выпивает её, после чего общее количество пустых у него уменьшается на [latex]c-1[/latex]. То есть за [latex]e+f[/latex] пустых бутылок он сможет выпить [latex]\frac{e+f}{c-1}[/latex] бутылок содовой воды. Нам также следует добавить к [latex]c-1[/latex] маленькую константу [latex]a = 0.0001[/latex] для корректировки значения, чтобы в случае когда количество бутылок кратно [latex]c-1[/latex], Тиму нельзя было взять новую бутылку с недостающим количеством пустых бутылок для этого, следовательно, он должен выпить на одну бутылку меньше. В результате выводим целое число бутылок содовой воды, которые Тим смог выпить, когда его замучила жажда.

Ссылки

Условие задачи на e-olymp
Код решения на ideone

e-olymp 1210. Очень просто!!!

Задача

По заданным числам [latex]n[/latex] и [latex]a[/latex] вычислить значение суммы: [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex]

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

Два натуральных числа [latex]n[/latex] и [latex]a[/latex].

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

Значение суммы. Известно, что оно не больше [latex]10^{18}[/latex].

Тесты

Входные данные Выходные данные
3 3 102
4 4 1252
9 3 250959
7 14 785923166
1009 1 509545

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

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

Данную задачу можно решить прямым линейным вычислением значений элементов заданного ряда, то есть получать значение элемента ряда с индексом [latex]i[/latex] умножением [latex]a[/latex] (которое необходимо возвести в степень [latex]i[/latex]) на индекс [latex]i[/latex] и накапливать сумму этих значений в выделенной переменной.
Но безусловно такое решение не является качественным (даже если будет использован алгоритм бинарного возведения в степень).

Для получения качественного решения распишем ряд подробно:
[latex]A[/latex] [latex]=[/latex] [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex] [latex]=[/latex] [latex]a+2a^2+3a^3+\ldots+\left( n-1 \right) a^{n-1}+na^{n}[/latex] [latex]=[/latex] [latex]na^{n}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-1}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{3}[/latex] [latex]+[/latex] [latex]2a^2[/latex] [latex]+[/latex] [latex]a[/latex].
Очевидно, что из полученного выражения можно вынести [latex]a[/latex] за скобки. Применим данную операцию:
[latex]A[/latex] [latex]=[/latex] [latex] \left( na^{n-1}+\left( n-1 \right)a^{n-2}+\ldots+3a^{2}+2a+1\right) \cdot a[/latex]
Из полученной формулы видно, что аналогичное действие можно применить вновь, для внутреннего выражения [latex]na^{n-1}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-2}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{2}[/latex] [latex]+[/latex] [latex]2a[/latex]. Получим:
[latex]A[/latex] [latex]=[/latex] [latex] \left( \left( na^{n-2}+\left( n-1 \right)a^{n-3}+\ldots+3a+2 \right) \cdot a +1 \right) \cdot a[/latex].
После конечного количества вынесений за скобки, получим:
[latex]A[/latex] [latex]=[/latex] [latex]\left( \left( \ldots \left( \left(na+\left(n-1\right)\right) \cdot a + \left(n-2\right) \right) \ldots+2\right) \cdot a +1\right) \cdot a[/latex].

Таким образом, решение данной задачи сводится к вычислению суммы «изнутри» скобок.

Но из-за того, что в условии подано ограничение только на сумму, программа с реализованным вычислением суммы изнутри и асимптотикой [latex]O \left( n \right)[/latex] не пройдёт все тесты системы www.e-olymp.com в силу частного случая [latex]a = 1[/latex], так как значение [latex]n[/latex] может быть для него достаточно большим, ибо числа [latex]a[/latex] и [latex]n[/latex] компенсируют друг-друга по отношению к максимальному значению суммы. Но в случае [latex]a = 1[/latex] сумма данного ряда является суммой арифметической прогрессии, а именно — натурального ряда. Для вычисления этой суммы существует формула [latex]\sum\limits_{i=1}^{n} {i} = \frac{n \left( n+1 \right)}{2}[/latex]. Этот частный случай легко отсеять.

Асимптотика программы: [latex]const[/latex] при [latex]a = 1[/latex], и [latex]O \left( n \right)[/latex] иначе.

Ссылки

e-olymp 4496. Приключение Незнайки и его друзей

Задача с сайта e-olymp.com.

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

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

В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.

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

В первой строке содержится количество человечков [latex]n (1 ≤ n ≤ { 10 }^{ 6 })[/latex] в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают [latex]{ 10 }^{ 9 }[/latex]. Далее следует количество запросов [latex]m (1 ≤ m ≤ { 10 }^{ 5 })[/latex]. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число [latex]v (1 ≤ v ≤ { 10 }^{ 9 })[/latex] – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа [latex]x (1 ≤ x ≤ n)[/latex] и [latex]y (1 ≤ y ≤ { 10 }^{ 9 })[/latex] — это значит, что вес человечка, стоящего на позиции [latex]x[/latex], теперь равен [latex]y[/latex].

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

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

Тесты

Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
3
2
2
0
2 2
1 2
3
1 4
2 1 10
1 4
2
0
3 2
999999999 1000000000
4
1 999999999
2 1 1000000000
1 999999999
1 1000000000
1
0
1

Код на C++

Код на Java

Описание

В данной задаче требуется эффективно выполнять две операции: изменять значение одного из элементов массива и находить, сколько человечков поместится в шар при заданной грузоподъёмности. Это было реализовано при помощи структуры segment_tree. В функции main сначала вводится значение n и заполняется массив весов человечков weights, после чего по нему выполняется построение дерева отрезков tr. В его вершинах хранятся частичные суммы элементов массива. Да и в целом функции для построения и выполнения запроса модификации у него такие же, как и у обычного дерева отрезков для нахождения суммы на отрезке. Для удобства в массиве weights и в самом дереве используются элементы с первого по [latex]n[/latex]-й, а не с нулевого по [latex]\left( n-1 \right) [/latex]-й. Далее в ходе работы функции main в цикле выполняется обработка запросов. Сначала вводится тип запроса type. Если запрос второго типа, вводятся позиция человечка x, его новый вес y и вызывается метод update, пересчитывающий значения суммы в вершинах, на которые влияет это изменение. Иначе вводится грузоподъемность воздушного шара v и вызывается метод find_numb_of_p, который находит количество человечков, поместившихся в шар. Работает он следующим образом: если выполняется условие tree_l == tree_r, значит, рассматриваемый отрезок состоит из одного элемента, и функция возвращает [latex]1[/latex], если человечек может поместиться в шар, и [latex]0[/latex], если он слишком тяжёлый. Если отрезок больше, вычисляется индекс элемента, находящегося посередине tree_m. Далее, если сумма весов человечков в левом поддереве tree[v*2] больше, чем грузоподъёмность шара, то никто из правого поддерева уже не поместится, и искать следует только в левом поддереве. Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно tree_m - tree_l + 1) и посмотреть, сколько поместится человечков из правого поддерева. При этом необходимо от максимально допустимого веса отнять вес человечков из левого поддерева, уже сидящих в шаре ( max_w-tree[v*2]).

Код на ideone.com. (C++)
Засчитанное решение на e-olymp.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.com. (Java)
При решении задачи был использован материал с сайта e-maxx.ru.

e-olymp 3358. Чёрный ящик

Задача

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

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

Первая строка содержит количество событий [latex]n[/latex] [latex]\left(1 \le n \le 2 \times 10^{5} \right)[/latex]. Каждая из следующих n строк содержит описание одного события:

  • [latex]+ x[/latex] — положен листок с числом [latex]x[/latex] [latex]\left(1 \le x \le 10^{6} \right)[/latex];
  • [latex]- x[/latex] — исчез листок с числом [latex]x[/latex] (гарантируется, что в ящике был хотя бы один листок с числом [latex]x[/latex]).

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

Вывести в точности [latex]n[/latex] строк — по одной для каждого события. Каждая строка должна содержать одно число — ответ к задаче. Если после какого-то события ящик оказался пуст, следует вывести [latex]0[/latex].

Тесты

Входные данные Выходные данные
3
+ 1
— 1
+ 2
1
0
2
6
+ 1
+ 1000000
— 1
+ 4
+ 4
— 1000000
1
1
1000000
4
4
4
8
+ 71
+ 91
+ 99
+ 71
— 71
— 91
— 71
— 99
71
71
71
71
71
71
99
0

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

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

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

«Даётся последовательность (массив) объектов leaf [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]\ldots[/latex], [latex]x_{999999}[/latex], [latex]x_{1000000}[/latex], представляющих из себя пару (number, amount)[latex]=x_{i}=\left(i, a_{i}\right) \in {\mathbb{N}_{0}}^{2}[/latex], где первые элементы пар [latex]i[/latex] представляет из себя число/номер листка, а вторые элементы [latex]a_{i}[/latex] — число листков с этим номером. Изначально все элементы пар [latex]a_{i}[/latex] равны нулю (так как изначально ящик пуст). Для запросов первого типа [latex]+ x[/latex] необходимо увеличивать на единицу число [latex]a_{i}[/latex] объекта, у которого номер [latex]i[/latex] равен [latex]x[/latex], а для запросов второго типа — уменьшать. Для каждого запроса необходимо вывести число [latex]j[/latex], удовлетворяющее условию [latex]j = \min\limits_{i \in \mathbb{K}}{i}[/latex], где [latex]\mathbb{K} = \{i \mid a_{i} = \max\limits_{k \in \{1, 2, \ldots, 1000000\}}{a_{k}} \}[/latex]».

Иными словами, число [latex]i[/latex] соответствует некоторому элементу [latex]x_{i} = \left(i, a_{i}\right)[/latex], который в свою очередь определяется операцией такой, что [latex]i[/latex] и [latex]a_{i}[/latex] удовлетворяют приведённым выше условиям. Очевидно, что данная операция является ассоциативной (как объединение минимума и максимума на заданных множествах), а потому для решения задачи воспользуемся универсальным деревом отрезков.

Создадим дерево отрезков box методом read_and_construct из объектов leaf. Так как нумерация листков начинается с единицы, а их число не превышает [latex]10^{6}[/latex], зададим размер базы дерева отрезков [latex]10^{6}+1[/latex], добавив неё элемент с индексом [latex]0[/latex]. Модифицируем метод read_and_construct таким образом, чтобы в функцию-препроцессор передавался номер элемента [latex]i[/latex], дабы была возможность задавать элементам [latex]x_{i}[/latex] их первоначальные значения [latex]\left(i, 0\right)[/latex]. Вышеупомянутую операцию назовём max_leafs и определим таким образом, чтобы она принимала два аргумента [latex]x_{i} = \left(i, a_{i}\right)[/latex] и [latex]x_{j} = \left(j, a_{j}\right)[/latex] и возвращала тот из них, у которого значение [latex]a[/latex] является большим, а в случае равенства этих значений — аргумент с меньшим индексом. Нейтральным элементом относительно данной операции будет, очевидно, пара [latex]\left(+\infty, 0\right)[/latex], но в силу того, что номера элементов не превышают [latex]10^6[/latex], вместо неё мы будем пользоваться парой [latex]\left(2 \times 10^{6}, 0\right)[/latex].

Далее при запросах вида [latex]+ x[/latex] будем увеличивать соответствующее значение [latex]a_{x}[/latex] пары [latex]\left(x, a_{x}\right)[/latex] на единицу, а при запросах вида [latex]- x[/latex] — уменьшать. Для обоих запросов будем выводить номер заданного листка, который удовлетворяет приведённым в задаче условиям, с использованием метода result_on_segment на всём отрезке [latex]\left[0, 10^{6}\right][/latex]. Ответом для каждого запроса будет значение number пары, которую вернёт метод.

Примечание: ситуация когда ящик становится пустым нигде не обрабатывается, но в силу того, что мы определили массив на отрезке [latex]\left[0, 10^{6}\right][/latex] вместо [latex]\left[1, 10^{6}\right][/latex] в нём всегда есть пара [latex]\left(0, 0\right)[/latex] (листки с номером [latex]0[/latex], число (значение [latex]b[/latex]) которых всегда равно [latex]0[/latex] в силу того, что листки с номером [latex]0[/latex] в ящик не добавляются). Так как определённая нами операция всегда возвращает минимальный номер листка, число которого максимально, то в случае, когда ящик пуст (т.е. значения всех [latex]a_{i} = 0, i = 0, 1, \ldots, 10^{6}[/latex]) будет выводится номер листка [latex]0[/latex]. Этот побочный эффект данного нами определения массива решает эту ситуацию и завершает решение задачи.

Ссылки

MS2. Сумма чисел во входном потоке

Условие

Сосчитайте сумму чисел во входном потоке.

Тесты

Ввод
Вывод
1 2 3 4 5 6 21
12 13 14 39
1-100

5050

Решение

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

Код на ideone C++
Код на ideone Java

Просто RSQ

Задача RSQ (Range Sum Query). Вам дан массив, необходимо отвечать на запросы получения суммы на отрезке и изменение одного элемента массива.

Ссылка на задачу на codeforces.com.

Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Ограничение по памяти: 2 секунды
Ограничение по времени: 256 мегабайт

Формат входного файла

Входной файл в первой строке содержит два числа [latex]n[/latex] [latex]\left(1 \le n \le 10^{5} \right)[/latex] — размер массива и [latex]m[/latex] [latex]\left(1 \le m \le 10^{5} \right)[/latex] — количество запросов. Во второй строке задано начальное состояние массива [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex] [latex]\left( -10^{5} \le a_{i} \le 10^{5} \right)[/latex].

Далее идёт [latex]m[/latex] строк с запросами вида [latex]t[/latex] [latex]x[/latex] [latex]y[/latex] [latex]\left( 0 \le t \le 1 \right)[/latex]. Если [latex]t = 0[/latex], тогда на запрос нужно вывести сумму элементов массива с индексами от [latex]x[/latex] до [latex]y[/latex] (в данном случае [latex]1 \le x \le y \le n[/latex]). Если [latex]t = 1[/latex], тогда надо присвоить элементу массива с индексом [latex]x[/latex] значение [latex]y[/latex] (в этом случае [latex]1 \le x \le n[/latex], [latex]-10^{5} \le y \le 10^{5}[/latex]).

Формат выходного файла

На каждый запрос суммы отрезка выведите одно число в новой строке — запрашиваемая сумма.

Примеры

rsq.in rsq.out
5 3
1 2 3 4 5
0 1 5
1 1 -14
0 1 5
15
0
8 2
7 3 -10 4 1 2 5 6
0 2 4
0 5 7
-3
8

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

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

Основная идея приведённого выше решения этой задачи заключается в оптимизации обработки запросов суммы построением дерева отрезков.
Сохраним сумму всех элементов массива в переменной sum. Теперь, если нам дан запрос суммы на отрезке [latex]\left[ x; y \right][/latex], то если [latex]y — x > \frac{n}{2}[/latex] (то есть если данный отрезок содержит больше элементов, чем половина всего отрезка) то считаем сумму элементов на отрезке [latex]\left[ 1; x-1 \right] \cup \left[ y+1; n \right] = \left[ 1; n \right] \setminus \left[ x; y \right][/latex] и отнимаем от суммы всех элементов, иначе (если [latex]y — x \le \frac{n}{2}[/latex], то) просто считаем сумму элементов на отрезке [latex]\left[ x; y \right][/latex]. Если же поступает запрос на замену значения элемента, то вычитаем из sum старое значение и прибавляем новое.

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

Ссылки

D2574. Сумма ряда

Задача

Найти сумму сходящегося ряда: [latex]\sum \limits_{n=1}^{n}\frac{\sin{nx}}{2^{n}}[/latex].

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

[latex]n[/latex] — количество шагов;
[latex]x[/latex] — значение [latex]x[/latex].

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

Сумма ряда [latex]\sum \limits_{n=1}^{n}\frac{sin(nx)}{2^{n}}[/latex].

Тесты

Входные данные Выходные данные
[latex]n[/latex] [latex]x[/latex]
10 0.523598 0.651170
25 3.141592 0
15 1.570796 0.399994

Код программы на C++

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

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone на C++;
Ideone на Java;
WolframAlpha.

A320. Вложенный цикл

Задача

Вычислить [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

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

Произвольные [latex]n[/latex]
и [latex]m.[/latex]

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

Значение [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

Тесты

Входные данные Выходные данные
[latex]n[/latex] [latex]m[/latex]
10 15 983455
2 5 150
3 6 816

Код программы на C++

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

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone C++;
Ideone Java;
WolframAlpha.

A322. Максимальная сумма делителей

Задача. Найти натуральное число с максимальной суммой делителей на заданном промежутке.

Входные данные:
— [latex]n[/latex] — промежуток чисел(от 1 до [latex]n[/latex]);

Выходные данные:
— [latex]max[/latex] _ [latex]sum[/latex] — максимальная сумма делителей числа на этом промежутке;
— [latex]max[/latex] _ [latex]number[/latex] — натуральное число с этой суммой;

Тесты:

[latex]n[/latex] [latex]max[/latex] _ [latex]number[/latex] [latex]max[/latex] _ [latex]sum[/latex]
100 96 252
8743 8400 30752
23000 22680 87120

Код на языке C++:

Код на языке Java:

Решение задачи:
Для нахождения суммы делителей используется функция [latex]sum[/latex] _ [latex]dividers[/latex], которая в созданном цикле сначала находит все делители числа, а после суммирует их, присваивая значение переменной [latex]sum[/latex]. Создав в главной функции [latex]main[/latex] еще один цикл со счетчиком от 1 до [latex]n[/latex], подставляю в предыдущую функцию [latex]sum[/latex] _ [latex]dividers[/latex] все натуральные числа на выбранном промежутке. C помощью свободных переменных [latex]max[/latex] _ [latex]sum[/latex] и [latex]max[/latex] _ [latex]number[/latex] нахожу максимальное значение сумм и соответствующее ему натуральное число.

Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 322

A334(б). Сумма в сумме

Условие

Вычислить [latex]\sum\limits _{ i=1 }^{ k }{ \sum\limits _{ j=1 }^{ t }{ \sin { ({ i }^{ 3 }+{ j }^{ 4 }) } } } [/latex] .

Решение

В данной задаче нам необходимо сделать два цикла, а конкретней — цикл в цикле.

Тесты

[latex]k[/latex] [latex]t[/latex] [latex]S[/latex]
1 1 0.9092
10 15 1.4908
20 30 8.8956
60 100 41.9133

Воспользуемся веб-приложением и посчитаем сумму ряда.

Ссылки

Задачник Абрамова
Код на ideone

A334(а). Вложенная сумма

Задача

Вычислить: [latex]\sum \limits_{i=1}^{m}\sum \limits_{j=1}^{n}\frac{1}{i+j^2}[/latex], где [latex]m,n[/latex] — вводимые нами числа.

Тесты

Вход([latex]m,n[/latex]) Выход([latex]S[/latex])
40 20 13.6458
100 50 24.6458
200 25 31.7764
1000 282 89.8078

Код на C++

Код на Java

 

 

Решение

Вводим два оператор цикла for, один вложенный в другой. Задаем наше выражение, а затем суммируем его, согласно циклу.

Ссылки

  1. Задание из сборника Абрамова
  2. Решение на C++
  3. Решение на Java
  4. Результат на WolframAlpha

 

D2548. Сходимость и сумма ряда

Условие

Доказать сходимость ряда и найти его сумму
[latex]\frac { 1 }{ 2 } + \frac { 3 }{ 4 } + \frac { 5 }{ 8 } + \ldots + \frac { 2n-1 }{ { 2 }^{ n } } + \ldots [/latex]

Решение

Для начала докажем, что наш ряд сходится. Докажем это, через признак Даламбера. Суть этого признака заключается в том, что если предел отношения последующего члена к предыдущему меньше [latex]1[/latex](или в частных случаях равен [latex]0[/latex]) то данный ряд будет сходится.
Берем отношение последующего и предыдущего [latex]\lim\limits_{ n\to \infty } \frac { \frac{ 2(n+1)-1 }{ { 2 }^{ n+1 } } }{ \frac{ 2n-1 }{ { 2 }^{ n } } }[/latex] превратим нашу 4-х этажную дробь в 2-х этажную [latex]\lim\limits _{ n\to \infty } \frac { ({ 2(n+1)-1){ 2 }^{ n } } }{ { (2n-1 }){ 2 }^{ n+1 } }[/latex] раскроем скобки и применим свойство степеней, получим [latex] \lim\limits _{ n\to \infty } \frac { (2n+2-1){ 2 }^{ n } }{ (2n-1){ 2 }^{ n }2 }[/latex] далее приведем подобные сократим дробь и снова раскроим скобки, получим [latex]\lim\limits _{ n\to \infty } \frac { 2n+1 }{ 4n-2 } [/latex] далее чтобы перейти непосредственно к пределу разделим коэффициенты при старших степенях числителя на знаменатель, в ответе получаем [latex]\frac { 2 }{ 4 }[/latex] [latex]=[/latex] [latex]\frac { 1 }{ 2 }[/latex].
[latex]\frac { 1 }{ 2 }[/latex] [latex]<[/latex] [latex]1[/latex] из этого следует что данный ряд сходится!
Далее найдем сумму это ряда. [latex]\sum\limits_{ n=1 }^{ \infty } { \frac { 2n-1 }{ { 2 }^{ n } } }[/latex] Воспользуемся веб-приложением и посчитаем сумму ряда.

Тесты

[latex]n[/latex] сумма [latex]n[/latex] элементов
1 0.5
2 1.25
3 1.875
23 2.99999
24 3

Код на ideone C++
Код на ideone Java