# Разбор задач 2019 года
Если Вы не знали как решать какую-то задачу и Вам было лень разбираться в коде на Pascal, то это пост специально для Вас.
:::warning
Убедительная просьба не копировать коды и не пересылать их. Помните -- Вы решаете задачи для себя!
:::

## [1. Достижение амплитуды](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2019_1)
:::spoiler Разбор
:::info
Заметим, что ответ равен $2 * n - 1$.

Асимптотика: $O(1)$.
:::
:::spoiler Код (C++, автор: [SashOK_Yatsuk](https://codeforces.com/profile/SashOK_Yatsuk))

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << 2 * n - 1 << endl;
    return 0;
}

:::

## [2. Ограниченное колебание](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2019_2)
:::spoiler Разбор
:::info
Давайте заметим, что у нас есть 4 случая:

1. Шарик еще не ударился и он находится в положительной координате.
2. Шарик еще не ударился и он находится в отрицательной координате.
3. Шарик уже ударился и он находится в отрицательной координате.
4. Шарик уже ударился и он находится в положительной координате.

Давайте разберем их.
:::
:::spoiler Код (C++, автор: [Wani4ka](https://codeforces.com/profile/Wani4ka))

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, R;
    cin >> n >> R;
    n %= R * 8;
    if (n <= R * 2) {
        if (n % 2 == 0)
            cout << "-" << n / 2 << endl;
        else cout << (n + 1) / 2 << endl;
    } else if (n <= R * 4) {
        if (n % 2 == 0)
            cout << "-" << (R * 4 - n) / 2 << endl;
        else cout << (R * 4 - n) / 2 << endl;
    } else if (n <= R * 6) {
        if (n % 2 == 0)
            cout << (n - R * 4) / 2 << endl;
        else cout << "-" << (n - R * 4 + 1) / 2 << endl;
    } else {
        if (n % 2 == 0)
            cout << (R * 8 - n) / 2 << endl;
        else cout << "-" << (R * 8 - n) / 2 << endl;
    }
    return 0;
}

:::

## [3. Трехканальное оповещение](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2019_3)
:::spoiler Разбор
:::info
Это одна из самых сложных задач из Витебских районов. С другой стороны, не такая уж и сложная.

Давайте забинарим минимально число звонков.
Теперь, меняя приоритеты звонков, проверяем, может ли каждый из звонящих совершить >= mid звонков.

Немного уточнений:

1. Если человеку может позвонить только один помощник, то он ему точно позвонит, т.е в приоритеты пихать таких людей не нужно.
2. Если человеку может позвонить все 3 помощника, то нам не нужны приоритеты для таких звонков.
3. Приоритеты могут быть на "одиночные" звонки и "двойные" звонки.
4. В начале мы пихаем(порядок обработки) все звонки по двойному приоритету, а распределяем по одиночному приоритету. Для лучшего понимания, смотрите код.

Асимптотика: $O(6 * 6 * (m1 + m2 + m3) * log(N / 3))$.
:::
:::spoiler Код (C++, автор: [Adamenko](https://codeforces.com/profile/Adamenko))

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> st(3);
vector<vector<bool>> use(3);

int n;

vector<int> m(3);

vector<int> ans;

int kol_all = 0;
vector<int> all;

vector<int> line(3);

int kol_1_2 = 0;
int kol_1_3 = 0;
int kol_2_3 = 0;

vector<int> can_1_2;
vector<int> can_1_3;
vector<int> can_2_3;

bool prioritet(int x, int y, vector<int> &pr) {
    int pos_1 = -1, pos_2 = -1;
    for (int i = 0; i < 3; ++i)
        if (pr[i] == x) pos_1 = i;
        else if (pr[i] == y) pos_2 = i;
    return pos_1 < pos_2;
}

void viber_fst(pair<int, int> tech, vector<int> &lol_1_2, vector<int> &lol_1_3, vector<int> &lol_2_3) {
    if (tech == make_pair(0, 1))
        ans[lol_1_2.back()] = 1, lol_1_2.pop_back();
    else if (tech == make_pair(0, 2))
        ans[lol_1_3.back()] = 1, lol_1_3.pop_back();
    else ans[lol_2_3.back()] = 2, lol_2_3.pop_back();
}

void viber_scd(pir<int, int> tech, vector<int> &lol_1_2, vector<int> &lol_1_3, vector<int> &lol_2_3) {
    if (tech == make_pair(0, 1))
        ans[lol_1_2.back()] = 2, lol_1_2.pop_back();
    else if (tech == make_pair(0, 2))
        ans[lol_1_3.back()] = 3, lol_1_3.pop_back();
    else ans[lol_2_3.back()] = 3, lol_2_3.pop_back();
}

bool ok(int mid) {
    if (min({m[0], m[1], m[2]}) < mid) return 0;

    vector<int> prior(3);
    for (int i = 0; i < 3; ++i) prior[i] = i;

    do {

        vector<pair<int, int>> lol;
        lol.push_back({0, 1});
        lol.push_back({0, 2});
        lol.push_back({1, 2});

        do {
            vector<pair<int, int>> kek;
            for (int i = 0; i < 3; ++i)
                if (lol[i] == make_pair(0, 1))
                    for (int j = 0; j < kol_1_2; ++j)
                        kek.push_back({0, 1});
                else if (lol[i] == make_pair(0, 2))
                    for (int j = 0; j < kol_1_3; ++j)
                        kek.push_back({0, 2});
                else if (lol[i] == make_pair(1, 2))
                    for (int j = 0; j < kol_2_3; ++j)
                        kek.push_back({1, 2});

            vector<int> kk(3);

            kk[0] = line[0];
            kk[1] = line[1];
            kk[2] = line[2];

            for (int i = 0; i < kek.size(); ++i)
                if (prioritet(kek[i].first, kek[i].second, prior) && kk[kek[i].first] < mid)
                    kk[kek[i].first]++;
                else kk[kek[i].second]++;

            int kol = 0;
            for (int i = 0; i < 3; ++i)
                kol += max(0, mid - kk[i]);

            if (kol <= kol_all) return 1;

        } while (next_permutation(lol.begin(), lol.end()));

    } while (next_permutation(prior.begin(), prior.end()));

    return 0;
}

void go(int mid) {
    vector<int> prior(3);
    for (int i = 0; i < 3; ++i)
        prior[i] = i;

    do {

        vector<pair<int, int>> lol;
        lol.push_back({0, 1});
        lol.push_back({0, 2});
        lol.push_back({1, 2});

        do {
            vector<pair<int, int>> kek;
            for (int i = 0; i < 3; ++i)
                if (lol[i] == make_pair(0, 1))
                    for (int j = 0; j < kol_1_2; ++j)
                        kek.push_back({0, 1});
                else if (lol[i] == make_pair(0, 2))
                    for (int j = 0; j < kol_1_3; ++j)
                        kek.push_back({0, 2});
                else if (lol[i] == make_pair(1, 2))
                    for (int j = 0; j < kol_2_3; ++j)
                        kek.push_back({1, 2});

            vector<int> kk(3);

            kk[0] = line[0];
            kk[1] = line[1];
            kk[2] = line[2];

            for (int i = 0; i < kek.size(); ++i)
                if (prioritet(kek[i].first, kek[i].second, prior) && kk[kek[i].first] < mid)
                    kk[kek[i].first]++;
                else kk[kek[i].second]++;

            int kol = 0;
            for (int i = 0; i < 3; ++i)
                kol += max(0, mid - kk[i]);

            if (kol <= kol_all) {

                kk[0] = line[0];
                kk[1] = line[1];
                kk[2] = line[2];

                vector<int> nonka_1_2 =  can_1_2;
                vector<int> nonka_1_3 =  can_1_3;
                vector<int> nonka_2_3 =  can_2_3;

                for (int i = 0; i < kek.size(); ++i)
                    if (prioritet(kek[i].first, kek[i].second, prior) && kk[kek[i].first] < mid)
                        kk[kek[i].first]++, viber_fst(kek[i], nonka_1_2, nonka_1_3, nonka_2_3);
                    else kk[kek[i].second]++, viber_scd(kek[i], nonka_1_2, nonka_1_3, nonka_2_3);

                int tech = kol_all;
                vector<int> now = all;

                for (int i = 0; i < 3; ++i)
                    while(kk[i] < mid)
                        tech--, kk[i]++, ans[now.back()] = i + 1, now.pop_back();

                for (int i = 0; i < tech; ++i)
                    ans[now.back()] = 1, now.pop_back();
                return;
            }
        } while (next_permutation(lol.begin(), lol.end()));
    } while (next_permutation(prior.begin(), prior.end()));
}


int main() {
    scanf("%i%i%i%i", &n, &m[0], &m[1], &m[2]);
    for (int i = 0; i < 3; ++i) {
        use[i].resize(n + 1, 0);
        for (int j = 0; j < m[i]; ++j) {
            int x;
            scanf("%i", &x);
            if (use[i][x]) continue;
            use[i][x] = 1;
            st[i].push_back(x);
        }
        m[i] = st[i].size();
    }


    ans.resize(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        int kol = 0;
        for (int j = 0; j < 3; ++j)
            if (use[j][i]) kol++;
        if (kol == 3) {
            kol_all++;
            all.push_back(i);
        } else if (kol == 1) {
            for (int j = 0; j < 3; ++j)
                if (use[j][i]) {
                    ans[i] = j + 1;
                    line[j]++;
                    break;
                }
        } else {
            if (use[0][i] && use[1][i])
                kol_1_2++,  can_1_2.push_back(i);
            else if (use[0][i] && use[2][i])
                kol_1_3++, can_1_3.push_back(i);
            else kol_2_3++, can_2_3.push_back(i);
        }
    }

    int l = min({line[0], line[1], line[2]}), r = min(n / 3, min({m[0], m[1], m[2]}));

    int ot = -1;

    while (l <= r) {
        int mid = (l + r) >> 1;
        if (ok(mid))
            l = mid + 1, ot = mid;
        else r = mid - 1;
    }
    go(ot);
    for (int i = 1; i <= n; ++i)
        printf("%i%c", ans[i], ' ');
    return 0;
}

:::
:::spoiler Код (C++, автор: [mrboorger](https://codeforces.com/profile/mrboorger))

#pragma gcc target("sse,sse2,sse3,ssse3,sse4")
#pragma gcc optimize("-Ofast")
//
#include <bits/stdc++.h>

#define F first
#define S second
#define ll long long
#define pb push_back

using namespace std;

const int maxn = 1e6 + 23;
const int inf = 1e9;

bool a[3][maxn];
int m[3];
int sum[3];
int answ[maxn];
int kek[maxn];
int kek01[maxn];
int kek02[maxn];
int kek12[maxn];
int cnt = 0;
int cnt01 = 0;
int cnt02 = 0;
int cnt12 = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n >> m[0] >> m[1] >> m[2];
    for(int k = 0; k < 3; ++k)
        for(int i = 0; i < m[k]; ++i)
        {
            int x;
            cin >> x;
            --x;
            a[k][x] = true;
        }
    for(int i = 0; i < n; ++i)
    {
        if (a[0][i] && a[1][i] && a[2][i])
        {
            kek[cnt++] = i;
            a[0][i] = false;
            a[1][i] = false;
            a[2][i] = false;
        }
        if (a[0][i] && !a[1][i] && !a[2][i])
        {
            answ[i] = 0;
            ++sum[0];
            a[0][i] = false;
        }
        if (!a[0][i] && a[1][i] && !a[2][i])
        {
            answ[i] = 1;
            ++sum[1];
            a[1][i] = false;
        }
        if (!a[0][i] && !a[1][i] && a[2][i])
        {
            answ[i] = 2;
            ++sum[2];
            a[2][i] = false;
        }
        //
        if (a[0][i] && a[1][i])
        {
            kek01[cnt01++] = i;
            a[0][i] = false;
            a[1][i] = false;
        }
        if (a[0][i] && a[2][i])
        {
            kek02[cnt02++] = i;
            a[0][i] = false;
            a[2][i] = false;
        }
        if (a[1][i] && a[2][i])
        {
            kek12[cnt12++] = i;
            a[1][i] = false;
            a[2][i] = false;
        }
    }
    int l = 0, r = (n + 2) / 3;
    int ans = -1;
    int lola = 0;
    int lolb = 0;
    int lolc = 0;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        bool f = false;
        int biba = 0;
        int bibb = 0;
        int bibc = 0;
        for(int a = 0; a <= cnt01; ++a)
        {
            int b = max(mid - sum[0] - a, 0);
            int c = max(mid - sum[1] - cnt01 + a, 0);
            if (b > cnt02 || c > cnt12) continue;
            if (sum[0] + a + b >= mid && sum[1] + cnt01 - a + c >= mid && sum[2] + cnt02 - b + cnt12 - c >= mid)
            {
                f = true;
                biba = a;
                bibb = b;
                bibc = c;
            }
        }
        if (f)
        {
            if (mid > ans)
            {
                ans = mid;
                lola = biba;
                lolb = bibb;
                lolc = bibc;
            }
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    sum[0] += lola + lolb;
    sum[1] += cnt01 - lola + lolc;
    sum[2] += cnt02 - lolb + cnt12 - lolc;
    for(int i = 0; i < lola; ++i)
        answ[kek01[i]] = 0;
    for(int i = lola; i < cnt01; ++i)
        answ[kek01[i]] = 1;

    for(int i = 0; i < lolb; ++i)
        answ[kek02[i]] = 0;
    for(int i = lolb; i < cnt02; ++i)
        answ[kek02[i]] = 2;
    for(int i = 0; i < lolc; ++i)
    {
        answ[kek12[i]] = 1;
    }
    for(int i = lolc; i < cnt12; ++i)
        answ[kek12[i]] = 2;

    int d[3] = {0, 0, 0};
    int sup = cnt;
    pair <int, int> ss[3] = {{sum[0], 0}, {sum[1], 1}, {sum[2], 2}};
    sort(ss, ss + 3);
    {
        int z = max(min(ss[1].F - ss[0].F, sup), 0);
        sup -= z;
        ss[0].F += z;
        d[ss[0].S] += z;
    }
    if (sup > 0)
    {
        int vvv = min(ss[2].F - ss[1].F, sup / 2);
        sup -= vvv * 2;
        ss[0].F += vvv;
        ss[1].F += vvv;
        d[ss[0].S] += vvv;
        d[ss[1].S] += vvv;
        if (sup == 1)
        {
            ss[0].F++;
            d[ss[0].S]++;
            --sup;
        }
    }

    int ost = sup % 3;
    sup /= 3;
    d[0] += sup + (ost > 0);
    --ost;
    d[1] += sup + (ost > 0);
    --ost;
    d[2] += sup + (ost > 0);
    for(int i = 0; i < d[0]; ++i)
        answ[kek[i]] = 0;
    for(int i = d[0]; i < d[0] + d[1]; ++i)
        answ[kek[i]] = 1;
    for(int i = d[0] + d[1]; i < cnt; ++i)
        answ[kek[i]] = 2;
    for(int i = 0; i < n; ++i)
        cout << answ[i] + 1 << ' ';
    return 0;
}

:::

## [4. Лабиринт Каталана](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2019_4)
:::spoiler Разбор
:::info
Пишем черепаху. На этом все!

Асимптотика: $O(N * M)$.
:::
:::spoiler Код (C++, автор: [Adamenko](https://codeforces.com/profile/Adamenko))

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int a[1000][10000];
int dp[1000][10000];

int n, m;

int main() {
    scanf("%i%i", &n, &m);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            scanf("%i", &a[i][j]);
    dp[0][0] = 1;
    for (int i = 1; i < n; ++i)
        if (a[i][0] - a[i - 1][0] <= 1)
            dp[i][0] = 1;
        else break;
    for (int i = 1; i < m; ++i)
        if (a[0][i] - a[0][i - 1] <= 1)
            dp[0][i] = 1;
        else break;
    for (int i = 1; i < n; ++i)
        for (int j = 1; j < m; ++j) {
            if (a[i][j] - a[i - 1][j] <= 1)
                dp[i][j] += dp[i - 1][j];
            dp[i][j] %= mod;
            if (a[i][j] - a[i][j - 1] <= 1)
                dp[i][j] += dp[i][j - 1];
            dp[i][j] %= mod;
        }
    printf("%i", dp[n - 1][m - 1]);
    return 0;
}

:::