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

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

Представим пол индийского храма в виде двумерного массива. Т.к по условию движение мышки начинается с левого нижнего угла, при заполнении произойдет сдвиг, где позиция с изначальным номером [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]. Двигаясь в начальную клетку по закону, что предыдущая клетка слева или снизу должна содержать максимальное количество зернышек из всех возможных путей мыши, записываем в строку соответствующую букву, которая указывает на сделанный ход. По достижению цели мы получаем строку почти с готовым ответом. Перевернем ее, и теперь она указывает правильный путь не с конца в начало, а с начала в конец, что и требовалось. Выведем ответ.

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

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

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

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

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

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

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

Тесты

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

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

Решение
Для решения задачи воспользуемся рекуррентным соотношением [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
Задача с сайта 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

e-olymp 7447. Обрезка строки

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

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

Имеется строка [latex]s[/latex]. Разрешается взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. Сначала Вы можете выбрать любое количество символов в строке и удалить их. Определить наименьшее количество символов, которое Вы можете удалить сначала так, чтобы затем выполняя разрешенную операцию, получить пустую строку.

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

Содержит строку [latex]s[/latex] ([latex]1 ≤[/latex] длина[latex]\left( s \right) [/latex] [latex]≤ 100)[/latex].

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

Вывести наименьшее количество символов, которое следует удалить сначала.

Тесты

Входные данные Выходные данные
1 abbcddka 2
2 ABBA 0
3 abcde 5
4 abbac 1

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

Описание

Идея решения состоит в том, чтобы разбить строку на меньшие по длине подстроки и найти ответ на задачу для каждой из них. Для хранения строки используется переменная s, а ответы на подзадачи содержатся в двумерном массиве целых чисел answers. В answers[i][j] находится ответ для подстроки с i-ого по j-й символ включительно. В функции main сначала вводится строка s. Далее ширина и глубина массива answers устанавливаются равными длине s. После этого он заполняется начальными значениями. Значение [latex]-1[/latex] означает, что ответ для этой ячейки ещё не был найден. Однако очевидно, что если строка состоит ровно из одного символа, согласно условию задачи, его придётся удалить, значит, главную диагональ можно сразу заполнить единицами. Затем происходит вызов рекурсивной функции calculate, принимающей индексы левой и правой границ целевой подстроки. Первый раз она вызывается для всей строки от первого до последнего символа. Работает эта функция следующим образом: если индекс левой границы отрезка больше индекса правой, что, в случае данной задачи, не имеет смысла, она возвращает ноль. Иначе она возвращает ответ на задачу для данной подстроки, а если этого не делалось ранее, то предварительно находит его. Происходит это так: сначала значение ответа устанавливается равным длине подстроки, поскольку в худшем случае необходимо будет удалить её всю целиком. Если символы на концах подстроки одинаковые, они, как сказано в условии, будут удалены в дальнейшем, потому нужно рассматривать минимум из текущего значения ответа и ответа для подстроки без крайних символов. Однако может оказаться, что выгоднее удалить символы из каких-то двух меньших подстрок, потому далее в цикле рассматриваются все возможные комбинации двух подстрок, из которых можно составить конкатенацией текущую. В итоге получаем ответ на задачу для данной подстроки.

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