# Минимальная реализация алгоритма RSA на C++

### Описание программы

Алгоритм асимметричного шифрования RSA основан на практической сложности факторизации больших чисел, что делает его на сегодняшний день одним из самых популярных криптографических алгоритмов.
Однако он имеет свои отрицательные стороны, например среди них достаточно низкая скорость шифрования, поэтому зачастую используют смешанную криптосистему, в которой сначала две стороны передают симметричный ключ с помощью RSA, а затем шифруют сообщение с помощью какого-либо симметрического алгоритма, например AES.
О самом алгоритме можно почитать например тут.
RSA может шифровать числа до так называемого модуля, который является частью ключа. В настоящее время используются модули длиной в 1024, 2048 и даже 4096 бит. В нашей реализации без длинной арифметики получится иметь дело максимум с 64-битными ключами, однако для наглядности этого хватит. Для того, чтобы сообщение при шифровании многократно не увеличивалось в размере, шифровать его надо блоками по $k — 1$ бит, где $k$ — битность ключа. При этом каждый блок перейдет в $k$-битное число, то есть на больших файлах прирост размера составит всего лишь $\frac{k}{k-1}$ раз, и чем больше ключ — тем меньше этот прирост.
В программе делением массива чисел одной битности на числа другой битности занимается функция resize, дополняя недостающие биты нулями.
Шифрованием и одновременно дешифрованием занимается функция process_bytes, так как в RSA оба этих процесса имеют идентичные алгоритмы, отличающиеся только размером блока входа и выхода. Для этого используется алгоритм быстрого возведения в степень.
Также программа может генерировать ключи на основании предустановленных простых чисел (в будущем случайных), или на основании простых чисел, введенных пользователем. Для этого используется нахождении обратного в кольце по модулю расширенным алгоритмом Евклида.
Программа реализована в интерактивном виде, список команд можно вызвать командой h.

# Анаграммы

Игорю стало интересно какое количество перестановок букв его фамилии существует. Для этого он выписал на листке бумаге все буквы своей фамилии по алфавиту и начал создавать новые перестановки этих букву в лексикографическом порядке, записывая их на листок.

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

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

## Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка  first.

## Тесты

 № Ввод Вывод 1 2500 слов английского языка trace react crate dear dare read post stop spot

# Задача

Профессор из тридевятого царства решил, что посчитать сумму делителей числа $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).$$# Ссылки Код решения # Псевдо строчная таблица # Задача В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер m \times n. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле. # Входные данные Первая строка содержит два натуральных числа m и n, (1 \leqslant m,n \leqslant 100). Далее идут m строк содержащие по n натуральных чисел — s_1, s_2, \cdots , s_{n-1}, s_n — минимальные площади каждой ячейки (1 \leqslant s_i \leqslant 100). # Выходные данные Вывести минимальную высоту таблицы. # Тесты  2 \ 3 12 1 \ 2 \ 3 \\ 1 \ 2 \ 3 1 \ 3 10 2 \ 3 \ 5 4 \ 4 96 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 3 \ 1 6 2 \\ 2 \\ 2 5 \ 3 430 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 2 \ 6 216 7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31 7 \ 5 945 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 1 \ 1 5 5 3 \ 7 210 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 2 \ 2 202 100 \ 1 \\ 100 \ 1 # Код программы # Решение задачи Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером 1 \times n и найти их минимальную высоту. Как находить высоту h для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна m \cdot h. # Ссылки Код решения # И опять «низкая» таблица # Задача В тридевятом государстве новое соревнование. Организаторы поняли, что предыдущая задача «Низкая таблица» была слишком простой и решили усложнить жизнь нашей Аленушке. Она совсем растерялась и снова умоляет Вас о помощи. Итак, вот новое условие: каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из n строк и n столбцов. В каждой строке и столбце выбрано по одной ячейке, для которой указана минимальная площадь, которую должна занимать эта ячейка — S_i для ячейки, расположенной в i-ой строке. Остальные могут иметь площадь 0. Задача участников аналогична предыдущей — начертить таблицу наименьшей высоты. ## Входные данные В первой строке содержится единственное натуральное число n \leqslant 20. Во второй строке содержатся n натуральных чисел S_{1}, \ldots, S_{n}, не превышающие 10^{4}. ## Выходные данные Минимальная высота таблицы в магических миллиметрах, округленная до ближайшего меньшего целого. ## Тесты  Входные данные Выходные данные 3 1 2 3 17191 19 2899 338 8846 5896 3325 9199 6493 211 7878 6083 2074 8493 2889 3743 133 5725 9453 7890 3594 1548340398 18 3823 5708 1356 9979 8801 5310 2123 4575 566 5039 9367 26 1966 6540 1514 7193 7667 994 1252560358 8 8283 8769 3568 869 8285 4494 7185 4519 340953967 9 6375 3059 6206 4221 6027 2064 6278 1347 996 301905233 17 2765 8226 4472 1139 9080 675 3712 7735 9566 223 8899 9716 6594 9631 8871 6176 313 1414903854 10 2654 7458 2284 8767 6061 1149 7243 607 757 8532 385237635 6 6429 9121 9490 7035 6352 2021 231968881 8 52 6380 8169 5689 367 2403 3112 2850 185108459 2 8063 3128 21235115 9 9226 7811 4279 68 5976 1418 9721 6784 8580 418145363 13 8987 3714 247 679 1416 3489 1501 7654 2164 9101 7347 4043 3289 591377417 18 9349 9854 4308 1799 1501 8647 6300 9379 1123 7369 1164 3083 1207 2754 2933 1051 8566 4016 1324052855 3 1311 2984 9564 35581065 16 3460 6135 8911 5656 5496 5463 9566 8473 7575 7444 2717 8241 9868 6698 849 7118 1576424119 15 2264 4988 4454 726 17 9279 422 7916 698 5780 2517 9352 6291 2954 4775 763779068 10 3625 7189 773 7283 2952 7865 588 1670 1013 2982 305484098 18 2741 2630 4163 4926 9431 2212 6978 1607 9489 6746 4947 3333 3144 4809 3352 207 1919 1918 1207862952 5 4320 8413 1175 4527 1519 88794894 6 9534 5380 2500 683 4281 4803 145815522 14 1458 1341 6248 8840 8877 6891 409 5853 6726 6401 4932 9007 5710 745 905996755 ## Код программы ## Решение задачи Поменяем местами строки таблицы так, чтобы ячейки, для которых указана минимальная площадь, лежали на главной диагонали. От этого не изменится ни ширина, ни высота таблицы. Обозначим эти ячейки S_{ii} для ячейки, лежащей на пересечении i-ой строки и i-ого столбца. Докажем, что минимальная площадь указанной в условии таблицы S = \left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{nn}} \right )^2. Воспользуемся методом математической индукции. База индукции. Случай при n=2 был доказан здесь. Предположение индукции. Пусть утверждение верно \forall n \leq k, \ k \geq 2. Шаг индукции. Докажем, что утверждение верно для n = k+1. Рассмотрим подтаблицу T_1 нашей таблицы T, которая состоит из первых k столбцов и k строк исходной таблицы. По предположени индукции ее минимальная площадь S_{T_1} = \left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}} \right )^2. Теперь можем рассматривать таблицу T как таблицу, состоящую из двух строк и двух столбцов, так, что таблица T_1 будет верхней левой ячейкой. Тогда, учитывая утверждение, доказанное в базе индукции находим минимальную площать таблицы T$$\begin{multline}S_{T} = \left (\sqrt{S_{T_1}}+\sqrt{S_{k+1k+1}} \right ) ^ 2 = \\ = \left (\sqrt{\left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}} \right )^2}+\sqrt{S_{k+1k+1}} \right ) ^ 2 = \\ = \left ( \sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}}+\sqrt{S_{k+1k+1}}\right )^2.\end{multline}$$Что и требовалось доказать. Заметим, что для тривиального случая n = 1 формула также остается в силе. Пусть h высота таблицы, а l — ее ширина. Учитывая, что по условию l = 1, а S = hl, находим, что минимальное значение высоты таблицы h_{min} = \left ( \sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{nn}}\right )^2. ## Ссылки Код решения на Ideone # Строчная таблица # Задача В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер 1 \times n. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Задача участников — начертить таблицу наименьшей высоты и вычислить ширину каждой ячейки. Алиса очень хочет победить, но она плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле. # Входные данные Первая строка содержит натуральное число n, \ (1 \leqslant n \leqslant 100). Вторая строка содержит n натуральных чисел — s_1, s_2, \cdots , s_{n-1}, s_n — минимальные площади каждой ячейки (1 \leqslant s_i \leqslant 100). # Выходные данные Вывести ширину каждой ячейки, учитывая, что высота таблицы должна быть минимальной, округлив ответ до четвертого знака после запятой. # Тесты  Входные данные Выходные данные 3 0.1333 \ 0.3333 \ 0.5333 2 \ 5 \ 8 6 0.0736 \ 0.2638 \ 0.3313 \ 0.0736 \ 0.1963 \ 0.0613 12 \ 43 \ 54 \ 12 \ 32 \ 10 2 0.3333 \ 0.6667 1 \ 2 3 0.3333 \ 0.3333 \ 0.3333 10 \ 10 \ 10 7 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.2500 1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 2 1 1.0000 2 4 0.5102 \ 0.1735 \ 0.2653 \ 0.0510 100 \ 34 \ 52 \ 10 2 0.9901 \ 0.0099 100 \ 1 6 0.0702 \ 0.2515 \ 0.3158 \ 0.0351 \ 0.1287 \ 0.1988 12 \ 43 \ 54 \ 6 \ 22 \ 34 2 0.5000 \ 0.5000 2 \ 2 10 0.0182 \ 0.0364 \ 0.0545 \ 0.0727 \ 0.0909 \ 0.1091 \ 0.1273 \ 0.1455 \ 0.1636 \ 0.1818 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10 3 0.0098 \ 0.9804 \ 0.0098 1 \ 100 \ 1 # Код программы # Решение задачи Пусть h=\displaystyle\frac{1}{\gamma} — высота таблицы, а x_1, \ x_2, \ \cdots, \ x_{n-1}, \ 1-x_1-x_2- \cdots -x_{n-1} – ширина каждой клетки. Тогда \displaystyle\frac{x_1}{\gamma} \geqslant s_1, \ \displaystyle\frac{x_2}{\gamma} \geqslant s_2, \ \cdots, \ \displaystyle\frac{x_{n-1}}{\gamma} \geqslant s_{n-1}, \ \displaystyle\frac{1-x_1-x_2- \cdots -x_{n-1}}{\gamma} \geqslant s_n. Получаем x_1 \geqslant s_1\gamma, \ x_2 \geqslant s_2\gamma, \ \cdots, \ x_{n-1} \geqslant s_{n-1}\gamma, \ 1-x_1-x_2- \cdots -x_{n-1} \geqslant s_n\gamma. Сделаем из неравенств равенства: x_1=s_1\gamma+\varepsilon_1, \ x_2=s_2\gamma+\varepsilon_2, \ \cdots, \ x_{n-1}=s_{n-1}\gamma+\varepsilon_{n-1}. Имеем 1-(s_1\gamma+\varepsilon_1)-(s_2\gamma+\varepsilon_2)- \cdots -(s_{n-1}\gamma+\varepsilon_{n-1}) \geqslant s_n\gamma \\ 1 \geqslant (s_1+s_2+ \cdots +s_{n-1}+s_n)\gamma+\varepsilon_1+\varepsilon_2+ \cdots +\varepsilon_{n-1} \\ \gamma \leqslant \displaystyle\frac{1-\varepsilon_1-\varepsilon_2- \cdots -\varepsilon_{n-1}}{s_1+s_2+ \cdots +s_{n-1}+s_n}. Максимальное значение \gamma достигается при \varepsilon_1=\varepsilon_2= \cdots =\varepsilon_{n-1}=0. Следовательно \gamma \leqslant \displaystyle\frac{1}{s_1+s_2+ \cdots +s_{n-1}+s_n}, а h=s_1+s_2+ \cdots +s_{n-1}+s_n. Тогда ширина каждой ячейки будет равняться \displaystyle\frac{s_i}{h} # Ссылки Код решения # Сумма делителей # Задача Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу: Найти сумму делителей данного числа 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}.$$

Код решения

# Задача

В тридевятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из двух столбцов и двух строк. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Известно, что для правой верхней и левой нижней ячейки это значение равно $0.$ Но вот незадача: значения минимальных площадей для левой верхней — $S_{11}$ и правой нижней — $S_{22}$ ячеек могут быть какими угодно (в пределах разумного, конечно, хотя кто их этих сказочных персонажей разберет). Задача участников — начертить таблицу наименьшей высоты. Аленушка очень хочет победить, но она плохо знает математику, поэтому просит Вас помочь ей в этом непростом деле.

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

В единственной строке содержатся два натуральных числа: $S_{11}, \ S_{22},$ не превышающие $10^{14}.$

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

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

## Тесты

 Входные данные Выходные данные 1 2 5828 466 1194 3151849 8067 2659 19988861 5125 6755 23647646 3317 2652 11900840 25 9293 10282002 7081 7189 10282002 8192 1042 15077308 6795 1568 14891264 680 4510 8692456 9107 4760 27035040 7095 7846 29863113 6142 3794 19590583 9347 3639 24650258 8495 5394 27427394 2179 8718 19613999 1187 778 3886963 71 5592 6923209 100000000000000 100000000000000 400000000000000000

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

Пусть $h$ и $l$ — высота и ширина таблицы соответственно. Тогда ее площадь $S=hl.$ В силу того, что $l=1,$ задача о нахождении минимальной высоты таблицы сводится к нахождению ее минимальной площади. Обозначим высоту $i$-ой строки $h_i$, ширину $j$-го столбца $l_j$, а площадь ячейки таблицы, находящейся на пересечении $i$-ой строки и $j$-го столбца — $S_{ij}.$ Тогда $$\begin{multline}S = S_{11} +S_{12}+S_{21}+S_{22}=S_{11}+l_2 h_1+l_1 h_2+S_{22}= \\ =S_{11}+S_{11} \frac{l_2}{l_1} +S_{22} \frac{l_1}{l_2}+S_{22} = S_{11}+S_{11} y+S_{22} y^{-1}+S_{22},\end{multline}$$ где $y=\frac{l_2}{l_1}.$ Зафиксируем теперь $S_{11}$ и $S_{22}$ и рассмотрим функцию площади $S \left( y \right ) = S_{11}+S_{11} y+S_{22} y^{-1}+S_{22}.$ Найдем наименьшее значение данной функции. $\frac{\mathrm{d} S \left( y \right )}{\mathrm{d} y} = S_{11}-\frac{S_{22}}{y^{2}}.$ Приравнивая производную функции к нулю, находим, что функция имеет единственную стационарную точку $y_{0} = \sqrt{\frac{S_{22}}{S_{11}}}.$ Легко убедиться, что $y_0$ – точка глобального минимума, тогда $\min\limits_{y \in D\left(S\right)}S\left( y \right ) = S \left(y_0\right) = S_{11} + S_{22} + 2 \cdot \sqrt{S_{11} \cdot S_{22}} = \left( \sqrt{S_{11}} + \sqrt{S_{22}} \right )^2.$ Очевидно теперь, что минимальное значение площадь таблицы будет принимать при $S_{11}={S_{11}}’, \ S_{22}={S_{22}}’$ где ${S_{11}}’, \ {S_{22}}’$ – данные в условии минимальные значения площадей соответствующих ячеек. Отсюда имеем минимальное значение высоты таблицы $h_{min}=\left( \sqrt{{S_{11}}’} + \sqrt{{S_{22}}’} \right )^2.$

## Ссылки

Код решения на Ideone

# Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

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

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

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

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

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

# Тесты

 Входные данные Выходные данные $6$ $9$ $3$ $1\, 3\, 2$ $2$ $2\, 3$ $2$ $5$ $2$ $3\, 2$ $2$ $2\, 3$ $5$ $41$ $4$ $84\, 50\, 50\ 8$ $2$ $1\, 21$ $100$ $100$ $2$ $1\, 50$ $4$ $1\, 2\, 3\, 4$

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

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
Найдем теперь общее минимальное время работы роботов, требуемое для завершения обработки всех деталей. Пусть нам уже известно, за какое время обрабатывают роботы первого типа каждую из данных деталей. Очевидно, что если возможно выполнить работу за $t$, то возможно выполнить работу и за $t+1$, а также, если невозможно выполнить работу за $t$, то невозможно выполнить работу за $t-1$. Следовательно, для решения данной задачи можно применить бинарный поиск по ответу. Применим бинарный поиск по ответу, рассматривая детали по мере их поступления с конца: роботы могут выполнить работу за $T$, если для каждой детали существует такой робот второго типа, который выполнит работу за $T_{2}$, такое, что $T_{1}+T_{2}$ $\leqslant T$, где $T_{1}$ – время, за которое эту деталь выполнит робот первого типа.
Теперь оценим сложность работы алгоритма. Бинарный поиск работает за $O(\log n)$. Для каждого этапа бинарного поиска мы обрабатываем $n$ деталей. Далее для каждой из $n$ деталей работает логарифмическая вставка в мультисет. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log^2n)$.

# Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

# Задача

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

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

Два натуральных числа $n$ и $a$.

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

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

# Тесты

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

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

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

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

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

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

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

# 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:

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

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

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

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

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

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

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

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

Тесты

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

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

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

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

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

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

## Задача

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

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

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

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

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

## Тесты

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

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

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

## Решение

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

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

## Задача

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

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

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

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

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

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

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

## Тесты

 № Входные данные Выходные данные 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

## Решение

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

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

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

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

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

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

Код на с++:

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

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

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

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

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

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

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

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

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

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

### Тесты

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

### Описание

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

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

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

## Задача

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

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

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

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

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

## Тесты

 № Входные данные Выходные данные 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

## Решение

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

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

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

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

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

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

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

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

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

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

### Тесты

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

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

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

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

#### Описание

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

Код на ideone.com.

### Решение с использованием рекурсивной функции

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

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

#### Описание

В данном случае используется функция $f$, принимающая номер ячейки массива и возвращающая максимальное количество монет после посещения ячейки с этим номером. Сначала объявляются два глобальных массива:
$dp$, в $i$-й ячейке которого изначально хранится количество монет в $i$-й ячейке лабиринта, и $used$, элементы которого принимают значения $0$ или $1$ (значение $0$ в $i$-й ячейке означает, что максимальное количество монет после посещения
ячейки лабиринта с тем же номером рассчитано ещё не было). Далее всё происходит как в решении с использованием цикла, но одновременно с чтением входных данных обнуляются элементы $used$, а вместо второго цикла происходит вызов функции $f$. Сама же функция $f$, если значение параметра меньше двух, возвращает $0$, а иначе, если этого не было сделано ранее, вычисляет максимальное количество монет после посещения ячейки с номером $i$ по формуле $dp[i] = dp[i] + max(dp[i-2], dp[i-3])$ и возвращает его.

Код на ideone.com.
Кроме того, об идее решения данной задачи можно почитать здесь.

# Универсальное дерево отрезков

## Некоторые теоретические сведения

Обобщённое условие задач на дерево отрезков, как правило, выглядит так:
«Пусть дан моноид $\left(\mathbb{G}, \circ\right)$, где $\mathbb{G}$ — некоторое непустое множество, $\circ$ — ассоциативная бинарная алгебраическая операция на этом множестве, имеющая нейтральный элемент, $A$ — последовательность (массив) элементов из $\mathbb{G}$, содержащая $n$ элементов ($n \in \mathbb{N}$; с математической точки зрения $A$ — вектор, построенный из элементов $\mathbb{G}$, или $А = \left( x_{0}, x_{1}, \ldots, x_{n-1} \right) \in \mathbb{G}^{n}$).
Даётся $m$ ($m \in \mathbb{N}$) запросов двух типов:
1) вычислить значение выражения $x_{i} \circ x_{i+1} \circ \ldots \circ x_{j-1} \circ x_{j}$ с заданными $i$, $j$ ($0 \le i \le j \le n-1$, $i, j \in \mathbb{N} \cup \{ 0 \}$) и вывести его;
2) заменить значение элемента с индексом $k$ на $y$ ($k \in \mathbb{N} \cup \{ 0 \}$, $k \le n-1$, $y \in \mathbb{G}$).»

Как правило, человек, впервые увидевший задачу подобного рода, решает её следующим образом: для запросов первого типа (далее — запросы значения на отрезке $\left[i, j\right]$) создаётся вспомогательная переменная, изначально равная нейтральному элементу моноида (к примеру, если $\left( \mathbb{G}, \circ \right) = \left( \mathbb{Z}, + \right)$ то нейтральным элементом относительно $+$ является $0$), и запускается цикл на заданном отрезке, который «прибавляет» к ней новые «слагаемые», а обработка запросов из пункта 2 реализуется через простое присваивание элементу массива с заданным индексом $i$ значения $y$. Таким образом вычислительная сложность запросов замены составляет $O\left(1\right)$, а запросов поиска значения на отрезке $\left[i, j\right]$ в лучшем случае составляет $O\left(1\right)$, когда $i = j$, а в худшем $O\left(n\right)$, когда $i = 0$, $j = n-1$.

Дерево отрезковструктура данных, которая позволяет сбалансировать операции замены и вычисления значения на заданном отрезке до вычислительной сложности $O\left(\log_{2}{n}\right)$ и значительно улучшить общую сложность программы с $O\left(n+n\cdot m\right) = O\left(n\cdot m\right)$ до $O\left(n+m\cdot\log_{2}{n}\right)$.

Определение: массив/последовательность элементов/вектор, над которым построено дерево отрезков, называется базой дерева или просто базой, а число её элементов — её размерностью.

# Задача 1: единичная модификация

Написать класс «дерево отрезков», применимый к любой задаче на моноиде, в которой присутствуют запросы замены элемента и результата операции на отрезке,
и таблицу его базовых функций и параметров.

# Описание класса

Далее $n$ — размерность базы дерева.

Название объекта Описание
Параметр
TYPE Тип объектов дерева, над которыми будут проводится вычисления.
Внутренние объекты
SegmentTree Массив, хранящий в себе дерево отрезков.
base_capacity Переменная, хранящая округлённую к ближайшей большей степени двойки размерность базы дерева отрезков.
g Указатель на функцию, которая представляет из себя ассоциативную бинарную операцию. Формально определяется как функция/операция.
neutral Нейтральный элемент относительно бинарной операции g.
Методы класса
construct

Аргументы:

1. Адрес начала полуинтервала $a$;
2. Адрес конца полуинтервала $b$;
3. Ассоциативная бинарная операция f;
4. Нейтральный элемент относительно f.

Генерирует базу на основе полуинтервала $\left[a; b\right)$, копируя его элементы внутрь дерева, и строит на основе этой базы дерево отрезков.
Вычислительная сложность: $O\left(n\right)$.

read_and_construct Аргументы:

1. Размер базы дерева;
2. Функция-препроцессор;
3. Ассоциативная бинарная операция f;
4. Нейтральный элемент относительно f.

Генерирует базу на основе элементов, возвращаемых функцией-препроцессором, и строит на их основе дерево отрезков.
Вычислительная сложность: $O\left(n\right)$.

assign Аргументы:

1. Индекс элемента;
2. Новое значение элемента.

Заменяет значение элемента с заданным индексом на новое.
Вычислительная сложность: $O\left(\log_{2}{n}\right)$.

result_on_segment Аргументы:

1. Индекс левого конца отрезка;
2. Индекс правого конца отрезка.

Возвращает результат функции на заданном отрезке.
Вычислительная сложность: $O\left(\log_{2}{n}\right)$.

# Инструкция по применению

Прежде всего, код универсального дерева отрезков необходимо скопировать в исходную программу.

Построение:

• Создать тип объектов (структуру данных), который будет использоваться в дереве для вычислений; (в зависимости от задачи. Вполне может быть, что необходимый для решения задачи класс уже создан. Например — int или double.)
• Инициализировать дерево отрезков, передав классу segments_tree в качестве параметра тип объектов, над которыми будут проводиться вычисления, и задав дереву имя. (инициализация класса segments_tree происходит аналогично инициализации класса vector)
• Построить дерево отрезков на основе заданных элементов при помощи метода construct или read_and_construct, передав методу соответствующие параметры (упомянутые в таблице выше);

Далее для вычисления результатов на отрезках и модификаций элементов с заданным индексом использовать методы result_on_segment и assign соответственно.

# Пример использования

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

### Решение задачи №4082 на www.e-olymp.com

Так как в задаче необходимо выводить знак или произведения на заданных отрезках (либо нуль), то очевидно, что сами числа не интересуют нас. Тогда каждое из них можно представить в виде пары (zero, plus)$= \left(a, b\right) \in \mathbb{B}^{2}$ (где $\mathbb{B}$ — булево множество), где первый элемент пар $a$ будет характеризовать равенство числа нулю, а $b$ — его положительность. Назовём структуру данных пар такого типа number_sign. Функция make_number_sign будет преобразовывать числа типа short в number_sign. Затем определим для этой структуры функцию умножения prod формулой prod(number_sign a, number_sign b)$=$ (a.zero|b.zero, !(a.plus^b.plus));. В первой части формулы используется дизъюнкция, так как произведение нуля и произвольного числа всегда должно возвращать нуль, а во второй части — эквиваленция, так как результат произведения является отрицательным, если оба аргумента различны по знаку.

Затем, предварительно считав размер базы, конструируем дерево отрезков методом read_and_construct, передавая ему число элементов базы, анонимную функцию-препроцессор, которая считывает элементы базы из входного потока и которая преобразует их в тип данных number_sign, функцию произведения prod и её нейтральный элемент number_sign(), являющийся парой $\left(0, 1\right)$, который по сути представляет из себя число $+1$ (нейтральный элемент умножения).

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

# Задача 2

Дополнить класс «дерево отрезков» из первой задачи таким образом, чтобы для базы дерева были реализованы:

• параметры «вместимость» и «размер»;
• функции добавления нового элемента в базу;
• функции, возвращающие размер базы и вместимость дерева;
• функция изменения размера базы.

Написать таблицу новых функций и параметров.

# Описание дополнительных объектов класса

Название объекта Описание
Новый внутренний объект
base_size Переменная, хранящая размерность базы дерева отрезков.
Новые методы класса
begin

Аргументы: отсутствуют.
Возвращает адрес начала базы.
Вычислительная сложность: константа.

end Аргументы: отсутствуют.
Возвращает адрес конца базы.
Вычислительная сложность: константа.
push_back Аргумент: значение нового элемента базы.
Добавляет новый элемент в конец базы.
Вычислительная сложность: если база заполнена, то $O\left(n\right)$, иначе — $O\left(\log_{2}{n}\right)$.

pop_back

Аргументы: отсутствуют.
Удаляет элемент в конце базы.
Вычислительная сложность: $O\left(\log_{2}{n}\right)$.

insert

Аргументы:

1. Индекс нового элемента;
2. Значение нового элемента.

Добавляет на заданную позицию базы новый элемент с заданным значением.
Вычислительная сложность: $O\left(n\right)$.

erase

Аргумент: индекс удаляемого элемента.
Удаляет из базы элемент с заданным индексом.
Вычислительная сложность: $O\left(n\right)$.

size

Аргументы: отсутствуют.
Возвращает размерность базы дерева.
Вычислительная сложность: константа.

capacity

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

resize

Аргумент: новый размер базы.
Изменяет размер базы дерева, и преобразовывает незадействованные элементы в нейтральные
Вычислительная сложность: $O\left(n\right)$, если новый размер базы превысил вместимость дерева или является меньше, чем старый, и константа в противном случае.

# Монстр

Задача 787A с сайта codeforces.com.

## Задача

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени b, b + a, b + 2a, b + 3a, …, а Морти кричит в моменты времени d, d + c, d + 2c, d + 3c, …. Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

## Ввод

Первая строка входных данных содержит два целых числа a и b (1 ≤ a, b ≤ 100).

Вторая строка входных данных содержит два целых числа c и d (1 ≤ c, d ≤ 100).

## Вывод

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или  - 1, если они никогда не закричат одновременно.

## Тесты

 Ввод Вывод 20 2 9 19 82 2 1 16 12 -1

## Решение

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при и c. Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.