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 15. Мышка и зернышки

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

В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 1 х 1, на каждую из которых высыпано от 0 до k зернышек (k ≤ 30000). Размеры пола m х n. Мышка выбегает из левого нижнего угла пола храма и двигается к входу в другую норку, расположенную в противоположном углу. Мышка может двигаться только вправо или вперед, собирая все зернышки с плитки, на которой она находится.

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

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

Первая строка содержит числа m и n – размеры пола (1 ≤ m, n ≤ 100). Далее идет m строк, начиная сверху, в каждой из которых размещено n чисел – количество зернышек на соответствующей плитке.

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

Вывести маршрут движения мышки в формате: RRFFFRF (F – шаг вперед, R – шаг вправо).

Тесты:

Входные данные Выходные данные
2 3
3 2 4
1 5 1
RFR
4 4
34 5 7 8
7 8 9 23
1 2 909 54
3 4 8 0
RRFRFF
7 8
23 4 7 8 94 23 5 6
2 9 7 56 83 5 44 2
1 2 3 4 5 6 7 8
8 7 6 5 4 32 2 1
90 87 3 5 4 3 2 5
28 75 60 94 33 3 2 7
76 92000 402 28 3 2 11 200
RFRRFFFFRFRRR

Код на С++:

Код на Java:

Описание решения задачи:

Представим пол индийского храма в виде двумерного массива. Т.к по условию движение мышки начинается с левого нижнего угла, при заполнении произойдет сдвиг, где позиция с изначальным номером [latex][n-1][0][/latex] примет позицию под номером [latex][0][0][/latex] и так далее пока данный сдвиг не достигнет плитки с номером [latex][n-1][0][/latex], где станет клеткой [latex][n-1][m-1][/latex]. Далее с помощью обхода в несколько циклов пересчитаем ячейки массива [latex]X[/latex] так, чтобы [latex]X[i][j][/latex] содержало максимальное количество зернышек, которое можно собрать по достижении плитки [latex](i, j)[/latex]. Переместимся в конец массива, в позицию под номером [latex]X[n-1][m-1][/latex]. Двигаясь в начальную клетку по закону, что предыдущая клетка слева или снизу должна содержать максимальное количество зернышек из всех возможных путей мыши, записываем в строку соответствующую букву, которая указывает на сделанный ход. По достижению цели мы получаем строку почти с готовым ответом. Перевернем ее, и теперь она указывает правильный путь не с конца в начало, а с начала в конец, что и требовалось. Выведем ответ.

Код задачи на с++
Код задачи на Java
Засчитанное решение на C++
Засчитанное решение на Java

e-olymp 1281. Простая задачка Шарика

Задача
Ещё задолго до того, как Шарик нашёл умную книжку, утерянную Печкиным, когда он только начинал свои эксперименты по распиливанию шахматных досок, когда ещё на шахматной доске белые поля были белыми, а чёрные – чёрными, он задал одну из своих первых задачек Матроскину.

«Сколько разных последовательностей длины [latex]n[/latex] можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд»?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

Входные данные
Длина последовательности [latex]n[/latex] ([latex]n ≤ 64[/latex]).

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

Тесты

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

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

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

Решение
Для решения задачи воспользуемся рекуррентным соотношением [latex]f \left( n \right) = f \left( n-1 \right)+f \left( n-2 \right)+f \left( n-3 \right)[/latex], где [latex]f[/latex] — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины 1, 2, и 3 соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения [latex]f \left( n \right)[/latex] при [latex]n \le 3[/latex] можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.

Ссылки
Код на ideone.com (C++)
Код на ideone.com (Java)
Задача с сайта e-olymp.com.
Засчитанное решение.

e-olymp 5062. Максимальный подпалиндром

Задача

Из данной строки удалите наименьшее количество символов так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).

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

Непустая строка длиной не более [latex]100[/latex] символов. Строка состоит только из заглавных латинских букв.

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

Вывести строку-палиндром максимальной длины, которую можно получить из исходной вычёркиванием нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.

Тесты

 №  Входные данные  Выходные данные
 1 QWEERTYY YY
 2  QWEERT EE
 3 BAOBAB BAOAB
 4  ABCDCBA  ABCDCBA

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

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

Решение

Так как палиндром читается одинаково как справа налево, так и слева направо, то максимальным подпалиндромом будет наибольшая общая подстрока двух строк: исходной строки [latex]s_1[/latex] и этой же строки, но записанной в обратном порядке [latex]s_2[/latex] (как, если бы мы её читали справа налево). Для нахождения их наибольшей общей подстроки следует заполнить таблицу [latex]D[/latex] размером [latex] (n+1)\times(n+1) [/latex], где [latex]n[/latex]-длина строки. Заполнять таблицу будем методом аналогичным поиску длины наибольшей общей подстроки, но в каждой ячейке [latex]D_{i j}[/latex] таблицы будем хранить наибольшую подстроку строки, содержащей только первые [latex]i[/latex] символов [latex]s_1[/latex], и строки, содержащей только [latex]j[/latex] первых символов [latex]s_2[/latex]. В ячейках [latex]D_{0 j}[/latex] и [latex]D_{i 0}[/latex] будем хранить пустые строки. Если [latex]i[/latex]-й символ строки [latex]s_1[/latex] равен [latex]j[/latex]-ому символу строки [latex]s_2[/latex], то в ячейку [latex]D_{i j}[/latex] запишем конкатенацию строки из ячейки [latex]D_{i-1 j-1}[/latex] и данного символа. Иначе в ячейке [latex]D_{i j}[/latex] будем хранить наибольшую из строк [latex]D_{i-1 j}[/latex] и [latex]D_{i j-1}[/latex]. Таким образом в ячейке [latex]D_{n n}[/latex] будет хранится наибольший подпалиндром исходной строки.

Ссылки

e-olymp 1285. Деление Гольдбаха

Задача

Широко известна проблема Гольдбаха! Вот одна из её версий:

  • Любое нечетное число больше [latex]17[/latex] можно записать в виде суммы трёх нечётных простых чисел;
  • Любое чётное число больше [latex]6[/latex] можно записать в виде суммы двух нечётных простых чисел.

Если число чётное, то мы раскладываем его на суммы двух простых разных нечётных, а если нечётное — то на суммы трёх простых разных нечётных. Такой способ разложения для заданного [latex]N[/latex] назовём делением Гольдбаха и обозначим как [latex]G\left( N \right)[/latex].
Зная заданное число [latex]N[/latex], найти [latex]\left| G\left( N \right) \right| [/latex], т.е. количество различных [latex]G(N)[/latex].

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

Входные данные содержат несколько тестовых случаев.
Каждый тест в отдельной строке содержит одно единственное число [latex]N \left( 1\le N\le 20000 \right) [/latex].
Ввод продолжается до конца входного файла.

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

Для каждого тестового случая вывести в отдельной строке одно число — найденное значение [latex]\left| G\left( N \right) \right| [/latex].

Тесты

 №  Входные данные  Выходные данные
 1 5
8
18
19
20
0
1
2
1
2
 2 13
22
78
4
150
0
2
7
0
12
 3 2000 37
 4 6
8
17
19
337
0
1
0
1
195

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

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

Решение

Поместим все тестовые случаи в вектор и найдём максимальное из данных чисел — [latex]max[/latex]. Затем найдём все нечётные простые числа меньшие [latex]max[/latex] (единственное чётное простое число — [latex]2[/latex]). Заведём массив размером [latex]max+1[/latex], [latex]i[/latex]-м элементом которого будет [latex]\left| G\left( i \right) \right| [/latex]. Тогда, если [latex]i[/latex]- чётное, то одно из слагаемых суммы [latex]a_{i}+b_{i}[/latex] двух простых разных нечётных чисел будем подбирать из найденных ранее простых нечётных чисел, но строго меньших [latex]\frac { i }{ 2 } [/latex], чтобы разбиения, отличающиеся только порядком следования частей считать равными, и выполнялось неравенство [latex]a_{i}\neq b_{i}[/latex]. Если разность [latex]i[/latex] и подобранного таким образом числа — нечётное простое число, то это деление Гольдбаха, тогда увеличиваем на единицу [latex]\left| G\left( i \right) \right| [/latex]. Если [latex]i[/latex] — нечётное, то [latex]a_{i}[/latex]из суммы [latex]a_{i}+b_{i}+c_{i}[/latex] трёх простых разных нечётных чисел будем подбирать из всех простых нечётных чисел строго меньших [latex]i[/latex]. Разностью [latex]i[/latex] и подобранного числа [latex]a_{i}[/latex] (разность двух нечётных) будет чётное число [latex]j[/latex], [latex]\left| G\left( j \right) \right| [/latex] мы уже нашли ранее. Тогда можем представить [latex]\left| G\left( j \right) \right| [/latex] различных разложений [latex]G\left( i \right)[/latex] в виде [latex]a_{i}+G\left( j \right)_{k}[/latex] или [latex]a_{i}+{a_j}_{k}+{b_j}_{k}[/latex], где [latex]k=\overline { 1,\left| G\left( j \right)  \right|  }  [/latex], a [latex]G\left( j \right)_{k}[/latex] — [latex]k[/latex]-е разбиение числа [latex]j[/latex]. Значит все полученные [latex]\left| G\left( j \right) \right| [/latex] будем прибавлять к [latex]\left| G\left( i \right) \right| [/latex], а чтоб избежать ситуаций [latex]a_i={a_j}_k[/latex] и [latex]a_i={b_j}_k[/latex], если [latex]i-2a_{i}[/latex] — простое число не равное [latex]a_{i}[/latex] (то есть при некотором значении [latex]k[/latex] одно из чисел [latex] G\left( j \right)_{k} [/latex] равно [latex]a_{i}[/latex] и не равно второму числу, так как [latex]{a_{j}}_k\neq {b_{j}}_k[/latex] мы учли ранее), то будем отнимать единицу от [latex]\left| G\left( i \right) \right| [/latex]. В разбиениях [latex]j[/latex] мы не учитываем порядок следования частей. Чтобы не учитывать его в и разбиениях числа [latex]i[/latex], разделим полученный результат [latex]\left| G\left( i \right) \right| [/latex] на [latex]3[/latex].

Ссылки

Вычисление математических выражений

Условие задачи:
Пусть дана строка, которая является математическим выражением, содержащим числа, переменные и различные операции. Требуется вычислить его значение.

Помимо создания прототипа работы элементарного калькулятора, рассмотрим решение одной из подзадач — «Многочлен», найденную на просторах сайта e-olymp.

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

В первой строке входного файла записано математическое выражение. Между операндами используются бинарные операторы ([latex]+[/latex], [latex]–[/latex], [latex]\ast[/latex], [latex]/[/latex], [latex]\wedge[/latex]) и унарный знак ([latex]–[/latex]). Если данное выражение представляет собой многочлен, то каждый одночлен записывается как [Коэффициент*]x[^Степень] или [Коэффициент], где [Коэффициент] — натуральное число, не превосходящее 100, x — символ переменной (всегда маленькая латинская буква [latex]x[/latex]), [Степень] — натуральное число, не превосходящее 4. Параметры, взятые в квадратные скобки, могут быть опущены. Во второй строке будет записано одно целое число — значение x. Все числа в исходном файле по модулю не превосходят 100. Количество одночленов не более 10 (могут быть одночлены одинаковой степени).

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

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

Тесты:

Входные данные Выходные данные
16-(4^3+52/2) -74
-2+x^1-3*x^2+x^2+100*x^3-2*x -7 -34393
-2*x^2+16*x^3-x (-3)^4 8489853
x^2-5*x+15-8*x^4 0 15

Код на с++:

Описание решения задачи:

В основе решения данной задачи лежит алгоритм, который переводит математические выражения в обратную польскую нотацию, что в дальнейшем позволяет решать данные выражения. Особенностью данной записи, в отличие от привычных нам, является постфиксная форма представления, где операторы математической формулы размещены после своих операндов.
Рассмотрим само решение. На входе программа получает две строки: одна из них представляет само математическое выражение/многочлен — [latex]formula[/latex] и при необходимости вторую — [latex]x[/latex], где передается значение переменной, использованной в многочлене. Если же на вход поступил не многочлен, данная строка сразу же идет на преобразование из инфиксной формы(оператор размещен между операндами) в постфиксную. В ином случае, с помощью встроенных библиотечных функций класса [latex]string[/latex] мы заменяем все переменные на вторую строку [latex]x[/latex] и выполняем точно такую же работу. Разберем ближе сам алгоритм преобразования строки и ее подсчета. Заведём два стека: [latex]value[/latex] — для чисел, [latex]op[/latex] — операций и скобок. Для второго стека является основным предусловие, что все операции упорядочены в нём по строгому убыванию приоритета, если двигаться от вершины стека. Будем идти слева направо по выражению в обратной польской нотации; если текущий элемент — число, то кладём на вершину стека [latex]value[/latex] его значение; если же текущий элемент — операция, то достаём из стека два верхних элемента (или один, если операция унарная), применяем к ним операцию, и результат кладём обратно в стек. Итого в [latex]value[/latex] останется один элемент — значение выражения.

Код задачи на с++
Засчитанное решение на e-olymp