Форум Всеукраїнської інтернет-олімпіади NetOI

На форумі цього року в основному активність проявляють різні недо-SEO боти, але все ж на випадок, якщо хтось із живих учасників ще тут буває - викладаю повнобальні рішення з короткими розборами.

Bicycle

У новій системі без вісімок для запису числа доступні лише 9 цифр з 10. Тобто для отримання відповіді достатньо перевести число N в дев'яткову систему числення. При цьому пам'ятаємо, що під забороною у нас цифра 8, а не 9 (тобто цифровий "алфавіт" - не 012345678, а 012345679). Тож при переведенні замінимо усі вісімки на дев'ятки.

Асимптотика.

Час: O(log N)
Пам'ять: O(1)

Код рішення на С++.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    char converted[16];
    auto *p = converted + 15;
    *p = 0;

    while (n) {
        auto digit = n % 9;
        if (digit == 8) digit = 9;
        *--p = static_cast<char>(digit + '0');
        n /= 9;
    }

    cout << p << endl;
}

Disko

Перш за все розглянемо тривіальний випадок коли  N ≤ S. В такому випадку ми можемо запустити обидві лампи з нульовою затримкою. Першу запускаємо одразу, другу - через S секунд (до того часу перша вже відсвітить свої N секунд). Тобто відповідь - S + N.

Якщо ж N > S, то лампи доведеться викати по черзі і треба знайти мінімально можливу затримку між увімкненнями.
По-перше нам важливо, щоб перша лампа не горіла через S секунд (оскільки тоді загориться друга лампа, а за умовою вони не можуть горіти одночасно). Перша лампа горітиме через S секунд тоді і тільки тоді, коли S ділиться націло на період мигання. Тобто крім того, що період має бути мінімально можливим - він не може бути дільником S.
Затримки двох ламп можуть не співпадати за умовою. Тож може здатися, що для другої лампи в деяких випадках можна було б взяти меншу затримку, ніж для першої. Однак можна показати (або запустити кілька симуляцій і перевірити), що в такому разі (коли затримки першої і другої ламп не співпадають і N > S) - в якийсь момент обом лампам доведеться загорітися одночасно.
Таким чином, період загорання обох ламп буде однаковим (позначимо його K) і ми маємо лише 2 обмеження для нього: він має бути мінімально можливим і не бути дільником S. Шукаємо його простим перебором.

Знайдемо відповідь. Перша лампа догорить раніше за другу, тож її можна ігнорувати. Друга почне горіти на S-ій секунді і блиматиме N разів з періодом K. Однак після останнього загорання враховувати час очікування уже не варто, лише 1 секунду безпосереднього горіння.

Тож кінцевою відповіддю буде значення S + (N - 1) * K + 1.

Асимптотика.
Час: O(log S)
Пам'ять: O(1)

Код рішення на С++.

#include <iostream>
using namespace std;

int main() {
    int s, n;
    cin >> s >> n;

    if (n <= s) {
        cout << s + n << endl;
    } else {
        int stride;
        for (stride = 2; s % stride == 0; ++stride);

        cout << s + (n - 1) * stride + 1 << endl;
    }
}

Eleven

Рішення складається з трьох кроків:
1) отримати максимально можливе число із цифр вхідного числа
2) перевірити, чи кратне воно 11
3) Якщо так - "виправити" його, щоб воно більше не було кратним

Для першого кроку просто відсортуємо цифри за спаданням.
Оскільки вхідне число може бути довжиною до 1000 цифр, ми не можемо перевіряти подільність на 11 "в лоб". Тому використаємо ознаку подільності на 11: число ділиться на 11 тоді і тільки тоді, коли в його десятковому записі різниця між сумами цифр на парних і непарних позіціях ділиться націло на 11.

І нарешті основний, третій крок.
Перш за все, порівняємо першу і останню цифри отриманого числа. Якщо вони рівні, то це означає, що усі цифри числа однакові (адже вони відсортовані), тож єдине, що ми можемо зробити для "виправлення" подільності - це забрати одну цифру. Це зменшить число на якуcь величину k * 10^n, де 1 ≤ k ≤ 9. Жоден з 2 множників не може бути кратним 11 при будь-яких n і k, а отже не кратний і увесь добуток (адже 11 - просте число). Тож і наше число після віднімання перестане бути кратним 11.
В іншому випадку - ми можемо виправити подільність і не зменшуючи число так сильно. Достатньо просто поміняти місцями дві різні цифри, що стоять поряд. При чому міняти треба якомога молодші розряди. Тож просто ідемо з кінця числа, шукаємо першу пару різних цифр і міняємо їх місцями.

Покажемо, що число перестане ділитися на 11 після такої операції. Позначимо різницю між переставленими цифрами як k (тобто 1 ≤ |k| ≤ 9). Тоді після перестановки число змінилося на величину (k * 10^n - k * 10^(n-1)) = k * 10^(n-1) * (10 - 1) = 9 * k * 10^(n-1). Як легко побачити, ситуація повністю аналогічна тій, де ми прибирали одну із цифр, за виключенням множника 9, який теж не є кратним 11, а отже не впливає на подільність добутку на 11.

Асимптотика (N - довжина вхідного числа)
По часу: O(N * log N)
- сортування: O(N * log N)
- перевірка подільності: O(N)
- виправлення поільності: O(N)
По пам'яті: O(N)

Код рішення на С++.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

void fix_divisible(char *digits, size_t n) {
    if (digits[0] == digits[n - 1]) {
        digits[n-1] = 0;
        return;
    }

    for (auto i = n - 2; i < n; --i) {
        if (digits[i] != digits[i + 1]) {
            swap(digits[i], digits[i+1]);
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    char digits[1001];
    cin >> digits;

    auto n = strlen(digits);
    sort(digits, digits + n, greater<>());

    int sum_even = 0;
    int sum_odd = 0;

    for (int i = 0; i < n; ++i) {
        auto digit = digits[i] - '0';
        sum_odd += (i & 1) * digit;
        sum_even += !(i & 1) * digit;
    }

    if ((sum_even - sum_odd) % 11 == 0) fix_divisible(digits, n);

    cout << digits << endl;
}

Mult2021

Розв'яжемо задачу в 2 кроки:
1) Переберемо усі можливі розбиття числа m на множники менші за 10, у яких загальна кількість множників дорівнює n.
2) Для кожної успішної факторизації застосуємо комбінаторну формулу пошуку кількості перестановок з повтореннями.

Для пошуку факторизацій просто в лоб робимо повний перебір. Рекурсія виглядає акуратніше, але в принципі можна і 8 вкладених циклів бахнути. Для зручнішого підрахунку перестановок кожну факторизацію зберігаємо у вигляді масиву А з 9 елементів, такого що A[i​] - кількість множників i+1 у поточній факторизації (або кількість цифр i+1 у числі). Сума усіх елементів масиву A дорівнюватиме n.

Приклади:
Для n=2 m=4 будуть наступні факторизації:

1,0,0,1,0,0,0,0,0 // 1^1 * 4^1
0,0,2,0,0,0,0,0,0 // 2^2

Для n=10 m=120 будуть такі факторизації:

7,0,0,1,1,1,0,0,0 // 1^7 * 4^1 * 5^1 * 6^1
7,0,1,0,1,0,0,1,0 // 1^7 * 3^1 * 5^1 * 8^1
6,1,1,1,1,0,0,0,0 // 1^6 * 2^1 * 3^1 * 4^1 * 5^1
6,2,0,0,1,1,0,0,0 // 1^6 * 2^2 * 5^1 * 6^1
5,3,1,0,1,0,0,0,0 // 1^5 * 2^3 * 3^1 * 5^1

Коли отримали чергову факторизацію - застосовуємо формулу підрахунку кількості перестановок з повтореннями. Іншими словами, нам треба поділити факторіал суми елементів масиву А на добуток факторіалів окремих елементів масиву. Робити це в лоб не варто - легко вилізти за межі усіх інтів, а якщо порахувати факторіали по модулю, то для ділення доведеться шукати обернені по модулю числа для множників із знаменника, що доволі незручно і повільно (хоча загалом цілком можливо).
Щоб цього уникнути - будемо після кожного домноження чисельника на черговий множник акуратно пробувати скоротити його з одним із факторіалів у знаменнику. Коли знаменник закінчиться - можна уже спокійно брати модуль і домножати залишки множників для факторіала у чисельнику. Якщо проводити обчислення у 64-бітних інтах, то переповнень не буде.

Асимптотика.
По часу: O(K), де K - кількість успішних факторизацій m
По пам'яті: O(1)

Код кінцевого рішення на С++.

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;

const uint64_t mod = 1000000007;
uint64_t result = 0;

uint64_t count_factorization(const vector<int> &powers_in) {
    vector<int> powers(powers_in);
    auto n = accumulate(powers.begin(), powers.end(), 0);

    auto elem = max_element(powers.begin(), powers.end());
    int max_power = *elem;
    *elem = 0;
    int remaining = n - max_power;

    uint64_t res = 1;
    int i;

    for (i = max_power + 1; i <= n && remaining; ++i) {
        res *= i;
        for (auto &cnt: powers) {
            while (cnt && res % cnt == 0) {
                res /= cnt--;
                remaining--;
            }
        }
    }

    for (; i <= n ; ++i) {
        res *= i;
        res %= mod;
    }

    return res % mod;
}

void bruteforce(vector<int> &powers, int m, int i) {
    if (m == 1) {
        result = (result + count_factorization(powers)) % mod;
    }

    if (m == 1 || i > powers.size()) return;

    bruteforce(powers, m, i+1);

    while (m % i == 0 && powers[0]) {
        m /= i;
        powers[i-1]++;
        powers[0]--;
        bruteforce(powers, m, i+1);
    }
    powers[0] += powers[i-1];
    powers[i-1] = 0;
}

uint64_t search_factorizations(int n, int m) {
    vector<int> powers(9, 0);
    powers[0] = n;

    bruteforce(powers, m, 2);

    return result % mod;
}

int main() {
    int n, m;
    cin >> n >> m;

    cout << search_factorizations(n, m) << endl;
}

Palindrom2021

Знайдемо найдовший префікс рядка, що є паліндромом. Довжина суфікса, який не увійшов у префікс-паліндром і буде відповіддю (адже цей суфікс можна розвернути і приклеїти до початку рядка, отримавши таким чином паліндром). Аналогічним чином перевіримо і інший кінець рядка: знайдемо найдовший суфікс, що є паліндромом і префікс, який в нього не входить. Виведемо найменшу з двох отриманих відповідей.

З обмеженнями до 255 символів шукати паліндроми-префікси можна і в лоб за квадрат. Але можна застосувати трохи модифікований алгоритм КМП і шукати їх за лінійний час. Але повторюся, для 255 символів сенсу у тому небагато.

Асимптотика.
Час: O(N), де N - довжина вхідного рядка.
Пам'ять: O(N)

Код рішення на С++.

#include <iostream>
#include <algorithm>

using namespace std;

int get_lps(const string &str) {
    auto temp = str + '?';
    temp.append(str.rbegin(), str.rend());

    auto n = temp.length();
    int lps[512] = {};

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

        int len = lps[i - 1];

        while (len > 0 && temp[len] != temp[i]) {
            len = lps[len - 1];
        }

        if (temp[i] == temp[len]) {
            len++;
        }

        lps[i] = len;
    }

    return lps[n-1];
}

int main() {
    string str;
    cin >> str;

    int prefix_pali = get_lps(str);
    reverse(str.begin(), str.end());
    int suffix_pali = get_lps(str);

    cout << str.length() - max(prefix_pali, suffix_pali) << endl;
}