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

Повідомлення про завершення туру ще не було, але рішення вже перевірені, так що думаю, розв'язками можна ділитися.
Задачі цього року трохи простіші, ніж зазвичай (і суб'єктивно і судячи з таблиці результатів, де у 44 учасників 250+ балів. Зазвичай таких не більше 15-20).

Не всі розбори дуже докладні, але думаю, ідеї в більшості мають бути зрозумілими.
Удачі учасникам 4 туру


Train2020

Помітимо, що якщо вагони N та M зчеплені за рахунок спільного дільника K, то між N та M можна вставити довільну кількість чисел, що діляться на K. Тобто якщо вагон можна з'єднати хоча-б з двома іншими вагонами - його точно можна буде кудись прилаштувати (мабуть можна і математично/строго це довести, але я не доводив). Усі такі вагони можна взяти в поїзд.
Якщо у вагону є лише один потенційний сусід - такий вагон повинен буде стояти в голові, або в хвості поїзда. Тобто таких вагонів можна взяти не більше двох.
Ну і якщо для вагону немає сусідів - включити його в поїзд не вийде.

Підрахуємо ці кількості.
У вагону з номером K немає жодного сусіда тоді і тільки тоді, коли K - просте число і N < 2 * K.
У вагону з номером K є лише один сусід тоді і тільки тоді, коли K - просте число і 2 * K ≤ N < 3 * K.
В усіх інших випадках у вагонів є щонайменше 2 сусіди.

Таким чином, задача розв'язується за один прохід решета Ератосфена:

З самого початку ініціалізуємо відповідь значенням N, а кількість вагонів з одинм сусідом - нулем.
Запускаємо решето Ератосфена.
Коли знайшли чергове просте число p:
якщо N < 2 * p - зменшуємо відповідь на 1 (знайшли вагон без сусідів)
якщо 2 * p ≤ N < 3 * p - збільшуємо на 1 кількість вагонів з одинм сусідом.
Якщо після закінчення роботи решета кількість вагонів з одним сусідом більша за 2 - зменшуємо відповідь на ("кількість вагонів з одинм сусідом" - 2).

Асимптотика.
Звичайна асимптотика решета Ератосфена.

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

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

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int solve(int n) {
    constexpr int MAX_N = 100000;

    if (n == 2 || n == 3) return 2;

    int res = n;
    int n_single_neighbour = 0;

    bool prime[MAX_N + 1];
    fill_n(prime, n + 1, true);

    for (int p = 2; p <= n; ++p) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p) prime[i] = false;

            res -= p * 2 > n;
            n_single_neighbour += p * 2 <= n && p * 3 > n;
        }
    }

    return res - max(0, n_single_neighbour - 2);
}

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

    cout << solve(n) << endl;
}

Game2020

Гра зводиться до класичної гри Нім згідно теореми Шпрага-Гранді. Розмірами купок тут будуть суми розмірів непустих кошиків, що йдуть підряд. Наприклад, тесту

10
1 0 1 2 3 0 7 5 0 9

відповідає гра в Нім з розмірами купок

1 6 12 9

Доведемо цю відповідність (якщо цікавить лише рішення, а не доведення його коректності, то розділ можна пропустити)

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

1 2 3 -> 1 0 3
або
1 2 3 4 5 -> 1 0 2 0 3

Нехай початкова сума групи кошиків була N, гравець взяв всього X цукерок
і отримав K нових груп розмірами M[i​]. g(N) - значення Шпрага-Гранді для
групи розміром N.

У такому випадку згідно з теоремою, значенням Шпрага-Гранді для N буде
g(N) = mex (states), де states =
{0, ..., N - 1} адже гравець все ще може взяти від 1 до N цукерок, не розділяючи групу
∪
{g(M[1​] ⊕ ... ⊕ M[K​]) для всих можливих X та всих можливих розділень}

Для доведення відповідності нам необхідно і достатньо показати, що серед
значень g(M[1​] ⊕ ... ⊕ M[K​]) немає значення N.

Показати це нескладно, адже XOR-сума не може бути більшою за алгебраїчну
суму. Тобто усі значення M[1​] ⊕ ... ⊕ M[K​] будуть менші або рівні за (N - X).
А оскільки X > 0, то M[1​] ⊕ ... ⊕ M[K​] < N.

Таким чином, рішення доволі просте - пробігаємося по вхідному масиву, рахуємо суми розмірів груп непустих кошиків і xor-имо ці суми.

Зауваження по реалізації. Важливо правильно обрати формат даних, адже хоча окремі числа і менші за 10^5, але їх може бути 10^6 штук, і ми їх сумуємо. Тобто загальне значення може бути до 10^11 і в 32-бітний інт воно не влізе.

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

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

#include <iostream>

using namespace std;

long long sprague_grundy(int n, int *a) {
    long long res = 0;
    long long sum = 0;

    for (int i = 0; i < n; ++i) {
        sum += a[i];
        if (a[i] == 0) {
            res ^= sum;
            sum = 0;
        }
    }
    res ^= sum;

    return res;
}

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

    int t;
    cin >> t;

    string s;

    while (t--) {
        static int a[1000000];
        int n;
        cin >> n;

        for (int i = 0; i < n; ++i) cin >> a[i];

        s += sprague_grundy(n, a) ? 'N' : 'Y';
    }
    cout << s << endl;
}

Wall2020
На каналі 3Blue1Brown є серія відео, присвячених цій задачі. Підозрюю, що автор задачі надихався саме ними
Наполегливо рекомендую переглянути ці та інші відео з каналу. Там багато цікавого для тих, хто любить математику.

Власне серія відео:
https://www.youtube.com/watch?v=HEfHFsfGXjs
https://www.youtube.com/watch?v=jsYwFizhncE
https://www.youtube.com/watch?v=brU5yLm9DZM

Більш строгий документ з описом експерименту, купою математики і строгим виведенням того, як обчислити число пі за допомогою двох ідеально пружних кубів на ідеально рівній поверхні:
https://www.maths.tcd.ie/~lebed/Galperi … h%20pi.pdf

Можливо пізніше додам основні моменти з відео в пост, але мені поки що лінь, а відео хороше

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

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

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const long double pi = 3.141592653589793238462643383279502884L;

int main() {
    long double m1, m2;

    cin >> m1 >> m2;

    auto theta = atan(sqrt(m1 / m2));
    int result = static_cast<int>(pi / theta);

    if (pi - result * theta < 1e-6L) {
        --result;
    }

    cout << result << endl;
}

Trunks
Відповіддю є послідовність A059881 з OEIS, яка в свою чергу є сумою послідовностей A059882 та A059883.

Задача розв'язується за допомогою ДП.
Нехай
T[n​][k​] - кількість способів набрати n​ монет, взявши з першої скрині рівно k​ монет, з другої - більше за k​, з третьої - менше, ніж з другої і т.д.
S[n​][k​] - кількість способів набрати n​ монет, взявши з першої скрині рівно k​ монет, з другої - менше за k​, з третьої - більше, ніж з другої і т.д.

тоді
T[n​][k​] дорівнюватиме сумі S[n-k​][j​] для усих j​ від k​+1 до n-k включно
S[n​][k​] дорівнюватиме сумі T[n-k​][j​] для усих j​ від 1 до k-1 включно
І база ДП: T[n​][n​] = S[n​][n​] = 1

Якщо реалізувати таку динаміку влоб, то отримаємо кубічну асимптотику і в ТЛ не вліземо. Але можна дуже легко перетворити підрахунок суми з лінійного на константний, якщо зберігати в наших таблицях не самі значення T[n​][k​] та S[n​][k​], а префіксні суми. Тобто суми значень від T[n​][0​] до T[n​][k​] та від S[n​][0​] до S[n​][k​] відповідно.

І оскільки із застосуванням префіксних сум нам доведеться іноді віднімати значення - треба не забути в кінці зробити значення відповіді додатнім ((res % MOD + MOD) % MOD).

Асимптотика.
Час: O(N^2)
Пам'ять: O(N^2)

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

#include <iostream>

using namespace std;

int solve(int n, int k) {
    constexpr size_t MAX_N = 5001;
    constexpr int MOD = 1000000007;

    if (n == k) return 1;

    static int dp[MAX_N][MAX_N][2] = {};

    for (int total = 1; total <= n; ++total) {
        for (int first = 1; first < total; ++first) {
            int inc_addend = (total - first > first) * (dp[total - first][total - first][0] - dp[total - first][first][0]) % MOD;

            dp[total][first][0] = (dp[total][first - 1][0] + dp[total - first][first - 1][1]) % MOD;
            dp[total][first][1] = (dp[total][first - 1][1] + inc_addend) % MOD;
        }

        dp[total][total][0] = (dp[total][total - 1][0] + 1) % MOD;
        dp[total][total][1] = (dp[total][total - 1][1] + 1) % MOD;

        for (int i = total + 1; i <= n; ++i) {
            dp[total][i][0] = dp[total][total][0];
            dp[total][i][1] = dp[total][total][1];
        }
    }

    int resDec = (dp[n][k][0] - dp[n][k-1][0]) % MOD;
    int resInc = (dp[n][k][1] - dp[n][k-1][1]) % MOD;

    int res = (resInc + resDec) % MOD;

    return (res + MOD) % MOD;
}

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

    cout << solve(n, k) << endl;
}

Kingdoms2020

Ключ до розв'язку - послідовність A051034 з OEIS, або більш загально - гіпотеза Ґольдбаха.
Відмітимо кілька речей:
1. Будь-яке число можна представити у вигляді суми трьох або менше простих чисел.
2. У вигляді суми двох простих чисел можна представити усі парні числа, більші за 2, а також непарні числа N такі, що N-2 - просте.

Таким чином, для розв'язку розділимо вхідний діапазон N на 3 частини:
1. N ≥ 3
2. N = 1
3. N = 2

Для першої частини відповіддю буде (c - d + 1) * (b - max(a, 3) + 1), адже як ми з'ясували, для N ≥ 3 існують усі (N, K)-царства.
Для другої частини відповіддю буде кількість простих чисел у діапазоні [c, d].
Для третьої - кількість чисел i у діапазоні [c, d] таких, що
1. число i просте АБО
2. число i парне АБО
3. число i - 2 просте

Враховуючи дуже невеликі обмеження, особливих вимог до реалізації немає і вона може бути якою завгодно. Все одно працюватиме швидко. Хіба що на простоту варто перевіряти за корінь, а не лінійно. Ну і пам'ятати про граничні випадки (для K = 1 не існує жодного (N, K)-царства).

Асимптотика.
Час: O((d - c) * sqrt(d))
Пам'ять: O(1)

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

#include <iostream>
#include <algorithm>

using namespace std;

bool is_prime(int n) {
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }

    return true;
}

int solve(int minN, int maxN, int minK, int maxK) {
    minK = max(minK, 2);
    if (maxK < minK) return 0;

    int result = (maxK - minK + 1) * max(0, maxN + 1 - max(minN, 3));

    if (minN >= 3) return result;
    maxN = min(maxN, 2);

    for (int i = minK; i <= maxK; ++i) {
        if (is_prime(i)) {
            result += maxN - minN + 1;
        } else if (maxN >= 2 && (i % 2 == 0 || is_prime(i - 2))) {
            result++;
        }
    }

    return result;
}

int main() {
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    cout << solve(a, b, c, d) << endl;
}