И опять «низкая» таблица

12/07/2018 by Кирилл Волков

Задача

В тридевятом государстве новое соревнование. Организаторы поняли, что предыдущая задача «Низкая таблица» была слишком простой и решили усложнить жизнь нашей Аленушке. Она совсем растерялась и снова умоляет Вас о помощи. Итак, вот новое условие: каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из $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

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

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int main(){
    int n;
    cin >> n;
    double sqrtOfHeight = 0;
    for(int i = 0; i < n; i++){
        int square;
        cin >> square;
        sqrtOfHeight +=  sqrt(square);
    }
    cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight);
    return 0;
}

#include <iostream>

#include <cmath>

#include <climits>

using namespace std;

int main(){

int n;

cin >> n;

double sqrtOfHeight = 0;

for(int i = 0; i < n; i++){

int square;

cin >> square;

sqrtOfHeight += sqrt(square);

}

cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight);

return 0;

}

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

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

Related Images:

Строчная таблица

11/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $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$

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long double s[n], h=0;
    for(int i=0; i<n; i++)
    {
        cin >> s[i];
        h+=s[i];
    }
    for(int i=0; i<n; i++)
    {
        cout.precision(4);
        cout << fixed << s[i]/h << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

long double s[n], h=0;

for(int i=0; i<n; i++)

{

cin >> s[i];

h+=s[i];

}

for(int i=0; i<n; i++)

{

cout.precision(4);

cout << fixed << s[i]/h << " ";

}

return 0;

}

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

Пусть $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}$

Ссылки

Код решения

Related Images:

Сумма делителей

11/07/2018 by Алиса Ворохта

Задача

Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $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$

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

#include <iostream>
#include <map>
using namespace std;
int main ()
{
    long long n, sumOfDivisors = 1;
    cin >> n;
    map<long long, long long> primeDivInPow;
    for(long long i = 2; i * i <= n; i++){
        while(n % i == 0){
            if(primeDivInPow.find(i) == primeDivInPow.end()){
                primeDivInPow[i] = 1;
            }
            primeDivInPow[i] *= i;
            n /= i;
        }
    }
    if(n != 1){
        primeDivInPow[n] = n;
    }
    for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){
        sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1);
    }
    cout << sumOfDivisors;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main ()

{

long long n, sumOfDivisors = 1;

cin >> n;

map<long long, long long> primeDivInPow;

for(long long i = 2; i * i <= n; i++){

while(n % i == 0){

if(primeDivInPow.find(i) == primeDivInPow.end()){

primeDivInPow[i] = 1;

}

primeDivInPow[i] *= i;

n /= i;

}

if(n != 1){

primeDivInPow[n] = n;

}

for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){

sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1);

}

cout << sumOfDivisors;

return 0;

}

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

Пусть $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}.$$

Ссылки

Код решения

Related Images:

«Низкая» таблица

11/07/2018 by Кирилл Волков

Задача

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

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

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    unsigned long long s1;
    unsigned long long s2;
    cin >> s1 >> s2;
    double sqrtOfHeight = sqrt(s1) + sqrt(s2);
    cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight);
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

unsigned long long s1;

unsigned long long s2;

cin >> s1 >> s2;

double sqrtOfHeight = sqrt(s1) + sqrt(s2);

cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight);

}

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

Пусть $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

Related Images:

e-olymp 161. Роботы

01/03/2018 by Костя Григорян

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $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$ пренебречь.

Тесты

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

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

#include <iostream>
#include <set>
#include <climits>
using namespace std;

int inf = INT_MAX;

int main() {
    cin.sync_with_stdio(false);
    int n;
    cin >> n;
    int na;
    cin >> na;
    multiset<pair<int, int> > s;
    int a[na];
    int resa[n];
    for(int i=0; i<na; i++)
    {
        cin >> a[i];
        s.insert({a[i], a[i]});
    }
    for(int i=0; i<n; i++)
    {
        auto it=s.begin();
        int val=it->first;
        int t=it->second;
        s.erase(it);
        s.insert({val+t, t});
        resa[i]=val;
    }
    int nb;
    cin >> nb;
    int b[nb];
    for(int i=0; i<nb; i++)
    {
        cin >> b[i];
    }
    multiset<pair<int, int> > q;
    long long l=resa[n-1], r=10000100;
    while(l<r)
    {
        int w=0;
        int m=(l+r)/2;
        for(int i=0; i<nb; i++)
        {
            q.insert({b[i], b[i]});
        }
        q.insert({inf, inf});
        for(int i=n-1; i>=0; i--)
        {
            int y=m-resa[i];
            auto x=q.begin();
            if(y<(x->first))
            {
                w++;
                break;
            }
            else{
                auto it=q.lower_bound({y, -1});
                int z=it->first;
                if(z>y)
                    it--;
                int val=it->first;
                int t=it->second;
                q.erase(it);
                q.insert({val+t, t});
            }
        }
        if(w==0)
            r=m;
        else
            l=m+1;
        q.clear();  
    }
    cout << l;
    return 0;
}

#include <iostream>

#include <set>

#include <climits>

using namespace std;

int inf = INT_MAX;

int main() {

cin.sync_with_stdio(false);

int n;

cin >> n;

int na;

cin >> na;

multiset<pair<int, int> > s;

int a[na];

int resa[n];

for(int i=0; i<na; i++)

{

cin >> a[i];

s.insert({a[i], a[i]});

}

for(int i=0; i<n; i++)

{

auto it=s.begin();

int val=it->first;

int t=it->second;

s.erase(it);

s.insert({val+t, t});

resa[i]=val;

}

int nb;

cin >> nb;

int b[nb];

for(int i=0; i<nb; i++)

{

cin >> b[i];

}

multiset<pair<int, int> > q;

long long l=resa[n-1], r=10000100;

while(l<r)

{

int w=0;

int m=(l+r)/2;

for(int i=0; i<nb; i++)

{

q.insert({b[i], b[i]});

}

q.insert({inf, inf});

for(int i=n-1; i>=0; i--)

{

int y=m-resa[i];

auto x=q.begin();

if(y<(x->first))

{

w++;

break;

}

else{

auto it=q.lower_bound({y, -1});

int z=it->first;

if(z>y)

it--;

int val=it->first;

int t=it->second;

q.erase(it);

q.insert({val+t, t});

}

if(w==0)

r=m;

else

l=m+1;

q.clear();

}

cout << l;

return 0;

}

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

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
Найдем теперь общее минимальное время работы роботов, требуемое для завершения обработки всех деталей. Пусть нам уже известно, за какое время обрабатывают роботы первого типа каждую из данных деталей. Очевидно, что если возможно выполнить работу за $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
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

Related Images:

e-olymp 1210. Очень просто!!!

04/12/2017 by Вадим Гордийчук

Задача

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

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

Два натуральных числа [latex]n[/latex] и [latex]a[/latex].

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

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

Тесты

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

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

#include <iostream>
using namespace std;

int main()
{
    unsigned long long int n, a, answer;
    cin >> n >> a;
    if (a > 1)
    {
        answer = n*a;
        for(unsigned long long int i = n-1; i > 0; --i)
            answer = (answer+i)*a;
    }
    else
        answer = n*(n+1)/2;
    cout << answer;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned long long int n, a, answer;

cin >> n >> a;

if (a > 1)

{

answer = n*a;

for(unsigned long long int i = n-1; i > 0; --i)

answer = (answer+i)*a;

}

else

answer = n*(n+1)/2;

cout << answer;

return 0;

}

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextInt(), a = in.nextInt(), ans;
        if (a > 1)
        {
            ans = n*a;
            for(long i = n-1; i > 0; --i)
                ans = (ans+i)*a;
        }
        else
            ans = n*(n+1)/2;
        System.out.println(ans);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

long n = in.nextInt(), a = in.nextInt(), ans;

if (a > 1)

{

ans = n*a;

for(long i = n-1; i > 0; --i)

ans = (ans+i)*a;

}

else

ans = n*(n+1)/2;

System.out.println(ans);

}

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

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

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

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

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

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

Ссылки

Related Images:

e-olymp 15. Мышка и зернышки

17/06/2017 by Валентина Андриеш

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

В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 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

Код на С++:

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
    int m,n;
    long long X[100][100];
    string ans;
    cin>>n>>m;
    for (int i=n-1; i>=0; i--){
        for (int j=0; j<m; j++)cin>>X[i][j];
    }
    for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];
    for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];
    for (int i=1; i<n; i++){
        for (int j=1; j<m; j++) X[i][j]=X[i][j]+max(X[i - 1][j], X[i][j - 1]);
    }
    int k=n-1, t=m-1;
    while (k>0 || t>0){
        if (k>0 && t>0){
            if (X[k-1][t]>X[k][t-1]){
                ans+="F";
                k--;
            }
            else{
                ans+="R";
                t--;    
            } 
        }
        else if (k==0){
            ans+="R";
            t--;
        }
        else if (t==0){
            ans+="F";
            k--;
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

int main() {

int m,n;

long long X[100][100];

string ans;

cin>>n>>m;

for (int i=n-1; i>=0; i--){

for (int j=0; j<m; j++)cin>>X[i][j];

}

for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];

for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];

for (int i=1; i<n; i++){

for (int j=1; j<m; j++) X[i][j]=X[i][j]+max(X[i - 1][j], X[i][j - 1]);

}

int k=n-1, t=m-1;

while (k>0 || t>0){

if (k>0 && t>0){

if (X[k-1][t]>X[k][t-1]){

ans+="F";

k--;

}

else{

ans+="R";

t--;

}

else if (k==0){

ans+="R";

t--;

}

else if (t==0){

ans+="F";

k--;

}

reverse(ans.begin(),ans.end());

cout<<ans;

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        long[][] X = new long[100][100];
        String ans = new String("");
        for (int i=n-1; i>=0; i--){
            for (int j=0; j<m; j++)X[i][j]=in.nextLong();
        }
        for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];
        for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];
        for (int i=1; i<n; i++){
            for (int j=1; j<m; j++) X[i][j]=X[i][j]+Math.max(X[i - 1][j], X[i][j - 1]);
        }
        int k=n-1, t=m-1;
        while (k>0 || t>0){
            if (k>0 && t>0){
                        if (X[k-1][t]>X[k][t-1]){
                            ans+="F";
                            k--;
                        }
                        else{
                            ans+="R";
                            t--;    
                        }
            }
                    else if (k==0){
                        ans+="R";
                        t--;
            }
            else if (t==0){
                        ans+="F";
                        k--;
            }
        }
        String reverse = new StringBuffer(ans).reverse().toString();
        System.out.println(reverse);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

int m=in.nextInt();

long[][] X = new long[100][100];

String ans = new String("");

for (int i=n-1; i>=0; i--){

for (int j=0; j<m; j++)X[i][j]=in.nextLong();

}

for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];

for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];

for (int i=1; i<n; i++){

for (int j=1; j<m; j++) X[i][j]=X[i][j]+Math.max(X[i - 1][j], X[i][j - 1]);

}

int k=n-1, t=m-1;

while (k>0 || t>0){

if (k>0 && t>0){

if (X[k-1][t]>X[k][t-1]){

ans+="F";

k--;

}

else{

ans+="R";

t--;

}

else if (k==0){

ans+="R";

t--;

}

else if (t==0){

ans+="F";

k--;

}

String reverse = new StringBuffer(ans).reverse().toString();

System.out.println(reverse);

}

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

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

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

Related Images:

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

12/06/2017 by Иванна Ялымова

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

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

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

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

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

Тесты

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

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

#include<iostream>  
using namespace std;
     
int main() {
    long n,x1,x2,x3,x4;
    cin >> n;
    x1=2;
    x2=4;
    x3=7;
    for (int i=3; i<n; i++) {
        x4=x1+x2+x3;
        x1=x2;
        x2=x3;
        x3=x4;    
    }
    if (n==1) 
        cout << 2 << endl; 
    else if (n==2) 
        cout << 4 << endl; 
    else if (n==3)
        cout << 7 << endl; 
    else 
        cout << x4 << endl; 
    return 0;
}

#include<iostream>

using namespace std;

int main() {

long n,x1,x2,x3,x4;

cin >> n;

x1=2;

x2=4;

x3=7;

for (int i=3; i<n; i++) {

x4=x1+x2+x3;

x1=x2;

x2=x3;

x3=x4;

}

if (n==1)

cout << 2 << endl;

else if (n==2)

cout << 4 << endl;

else if (n==3)

cout << 7 << endl;

else

cout << x4 << endl;

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long x1,x2,x3;
        long x4=0;
        long n=in.nextLong();
        x1=2;
        x2=4;
        x3=7;
        for (int i=3; i<n; i++) {
            x4=x1+x2+x3;
            x1=x2;
            x2=x3;
            x3=x4;    
        }
        if (n==1) 
            System.out.println(2); 
        else if (n==2) 
            System.out.println(4); 
        else if (n==3)
            System.out.println(7); 
        else 
            System.out.println(x4);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

long x1,x2,x3;

long x4=0;

long n=in.nextLong();

x1=2;

x2=4;

x3=7;

for (int i=3; i<n; i++) {

x4=x1+x2+x3;

x1=x2;

x2=x3;

x3=x4;

}

if (n==1)

System.out.println(2);

else if (n==2)

System.out.println(4);

else if (n==3)

System.out.println(7);

else

System.out.println(x4);

}

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

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

Related Images:

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

10/06/2017 by Тимур Фирсов

Задача

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

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

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

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

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

Тесты

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

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

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string **dp;
int main() {
    string s1,s2;
    long long i,j;
    cin>>s1;
    s2=s1;
    long long m=s1.size()+1;
    reverse(s2.begin(),s2.end());
    dp=new string* [m];
    for(i=0;i<m;i++)dp[i]=new string [m];
    for(i=1;i<m;i++){
        for(j=1;j<m;j++){
            if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1];
            else{
                if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j];
                else dp[i][j]=dp[i][j-1];
            }
        }
    }
    cout<<dp[m-1][m-1];
    return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

string **dp;

int main() {

string s1,s2;

long long i,j;

cin>>s1;

s2=s1;

long long m=s1.size()+1;

reverse(s2.begin(),s2.end());

dp=new string* [m];

for(i=0;i<m;i++)dp[i]=new string [m];

for(i=1;i<m;i++){

for(j=1;j<m;j++){

if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1];

else{

if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j];

else dp[i][j]=dp[i][j-1];

}

cout<<dp[m-1][m-1];

return 0;

}

Засчитанное решение на 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] будет хранится наибольший подпалиндром исходной строки.

Ссылки

Related Images:

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

10/06/2017 by Тимур Фирсов

Задача

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

Любое нечетное число больше [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

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

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

bool prime (int x){ //функция для проверки простоты нечётного числа
    bool pr=true;
    for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;
    return pr;
}
int main() {
    vector <int> v,prime_v;
    unordered_map <int,bool> prime_m;
    int u,i,j,maxx=0;
    while(cin>>u){
        v.push_back(u);
        maxx=max(maxx,u);//максимальное значение во входном потоке
    }
    for(i=3;i<=maxx;i+=2){
        if(prime(i)){
            prime_m[i]=true;
            prime_v.push_back(i); 
        }
    }
    int *dp,k;
    dp = new int [maxx+1];
    for(i=0;i<=maxx;i++)dp[i]=0;
    for(i=8;i<=maxx;i++){//заполняем массив значениями |G(i)|
        if(i%2){
            for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){
                k=i-prime_v[j];
                if(dp[k]){
                    dp[i]+=dp[k];
                    if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];
                }
            }
        }
        else{
            for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){
                k=i-prime_v[j];
                if(prime_m[k])dp[i]++;
            }
        }
        if(i%2)dp[i]/=3;
    }
    for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';
    return 0;
}

#include <iostream>

#include <vector>

#include <unordered_map>

#include <cmath>

using namespace std;

bool prime (int x){ //функция для проверки простоты нечётного числа

bool pr=true;

for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;

return pr;

}

int main() {

vector <int> v,prime_v;

unordered_map <int,bool> prime_m;

int u,i,j,maxx=0;

while(cin>>u){

v.push_back(u);

maxx=max(maxx,u);//максимальное значение во входном потоке

}

for(i=3;i<=maxx;i+=2){

if(prime(i)){

prime_m[i]=true;

prime_v.push_back(i);

}

int *dp,k;

dp = new int [maxx+1];

for(i=0;i<=maxx;i++)dp[i]=0;

for(i=8;i<=maxx;i++){//заполняем массив значениями |G(i)|

if(i%2){

for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){

k=i-prime_v[j];

if(dp[k]){

dp[i]+=dp[k];

if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];

}

else{

for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){

k=i-prime_v[j];

if(prime_m[k])dp[i]++;

}

if(i%2)dp[i]/=3;

}

for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';

return 0;

}

Засчитанное решение на 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].

Ссылки

Related Images:

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

06/06/2017 by Валентина Андриеш

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

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

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

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

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

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

Тесты:

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

Код на с++:

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

 //в этой функции рассмотрим все возможные операции, что могут встретиться в строке
bool operation(char c){
    return c=='+' || c=='-' || c=='*' ||  c=='/' || c=='^';
}

//данная функция будет возвращать приоритет поступившей операции
int prioritet(char op){ 
    if(op<0) return 3;
    else{
        if(op == '+' || op == '-')return 1;
        else if(op == '*' || op == '/' )return 2;
        else if(op == '^')return 4;
        else return -1;
    }
}

//следующая функция описывает принцип работы каждого оператора
void action(vector<long> &value, char op){
    if(op<0){                            //для унарных операций
        long unitar=value.back();
        value.pop_back();
        if(-op=='-')value.push_back(-unitar);
    }
    else{                               //для бинарных операций
        long right = value.back();
        value.pop_back();
        long left = value.back();
        value.pop_back();
        if(op=='+')value.push_back(left+right);
        else if(op=='-')value.push_back(left-right);
        else if(op=='*')value.push_back(left*right);
        else if(op=='/')value.push_back(left/right);
        else if(op=='^')value.push_back(pow(left,right));
    }
}

long calculus(string &formula){
    bool unary=true;        //создадим булевскую переменную, для распределения операторов на унарные и бинарные
    vector<long>value;        //заведем массив для целых чисел
    vector<char>op;           //и соответственно для самых операторов
    for(int i=0; i<formula.size(); i++){
            if(formula[i]=='('){    //если текущий элемент — открывающая скобка, то положим её в стек
                op.push_back('(');  
                unary=true;
            }
            else if(formula[i]==')'){
                while(op.back()!='('){  //если закрывающая скобка - выполняем все операции, находящиеся внутри этой скобки
                    action(value, op.back());
                    op.pop_back();
                }
                op.pop_back();
                unary=false;
            }
            else if(operation(formula[i])){ //если данный элемент строки является одни из выше перечисленных операндов,то
                char zn=formula[i];
                if(unary==true)zn=-zn; //придает отрицательное значение, для распознавания функции унарности оператора 
                while(!op.empty() && prioritet(op.back())>=prioritet(zn)){
                    action(value, op.back());   //выполняем сами алгебраические вычисления, где все уже операции упорядочены  
                    op.pop_back();              //в одном из стеков по строгому убыванию приоритета, если двигаться от вершины
                }
                op.push_back(zn);
                unary=true;
            }
            else{
                string number;      //заведем строку для найденных числовых операндов
                while(i<formula.size() && isdigit(formula[i]))number+=formula[i++];//распознаем их с помощью библиотечной функции строк
                i--;
                value.push_back(atol(number.c_str()));//поместим в наш стек с числовыми выражениями
                unary=false;
            }
        }
    while(!op.empty()){     //выполним еще не использованные операции в стеке 
        action(value, op.back());
        op.pop_back();
    }
    return value.back(); //получим на выходе значение выражения
}
    
int main() {
    string formula,x; //введем две строки: сам многочлен/числовое выражение и по необходимости значение переменной 
    cin>>formula>>x;
    if(x[0]=='-'){  //для слаженной работы унитарного минуса при отрицательном значении переменной, заключим его в скобки
        x.insert(x.begin(),'(');
        x.insert(x.end(),')');
    }
    int size=2*formula.size();  //зададим максимальный размер строки с учетом замены переменной
    for(int i=0; i<size; i++){
        if(formula[i]=='x'){
            formula.erase(i,1);
            formula.insert(i,x);//проведем замену
        }
    }
    cout<<calculus(formula);  //выведем ответ
    return 0;
}

100

101

#include <iostream>

#include <vector>

#include <string>

#include <cmath>

using namespace std;

//в этой функции рассмотрим все возможные операции, что могут встретиться в строке

bool operation(char c){

return c=='+' || c=='-' || c=='*' || c=='/' || c=='^';

}

//данная функция будет возвращать приоритет поступившей операции

int prioritet(char op){

if(op<0) return 3;

else{

if(op == '+' || op == '-')return 1;

else if(op == '*' || op == '/' )return 2;

else if(op == '^')return 4;

else return -1;

}

//следующая функция описывает принцип работы каждого оператора

void action(vector<long> &value, char op){

if(op<0){ //для унарных операций

long unitar=value.back();

value.pop_back();

if(-op=='-')value.push_back(-unitar);

}

else{ //для бинарных операций

long right = value.back();

value.pop_back();

long left = value.back();

value.pop_back();

if(op=='+')value.push_back(left+right);

else if(op=='-')value.push_back(left-right);

else if(op=='*')value.push_back(left*right);

else if(op=='/')value.push_back(left/right);

else if(op=='^')value.push_back(pow(left,right));

}

long calculus(string &formula){

bool unary=true; //создадим булевскую переменную, для распределения операторов на унарные и бинарные

vector<long>value; //заведем массив для целых чисел

vector<char>op; //и соответственно для самых операторов

for(int i=0; i<formula.size(); i++){

if(formula[i]=='('){ //если текущий элемент — открывающая скобка, то положим её в стек

op.push_back('(');

unary=true;

}

else if(formula[i]==')'){

while(op.back()!='('){ //если закрывающая скобка - выполняем все операции, находящиеся внутри этой скобки

action(value, op.back());

op.pop_back();

}

op.pop_back();

unary=false;

}

else if(operation(formula[i])){ //если данный элемент строки является одни из выше перечисленных операндов,то

char zn=formula[i];

if(unary==true)zn=-zn; //придает отрицательное значение, для распознавания функции унарности оператора

while(!op.empty() && prioritet(op.back())>=prioritet(zn)){

action(value, op.back()); //выполняем сами алгебраические вычисления, где все уже операции упорядочены

op.pop_back(); //в одном из стеков по строгому убыванию приоритета, если двигаться от вершины

}

op.push_back(zn);

unary=true;

}

else{

string number; //заведем строку для найденных числовых операндов

while(i<formula.size() && isdigit(formula[i]))number+=formula[i++];//распознаем их с помощью библиотечной функции строк

i--;

value.push_back(atol(number.c_str()));//поместим в наш стек с числовыми выражениями

unary=false;

}

while(!op.empty()){ //выполним еще не использованные операции в стеке

action(value, op.back());

op.pop_back();

}

return value.back(); //получим на выходе значение выражения

}

int main() {

string formula,x; //введем две строки: сам многочлен/числовое выражение и по необходимости значение переменной

cin>>formula>>x;

if(x[0]=='-'){ //для слаженной работы унитарного минуса при отрицательном значении переменной, заключим его в скобки

x.insert(x.begin(),'(');

x.insert(x.end(),')');

}

int size=2*formula.size(); //зададим максимальный размер строки с учетом замены переменной

for(int i=0; i<size; i++){

if(formula[i]=='x'){

formula.erase(i,1);

formula.insert(i,x);//проведем замену

}

cout<<calculus(formula); //выведем ответ

return 0;

}

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

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

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

Related Images:

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

12/05/2017 by Эммануил Прокопов

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

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

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

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

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

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

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

Тесты

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

Код на C++

#include <iostream>
#include <string>
using namespace std;

int **answers;
string s;

int calculate(int l, int r){
    if(l > r) return 0;  //Если индекс левой границы отрезка больше индекса правой.
    if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.
        answers[l][r] = s.size();
        if(s[l] == s[r]) answers[l][r] = min(answers[l][r], calculate(l+1, r-1));
        for(int i = l; i < r; ++i){
            answers[l][r] = min(answers[l][r], calculate(l, i) + calculate(i+1, r));
        }
    }
    return answers[l][r];
}

int main() {
    getline(cin, s); //Ввод строки.
    
    answers = new int*[s.size()];
    for(int i = 0; i < s.size(); ++i){
        answers[i] = new int[s.size()];
    }
    //Заполнение массива начальными значениями.
    for(int i = 0; i < s.size(); ++i){
        for(int j = 0; j <= s.size(); ++j){
            if(i == j) answers[i][j] = 1;
            else answers[i][j] = -1;
        }
    }
    //Вывод ответа.
    cout<<calculate(0, s.size()-1);
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int **answers;

string s;

int calculate(int l, int r){

if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой.

if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.

answers[l][r] = s.size();

if(s[l] == s[r]) answers[l][r] = min(answers[l][r], calculate(l+1, r-1));

for(int i = l; i < r; ++i){

answers[l][r] = min(answers[l][r], calculate(l, i) + calculate(i+1, r));

}

return answers[l][r];

}

int main() {

getline(cin, s); //Ввод строки.

answers = new int*[s.size()];

for(int i = 0; i < s.size(); ++i){

answers[i] = new int[s.size()];

}

//Заполнение массива начальными значениями.

for(int i = 0; i < s.size(); ++i){

for(int j = 0; j <= s.size(); ++j){

if(i == j) answers[i][j] = 1;

else answers[i][j] = -1;

}

//Вывод ответа.

cout<<calculate(0, s.size()-1);

return 0;

}

Код на Java

import java.util.*;

class Main
{
    static int[][] answers;
    static String s;

    static int calculate(int l, int r){
        if(l > r) return 0;  //Если индекс левой границы отрезка больше индекса правой.
        if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.
            answers[l][r] = s.length();
            if(s.charAt(l) == s.charAt(r)) answers[l][r] = Math.min(answers[l][r], calculate(l+1, r-1));
            for(int i = l; i < r; ++i){
                answers[l][r] = Math.min(answers[l][r], calculate(l, i) + calculate(i+1, r));
            }
        }
        return answers[l][r];
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        s = in.nextLine();  //Ввод строки.
        
        answers = new int[s.length()][s.length()];
        //Заполнение массива начальными значениями.
        for(int i = 0; i < s.length(); ++i){
            for(int j = 0; j < s.length(); ++j){
                if(i == j) answers[i][j] = 1;
                else answers[i][j] = -1;
            }
        }
        //Вывод ответа.
        System.out.print(calculate(0, s.length()-1));
    }
}

import java.util.*;

class Main

{

static int[][] answers;

static String s;

static int calculate(int l, int r){

if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой.

if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.

answers[l][r] = s.length();

if(s.charAt(l) == s.charAt(r)) answers[l][r] = Math.min(answers[l][r], calculate(l+1, r-1));

for(int i = l; i < r; ++i){

answers[l][r] = Math.min(answers[l][r], calculate(l, i) + calculate(i+1, r));

}

return answers[l][r];

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

s = in.nextLine(); //Ввод строки.

answers = new int[s.length()][s.length()];

//Заполнение массива начальными значениями.

for(int i = 0; i < s.length(); ++i){

for(int j = 0; j < s.length(); ++j){

if(i == j) answers[i][j] = 1;

else answers[i][j] = -1;

}

//Вывод ответа.

System.out.print(calculate(0, s.length()-1));

}

Описание

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

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

Related Images:

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

07/05/2017 by Тимур Фирсов

Задача

Имея два двумерных массива [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)

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int n;
vector <int> v;
void f(long long **a, long long i, long long j ){
    if(a[j][i]>0){
        v.push_back(a[j][i]);
        if((a[j][i]<=n)&&(i<=n)&&(j<=n)){
            f(a,i,a[j][i]);
            f(a,a[j][i],j);
        }
    }
}
string answer(long long x, long long si, long long sj, long long el){
     long long z1=el,z2=el;
     if(sj!=si){
        if(si!=x){
            while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;
        }
        if(sj!=(x+1)){
            while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++; 
        }
     }
    return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";
}
int main() {
    long long i,j,useless,number=1,**dp;
    cin>>n;
    while(n){
        n++;
        dp = new long long* [n];
        for(i=0;i<n;i++)dp[i]=new long long [n];
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                dp[i][j]=0;
            }
        }
        cin>>dp[0][0];
        for(i=1;i<n;i++){
            cin>>dp[i][i];
            if(i<(n-1))cin>>useless;//лишние для нас значения
        }
        i=2;
        for(i=2;i<n;i++){        
            for(j=0;j<=(i-2);j++){
                dp[i][j]=2e10;
            }
        }
        long long t;
        for(i=2;i<n;i++){
            for(j=0;j<(n-i);j++){
                long long k=j+i;
                for(t=1;(j+t)<(n-1);t++){
                    if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){
                        dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];
                        dp[j][k]=j+t;//запоминаем последнее умножение
                    }
                }
            }
        }
        f(dp,n-1,0);//восстанавливаем порядок умножений (от последнего к первому)
        reverse(v.begin(),v.end());
        cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';
        number++;
        delete [] dp;//очищаем память для следующего теста
        v.clear();
        cin>>n;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

int n;

vector <int> v;

void f(long long **a, long long i, long long j ){

if(a[j][i]>0){

v.push_back(a[j][i]);

if((a[j][i]<=n)&&(i<=n)&&(j<=n)){

f(a,i,a[j][i]);

f(a,a[j][i],j);

}

string answer(long long x, long long si, long long sj, long long el){

long long z1=el,z2=el;

if(sj!=si){

if(si!=x){

while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;

}

if(sj!=(x+1)){

while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++;

}

return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";

}

int main() {

long long i,j,useless,number=1,**dp;

cin>>n;

while(n){

n++;

dp = new long long* [n];

for(i=0;i<n;i++)dp[i]=new long long [n];

for(i=0;i<n;i++){

for(j=0;j<n;j++){

dp[i][j]=0;

}

cin>>dp[0][0];

for(i=1;i<n;i++){

cin>>dp[i][i];

if(i<(n-1))cin>>useless;//лишние для нас значения

}

i=2;

for(i=2;i<n;i++){

for(j=0;j<=(i-2);j++){

dp[i][j]=2e10;

}

long long t;

for(i=2;i<n;i++){

for(j=0;j<(n-i);j++){

long long k=j+i;

for(t=1;(j+t)<(n-1);t++){

if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){

dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];

dp[j][k]=j+t;//запоминаем последнее умножение

}

f(dp,n-1,0);//восстанавливаем порядок умножений (от последнего к первому)

reverse(v.begin(),v.end());

cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';

number++;

delete [] dp;//очищаем память для следующего теста

v.clear();

cin>>n;

}

return 0;

}

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

Ссылки

Related Images:

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

02/05/2017 by Эммануил Прокопов

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

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

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

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [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

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

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

#include <iostream>
using namespace std;

int main() {
    int n, i;
    cin >> n;
    int *dp;
    dp = new int [n+1];
    for(i = 1; i<=n; ++i){
        cin >> dp[i];
    }
    dp[0] = 0;
    dp[1] = 0;
    for(int i = 2; i<=n; ++i){
        if(i - 3 >= 0) dp[i] = dp[i] + max(dp[i-2], dp[i-3]);
    }
    cout << dp[n];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, i;

cin >> n;

int *dp;

dp = new int [n+1];

for(i = 1; i<=n; ++i){

cin >> dp[i];

}

dp[0] = 0;

dp[1] = 0;

for(int i = 2; i<=n; ++i){

if(i - 3 >= 0) dp[i] = dp[i] + max(dp[i-2], dp[i-3]);

}

cout << dp[n];

return 0;

}

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

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив [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.

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

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

#include <iostream>
using namespace std;

int *dp;
int *used;

int f(int i){
    if(i < 2) return 0;
    else{
        if(used[i] == 0){
            dp[i] = dp[i] + max(f(i-2), f(i-3));
            used[i] = 1;
        }
        return dp[i];
    }
}

int main() {
    int n, i;
    cin >> n;
    dp = new int [n+1];
    used = new int [n+1];
    for(i = 1; i<=n; ++i){
        cin >> dp[i];
        used[i] = 0;
    }
    f(n);
    cout << dp[n];
    return 0;
}

#include <iostream>

using namespace std;

int *dp;

int *used;

int f(int i){

if(i < 2) return 0;

else{

if(used[i] == 0){

dp[i] = dp[i] + max(f(i-2), f(i-3));

used[i] = 1;

}

return dp[i];

}

int main() {

int n, i;

cin >> n;

dp = new int [n+1];

used = new int [n+1];

for(i = 1; i<=n; ++i){

cin >> dp[i];

used[i] = 0;

}

f(n);

cout << dp[n];

return 0;

}

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

Описание

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

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

Related Images:

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

27/04/2017 by Вадим Гордийчук

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

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

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

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

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

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

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

Код класса

#include <iostream>
using namespace std;

template <class TYPE> class segments_tree
{
    TYPE *SegmentTree;
    size_t base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;

    /*
    TYPE:
        Type of elements in the tree.

    SegmentTree: (pointer)
        Array-based tree of elements.

    base_capacity: (unsigned integer value)
        Parental array size, rounded to the closest upper power of 2.

    g: (pointer)
        Pointer to the funtion (associative binary operation), applied on the given array of elements.
        WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

    neutral: (array element)
        The value of element, which is neutral relatively to "g" function.

    ################################
    #### INNER HELPER FUNCTIONS ####
    ################################
    result_on_segment_in:
        returns value on segment [l, r];
    */
    TYPE result_on_segment_in
    (
        size_t v, size_t tl,
        size_t tr, size_t l,
        size_t r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            size_t tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }

    /*
    make_monoid_and_fill_rest:
        - fills the unused space of array (which appears due to rounding of size of parental array)
        with neutral elements.
        - assigns the necessary values to the upper "vertexes" of the tree.
    */
    void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(size_t i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }

    /*
    fix_capacity:
        Rounds base_capacity of the base array to closest upper power of 2.
    */
    void fix_capacity(const size_t &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }

    public:
    /*
    ##########################
    #### PUBLIC FUNCTIONS ####
    ##########################
    Definitions:
        n - amount of elements in the parental array;
        lb - binary logarithm.
        Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
        and (if exists) unused space, filled with neutral elements.
    
    
    construct:
        Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        Complexity: O(n).
    */
    void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        size_t base_size = end - begin;
        fix_capacity(base_size);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < base_size; ++i)
        {
            NewTree[base_capacity+i] = begin[i];
        }
        make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
    }

    /*
    read_and_construct:
        Constructs the tree by filling with it with elements, created by "preprocessing_function",
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        This method is useful for creating tree by giving preprocessing_function an ability to read
        the data from the incoming stream, if the separate memorisation of the base array is not needed.
        Complexity: O(n).
    */
    void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function();
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }

    /*
    assign:
        Assigns new value to the element of base array with given index.
        Complexity: O(lb(n))
    */
    void assign(const size_t index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }

    /*
    result_on_segment:
        Returns value of operation on the given segment of parental array.
        Complexity: O(lb(n)).
    */
    TYPE result_on_segment (size_t l, size_t r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

int sum(int a, int b)
{
    return a+b;
}

int main()
{
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

#include <iostream>

using namespace std;

template <class TYPE> class segments_tree

{

TYPE *SegmentTree;

size_t base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE:

Type of elements in the tree.

SegmentTree: (pointer)

Array-based tree of elements.

base_capacity: (unsigned integer value)

Parental array size, rounded to the closest upper power of 2.

g: (pointer)

Pointer to the funtion (associative binary operation), applied on the given array of elements.

WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

neutral: (array element)

The value of element, which is neutral relatively to "g" function.

################################

#### INNER HELPER FUNCTIONS ####

################################

result_on_segment_in:

returns value on segment [l, r];

TYPE result_on_segment_in

(

size_t v, size_t tl,

size_t tr, size_t l,

size_t r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

size_t tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

make_monoid_and_fill_rest:

- fills the unused space of array (which appears due to rounding of size of parental array)

with neutral elements.

- assigns the necessary values to the upper "vertexes" of the tree.

void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(size_t i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

fix_capacity:

Rounds base_capacity of the base array to closest upper power of 2.

void fix_capacity(const size_t &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

##########################

#### PUBLIC FUNCTIONS ####

##########################

Definitions:

n - amount of elements in the parental array;

lb - binary logarithm.

Lowest level of the tree - parental array (segment of elements, which is a base of the tree)

and (if exists) unused space, filled with neutral elements.

construct:

Constructs the tree by copying elements of [begin; end) memory block into the segment tree,

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

Complexity: O(n).

void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)

{

size_t base_size = end - begin;

fix_capacity(base_size);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < base_size; ++i)

{

NewTree[base_capacity+i] = begin[i];

}

make_monoid_and_fill_rest(NewTree, base_size, f, neutr);

}

read_and_construct:

Constructs the tree by filling with it with elements, created by "preprocessing_function",

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

This method is useful for creating tree by giving preprocessing_function an ability to read

the data from the incoming stream, if the separate memorisation of the base array is not needed.

Complexity: O(n).

void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function();

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

assign:

Assigns new value to the element of base array with given index.

Complexity: O(lb(n))

void assign(const size_t index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

result_on_segment:

Returns value of operation on the given segment of parental array.

Complexity: O(lb(n)).

TYPE result_on_segment (size_t l, size_t r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

int sum(int a, int b)

{

return a+b;

}

int main()

{

return 0;

}

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

Далее [latex]n[/latex] — размерность базы дерева.

Название объекта	Описание
Параметр
TYPE	Тип объектов дерева, над которыми будут проводится вычисления.
Внутренние объекты
SegmentTree	Массив, хранящий в себе дерево отрезков.
base_capacity	Переменная, хранящая округлённую к ближайшей большей степени двойки размерность базы дерева отрезков.
g	Указатель на функцию, которая представляет из себя ассоциативную бинарную операцию. Формально определяется как функция/операция.
neutral	Нейтральный элемент относительно бинарной операции g.
Методы класса
construct	Аргументы: Адрес начала полуинтервала [latex]a[/latex]; Адрес конца полуинтервала [latex]b[/latex]; Ассоциативная бинарная операция f; Нейтральный элемент относительно f. Генерирует базу на основе полуинтервала [latex]\left[a; b\right)[/latex], копируя его элементы внутрь дерева, и строит на основе этой базы дерево отрезков. Вычислительная сложность: [latex]O\left(n\right)[/latex].
read_and_construct	Аргументы: Размер базы дерева; Функция-препроцессор; Ассоциативная бинарная операция f; Нейтральный элемент относительно f. Генерирует базу на основе элементов, возвращаемых функцией-препроцессором, и строит на их основе дерево отрезков. Вычислительная сложность: [latex]O\left(n\right)[/latex].
assign	Аргументы: Индекс элемента; Новое значение элемента. Заменяет значение элемента с заданным индексом на новое. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].
result_on_segment	Аргументы: Индекс левого конца отрезка; Индекс правого конца отрезка. Возвращает результат функции на заданном отрезке. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

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

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

Построение:

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

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

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

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

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

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

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

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

Фрагмент кода

#include <iostream>
using namespace std;

// . . . . . . . . . . . . . . . . . . . .
// . . . . segments_tree class . . . . . .
// . . . . . . . . . . . . . . . . . . . .

struct number_sign
{
    bool zero, plus;
    number_sign()
    {
        zero = 0;
        plus = 1;
    }
    number_sign(bool a, bool b)
    {
        zero = a;
        plus = b;
    }
};

number_sign make_number_sign(const short &X)
{
    return number_sign(X == 0, X > 0);
}

number_sign prod(number_sign a, number_sign b)
{
    return number_sign(a.zero|b.zero, !(a.plus^b.plus));
}

char sign(const number_sign d)
{
    if (d.zero) return '0';
    else if (d.plus) return '+';
    else return '-';
}

int main()
{
    unsigned int i, j, m;
    char q;
    short X;
    
    segments_tree <number_sign> A;
    number_sign *B, neutr;
    while (cin >> i)
    {
        scanf("%u", &m);
        A.read_and_construct(i, [] () {short X; scanf("%hd", &X); return make_number_sign(X);}, prod, number_sign());
        scanf("\n");
        ++m;
        while (--m)
        {
            scanf("%c%u", &q, &i);
            if (q == 'P')
            {
                scanf("%u", &j);
                printf("%c", sign(A.result_on_segment(i-1, j-1)));
            }
            else
            {
                scanf("%hd", &X);
                A.assign(i-1, make_number_sign(X));
            }
            scanf("\n");
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

// . . . . . . . . . . . . . . . . . . . .

// . . . . segments_tree class . . . . . .

// . . . . . . . . . . . . . . . . . . . .

struct number_sign

{

bool zero, plus;

number_sign()

{

zero = 0;

plus = 1;

}

number_sign(bool a, bool b)

{

zero = a;

plus = b;

}

};

number_sign make_number_sign(const short &X)

{

return number_sign(X == 0, X > 0);

}

number_sign prod(number_sign a, number_sign b)

{

return number_sign(a.zero|b.zero, !(a.plus^b.plus));

}

char sign(const number_sign d)

{

if (d.zero) return '0';

else if (d.plus) return '+';

else return '-';

}

int main()

{

unsigned int i, j, m;

char q;

short X;

segments_tree <number_sign> A;

number_sign *B, neutr;

while (cin >> i)

{

scanf("%u", &m);

A.read_and_construct(i, [] () {short X; scanf("%hd", &X); return make_number_sign(X);}, prod, number_sign());

scanf("\n");

++m;

while (--m)

{

scanf("%c%u", &q, &i);

if (q == 'P')

{

scanf("%u", &j);

printf("%c", sign(A.result_on_segment(i-1, j-1)));

}

else

{

scanf("%hd", &X);

A.assign(i-1, make_number_sign(X));

}

scanf("\n");

}

printf("\n");

}

return 0;

}

Задача 2

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

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

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

Код класса

#include <iostream>
using namespace std;

template <class TYPE> class segments_tree
{
    TYPE *SegmentTree;
    size_t base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;

    /*
    TYPE:
        Type of elements in the tree.

    SegmentTree: (pointer)
        Array-based tree of elements.

    base_capacity: (unsigned integer value)
        Parental array size, rounded to the closest upper power of 2.

    g: (pointer)
        Pointer to the funtion (associative binary operation), applied on the given array of elements.
        WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

    neutral: (array element)
        The value of element, which is neutral relatively to "g" function.

    ################################
    #### INNER HELPER FUNCTIONS ####
    ################################
    result_on_segment_in:
        returns value on segment [l, r];
    */
    TYPE result_on_segment_in
    (
        size_t v, size_t tl,
        size_t tr, size_t l,
        size_t r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            size_t tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }

    /*
    make_monoid_and_fill_rest:
        - fills the unused space of array (which appears due to rounding of size of parental array)
        with neutral elements.
        - assigns the necessary values to the upper "vertexes" of the tree.
    */
    void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(size_t i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }

    /*
    fix_capacity:
        Rounds base_capacity of the base array to closest upper power of 2.
    */
    void fix_capacity(const size_t &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }

    public:
    /*
    ##########################
    #### PUBLIC FUNCTIONS ####
    ##########################
    Definitions:
        n - amount of elements in the parental array;
        lb - binary logarithm.
        Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
        and (if exists) unused space, filled with neutral elements.
    
    
    construct:
        Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        Complexity: O(n).
    */
    void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        size_t base_size = end - begin;
        fix_capacity(base_size);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < base_size; ++i)
        {
            NewTree[base_capacity+i] = begin[i];
        }
        make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
    }

    /*
    read_and_construct:
        Constructs the tree by filling with it with elements, created by "preprocessing_function",
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        This method is useful for creating tree by giving preprocessing_function an ability to read
        the data from the incoming stream, if the separate memorisation of the base array is not needed.
        Complexity: O(n).
    */
    void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function();
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }

    /*
    assign:
        Assigns new value to the element of base array with given index.
        Complexity: O(lb(n))
    */
    void assign(const size_t index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }

    /*
    result_on_segment:
        Returns value of operation on the given segment of parental array.
        Complexity: O(lb(n)).
    */
    TYPE result_on_segment (size_t l, size_t r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

int main()
{
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include <iostream>

using namespace std;

template <class TYPE> class segments_tree

{

TYPE *SegmentTree;

size_t base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE:

Type of elements in the tree.

SegmentTree: (pointer)

Array-based tree of elements.

base_capacity: (unsigned integer value)

Parental array size, rounded to the closest upper power of 2.

g: (pointer)

Pointer to the funtion (associative binary operation), applied on the given array of elements.

WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

neutral: (array element)

The value of element, which is neutral relatively to "g" function.

################################

#### INNER HELPER FUNCTIONS ####

################################

result_on_segment_in:

returns value on segment [l, r];

TYPE result_on_segment_in

(

size_t v, size_t tl,

size_t tr, size_t l,

size_t r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

size_t tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

make_monoid_and_fill_rest:

- fills the unused space of array (which appears due to rounding of size of parental array)

with neutral elements.

- assigns the necessary values to the upper "vertexes" of the tree.

void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(size_t i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

fix_capacity:

Rounds base_capacity of the base array to closest upper power of 2.

void fix_capacity(const size_t &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

##########################

#### PUBLIC FUNCTIONS ####

##########################

Definitions:

n - amount of elements in the parental array;

lb - binary logarithm.

Lowest level of the tree - parental array (segment of elements, which is a base of the tree)

and (if exists) unused space, filled with neutral elements.

construct:

Constructs the tree by copying elements of [begin; end) memory block into the segment tree,

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

Complexity: O(n).

void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)

{

size_t base_size = end - begin;

fix_capacity(base_size);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < base_size; ++i)

{

NewTree[base_capacity+i] = begin[i];

}

make_monoid_and_fill_rest(NewTree, base_size, f, neutr);

}

read_and_construct:

Constructs the tree by filling with it with elements, created by "preprocessing_function",

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

This method is useful for creating tree by giving preprocessing_function an ability to read

the data from the incoming stream, if the separate memorisation of the base array is not needed.

Complexity: O(n).

void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function();

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

assign:

Assigns new value to the element of base array with given index.

Complexity: O(lb(n))

void assign(const size_t index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

result_on_segment:

Returns value of operation on the given segment of parental array.

Complexity: O(lb(n)).

TYPE result_on_segment (size_t l, size_t r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

int main()

{

return 0;

}

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

Название объекта	Описание
Новый внутренний объект
base_size	Переменная, хранящая размерность базы дерева отрезков.
Новые методы класса
begin	Аргументы: отсутствуют. Возвращает адрес начала базы. Вычислительная сложность: константа.
end	Аргументы: отсутствуют. Возвращает адрес конца базы. Вычислительная сложность: константа.
push_back	Аргумент: значение нового элемента базы. Добавляет новый элемент в конец базы. Вычислительная сложность: если база заполнена, то [latex]O\left(n\right)[/latex], иначе — [latex]O\left(\log_{2}{n}\right)[/latex].
pop_back	Аргументы: отсутствуют. Удаляет элемент в конце базы. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].
insert	Аргументы: Индекс нового элемента; Значение нового элемента. Добавляет на заданную позицию базы новый элемент с заданным значением. Вычислительная сложность: [latex]O\left(n\right)[/latex].
erase	Аргумент: индекс удаляемого элемента. Удаляет из базы элемент с заданным индексом. Вычислительная сложность: [latex]O\left(n\right)[/latex].
size	Аргументы: отсутствуют. Возвращает размерность базы дерева. Вычислительная сложность: константа.
capacity	Аргументы: отсутствуют. Возвращает размерность базы дерева, округлённую к ближайшей большей степени двойки. Позволяет оценить число неиспользованных ячеек, на которые уже выделена память. Вычислительная сложность: константа.
resize	Аргумент: новый размер базы. Изменяет размер базы дерева, и преобразовывает незадействованные элементы в нейтральные Вычислительная сложность: [latex]O\left(n\right)[/latex], если новый размер базы превысил вместимость дерева или является меньше, чем старый, и константа в противном случае.

Ссылки

Код универсального дерева отрезков;
Код универсального дерева отрезков (дополнение функциями вектора);
Код универсального дерева отрезков (множественная модификация);
Статья о дереве отрезков на e-maxx.ru, за которую выражаю unsigned long long int (то есть очень большую 🙂 ) благодарность её автору.

Related Images:

Монстр

18/04/2017 by Антон Куперман

Задача 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

Код

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int a,b,c,d,n,m;
    vector <int> s;
    cin>>a>>b;
    cin>>c>>d;
    for(int i=0;i<=100;i++)
    {
        for(int j=0;j<=100;j++)
        {
            n=b+i*a;
            m=d+j*c;
            if(m==n)
            {   
                s.push_back(n);
            } 
        }
    }
    if(s.empty()==true)
    {
        cout<<-1;
    } else cout<<s.at(0);
    
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int a,b,c,d,n,m;

vector <int> s;

cin>>a>>b;

cin>>c>>d;

for(int i=0;i<=100;i++)

{

for(int j=0;j<=100;j++)

{

n=b+i*a;

m=d+j*c;

if(m==n)

{

s.push_back(n);

}

if(s.empty()==true)

{

cout<<-1;

} else cout<<s.at(0);

return 0;

}

Решение

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

Related Images:

Код Хаффмана

15/04/2017 by Вадим Гордийчук

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированную строку.

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

Некоторая последовательность символов и endl.

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

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированная строка.

Тест

Входные данные	Выходные данные
MOLOKO KIPIT	digraph G { "'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ]; "'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ]; "'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ]; "'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ]; "'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ]; "'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ]; "' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ]; "' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ]; "' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ]; "' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ]; "'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ]; "'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ]; "'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ]; "'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ]; } Codes of letters: 'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100) Encoded string: 00001001011010110010111011111101110

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

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

MOLOKO KIPIT

digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

struct ltcode
{
    unsigned long long frequency;
    unsigned char letter;
    string code = "";
};

void zeroset(ltcode *c)
{
    for (unsigned int i = 0; i < 256; ++i)
    {
        c[i].frequency = 0;
        c[i].letter = i;
    }
}

bool f(ltcode x, ltcode y)
{
    if (x.frequency != y.frequency) return x.frequency > y.frequency;
    else return x.letter > y.letter;
}

struct B
{
    string list;
    int i;
    
    int left;
    int right;
    
    string code = "";
    
    B()
    {
        list = "";
        i = 0;
    }
};

void print_binary_tree(int num, vector <B> &tree)
{
    if (tree[num].list.size() > 1)
    {
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";
        print_binary_tree(tree[num].left, tree);
        print_binary_tree(tree[num].right, tree);
    }
}

void print_tree_graph(vector <B> &tree)
{
    cout << "digraph G {\n";
    print_binary_tree(tree.size()-1, tree);
    cout << "}\n";
}

void huffman_encoding_in(int num, string code, vector <B> &tree, ltcode *letter_codes)
{
    tree[num].code = code;
    if (tree[num].list.size() > 1)
    {
        huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);
        huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);
    }
    else
    {
        for (int j = 0; ; ++j)
        {
            if (letter_codes[j].letter == tree[num].list[0])
            {
                letter_codes[j].code = code;
                break;
            }
        }
    }
}

void huffman_encoding(vector <B> &sorted_tree, ltcode *letter_codes)
{
    huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);
}

int main() {
    unsigned char c;
    string S;
    ltcode count[256], stringlinks[256];
    zeroset(count);

    while (scanf("%c", &c))
    {
        if (c == '\n') break;
        S += c;
        ++count[c].frequency;
    }
    sort(count, count+256, f);
    
    vector <B> tree;
    B tmp;
    tmp.list = "0";
    int j = 0, letter_amount;
    for (j = 0; (count[j].frequency); ++j)
    {
        tmp.i = count[j].frequency;
        tmp.list[0] = count[j].letter;
        tree.push_back(tmp);
    }
    int maxsize = j-1, size;
    
    sort(tree.begin(), tree.end(), [] (B a, B b)
    {
        if (a.i != b.i) return (a.i < b.i);
        else return (a.list.size() < b.list.size());
    });
    
    for (j = 0; size < maxsize;)
    {
        tmp.list = tree[j].list + tree[j+1].list;
        tmp.i = tree[j].i + tree[j+1].i;
        tmp.left = j;
        tmp.right = j+1;
        
        size = tmp.list.size();
        
        tree.push_back(tmp);
        j += 2;
        sort(tree.begin()+j, tree.end(), [] (B a, B b)
        {
            if (a.i != b.i) return (a.i < b.i);
            else return (a.list.size() < b.list.size());
        }
        );
    }
    huffman_encoding(tree, count);
    print_tree_graph(tree);
    cout << "\nCodes of letters:\n";
    for (j = 0; (count[j].frequency); ++j)
    {
        cout << '\'' << count[j].letter << "\'(" << count[j].code << ")  ";
        stringlinks[count[j].letter].code = count[j].code;
    }
    cout << "\n\nEncoded string:\n";
    for (unsigned int i = 0; i < S.size(); ++i)
    {
        cout << stringlinks[S[i]].code;
    }
    cout << '\n';
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

struct ltcode

{

unsigned long long frequency;

unsigned char letter;

string code = "";

};

void zeroset(ltcode *c)

{

for (unsigned int i = 0; i < 256; ++i)

{

c[i].frequency = 0;

c[i].letter = i;

}

bool f(ltcode x, ltcode y)

{

if (x.frequency != y.frequency) return x.frequency > y.frequency;

else return x.letter > y.letter;

}

struct B

{

string list;

int i;

int left;

int right;

string code = "";

B()

{

list = "";

i = 0;

}

};

void print_binary_tree(int num, vector &tree)

{

if (tree[num].list.size() > 1)

{

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";

print_binary_tree(tree[num].left, tree);

print_binary_tree(tree[num].right, tree);

}

void print_tree_graph(vector &tree)

{

cout << "digraph G {\n";

print_binary_tree(tree.size()-1, tree);

cout << "}\n";

}

void huffman_encoding_in(int num, string code, vector &tree, ltcode *letter_codes)

{

tree[num].code = code;

if (tree[num].list.size() > 1)

{

huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);

huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);

}

else

{

for (int j = 0; ; ++j)

{

if (letter_codes[j].letter == tree[num].list[0])

{

letter_codes[j].code = code;

break;

}

void huffman_encoding(vector &sorted_tree, ltcode *letter_codes)

{

huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);

}

int main() {

unsigned char c;

string S;

ltcode count[256], stringlinks[256];

zeroset(count);

while (scanf("%c", &c))

{

if (c == '\n') break;

S += c;

++count[c].frequency;

}

sort(count, count+256, f);

vector tree;

B tmp;

tmp.list = "0";

int j = 0, letter_amount;

for (j = 0; (count[j].frequency); ++j)

{

tmp.i = count[j].frequency;

tmp.list[0] = count[j].letter;

tree.push_back(tmp);

}

int maxsize = j-1, size;

sort(tree.begin(), tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

});

for (j = 0; size < maxsize;)

{

tmp.list = tree[j].list + tree[j+1].list;

tmp.i = tree[j].i + tree[j+1].i;

tmp.left = j;

tmp.right = j+1;

size = tmp.list.size();

tree.push_back(tmp);

j += 2;

sort(tree.begin()+j, tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

}

);

}

huffman_encoding(tree, count);

print_tree_graph(tree);

cout << "\nCodes of letters:\n";

for (j = 0; (count[j].frequency); ++j)

{

cout << '\'' << count[j].letter << "\'(" << count[j].code << ") ";

stringlinks[count[j].letter].code = count[j].code;

}

cout << "\n\nEncoded string:\n";

for (unsigned int i = 0; i < S.size(); ++i)

{

cout << stringlinks[S[i]].code;

}

cout << '\n';

return 0;

}

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

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.

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

Ссылки

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

Related Images:

Просто RSQ

15/04/2017 by Вадим Гордийчук

Задача RSQ (Range Sum Query). Вам дан массив, необходимо отвечать на запросы получения суммы на отрезке и изменение одного элемента массива.

Ссылка на задачу на codeforces.com.

Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Ограничение по памяти: 2 секунды
Ограничение по времени: 256 мегабайт

Формат входного файла

Входной файл в первой строке содержит два числа [latex]n[/latex] [latex]\left(1 \le n \le 10^{5} \right)[/latex] — размер массива и [latex]m[/latex] [latex]\left(1 \le m \le 10^{5} \right)[/latex] — количество запросов. Во второй строке задано начальное состояние массива [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex] [latex]\left( -10^{5} \le a_{i} \le 10^{5} \right)[/latex].

Далее идёт [latex]m[/latex] строк с запросами вида [latex]t[/latex] [latex]x[/latex] [latex]y[/latex] [latex]\left( 0 \le t \le 1 \right)[/latex]. Если [latex]t = 0[/latex], тогда на запрос нужно вывести сумму элементов массива с индексами от [latex]x[/latex] до [latex]y[/latex] (в данном случае [latex]1 \le x \le y \le n[/latex]). Если [latex]t = 1[/latex], тогда надо присвоить элементу массива с индексом [latex]x[/latex] значение [latex]y[/latex] (в этом случае [latex]1 \le x \le n[/latex], [latex]-10^{5} \le y \le 10^{5}[/latex]).

Формат выходного файла

На каждый запрос суммы отрезка выведите одно число в новой строке — запрашиваемая сумма.

Примеры

rsq.in	rsq.out
5 3 1 2 3 4 5 0 1 5 1 1 -14 0 1 5	15 0
8 2 7 3 -10 4 1 2 5 6 0 2 4 0 5 7	-3 8

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

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream cin("rsq.in");
    ofstream cout("rsq.out");
    ios::sync_with_stdio(false);
    unsigned int n, m, i;
    long long sum = 0, sum_k;
    int *a, x, y;
    bool t;
    cin >> n >> m; n++;
    a = new int[n];
    for (i = 1; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    const unsigned int ndiv2 = n/2;
    while (m--)
    {
        cin >> t >> x;
        if (t)
        {
            sum -= a[x];
            cin >> a[x];
            sum += a[x];
        }
        else
        {
            cin >> y;
            y++;
            if (y - x > ndiv2)
            {
                sum_k = sum;
                for (i = 1; i < x; i++)
                {
                    sum_k -= a[i];
                }
                for (i = y; i < n; i++)
                {
                    sum_k -= a[i];
                }
            }
            else
            {
                sum_k = 0;
                for (; x < y; x++)
                {
                    sum_k += a[x];
                }
            }
            cout << sum_k << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

ifstream cin("rsq.in");

ofstream cout("rsq.out");

ios::sync_with_stdio(false);

unsigned int n, m, i;

long long sum = 0, sum_k;

int *a, x, y;

bool t;

cin >> n >> m; n++;

a = new int[n];

for (i = 1; i < n; i++)

{

cin >> a[i];

sum += a[i];

}

const unsigned int ndiv2 = n/2;

while (m--)

{

cin >> t >> x;

if (t)

{

sum -= a[x];

cin >> a[x];

sum += a[x];

}

else

{

cin >> y;

y++;

if (y - x > ndiv2)

{

sum_k = sum;

for (i = 1; i < x; i++)

{

sum_k -= a[i];

}

for (i = y; i < n; i++)

{

sum_k -= a[i];

}

else

{

sum_k = 0;

for (; x < y; x++)

{

sum_k += a[x];

}

cout << sum_k << endl;

}

return 0;

}

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

Основная идея приведённого выше решения этой задачи заключается в оптимизации обработки запросов суммы построением дерева отрезков.
Сохраним сумму всех элементов массива в переменной sum. Теперь, если нам дан запрос суммы на отрезке [latex]\left[ x; y \right][/latex], то если [latex]y — x > \frac{n}{2}[/latex] (то есть если данный отрезок содержит больше элементов, чем половина всего отрезка) то считаем сумму элементов на отрезке [latex]\left[ 1; x-1 \right] \cup \left[ y+1; n \right] = \left[ 1; n \right] \setminus \left[ x; y \right][/latex] и отнимаем от суммы всех элементов, иначе (если [latex]y — x \le \frac{n}{2}[/latex], то) просто считаем сумму элементов на отрезке [latex]\left[ x; y \right][/latex]. Если же поступает запрос на замену значения элемента, то вычитаем из sum старое значение и прибавляем новое.

Таким образом, максимальная сложность запросов суммы (при простом подходе к задаче) уменьшается вдвое.

Ссылки

Related Images:

Душевая кабина

14/04/2017 by Антон Куперман

Разбор задачи F с 1/8 ACM ICPC по украинскому региону 25 марта 2017.

Задача

Степан приобрел душевую кабину, которую решил установить в дачном домике. Дачный домик представляет собой прямоугольник [latex]N \times M[/latex], разбитый на одинарные квадратики. Степан знает, что душевая кабина занимает ровно две клетки с общей стороной. Также Степану известно, что некоторые клетки дома заняты разными вещами. Помогите Степану узнать сколькими способами он может разместить душевую кабину в дачном домике.

Ввод

В первом ряду входных данных находятся два целых числа [latex] N,M(1<=N,M<=1000)[/latex] — размеры дачного домика Степана. Каждый из следующих [latex] N[/latex] рядов содержит по [latex] M[/latex] символов — описание дачного домика Степана. Символ «#» означает, что соответствующая клетка уже чем-то занята, а символ «.» — что она свободна и может стать одной из двух, занятых душевой кабиной.

Вывод

Одно число — количество способов расположить душевую кабину в дачном домике.

Тесты

Код

#include <iostream>
using namespace std;

int main() {
    int n,m;
    long s=0;
    cin>>n>>m;
    char x[n*m];
    for(int i=0;i<n*m;i++)
    {
        cin>>x[i];
    }
    for(int i=0;i<n*m;i++)
    {
        if(x[i]=='.')
        {
            if(x[i]==x[i+1])
            {
                if((i+1)%m!=0)
                {
                    s++;
                }
            }
            if(x[i]==x[i+m])
            {
                s++;
            }
        }
    }
    cout<<s;
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,m;

long s=0;

cin>>n>>m;

char x[n*m];

for(int i=0;i<n*m;i++)

{

cin>>x[i];

}

for(int i=0;i<n*m;i++)

{

if(x[i]=='.')

{

if(x[i]==x[i+1])

{

if((i+1)%m!=0)

{

s++;

}

if(x[i]==x[i+m])

{

s++;

}

cout<<s;

return 0;

}

Решение

Считываем символы в массив . Размер такого массива всегда будет [latex]n \times m[/latex]. Зная это, заводим цикл, в котором проверяем наличие точки(‘.’). Затем проверяем первое условие: если следующий символ тоже точка и если мы не перешли на новую строку, увеличиваем счетчик. Зная количество символов в каждой строке, проверяем символ «под» точкой и если они совпадают опять же увеличиваем счетчик.

Related Images:

Черная пятница

06/04/2017 by Курьянов Павел

Разбор задачи с 1/8 ACM ICPC по украинскому региону 25 марта 2017.

Задача. Завтра черная пятница — самая большая новогодняя распродажа. Степан, как владелец магазина, принял решение, что цены всех товаров будет снижено на 25%. Он выяснил, что начальные цены на все товары делились на 4, поэтому после снижения цен все цены тоже выражаются целым числом. Степан вечером перед распродажей снял ценники с всех товаров и напечатал для каждого товара еще один ценник со скидкой. Он оставил их на столе, рассчитывая утром их развесить. Но, когда он пришел утром в магазин, то выяснилось, что уборщица смешала все ценники вместе, и теперь Степану нужно отделить старые ценники от новых.
Помогите ему.
Входные данные:
Первый ряд входного файла содержит одно число N (2 ≤ N ≤ 105), N — четное. Следующие N рядов содержат положительные числа не больше чем 109, которые идут в порядке возрастания по одному в ряду — числа со всех ценников (как старых так и новых). Гарантируется, что входные данные корректны, то есть решение существует.
Выходные данные:
Вывести N/2 целых числе в порядке возрастания — стоимость товаров после снижения цен.

Тесты

входные данные	результат работы
6	30
30	40
40	45
42
45
56
60

Код задачи

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n;
    cin>>n;
    long long x[n];
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
    }
    int ind=0;
    for(int i=0;i<n-1;i++)
    {
        if(x[i]!=0)
        {
            ind=find(x+ind,x+n,x[i]*4/3)-x;
                cout<<x[i]<<'\n';
                x[ind]=0;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long n;

cin>>n;

long long x[n];

for(int i=0;i<n;i++)

{

cin>>x[i];

}

int ind=0;

for(int i=0;i<n-1;i++)

{

if(x[i]!=0)

{

ind=find(x+ind,x+n,x[i]*4/3)-x;

cout<<x[i]<<'\n';

x[ind]=0;

}

return 0;

}

Решение задачи
Так как нам изначально известно, общее количество ценников, то вводим их все в массив, где как нам уже сказано по условию, они будут располагаться в порядке возрастания. Значит, уже с первого элемента мы получим новую цену так как она будет точно меньше любой наименьшей до скидки. Находим старую цену соответствующую ей и обнуляем ее (это делается для оптимизации времени работы кода, чтоб потом мы не искали старую цену от этого элемента). Так же, после первого нахождения старой цены мы начинаем поиск остальных с этого же места, потому что меньше они точно не могут быть и наш алгоритм должен продвигаться только вперед.
Таким образом, мы проходим через все цены, выписываем все новые цены, а старые «выбрасываем» из-за ненужности.
Ссылка на код задачи