# Разбор задач 2021 года
:::warning
Убедительная просьба не копировать коды и не пересылать их. Помните -- Вы решаете задачи для себя!
:::

## 1. Простые соседних интервалов
:::spoiler Разбор
:::info
Давайте забинарим ответ. И теперь для каждого отрезка длины mid проверим, содержит ли он как минимум $K$ простых чисел. Это можно делать эффективно предпрощитав зарание массив преффиксов $pref_i$ - количество простых чисел на отрезке $[1..i]$ и при проверке в бинарном поиске за $О(n)$ проверим на корректность каждый отрезок.
:::

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

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define endl '\n'
#define TIME 1.0*clock()/CLOCKS_PER_SEC
#define pii pair < int , int >
#define Endl '\n'

#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;


template <typename T>
using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;

const int SX[4] = {0 , 1 , -1 , 0};
const int SY[4] = {1 , 0 , 0 , -1};
const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};

typedef cc_hash_table< int, int, hash<int>, equal_to<int>, direct_mask_range_hashing<int>, hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>> ht;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    int a, b, k;
    cin >> a >> b >> k;
    int ans = 1e9;
    vector < int > pref(b + 1);
    pref[0] = 0;
    pref[1] = 0;
    for (int i = 2;i <= b; ++i){
        bool ok = 1;
        for (int d = 2;d * d <= i; ++d){
            if (i % d == 0){
                ok = 0;
                break;
            }
        }
        pref[i] = pref[i - 1] + ok;
    }
    int ot = -1;
    int l = 1, r = b - a + 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        bool ok = 1;
        for (int i = a;i + mid - 1 <= b; ++i){
            if (pref[i + mid - 1] - pref[i - 1] >= k)continue;
            ok = 0;
            break;
        }
        if (ok)r = mid - 1, ot = mid;
        else l = mid + 1;
    }
    cout << ot << endl;
    return 0;
}

:::

## [2. Минимумы в перестановке](https://codeforces.com/group/skz9fIV5Hq/contest/321564/problem/B)
:::spoiler Разбор
:::info
Давайте решим данную задачу для $N \leq 7$ и сделаем некоторые замечания:

1. Количество последовательностей, котоорые нам подходят под условия задачи $(N - 1) ^ 2$.
2. Три числа $N$, $N - 1$, $N - 2$ постоянно находятся "рядом" друг с другом.

Вот 4 случая расположения этих 3-х чисел:

    // 1
    all[0][0] = n - 2;
    all[0][1] = n - 1;
    all[0][2] = n;
 
    // 2
    all[1][0] = n - 2;
    all[1][1] = n;
    all[1][2] = n - 1;
 
    // 3
    all[2][0] = n - 1;
    all[2][1] = n;
    all[2][2] = n - 2;
 
    // 4
    all[3][0] = n;
    all[3][1] = n - 1;
    all[3][2] = n - 2;

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

3. Эти три числа двигаются от конца к началу.

1 2 3 [4 5 6]
1 2 3 [4 6 5]
1 2 3 [5 6 4]
1 2 3 [6 5 4]
1 2 [4 5 6] 3
1 2 [4 6 5] 3
1 2 [5 6 4] 3
1 2 [6 5 4] 3
...
1 [4 5 6] 3 2
1 [4 6 5] 3 2
1 [5 6 4] 3 2
1 [6 5 4] 3 2

4. Давайте рассмотрим больший пример и придумаем конструктор.
5. Давайте научимся определять последний элемент.
6. Заведем множество чисел, в которое будут входить числа от [1 до N - 3].
7. Давайте заметим, что количество последовательностей, которые заканчиваются на

$N - 3$ - 4 шт.
$N - 4$ - 8 шт.
$N - 5$ - 16 шт.

8. Давате вычтем из K -= $2^x$, где $x$ - максимальная степень двойки, которая строго меньше K. Текущий элемент последовательности это (x - 2)-ый элемент по убыванию, из множества чисел. Поставили число, затем удалили его из множества.
9. Крайний случай, когда K <= 4. Разберем его отдельно.

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

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define endl '\n'
#define TIME 1.0*clock()/CLOCKS_PER_SEC
#define pii pair < int , int >
#define Endl '\n'

#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;

const int SX[4] = {0 , 1 , -1 , 0};
const int SY[4] = {1 , 0 , 0 , -1};
const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};

typedef cc_hash_table< int, int, hash<int>, equal_to<int>, direct_mask_range_hashing<int>, hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>> ht;

void solve(){
    ll n, k;
    cin >> n >> k;
    if (n == 1){
        cout << 1 << endl;
        return;
    }
    if (n == 2){
        if (k == 1)cout << "1 2" << endl;
        else cout << "2 1" << endl;
        return;
    }
    int all[4][3];
    // 1
    all[0][0] = n - 2;
    all[0][1] = n - 1;
    all[0][2] = n;

    // 2
    all[1][0] = n - 2;
    all[1][1] = n;
    all[1][2] = n - 1;

    // 3
    all[2][0] = n - 1;
    all[2][1] = n;
    all[2][2] = n - 2;

    // 4
    all[3][0] = n;
    all[3][1] = n - 1;
    all[3][2] = n - 2;

    int ans[n];
    set < int > st;
    for (int i = 0;i < n; ++i)st.insert(i + 1);
    st.erase(n);
    st.erase(n - 1);
    st.erase(n - 2);

    int pos = n - 1;
    while(k){
        if (k <= 4){
            int mem = 0;
            for (int i = 0;i <= pos; ++i){
                if (st.size()){
                    ans[i] = *st.begin();
                    st.erase(ans[i]);
                }else{
                    ans[i] = all[k - 1][mem];
                    mem++;
                }
            }
            k = 0;
            continue;
        }
        ll kol = 4;
        int p = 0;
        while(k - kol * 2 > 0)kol *= 2, p++;
        k -= kol;
        vector < int > lol;
        for (auto to : st)lol.pb(to);
        for (int i = 0;i < p; ++i)lol.pop_back();
        ans[pos] = lol.back();
        st.erase(lol.back());
        pos--;
    }

    for (auto to : ans)cout << to << " ";
    cout << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while(t --> 0)solve();
    return 0;
}

:::

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

Асимптотика: $O(N + |allS|)$, где $|allS|$ -- длина всех строк.
:::

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

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

vector<string> w;

int main() {
    string s;

    getline(cin,s);
    string cur = "";
    for (int i = 0; i < s.size(); i++)
        if (s[i] == ' ') {
            w.push_back(cur);
            cur = "";
        } else cur += s[i];
    if (cur != "")
        w.push_back(cur);

    int ma=0;
    string ans;

    for (int i = 0; i < w.size(); i++) {
        vector<int> gl;
        int pr = -1;
        for (int j = 0; j < w[i].size(); j++)
            if (w[i][j]=='a' || w[i][j]=='e' || w[i][j]=='y' || w[i][j]=='i' || w[i][j]=='o' || w[i][j]=='u')
                gl.pb(j);
        int cur = 0;
        string t;

        for (int j = 0; j < w[i].size(); j++)
            if (cur == 0 && j < gl[0])
                t += w[i][j];
            else if(cur == gl.size()-1 && j >= gl[cur])
                t+=w[i][j];
            else if (gl[cur] == j && cur != gl.size()-1) {
                t += w[i][j];
                cur++;
                if (gl[cur] - gl[cur-1] <= 2 || w[i][j] == 'y') {
                    if (t.size() > ma) {
                        ans = t;
                        ma = t.size();
                    }
                    t = "";
                }
            } else if (gl[cur-1] == j-1) {
                t += w[i][j];
                if (t.size()>1) {
                    if (t.size() > ma) {
                        ans = t;
                        ma = t.size();
                    }
                    t = "";
                }
            } else t+=w[i][j];

        if(t != "") {
            if (t.size() > ma) {
                ans = t;
                ma = t.size();
            }
            t = "";
        }
    }

    cout << ans << endl;
}

:::

## [4. Пессимистичный прогноз](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2016_4)
:::spoiler Разбор
:::info
Давайте напишем жадный алгоритм. Вначале отсортируем все команды по рейтингу (он описан в условии). Теперь все команды, которые выше $k$-й, мы трогать не будем (выдавать медали). Оставшимся командам будем жадно выдавать медали по следующему алгоритму:
1. Пытаемся выдать на $1$ бронзовую медаль больше, чем у $k$-й (если можем), при этом уравниваем количество золотых и серебрянных медалей.
2. Пытаемся выдать на $1$ серебрянную медаль больше, чем у $k$-й (если можем), при этом уравниваем количество золотых медалей.
3. Пытаемся выдать на $1$ золотую медаль больше чем у $k$-й (если можем).

Асимптотика решения: $O(N * log(N))$.
:::

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

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

struct node {
    int Gold, Silver, Bronze;
    int id;
    node() {
        Gold = 0;
        Silver = 0;
        Bronze = 0;
        id = -1;
    }
    bool operator < (const node &x) {
        if (x.Gold != Gold) return x.Gold > Gold;
        else if (x.Silver != Silver) return x.Silver > Silver;
        else return x.Bronze > Bronze;
    }
};

vector<node> all;

int kol_Gold = 0;
int kol_Silver = 0;
int kol_Bronze = 0;

int main() {
    int n, k;
    cin >> n >> k >> kol_Gold >> kol_Silver >> kol_Bronze;
    all.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> all[i].Gold >> all[i].Silver >> all[i].Bronze;
        all[i].id = i + 1;
    }
    sort(all.rbegin(), all.rend());
    int ans = 0;
    bool ok = 1;
    node Team;
    for (int i = 0; i < n; ++i) {
        if (all[i].id != k && ok) {
            ans++;
            continue;
        }
        if (all[i].id == k) {
            ok = 0;
            Team = all[i];
            continue;
        }
        int need_Gold = -all[i].Gold + Team.Gold;
        int need_Silver = -all[i].Silver + Team.Silver;
        int need_Bronze = -all[i].Bronze + Team.Bronze;
        if (need_Gold <= kol_Gold && need_Silver <= kol_Silver && need_Bronze + 1 <= kol_Bronze) {
            kol_Gold -= (need_Gold < 0 ? 0 : need_Gold);
            kol_Silver -= (need_Silver < 0 ? 0 : need_Silver);
            kol_Bronze -= (need_Bronze >= 0 ? need_Bronze + 1 : 0);
            ans++;
            continue;
        }
        if (need_Gold <= kol_Gold && need_Silver + 1 < kol_Silver) {
            kol_Gold -= (need_Gold < 0 ? 0 : need_Gold);
            kol_Silver -= (need_Silver >= 0 ? need_Silver + 1 : 0);
            ans++;
            continue;
        }
        if (need_Gold + 1 <= kol_Gold) {
            kol_Gold -= (need_Gold >= 0 ? need_Gold + 1 : 0);
            ans++;
            continue;
        }
    }
    cout << ans << endl;
    return 0;
}

:::