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

Продовжую відновлювати традицію

Викладаю свої розв'язки з коментарями і закликаю інших ділитися своїми. Особливо якщо задачі розв'язані якимись іншими ідеями.

Chess22k17

На перший погляд може здатися, що задача розв'язується аналогічно до задачі Chess2k17 з першого туру. Але насправді все трохи складніше. Для неквадратних дошок просте розділення дошки навпіл по горизонталі і вертикалі не завжди дасть оптимальне розміщення тур. Простий приклад, щоб переконатися: дошка 10х15. Оптимальне розміщення тур виглядає ось так:

Розміщено 36 тур кожного кольору. Тоді як розділення чорних та білих фігур по "центральному хресту" дало б лише 35 фігур.

Тож для знаходження правильної відповіді необхідно знайти такі числа a і b, щоб значення min(a * b, (n - a) * (m - b)) було максимальним. Перебір усіх значень a і b для обмежень задачі не зайде по часу, але можна перебирати значення тільки вздовж однієї вісі. Очевидно, що значення min(a * b, (n - a) * (m - b)) буде максимальним тоді, коли значення a * b та (n - a) * (m - b) - рівні (адже збільшення одного з них неминуче призведе до зменшення іншого, а функція min безжалісно поверне менший результат). Тож перебирати будемо лише значення a. А значення b знайдемо з рівняння a * b = (n - a) * (m - b). Але ми працюємо з цілими числами, тому для кожного значення a будемо перевіряти по 2 значення b - округлене догори та донизу.

Ось і все. Плюс кілька невеликих оптимізацій:
- якщо обидві розмірності дошки - парні, то можна повертати значення n * m / 4, як і в задачі першого туру
- перебираємо вздовж меншої з розмірностей. На асимптотику не вплине, але на частині тестів може дати помітний виграш у швидкості.
- перебирати a можна тільки до середини дошки. Теж на асимптотику не вплине, але гарантовано зробить обчислення вдвічі швидшими.

Асимптотика рішення - O(min(N, M))

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

#include <iostream>

using namespace std;

long long solve(long long n, long long m) {
    if (n % 2 == 0 && m % 2 == 0) {
        return n * m / 4;
    }

    long long res = -1;
    for (long long a = 0; a <= n / 2; ++a) {
        long long b = m - a * m / n;
        long long r1 = min(a * b, (n - a) * (m - b));
        b -= 1;
        long long r2 = min(a * b, (n - a) * (m - b));
        long long r = max(r1, r2);

        if (r > res) {
            res = r;
        }
    }

    return res;
}

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

    if (n > m) {
        swap(n, m);
    }

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

Br2k17

Задача можна зробити кількома способами. Почну з найбільш чесного)
Якщо забути про правило, що забороняє вставляти квадратні дужки всередину круглих, то задача буде "класичною" - для неї існують готові формули і для обчислення напряму і для обчислення за допомогою ДП. Познайомитися з цими формулами і їх виведенням можна, наприклад, на e-maxx.ru в розділі Количество последовательностей. Але згадане обмеження трохи псує життя. За основу візьмемо ДП рішення і спробуємо в ньому це обмеження врахувати.

Перш за все помітимо, що для знаходження кількості послідовностей довжини n нам уже недостатньо знати, скільки є послідовностей довжин 0...(n-1). Нам ще треба знати, які з них містять квадратні дужки, а які ні. Тому заведемо 2 масива: dp[k] - кількість "якісних" дужкових послідовностей довжини k, та dps[k] - кількість "якісних" дужкових послідовностей довжини k, які містять квадратні дужки.

Очевидно, dp[0] = 1, бо пуста дужкова послідовність є якісною, а dps[0] = 0, бо квадратних дужок пуста послідовність не містить.

Тепер треба придумати формули для загального випадку. Почнемо з dp (тут варто заглянути в статтю на e-maxx, якщо ще цього не зробили, бо деякі речі, які там пояснюються, тут я пояснювати не буду).
Квадратні та кутові дужки ми можемо поставити у будь-якому випадку. Тому можемо додати dp[j] * dp[n - j - 1] * 2 до dp[n]. Круглі дужки ми можемо поставити тільки навколо послідовностей, які не містять квадратних дужок. При цьому праворуч від поставлених дужок може бути будь-яка "якісна" послідовність. Тож додаємо ще (dp[j] - dps[j]) * dp[n - j - 1].

Тепер масив dps. З ним все трохи складніше. Треба врахувати наступні випадки:

- квадратні дужки ставляться навколо послідовності без квадратних дужок і праворуч від вставлених дужок теж немає квадратних. Значення (dp[j] - dps[j]) * (dp[n - j - 1] - dps[n - j - 1])
- навколо послідовності, що містить квадратні дужки ставимо ще квадратні або кутові дужки (круглі не можемо за умовою). Праворуч від вставлених дужок будь-яка "якісна" послідовність (і з квадратними дужками і без). Значення dps[j] * dp[n - j - 1] * 2
- навколо послідовності, що не містить квадратних дужок ставимо дужки будь-якого з трьох видів. При цьому послідовність праворуч від вставлених дужок містить квадратні дужки. Значення (dp[j] - dps[j]) * dps[n - i - 1] * 3

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

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

Щодо не зовсім чесних рішень. Діапазон вхідних даних дуже невеликий, тому можна було нагенерувати масив констант і заслати його, щоб не переживати з приводу тайм лімітів.

Ну і зовсім для чітерів. В OEIS є послідовність A165976, яка і є відповіддю на задачу. Тож масив констант можна було навіть не генерувати самому, а взяти готовий.

Асимптотика "чесного" рішення - O(N^2). Чітерського - очевидно, O(1)

Код "чесного" рішення на С++.
Структура bigint для роботи з довгою арифметикою лежить окремо ось тут, щоб не сильно відволікати від основної ідеї розв'язку.

#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

    bigint dp[101];
    bigint dps[101];

    dp[0] = 1;
    dps[0] = 0;

    for (int n = 1; n <= N; ++n) {
        dp[n] = dps[n] = 0;
        for (int i = 0; i < n; ++i) {
            dp[n] += dp[i] * dp[n - i - 1] * 2 + (dp[i] - dps[i]) * dp[n - i - 1];

            dps[n] +=
                    (dp[i] - dps[i]) * (dp[n - i - 1] - dps[n - i - 1]) +
                    dps[i]           * dp[n - i - 1]                * 2 +
                    (dp[i] - dps[i]) * dps[n - i - 1]               * 3;
        }
    }

    cout << dp[N] << endl;
}

Pal2017

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

Таким чином, нам не дуже важливий сам початковий рядок. Важливо лише які символи знаходяться на парних позиціях, а які на непарних.

Щодо самого рішення. Окремо варто обробити два випадки: коли довжина початкового рядка парна і коли непарна. Якщо довжина парна, то відповідні символи з початку і з кінця паліндрому матимуть різну парність позицій. А якщо непарна, то однакову.

Для рядків непарної довжини ми можемо окремо зібрати 2 паліндроми для символів на парних і непарних позиціях, а потім з цих двох рядків отримати кінцевий.
А для рядків парної довжини ми можемо просто перебрати всі символи у порядку зростання і кидати половину з них на початок рядка-результату, а половину - на кінець. Перевіряючи, щоб кожного символу була однакова кількість на парних і непарних позиціях.
В кінці перевіряємо отриманий рядок на паліндромність і виводимо або його, або "-1".

Асимптотика мого рішення - O(N * LogN). При бажанні можна було б замінити словники на масиви і отримати лінійну асимптотику, але суттєвого виграшу по швидкості це не дасть.

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

#include <iostream>
#include <map>
#include <string>

using namespace std;

string stringFromEvenOdd(const string &even, const string &odd) {
    string result(even.length() + odd.length(), '_');
    for (int i = 0; i < even.length(); ++i) {
        result[2*i] = even[i];
    }
    for (int i = 0; i < odd.length(); ++i) {
        result[2*i + 1] = odd[i];
    }
    return result;
}

string getPaliOdd(map<char, int> &counts) {
    string result;
    string end;
    string central;

    for (map<char, int>::iterator it = counts.begin(); it != counts.end(); ++it) {
        if (it->second & 1) {
            if (central.empty()) {
                central += it->first;
            } else {
                return "";
            }
        }

        result.append(it->second / 2, it->first);
        end.append(it->second / 2, it->first);
    }

    result += central;
    result.append(end.rbegin(), end.rend());

    return result;
}

string getPaliEven(map<char, int> &countsEven, map<char, int> &countsOdd, map<char, int> &countsTotal) {
    string result;
    string end;
    for (map<char, int>::iterator it = countsTotal.begin(); it != countsTotal.end(); ++it) {
        char c = it->first;
        int cnt = it->second;
        if (countsEven[c] != countsOdd[c]) {
            return "";
        }
        result.append(cnt/2, c);
        end.append(cnt/2, c);
    }

    result.append(end.rbegin(), end.rend());

    return result;
}

string solve(map<char, int> &countsEven, map<char, int> &countsOdd, map<char, int> &countsTotal, int n) {
    string res;

    if (n & 1) {
        string even = getPaliOdd(countsEven);
        string odd = getPaliOdd(countsOdd);

        res = stringFromEvenOdd(even, odd);
    } else {
        res = getPaliEven(countsEven, countsOdd, countsTotal);
    }

    string::iterator i = res.begin();
    string::reverse_iterator ir = res.rbegin();

    bool isOk = true;

    for (; isOk && i != res.end() && ir != res.rend(); ++i, ++ir) {
        isOk = *i == *ir;
    }

    if (isOk && res.length() == n) {
        return res;
    } else {
        return "-1";
    }
}

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

    map<char, int> countsEven;
    map<char, int> countsOdd;
    map<char, int> countsTotal;

    string s;
    cin >> s;

    for (int i = 0; i < s.length(); ++i) {
        char c = s[i];
        map<char, int> &target = i & 1 ? countsOdd : countsEven;
        target[c]++;
        countsTotal[c]++;
    }

    cout << solve(countsEven, countsOdd, countsTotal, s.length()) << endl;
}

Robotsway

Задача по суті на єдину комбінаторну формулу перестановок з повтореннями.
Перебираємо кількість "довгих" відрізків шляху по k м. Позначимо цю кількість за l. І для кожного l додаємо до результату значення кількості перестановок з повтореннями: m!/(l!*o!), де l - кількість довгих сегментів шляху, o - кількість коротких, а m - загальна кількість відрізків у шляху. Очевидно, m = o + l. l ми перебираємо, o = n - k * l, m = n - k * l + l = n - l * (k - 1).

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

Тому треба рахувати більш акуратно.

Перш за все можна скоротити формулу ось так:
m!/(l!*o!) = (1*2*...*(m-1)*m)/(l!*o!) = ((l+1)*(l+2)*...*(m-1)*m)/o!

Тобто можна по-перше повністю позбутися одного з факторіалів, а по-друге - зменшити кількість обчислень для одного з факторіалів, що залишилися. Ну і очевидно, скорочувати варто на більший з факторіалів, не обов'язково саме на l!

Але цього все одно може бути недостатньо, тому замість обчислення чисельника і знаменника окремо варто завести дріб, у якому поступово домножувати чисельник і знаменник і після кожного множення цей дріб скорочувати.

Асимптотика - O(N^2 * LogN / K).

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

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

using namespace std;

struct Fraction
{
    long long numerator;
    long long denominator;
    Fraction(long long num, long long denom = 1): numerator(num), denominator(denom) {}

    Fraction &operator *=(long long n) {
        numerator *= n;
        relax();

        return *this;
    }

    Fraction &operator /=(long long n) {
        denominator *= n;
        relax();

        return *this;
    }

    long long getValue() const {
        return numerator / denominator;
    }

private:
    void relax() {
        long long d = gcd(numerator, denominator);
        numerator /= d;
        denominator /= d;
    }

    static long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a%b); }
};

long long permutations(long long total, long long group1, long long group2) {
    long long num = max(group1, group2) + 1;
    long long denomEnd = min(group1, group2);

    Fraction f(1);

    long long denom = 2;

    while (num <= total && denom <= denomEnd) {
        if (f.numerator < f.denominator) {
            f *= num++;
        } else {
            f /= denom++;
        }
    }

    while (num <= total) {
        f *= num++;
    }

    while (denom <= denomEnd) {
        f /= denom++;
    }

    return f.getValue();
}

long long solve(long long n, long long k) {
    int maxLongSegments = (n - 1) / k;
    long long res = 0;

    for (int lSegs = 1; lSegs <= maxLongSegments; ++lSegs) {
        res += permutations(n - lSegs * (k - 1), lSegs, n - lSegs * k);
    }

    return res;
}

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

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

Transmission

Знайти відстань між центрами, знаючи радіуси і довжину ременя важко. Зате знайти довжину ременя, знаючи відстань між центрами дисків та радіуси можна дуже просто. До того ж, зі збільшенням відстані збільшуватиметься і довжина ременя. А отже можна застосувати бінарний пошук.

Але спершу виведемо формулу довжини ременя для заданих радіусів дисків та відстані між центрами. Схоже, що з цим у багатьох учасників були проблеми, бо вони брали готові формули з інженерних статей/довідників, не дуже замислюючись над тим, звідки ті формули взялися .
В інженерних обчисленнях формули часто спрощують. Особливо "страждає" тригонометрія. Наприклад, для невеликих кутів sin x можуть замінити на x, і т.п. І це абсолютно нормально для інженерних цілей. По-перше, в житті кути дійсно будуть невеликі, бо пасові передачі майже завжди мають співвідношення швидкостей не більше 1:3 і диски розташовані достатньо далеко з суто практичних міркувань - так менша сила тертя і менше зношуються ремені. А по-друге - абсолютно точні обчислення нікому і не треба: ніхто не виготовлятиме ремінь з нанометровою точністю, а якби і виготовляли, то через ту саму силу тертя ремінь буде нагріватися і розширюватися, змінюючи свою ефективну довжину на значення значно більші, ніж точність обчислення за "правильними" формулами.

До формули.

Пряма DE проведена паралельно прямій O1O2.
Радіуси O1F і O2E також паралельні, бо вони перпендикулярні до дотичної FE.
Тоді O1DEO2 - паралелограм. А отже DE = O1O2 = d

Кути FDE і FO1O2 рівні як відповідні. Також вони рівні θ/2.

Із прямокутного трикутника FDE знайдемо косинус кута FDE. Він дорівнює FD / DE = (r1-r2) / d
Тоді кут FDE = acos((r1-r2) / d).

Отже θ = 2 * acos((r1-r2) / d)

Знаючи кут θ ми можемо знайти довжини частин ременя, що обтікають диски - це r1 * (2π - θ) для більшого диску і r2 * θ для меншого.

Залишилось знайти довжину відрізка дотичної. Повернемось у трикутник FDE і знову згадаємо тригонометрію.
FE = DE * sin(FDE) = d * sin(θ/2)

Таким чином, загальна формула довжини ременя має вигляд:
2 * d * sin(θ / 2) + r1 * (2π - θ) + r2 * θ

Любителі готових формул могли її взяти на сторінці англомовної вікіпедії: https://en.wikipedia.org/wiki/Belt_problem (так, картинку я свиснув саме звідти).

Тепер, як я й казав, просто застосовуємо бінарний пошук. Автор з якоїсь незрозумілої мені причини мовчав про необхідну точність результату, тому використовуємо найбільш точний з доступних тип чисел з плаваючою крапкою (long double в C++), а бінарному пошуку даємо можливість з запасом виконуватися протягом 100 ітерацій. Цього буде більш ніж достатньо, щоб отримати 20 знаків відповіді (хоча чекер, схоже, перевіряє з точністю 1e-3).

Асимптотика рішення - O(1)

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

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long double ld;

const ld PI = acosl(-1);

ld getL(ld r1, ld r2, ld d) {
    ld theta = 2 * acosl((r1 - r2)/d);
    return 2 * d * sinl(theta / 2) + r1 * (2 * PI - theta) + r2 * theta;
}

ld solve(ld L, ld R1, ld R2) {
    ld r = L /2;
    ld l = R1 + R2;
    ld m;

    for (int i = 0; i < 100; ++i) {
        m = (r + l) / 2;
        if (m == r || m == l) {
            break;
        }
        if (getL(R1, R2, m) < L) {
            l = m;
        } else {
            r = m;
        }
    }
    return m;
}

int main() {
    ld r1, r2, l;
    cin >> r1 >> r2 >>l;

    if (r1 < r2) {
        swap(r1, r2);
    }

    ld res = solve(l, r1, r2);

    cout << scientific << setprecision(20) << res << endl;
}

Відредаговано Dim_ov (2017-12-24 05:29:22)