e-olimp 8536. Заповнення смуги $3 \times n$

03/05/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

#include <iostream>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   int F[51] = {0, 1, 1, 2, 3};
   for(int i = 5; i <= n; i++) {
      F[i] = F[i-2] + F[i-3] + F[i-4];
   }
   cout << F[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int F[51] = {0, 1, 1, 2, 3};

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

F[i] = F[i-2] + F[i-3] + F[i-4];

}

cout << F[n];

return 0;

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

#include <iostream>
using namespace std;
 
int F[51] = {0, 1, 1, 2, 3};
 
int numberOfWays(int n) {
   if(F[n]) {
      return F[n];
   } else {
      F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
   }
   return F[n];
}
 
int main() {
   int n;
   cin >> n;
   cout << numberOfWays(n);
   return 0;
}

#include <iostream>

using namespace std;

int F[51] = {0, 1, 1, 2, 3};

int numberOfWays(int n) {

if(F[n]) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

int main() {

int n;

cin >> n;

cout << numberOfWays(n);

return 0;

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

Related Images:

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

30/03/2020 by Евгений Фищук

Триомино

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

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

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

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

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

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

Тесты

№	Входные данные	Выходные данные
1	3 3 4 6	3 0 11
2	4 12 15 21 9	153 571 7953 41

Код

#include <iostream>
#include <vector>
#define MOD 1000000
typedef long long ll;
using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {
    ll x00 = v1[0][0];
    ll x01 = v1[0][1];
    ll x10 = v1[1][0];
    ll x11 = v1[1][1];
    ll res00, res01, res10, res11;
    res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;
    res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;
    res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;
    res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;
    return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };
}
vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

    if (p == 1) return v;
    if ((p % 2) == 0) {
        vector<vector<ll>> vct = (pow_mod(v, p / 2));
        return multiply(vct);
    }
}

int main() {
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        if (n % 3)
        {
            cout << 0 << endl;
        }
        else
        {
            n /= 3;
            int p = 2;
            ll a1 = 1, a2 = 1;
            while (n > 0)
            {
                if (n & 1)
                {
                    vector<vector<ll>> a = { {4,-1},{1,0} };
                    a = pow_mod(a, p / 2);
                    ll tmp1 = a1;
                    ll tmp2 = a2;
                    a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;
                    a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;
                }
                p *= 2;
                n >>= 1;
            }
            cout << a1 % MOD << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#define MOD 1000000

typedef long long ll;

using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {

ll x00 = v1[0][0];

ll x01 = v1[0][1];

ll x10 = v1[1][0];

ll x11 = v1[1][1];

ll res00, res01, res10, res11;

res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;

res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;

res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;

res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;

return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };

}

vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

if (p == 1) return v;

if ((p % 2) == 0) {

vector<vector<ll>> vct = (pow_mod(v, p / 2));

return multiply(vct);

}

int main() {

int t, n;

cin >> t;

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

{

cin >> n;

if (n % 3)

{

cout << 0 << endl;

}

else

{

n /= 3;

int p = 2;

ll a1 = 1, a2 = 1;

while (n > 0)

{

if (n & 1)

{

vector<vector<ll>> a = { {4,-1},{1,0} };

a = pow_mod(a, p / 2);

ll tmp1 = a1;

ll tmp2 = a2;

a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;

a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;

}

p *= 2;

n >>= 1;

}

cout << a1 % MOD << endl;

}

return 0;

}

Решение

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

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

Ссылки

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

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

Related Images:

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

29/01/2020 by Валентин Цушко

Условие

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

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

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

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

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

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

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

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

Тесты

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

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

#include <iostream>
using namespace std;
 
int main()
{
    int w, n;
    const int NegNum = -1;
    cin >> w >> n;
    int WeiCos[n][2], s[w + 1];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            cin >> WeiCos[i][j];
        }
    }
    s[0] = 0;
    for(int j = 1; j <= w; j++){
        s[j] = NegNum;
    }
    for(int i = 0; i < n; i++){
        for(int j = WeiCos[i][0]; j <= w; j++){
            if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){
                s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];
            }
        }
    }
    int maxS = 0;
    for(int i = 1; i <= w; i++){
        maxS = max(maxS, s[i]);
    }
    cout << maxS;
 
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int w, n;

const int NegNum = -1;

cin >> w >> n;

int WeiCos[n][2], s[w + 1];

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

for(int j = 0; j < 2; j++){

cin >> WeiCos[i][j];

}

s[0] = 0;

for(int j = 1; j <= w; j++){

s[j] = NegNum;

}

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

for(int j = WeiCos[i][0]; j <= w; j++){

if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){

s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];

}

int maxS = 0;

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

maxS = max(maxS, s[i]);

}

cout << maxS;

return 0;

}

Решение

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

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

Related Images:

e-olymp 657. Игра с монетами

22/06/2019 by Богдан Подгорный

Задача взята с сайта e-olymp

Условие

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более $ K$ стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

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

В первой строке находится сначала число стопок $ N,$ за ним идут $ N$ чисел, задающих количество монет в стопках слева направо, а затем число $ K.$ Все числа в строке разделены пробелами.
$ 1 \leqslant N \leqslant 180, 1 \leqslant K \leqslant 80,$ количество монет в стопке — не менее $ 1$ и не более $ 20 000$.

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

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

Тесты

№	Inputs	Outputs
1	3 4 9 1 3	14
2	4 1 2 2 7 3	5
3	5 3 4 8 1 7 2	18
4	12 67 8 6 12 6 90 54 89 145 32 45 65 4	357
5	14 32 53 5 52 9 8 17 5 87 44 51 12 15 56 10	312
6	14 76 112 3 1 98 4 172 33 65 90 2 71 18 32 14	777

Код

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){
    if(sum[l][k][p]){
        return sum[l][k][p];
    }
    int ans = 0;
    if(arr.size() - l <= k){
        for(int i = l; i < arr.size(); i++){
            ans += arr[i];
        }
        if(p == 2){
            sum[l][k][p] = 0;
            return sum[l][k][p];
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    if(p == 1){
        int temp = 0;
        for(int i = 1; i <= k; i++){
            temp += arr[(l-1) + i];
            ans = max(ans, temp + solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    else{
        int ans = INT_MAX;
        for(int i = 1; i <= k; i++){
            ans = min(ans, solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
}

int main() {
    int n, k, a;
    vector<int> coins;
    cin >> n;
    for(int i = 0; i > a;
        coins.push_back(a);
    }
    cin >> k;
    cout << solution(coins, 0, k, 1);
    return 0;
}

#include <iostream>

#include <vector>

#include <limits.h>

using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){

if(sum[l][k][p]){

return sum[l][k][p];

}

int ans = 0;

if(arr.size() - l <= k){

for(int i = l; i < arr.size(); i++){

ans += arr[i];

}

if(p == 2){

sum[l][k][p] = 0;

return sum[l][k][p];

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

if(p == 1){

int temp = 0;

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

temp += arr[(l-1) + i];

ans = max(ans, temp + solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

else{

int ans = INT_MAX;

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

ans = min(ans, solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

int main() {

int n, k, a;

vector<int> coins;

cin >> n;

for(int i = 0; i > a;

coins.push_back(a);

}

cin >> k;

cout << solution(coins, 0, k, 1);

return 0;

}

Решение

Анализируя задачу, становится понятно, что ее можно решить методами динамического программирования, а именно трехмерная динамика по параметрам: количество уже взятых стопок — l, количество стопок, которые можно взять kи какой игрок сейчас ходит p. Каждый игрок старается ходить оптимально, тогда для первого игрока задача взять максимальное количество монет, а для второго игрока задача оставить наименьшее количество монет оппоненту. Решение исполнено с помощью рекурсии, где терминальный случай-когда в массиве осталось количество стопок, меньшее или равное тому, сколько игрок может взять. Также стоит проверять высчитывалась ли раньше данная позиция, иначе задача не зайдет по времени.

Ссылки

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:

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:

e-olymp 1266. CD

18/06/2015 by Байков Дмитро

Вам предстоит длительное путешествие на автомобиле. К сожалению, у Вас в машине есть только магнитофон, а лучшая музыка записана на компакт дисках. У Вас есть чистая магнитофонная лента с длительностью звучания [latex]N[/latex] минут. Вам нужно выбрать песни для записи на магнитофонную ленту таким образом, чтобы не используемое на ней место было минимально.

Предположения:

количество треков на CD не превышает [latex]100[/latex]
ни один трек не длится более [latex]N[/latex] минут
длина каждого трека выражена целым числом
[latex]N[/latex] также целое [latex](0\leq[/latex][latex]N\leq[/latex][latex]200)[/latex]

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

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

Входные данные содержат несколько строк. В каждой строке сначала задано число [latex]N[/latex], далее количество треков и длительность звучания каждого трека. Все числа разделены пробелами. Например, в первой строке входных данных первым задано [latex]N=5[/latex], далее количество треков [latex]s=3[/latex], первый трек имеет длительность [latex]1[/latex] минуту, второй — [latex]3[/latex] минуты, и последний — [latex]4[/latex] минуты.

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

Выведите строку «sum:» и далее продолжительность записи.

Входные данные	Выходные данные
5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2	sum:5 sum:10 sum:19 sum:55 sum:45

Код:

#include <cstdio>
using namespace std;
 
short d[210][110];
short arr[110];
 
short max (short a, short b) {
	return a<b ? b : a;	
}
int main() {
	int n;
	while (scanf("%d", &n)>0){
		int k;
		scanf("%d", &k);
		for (int i=1; i<=k; i++) scanf("%d", &arr[i]);
		for (int i=1; i<=k; i++)
			for (int j=0; j<=n; j++)
				if (arr[i]<=j) d[j][i]=max(d[j][i-1], arr[i]+d[j-arr[i]][i-1]);
				else d[j][i]=d[j][i-1];
		printf("sum:%d\n", d[n][k]);
	}
	return 0;
}

#include <cstdio>

using namespace std;

short d[210][110];

short arr[110];

short max (short a, short b) {

return a<b ? b : a;

}

int main() {

int n;

while (scanf("%d", &n)>0){

int k;

scanf("%d", &k);

for (int i=1; i<=k; i++) scanf("%d", &arr[i]);

for (int i=1; i<=k; i++)

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

if (arr[i]<=j) d[j][i]=max(d[j][i-1], arr[i]+d[j-arr[i]][i-1]);

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

printf("sum:%d\n", d[n][k]);

}

return 0;

}

Ссылка на засчитанное решение

Ссылка на ideone

import java.util.*;
import java.lang.*;
import java.io.*;
class CD
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[][] d = new int[210][110];
		short[] arr = new short[110];
		Scanner in = new Scanner(System.in); 
		while (in.hasNext()){
			short n = in.nextShort();	
			short k = in.nextShort();
			for (int i=1; i<=k; i++) arr[i] = in.nextShort();
			for (int i=1; i<=k; i++)
				for (int j=0; j<=n; j++)
					if (arr[i]<=j){
						if (d[j][i-1]< arr[i]+d[j-arr[i]][i-1]) d[j][i]=arr[i]+d[j-arr[i]][i-1];
						else d[j][i]=d[j][i-1];
					}
					else d[j][i]=d[j][i-1];
					System.out.printf("sum: " + d[n][k]);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class CD

{

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

{

int[][] d = new int[210][110];

short[] arr = new short[110];

Scanner in = new Scanner(System.in);

while (in.hasNext()){

short n = in.nextShort();

short k = in.nextShort();

for (int i=1; i<=k; i++) arr[i] = in.nextShort();

for (int i=1; i<=k; i++)

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

if (arr[i]<=j){

if (d[j][i-1]< arr[i]+d[j-arr[i]][i-1]) d[j][i]=arr[i]+d[j-arr[i]][i-1];

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

}

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

System.out.printf("sum: " + d[n][k]);

}

Ссылка на ideone

Алгоритм решения построен на методе динамического программирования.

Возможны два варианта:

Либо трек не попал на диск, следовательно длинна уже записанных треков на диск [latex](d[j][i])[/latex] равна предыдущему числу ранее записанных треков [latex](d[j][i-1])[/latex].
Либо трек попал на диск, а значит [latex]d[j][i][/latex] равно максимуму из суммы ранее записанных треков [latex](d[j][i-1])[/latex] и суммы заданной длинны [latex]arr[i][/latex] c [latex]d[j-arr[i]][i-1]][/latex], где [latex]d[j-arr[i]][i-1]][/latex] равен сумме уже записанных треков при предыдущем элементе массива [latex]arr[i-1][/latex]