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

## [1. Престиж фирмы](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2018_1)
:::spoiler Разбор
:::info
Давайте востановим цены товаров. Затем отсортируем их. Найдем максимальное количество товаров, которые мы можем купить. Пройдемся "скользящим" окном по всем ценам и выведем лучший ответ.

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

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

int main() {
    int can, n;
    cin >> can >> n;
    vector<int> a;
    int x;
    cin >> x;
    a.push_back(x);
    for (int i = 1; i < n; i++) {
        int y;
        cin >> y;
        a.push_back(a.back() + y);
    }
    sort(a.begin(), a.end());
    int cnt = 0, s = 0, l = 0;
    for (int i = 0; i < n; i++) {
        if (s + a[i] > can) break;
        s += a[i];
        cnt++;
    }
    int mn = a[0];

    while (cnt < n) {
        s += a[cnt];
        cnt++;
        mn = a[l];
        s -= mn;
        if (s > can) {
            cout << mn << endl;
            return 0;
        }
        l++;
        mn = a[l];
    }

    cout << mn << endl;
}

:::

## [2. Набор кода](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2018_2)
:::spoiler Разбор
:::info
*Скоро здесь будет разбор задачи*
:::
:::spoiler Код (C++, автор: [Zhdun](https://codeforces.com/profile/Zhdun))

:::

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

Асимптотика: $O(N^3)$.

Казалось бы, куб не должен работать, но с несколькими отсечениями по времени код летит.
Упражнение -- докажите, что решение работает быстро при данных ограничениях.

P.S. *Я сам не знаю точно, почему это решение работает быстро.*
:::
:::spoiler Код (C++, автор: [Adamenko](https://codeforces.com/profile/Adamenko))

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

#define TIME 1.0*clock()/CLOCKS_PER_SEC

int main() {
    int a, b, c, d, n;
    cin >> a >> b >> c >> d >> n;
    int kol_1 = 0;
    int kol_2 = 0;
    int kol_3 = 0;
    int kol_4 = 0;
    int ans = 0;
    int kol = a + b + c + d - n;
    if (kol < 0) {
        cout << 0 << endl;
        return 0;
    }
    if (kol == 0) {
        cout << 1 << endl;
        return 0;
    }
    for (int i = kol; i >= 0; --i) {
        kol_1 = i;
        kol_2 = i;
        if (TIME > 0.98) {
            cout << 0 << endl;
            return 0;
        }
        if (kol_1 > a || kol_2 > b) continue;
        for (int j = kol - i; j >= 0; --j) {
            kol_2 = i + j;
            kol_3 = j;
            if (TIME > 0.98) {
                cout << 0 << endl;
                return 0;
            }
            if (kol_2 > b || kol_3 > c) continue;
            for (int z = kol - i - j; z >= 0; --z) {
                kol_3 = z + j;
                kol_4 = z;
                if (TIME > 0.98) {
                    cout << 0 << endl;
                    return 0;
                }
                if (kol_3 > c || kol_4 > d) continue;
                int l = kol - i - j - z;
                kol_1 = i + l;
                kol_4 = z + l;
                if (kol_1 > a || kol_4 > d) continue;
                int SS = n - kol;
                if (SS == (a - kol_1) + (b - kol_2) + (c - kol_3) + (d - kol_4))ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

:::

## [4. Полоска королей](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2018_4)
:::spoiler Разбор
:::info
Давайте посчитаем динамику $dp[i][j][k]$ -- количество способов расставить $k$-го короля на позицию $[i][j]$.

Переходы:
1. $dp[j][0][kk] += dp[i][0][kk-1] + dp[i][1][kk-1]$, $(j - 2 \leq i \leq n)$
2. $dp[j][1][kk] += dp[i][0][kk-1] + dp[i][1][kk-1]$, $(j - 2 \leq i \leq n)$

Ответ считается как сумма всех $dp[i][0, 1][k]$.

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

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

long long dp[100][2][100];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        dp[i][0][1] = 1;
        dp[i][1][1] = 1;
    }
    for (int kk = 2; kk <= k; ++kk)
       for (int j = 1; j <= n; ++j)
           for (int i = j - 2;i >= 1; --i){
                dp[j][0][kk] += dp[i][0][kk-1] + dp[i][1][kk-1];
                dp[j][1][kk] += dp[i][0][kk-1] + dp[i][1][kk-1];
           }
    long long ans = 0;
    for (int i = 0; i <= n; ++i)
        ans += dp[i][0][k] + dp[i][1][k];
    cout << ans << endl;
    return 0;
}

:::