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

## [1. Порядок различных значений](https://codeforces.com/group/skz9fIV5Hq/contest/409232/problem/A)
:::spoiler Разбор
:::info
Отсортируем массив и пройдём по всем его элементам. Будем уменьшать $k$ на $1$ если предыдущий элемент не равен текущему. Если $k$ стало равно $0$, то текущий элемент является ответом. Чтобы вводить массив размером $10^6$ необходимо использовать быстрый ввод.
Асимптотика: $O(n*log(n))$
:::
:::spoiler Код (C++, автор: [andrewns](https://codeforces.com/profile/andrewns))

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll arr[1000002];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, k;
    cin >> n >> k;
    for(ll i = 0; i < n; i ++) {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    for(ll i = 0; i < n; i ++) {
        if(i == 0 || arr[i] != arr[i - 1]) {
            k --;
        }
        if(k == 0) {
            cout << arr[i];
            return 0;
        }
    }
    cout << -1;
}

:::

## [2. Количество перестановок](https://codeforces.com/group/skz9fIV5Hq/contest/409232/problem/B)
:::spoiler Разбор
:::info
Давайте найдём бинарным поиском максимальное $x$ такое, что лексикографически $x$-ая перестановка числа $N$ меньше либо равна числу $M$, и максимальное $y$ такое, что в лексикографически $y$-ой перестановке числа $N$ есть лидирующий ноль. Тогда ответ это $max(0, x-y)$.
Как найти лексикографически $k$-ую перестановку числа $N$? Давайте расставлять цифры слева направо, и для каждой позиции перебирать цифру от $0$ до $9$. Пусть на позицию $i$ мы пытаемся поставить цифру $j$. Тогда найдём количество перестановок с повторениями на суффиксе $[i + 1; |N|]$. Если оно больше либо равно $k$, то на позиции $i$ должна стоять цифра $j$, иначе отнимем его от $k$ и перейдём к следующей цифре.
Асимптотика: $O(|N| * 10 * log(|N|))$
:::
:::spoiler Код (C++, автор: [andrewns](https://codeforces.com/profile/andrewns))

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll fact[16];

ll P(vector<ll> kol)
{
    ll sum = 0, dv = 1;
    for(ll i : kol) {
        sum += i;
        dv *= fact[i];
    }
    return fact[sum] / dv;
}

string get_kth(vector<ll> kol, ll k)
{
    ll n = 0;
    for(ll i : kol) {
        n += i;
    }
    string s(n, '0');
    for(ll i = 0; i < n; i ++) {
        for(int j = 0; j <= 9; j ++) {
            if(kol[j] == 0) continue;
            kol[j] --;
            if(P(kol) >= k) {
                s[i] = char(j + '0');
                break;
            }
            else {
                k -= P(kol);
                kol[j] ++;
            }
        }
    }
    return s;
}

int main()
{
    string n, m;
    cin >> n >> m;
    fact[0] = 1;
    for(ll i = 1; i <= 15; i ++) {
        fact[i] = fact[i - 1] * i;
    }
    vector<ll> kol(10, 0);
    for(char i : n) {
        kol[i - '0'] ++;
    }
    ll l = 0, r = P(kol);
    while(l < r) {
        ll mid = (l + r + 1) / 2;
        string s = get_kth(kol, mid);
        if(s.length() < m.length() || (s.length() == m.length() && s <= m)) {
            l = mid;
        }
        else r = mid - 1;
    }
    ll lx = 0, rx = P(kol);
    while(lx < rx) {
        ll mid = (lx + rx + 1) / 2;
        if(get_kth(kol, mid)[0] == '0') {
            lx = mid;
        }
        else rx = mid - 1;
    }
    cout << max(0ll, l - lx);
}

:::