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 1521. Оптимальное умножение матриц

Задача

Имея два двумерных массива [latex]A[/latex] и [latex]B[/latex], мы можем вычислить [latex]C = AB[/latex] используя стандартные правила умножения матриц. Число колонок в массиве [latex]A[/latex] должно совпадать с числом строк массива [latex]B[/latex]. Обозначим через [latex]rows(A)[/latex] и [latex]columns(A)[/latex] соответственно количество строк и колонок в массиве [latex]A[/latex]. Количество умножений, необходимых для вычисления матрицы [latex]C[/latex] (ее количество строк совпадает с [latex]A[/latex], а количество столбцов с [latex]B[/latex]) равно [latex]rows(A) columns(B) columns(A)[/latex]. По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

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

Каждый тест состоит из количества [latex]n (n ≤ 10)[/latex] перемножаемых матриц, за которым следуют [latex]n[/latex] пар целых чисел, описывающих размеры матриц (количество строк и столбцов). Размеры матриц задаются в порядке их перемножения. Последний тест содержит [latex]n = 0[/latex] и не обрабатывается.

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

Пусть матрицы пронумерованы [latex]A_{1}[/latex], [latex]A_{2}[/latex],…, [latex]A_{n}[/latex]. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с [latex]1[/latex]. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

Тесты

 №  Входные данные  Выходные данные
 1 3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0
Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
 2  10
653 273
273 692
692 851
851 691
691 532
532 770
770 690
690 582
582 519
519 633
0
Case 1: (A1 x ((((((((A2 x A3) x A4) x A5) x A6) x A7) x A8) x A9) x A10))
 3  2
11 12
12 33
7
1 5
5 28
28 19
19 2
2 10
10 1
1 12
4
10 29
29 133
133 8
8 15
0
Case 1: (A1 x A2)
Case 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7)
Case 3: ((A1 x (A2 x A3)) x A4)

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

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

Решение

Пусть [latex]A[/latex]- любая не последняя матрица заданной последовательности, [latex]B[/latex] — матрица, что следует за [latex]A[/latex] в данной последовательности перемножаемых матриц. Заведём двумерный массив [latex]dp[/latex] размером [latex] {(n+1)}\times {(n+1)}[/latex]. По главной диагонали массива запишем размеры матриц, причём [latex]rows(B)[/latex] не будем записывать, так как [latex]rows(B)=columns(A)[/latex]. В dp[k][j] [latex]\left( j<k \right) [/latex] будем хранить минимальное количество операций необходимое для получения матрицы [latex]C_{kj}[/latex] такой, что [latex]columns(C_{kj})[/latex] равно элементу dp[k][k], а [latex]rows(C_{kj})[/latex] соответственно dp[j][j]. Для получения матрицы [latex]C_{kj}[/latex] нужно умножить матрицу [latex]C_{k(j+t)}[/latex] на [latex]C_{(j+t)j}[/latex] [latex](\left( k-j \right) >t>0)[/latex], для этого нам понадобиться [latex]rows(C_{k(j+t)}) columns(C_{(j+t)j}) columns(C_{k(j+t)}) [/latex], что равно dp[k][k]*dp[j][j]*dp[j+t][j+t], операций непосредственно на перемножение этих матриц, а также dp[k][j+t] и dp[j+t][j] операций для получения матриц [latex]C_{k(j+t)}[/latex] и [latex]C_{(j+t)j}[/latex] соответственно.
Тогда dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t]. При помощи цикла подберём [latex] t [/latex], при котором значение dp[k][j] выходит минимальным. Для получения матриц, которые даны изначально, не требуется ни одной операции, поэтому диагональ массива прилегающую к главной диагонали оставим заполненной нулями. Далее, при помощи вложенных циклов на каждом шаге внешнего цикла будем заполнять диагональ массива, что расположена ниже предыдущей. Параллельно будем запоминать номер последнего умножения, который будет равен [latex]j+t[/latex], в элемент массива, который расположен симметрично  dp[k][j] относительно главной диагонали (то есть в dp[j][k]). Таким образом от умножения двух исходных матриц поэтапно перейдём к оптимальному произведению [latex]n[/latex] матриц. Затем, рекурсивно восстановим оптимальный порядок умножения матриц. Для вывода ответа в соответствующем формате также воспользуемся рекурсией.

Ссылки

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

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

Решение

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

Ссылки

Ideone;
WolframAlpha.

Площадь поверхности

Задача

Найти площадь поверхности, которая является трёхмерным графиком функции [latex]f\left( x, y\right)[/latex], в пределах от [latex]a[/latex] до [latex]b[/latex] по оси [latex]x[/latex] и от [latex]c[/latex] до [latex]d[/latex] по оси [latex]y[/latex] c величиной шага [latex]h[/latex].

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

Четыре целых числа: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex].
Вещественное число: [latex]h[/latex].

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

Площадь поверхности [latex]S[/latex].

Тесты

 № [latex]f\left( x, y\right)[/latex] Входные данные Выходные данные
 [latex]a[/latex]  [latex]b[/latex]  [latex]c[/latex]  [latex]d[/latex]  [latex]h[/latex]  [latex]S[/latex]
 1  [latex]x+y[/latex]  -10  10  -10  10  0.001  692.82
 2  [latex]\left| x \right| +\left| y \right|[/latex]  -2  2  -2  2  0.005  27.7128
 3  [latex]1[/latex]  0  100  0  100  0.1  10000
 4  [latex]{x}^{2}+{y}^{2}[/latex]  -1  1  -1  1  0.0005  7.44626

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

Решение

Представим поверхность в виде множества геометрических фигур. Тогда её площадь будет суммой площадей этих фигур. В качестве фигур, покрывающих данную поверхность, возьмём треугольники, поскольку через любые [latex]3[/latex] точки в пространстве можно провести плоскость и только одну (а значит и треугольник). Координатную плоскость [latex]xy[/latex] условно поделим на квадраты, где сторона квадрата будет равняться заданному шагу [latex]h[/latex]. Будем рассматривать только квадраты, что лежат в заданных пределах.  Условно проведём одну из диагоналей у каждого квадрата — получим треугольники на плоскости. Поочередно будем искать координату [latex]z[/latex] вершин каждой пары треугольников, подставляя уже известные координаты [latex]x[/latex] и [latex]y[/latex] в указанную формулу. Зная координаты треугольников в пространстве, найдём площадь каждого, сумма данных площадей и будет площадью поверхности. Чтоб найти площадь треугольника, зная координаты его вершин, найдем векторное произведение его координат. Возьмем треугольник с координатами вершин  [latex]\left( x_i,y_i,z_{ii} \right) [/latex], [latex]\left( x_i, y_j, z_{ij} \right) [/latex] и [latex]\left( x_j, y_i, z_{ji} \right) [/latex], возьмём произвольные два вектора, которые образуют данный треугольник — [latex]\overrightarrow { a } =\left ( x_i-x_i, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, y_i-y_i, z_{ji}-z_{ii} \right)[/latex].
[latex]\overrightarrow { a } =\left ( 0, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, 0, z_{ji}-z_{ii} \right)[/latex].
Тогда векторное произведение [latex]\left [ \overrightarrow { a }, \overrightarrow { b } \right] =\left ( (y_i-y_j)( z_{ji}-z_{ii}), (z_{ii}-z_{ij})(z_{ji}-z_{ii} ), ( y_j-y_i)(x_j-x_i) \right)[/latex].
Поскольку длина вектора равного векторному произведения двух векторов в пространстве равна площади параллелограмма, образованного исходными векторами — найдём его длину и разделим пополам, чтоб получить площадь треугольника, образованного исходными векторами. Значит площадь каждого треугольника можно вычислить по формуле:
[latex]s =\frac { 1 }{ 2 } \sqrt{({(y_i-y_j)}^{2}{( z_{ji}-z_{ii})}^{2}+{(z_{ii}-z_{ij})}^{2}{(z_{ji}-z_{ii} )}^{2}+{( y_j-y_i)}^{2}{(x_j-x_i)}^{2})}[/latex] Тогда площадь поверхности в пределах заданных точек можно вычислить, сложив площади этих треугольников.

Модификация

Модифицируем данную программу для нахождения приблизительной площади поверхности, заданной функцией с корнем чётной степени.

Тесты

 № [latex]f\left( x, y\right)[/latex] [latex]z_0[/latex]  Входные данные  Выходные данные
 [latex]a[/latex]  [latex]b[/latex]  [latex]c[/latex] [latex]d[/latex]  [latex]h[/latex]  [latex]S[/latex]
 1 [latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]1[/latex]  -1  1  -1  1  0.00011  6.28734
 2 [latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]7y[/latex]  -1  1  -1  1  0.00011  23.0803
 3 [latex]\sqrt { 1-{ x }^{ 2 }-\frac{ { y }^{ 2 }}{ 2 } }[/latex] [latex]0[/latex]  -1  1  -2  2  0.00015  8.08214
 4 [latex]\sqrt { 2-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]-1[/latex]  -2  2  -2  2  0.0005  12.5835

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

Условно отделим от функцию [latex]f\left( x, y\right)[/latex] слагаемые, что не под корнем, если такие имеются. Тогда [latex]z_0[/latex] равно части функции, что не под корнем. Для того, чтоб рассматривать площади треугольников, вершины которых выходят за область определения функции, доопределим их в [latex]z_0[/latex] по оси [latex]z[/latex]. Затем вычислим площадь треугольников, у которых как минимум одна вершина не лежит на [latex]z=z_0[/latex] .

Ссылки

А329. Квадрат суммы цифр числа

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа [latex]n[/latex], [latex]m[/latex]. Получить все меньшие [latex]n[/latex] натуральные числа, квадрат суммы цифр которых равен [latex]m[/latex].

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

Два положительных числа [latex]n[/latex] и [latex]m[/latex].

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

Все целые числа из [latex]\left( 0,n \right)[/latex], удовлетворяющие условию.

Тесты

 Входные данные  Выходные данные
[latex]n[/latex] [latex]m[/latex]
 1  1234  9 3 12 21 30 102 111 120 201 210 300 1002 1011 1020 1101 1110 1200
 2 100  4 2 11 20
 3  49  49 7 16 25 34 43
 4 1000  1 1 10 100

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

Решение

Для того, чтоб найти каждую цифру числа будем искать остаток от деления на [latex]10[/latex], которым является последняя цифра числа, а затем делить число нацело на [latex]10[/latex], чтоб предпоследняя цифра стала последней. Будем повторять эту операцию пока число не равно [latex]0[/latex]. Все полученные цифры числа складываем. Таким способом будем искать сумму цифр каждого целого числа от [latex]1[/latex] до [latex]n-1[/latex], параллельно возводя полученную сумму в квадрат, а результат сравнивая с [latex]m[/latex].

Ссылки