e-olymp 399. Последствия гриппа в Простоквашино

Задача

”Дорогой дядя Фёдор!

После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

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

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

Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

Всегда твой верный друг – кот Матроскин.”

Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

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

В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

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

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

Тесты

Входные данные Выходные данные
1 3
2
3
4
1
0
2
2 5
3
11
7
43
27
0
0
0
0
0
3 6
2
28
42
14
64
0
1
2674440
24466267020
429
55534064877048198
1

Код

Решение

Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$

e-olymp 236. Триомино

Триомино

Сколькими способами можно замостить прямоугольник $2 × n$ триоминошками? Триомино — это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.

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

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

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

Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник $2 × n$. Результат следует выводить по модулю $10^6$.

Тесты

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

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

1 3
3
4
6
3
0
11
2 4
12
15
21
9
153
571
7953
41

Код

 

Решение

Если n нацело не делится на $3$, то выводится ноль,в ином случае данная задача решается через рекуррентную формулу $a_n=4*a_{n-1}-a_{n-2}$. Но из-за слишком больших чисел мы не можем использовать данную формулу просто так, поэтому мы воспользуемся быстрым вычислением членов рекуррентной последовательности через матрицы. Надо умножать матрицу

$\begin{pmatrix}
4&-1 \\\
1&0 \\\
\end{pmatrix}$ в степени $p$(где $p$ равна двойке в степени номера единицы в двоичной записи числа ${{n}\over{3}}$) на матрицу $\begin{pmatrix}
1\\\
1\\\
\end{pmatrix}$ каждый раз, когда встречается единица в двоичной записи числа ${{n}\over{3}}$. На выход подается первое число вектора $2 × 1$.

Ссылки

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

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

e-olymp 1661. Рюкзак Алладина

Условие

Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает — слишком большой вес рюкзак может просто не выдержать.

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

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

Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.

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

В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leqslant w \leqslant 250, 1 \leqslant n \leqslant 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leqslant w_{i} \leqslant 250, 1 \leqslant v_{i} \leqslant 250)$ — вес предмета типа $i$ и его стоимость.

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

Выведите максимальную стоимость груза, вес которого не превышает $w$.

Тесты

Входные данные Выходные данные
1 10 2
5 10
6 19
20
2 250 35
187 100
28 109
245 142
123 83
237 78
36 172
15 248
90 24
181 137
40 233
8 99
231 128
79 132
43 217
156 104
45 191
130 113
105 225
206 5
26 120
26 119
64 138
23 147
19 202
79 54
149 185
158 79
209 88
110 133
235 209
188 230
15 220
107 164
235 137
60 167
4067
3 35 4
20 4
1 2
10 8
7 6
70

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

Решение

Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив, больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.

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

e-olymp 595. Новый Лабиринт Амбера

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

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [latex]1[/latex] до [latex]N[/latex]. Из ячейки под номером [latex]i[/latex] можно попасть в ячейки под номерами [latex]i+2[/latex] (если [latex]i+2 ≤ N[/latex]) и [latex]i+3[/latex] (если [latex]i+3 ≤ N[/latex]). На каждой ячейке лежит какое-то количество золотых монет [latex]{ k }_{ i }[/latex]. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером [latex]N[/latex]. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером [latex]N[/latex], вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число [latex]N (2 ≤ N ≤ 100000)[/latex], а во второй [latex]N[/latex] целых чисел, разделенных одним пробелом, [latex]{ k }_{ i }[/latex] – количество монеток, лежащих в ячейке с номером [latex]i[/latex] [latex](0 ≤ i ≤ 1000)[/latex].

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

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

Тесты

Входные данные Выходные данные
1 5
1000 2 3 1 3
6
2 2
1 2
2
3 4
1 3 100 0
3

Решение с использованием цикла

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

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив [latex]dp[/latex] длиной [latex]n+1[/latex] элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего обнуляем значение нулевого элемента массива, поскольку ячейка, соответствующая ему, находится вне лабиринта, и первого, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером [latex]i[/latex] он может попасть или из ячейки с номером [latex]i-2[/latex], или из ячейки с номером [latex]i-3[/latex]. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения [latex]i[/latex]-й ячейки имеет вид [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex], и ответ к задаче хранится в [latex]n[/latex]-й ячейке массива. Дополнительно требуется проводить проверку на выход за границы массива.

Код на ideone.com.

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

e-olymp 263. Три единицы

Задача

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

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

Длина последовательностей $n$ $\left ( 1 \leq n \leq 10^{5} \right ).$

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

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

Тесты

Входные данные Выходные данные
$1$ $2$
$4$ $0$
$263$ $10159$
$10000$ $8872$

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

Решение

Объявим массив $f,$ в котором будем сохранять значения $f(1), f(2),\dots, f(n).$ Далее читаем входные данные и заносим в соответствующие ячейки массива $f$ значения $f(1), f(2)$ и $f(3).$ Вычисляем значения $f(i)$ по рекуррентной формуле $f(n) = f(n – 1) + f(n – 2) + f(n – 3).$
Эту формулу получили так: сперва обозначили через $f(n)$ количество искомых последовательностей из $0$ и $1$ длины $n.$ Далее мы смотрим, если на первом месте последовательности будет находиться $0,$ то начиная со второго места можно построить $f(n – 1)$ последовательность. Если на первом месте стоит $1,$ то на втором месте возможны оба варианта. Если там стоит $0,$ то на следующих $n – 2 $свободных местах можно построить $f(n – 2)$ последовательности. Если $1,$ то на третьем месте обязательно должен находиться $0$ и начиная с четвертого места можно построить $f(n – 3)$ последовательности.
Вычисления значения $f(i)$ производим по модулю $12345.$ В результате выводим количество искомых последовательностей по модулю.

Ссылки

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

Код решения задачи ideone

e-olymp 1521. Оптимальное умножение матриц

Задача

Имея два двумерных массива $A$ и $B$, мы можем вычислить $C = AB$ используя стандартные правила умножения матриц:

$$C_{ij} = \sum_{k}A_{ik}{Bkj}$$

Число колонок в массиве $A$ должно совпадать с числом строк массива $B$. Обозначим через $rows(A)$ и $columns(A)$ соответственно количество строк и колонок в массиве $A.$ Количество умножений, необходимых для вычисления матрицы $C$ (ее количество строк совпадает с $A$, а количество столбцов с $B$) равно $rows(A)$ $columns(B)$ $columns(A).$ Например, если A имеет размер 10 × 20, B имеет размер 20 × 15, то для их умножения необходимо совершить 10 × 15 × 20, или 3000 умножений для вычисления матрицы $C.$

Перемножать несколько матриц можно несколькими способами. Например, если у нас имеются матрицы $X$, $Y$ и $Z$, то вычислить $XYZ$ можно либо как $(XY)Z$, либо как $X(YZ)$. Пусть $X$ имеет размер 5 × 10, $Y$ имеет размер 10 × 20, $Z$ имеет размер 20 × 35. Подсчитаем количество умножений, необходимых для перемножения трех матриц в каждом из этих двух случаях:

$(XY)Z$

$5 × 20 × 10 = 1000$ умножений для определения матрицы (XY), имеющей размер $5 × 20.$
Потом $5 × 35 × 20 = 3500$ умножений для нахождения конечного результата.
Общее количество умножений: $4500.$
$X(YZ)$

$10 × 35 × 20 = 7000$ умножений для определения матрицы (YZ), имеющей размер $10 × 35.$
Потом $5 × 35 × 10$ умножений для нахождения конечного результата.
Общее количество умножений: $8750.$
Очевидно, что при вычислении $(XY)Z$ требуется меньшее количество умножений.

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

Входные данные
Для каждой последовательности перемножаемых матриц Вам будут даны лишь размеры матриц. Каждый тест состоит из количества $n (n \leq 10)$ перемножаемых матриц, за которым следуют $n$ пар целых чисел, описывающих размеры матриц (количество строк и столбцов); размеры матриц задаются в порядке их перемножения. Последний тест содержит $n = 0$ и не обрабатывается.

Выходные данные
Пусть матрицы пронумерованы $A1, A2,\ldots, An.$ Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с 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))
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))
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)

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

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

Обозначим результат перемножения матриц ${\displaystyle A_{i}A_{(i+1)}…A_{j}}$ ${\displaystyle A_{i}A_{(i+1)}…A_{j}}$ через ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$, где i\leq j. Если i<j, то существует такое k, которое разбивает ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ между матрицами ${\displaystyle A_{k}}$ A_k и ${\displaystyle A_{k+1}}$ A_${{k+1}}$, i\leq k<j. То есть для вычисления ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ надо сначала вычислить ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$, потом ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}$ и затем их перемножить. Выбор $k$ является аналогом расстановки скобок между матрицами. Выбрав некоторое $k$ мы свели задачу к двум аналогичным подзадачам для матриц ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$ и ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}.$ Объясняется оно просто: для того, чтобы найти произведение матриц ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ при i=j не нужно ничего делать — это и есть сама матрица ${\displaystyle A_{i}}$ A_${i}.$ При нетривиальном случае мы перебираем все точки разбиения матрицы ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}$ на матрицы ${\displaystyle A_{i..k}}$ ${\displaystyle A_{i..k}}$ и ${\displaystyle A_{k+1..j}}$ ${\displaystyle A_{k+1..j}}$, ищем кол-во операций, необходимое чтобы их получить и затем перемножаем для получения матрицы ${\displaystyle A_{i..j}}$ ${\displaystyle A_{i..j}}.$ (Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц ${\displaystyle A_{i..k}A_{k+1..j}}$ ${\displaystyle A_{i..k}A_{k+1..j}}$). Считаем, что размеры матриц заданы в массиве ${\displaystyle p}$ p и размер матрицы ${\displaystyle A_{i}}$ A_${i}$ равен ${\displaystyle p_{i-1}\times p_{i}}$ ${\displaystyle p_{i-1}\times p_{i}}.$ Будем запоминать в двумерном массиве m результаты вычислений для подзадач, чтобы избежать пересчета для уже вычислявшихся подзадач.

Ссылки

Описание алгоритма решения
Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 4018. Черепашка

Задача

В левом верхнем углу прямоугольной таблицы размером $n × m$ находится черепашка. На каждой клетке таблицы разлито некоторое количество кислоты. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

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

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

В первой строке записаны два натуральных числа $n$ и $m$, не превосходящие $1000$ — размеры таблицы. Далее идёт $n$ строк, каждая из которых содержит $m$ чисел, разделённых пробелами — описание таблицы с указанием для каждой клетки содержания кислоты на ней (в миллилитрах).

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

Вывести минимальную возможную стоимость маршрута черепашки.

Тесты

Входные данные Выходные данные
[latex]3 \ 4[/latex] [latex]35[/latex]
[latex]5 \ 9 \ 4 \ 3[/latex]
[latex]3 \ 1 \ 6 \ 9[/latex]
[latex]8 \ 6 \ 8 \ 12[/latex]
[latex]1 \ 1[/latex] [latex]1[/latex]
[latex]1[/latex]
[latex]5 \ 6[/latex] [latex]25[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]4 \ 1[/latex] [latex]103[/latex]
[latex]100[/latex]
[latex]1[/latex]
[latex]1[/latex]
[latex]1[/latex]
[latex]1 \ 5[/latex] [latex]7[/latex]
[latex]1 \ 1 \ 2 \ 2 \ 1[/latex]

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

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

Для начала посчитаем значение для каждой клетки $0$-ой строки и $0$-ого столбца. Далее, для каждой клетки $\left (i, j \right )$, где $i > 0$ и $j > 0$, считаем значение клетки как сумму значения, лежащего в этой клетке и минимум из пути, откуда черепашка могла прийти (т. е. минимум из клетки $\left (i-1, j \right )$ и клетки $\left (i, j-1 \right )$). Ответом будет значение, лежащее в клетке $\left (n-1, m-1 \right ).$
Для считывания данных использовался BufferedReader, а не Scanner, так как Scanner работает дольше и из-за этого проходит не все тесты.

Ссылки

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

e-olymp 1560. Уменьшающееся число

Задание

Над целым числом можно производить следующие операции:

  1. Если число делится на 3, то делить его на 3;
  2. Если число делится на 2, то делить его на 2;
  3. Вычитать 1.

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

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

Каждая строка содержит одно натуральное число [latex] n(1 ≤ n ≤ 10^{6})[/latex].

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

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

Тесты

Ввод Вывод
1
5
10
0
3
3
12
7
21
3
3
4
256
1037
8771
9022
102651
8
11
13
13
19

Код

Решение

Заведём массив на максимальное количество элементов. x[1] всегда будет равен 0, так как чтобы добраться от единицы к единице нужно 0 шагов. Затем, начиная со второго элемента, пробежимся по всему массиву до [latex]n[/latex], присваивая элементам значения предыдущих элементов, добавляя к ним единицу. Теперь остается выбрать минимум из самого элемента или элемента являющегося результатом деления(на 2 или на 3) с прибавлением единицы.

Ссылки

1.Код на Ideone
2.Условие на e-olymp