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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2019-12-30 22:36:32

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 301
Вебсайт

Розв'язки

Повнобальні рішення з короткими розборами.

SnakeWay

Відповідь до задачі, очевидно, буде або на 1 більша за кількість різних шляхів, що ведуть від початкового кутка до кінцевого (з урахуванням обмежень з умови), або -1, якщо таких шляхів не існує.
Для виведення закономірності, як кількість шляхів залежить від n, можна спробувати повиводити формули з рекурентних співвідношень і індукції. Можна помалювати шляхи на листочку і порахувати вручну. Можна поберегти папір і змусити "малювати" і рахувати комп'ютер. Простим перебором "в лоб". Наприклад якось так. Неефективно, але для N < ~14 порахує за адекватний час, і цього цілком достатньо, щоб помітити закономірності.

В усіх випадках отримуємо наступні формули:

D(n) = L(n) = 2 ^ (n - 2)
S(n) = 2 ^ ((n - 1)/2)

І окремо враховуємо граничні випадки: D(1) = 1, L(1) = 0, S(2 * k) = 0 (тобто S шляхів для парних n не існує).
Значення N можуть бути доволі великими, тому використовуємо алгоритм бінарного піднесення до степені.

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

Асимптотика.
По часу: O(Log N)
По пам'яті: O(1)

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

Код:

#include <iostream>

using namespace std;

const long long mod = 1000000007;

long long binpow (long long a, long long n) {
    long long res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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

    long long count = 0;

    switch (c) {
    case 'D':
        count = n == 1 ? 1 : binpow(2, n - 2);
        break;
    case 'L':
        count = n == 1 ? 0 : binpow(2, n - 2);
        break;
    case 'S':
        count = n & 1 ? binpow(2, n/2) : 0;
        break;
    }

    cout << (count ? (count + 1) % mod : -1) << endl;
}

Vars2019

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

Код:

y 2 3
1 x 4

2. Масиви у різних місцях задають вимоги до значень групи змінних, що суперечать одна одній. Наприклад,

Код:

x 2 3
1 x 3

Тут змінна x має прийняти значення 1, щоб задовольнити вимогу першого елементу і значення 2, щоб задовольнити вимогу другого елементу.

Код:

y 2 x
1 x y

У даному випадку третій елемент масивів прирівнює змінні x та y між собою. Тобто по суті їх можна сприймати як одну змінну. Таким чином отримали ситуацію, аналогічну попередньому прикладу.

Таким чином, загальний алгоритм буде таким:
1. Пробігаємося по масивах. Розглядаємо тільки пари чисел і шукаємо такі, що не збігаються. Якщо знайшли - відповідь N, кінець роботи.
2. Пробігаємося по масивах. Розглядаємо тільки пари змінних. Формуємо групи змінних, що мають бути однаковими (як x та y з останнього прикладу).
3. Востаннє біжимо по масивах і пробуємо задати значення змінним. Для цього розглядаємо тільки пари змінна-число. Беремо групу, якій належить змінна. Якщо цій групі уже присвоєне число і воно не співпадає з поточним числом - відповідь N, кінець роботи. Якщо число ще не присвоєне - присвоюємо поточне.
4. Якщо на попередніх етапах алгоритм не зупинився - відповідь Y.

Залишилося кілька нюансів:
1. Треба швидко знаходити, до якої групи належить змінна (і швидко об'єднувати групи змінних). Для цього можна використати структуру disjoint-set. Докладніше про неї можна почитати, наприклад, тут, або тут. Але варто звернути увагу, що евристика об'єднання за рангом/за розміром хоч формально і покращує асимптотику однієї операції з DSU до константної (а загальну, відповідно - до лінійної), але на практиці у даному випадку працює повільніше. Тому її я не використовував.
2. Треба ефективно працювати з іменами змінних. Якщо так і залишити їх 10-символьними рядками, то усі операції з ними будуть занадто повільними. Щоб обійти це обмеження - помітимо, що маленьких латинських букв всього 26. Відповідно, всього існує трохи менше, ніж 27^10 = 2 * 10^14 різних змінних. Тобто якщо сприймати імена змінних як числа, що записані у 27-чній системі числення, то для зберігання імені змінної буде достатньо всього 48 біт. А отже ім'я змінної "влізе" в 64-бітний цілий тип (наприклад long long в C++). Всі операції з 64-бітними цілими - значно швидші, ніж аналогічні операції з 10-символьними рядками.
3. 48 біт - це небагато для зберігання імені однієї змінної, але 2^48 - це дуже багато, якщо мова йде про пам'ять. Виділити статичні масиви такого розміру не вийде. Однак зустрінеться нам різних 48-бітних значень не більше, ніж 2*N. А отже замість масивів можна використати, наприклад, хеш-таблиці. До речі, хороші новини для C++-ників: у цьому році програми компілюються з підтримкою C++11. Тому можна взяти бібліотечний unordered_map замість написання свого велосипеда.

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

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

Код:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <unordered_map>

using namespace std;

typedef long long ll;

const int MAX_N = 100000;

struct Element {
    ll value;

    bool is_variable() { return value < 0; }

    friend istream &operator >>(istream &in, Element &element) {
        char buf[16];
        in >> buf;

        bool is_variable = *buf >= 'a' && *buf <= 'z';

        if (is_variable) {
            element.value = 0;
            for (char *pbuf = buf; *pbuf; ++pbuf) {
                element.value *= 27;
                element.value += *pbuf - 'a' + 1;
            }
            element.value = -element.value;
        } else {
            element.value = atoi(buf);
        }

        return in;
    }
};

ll find_set (ll v, unordered_map<ll, ll> &parent) {
    auto it = parent.find(v);
    if (it == parent.end())
        return v;
    return parent[v] = find_set (it->second, parent);
}

void union_sets (ll a, ll b, unordered_map<ll, ll> &parent) {
    a = find_set (a, parent);
    b = find_set (b, parent);
    if (a != b) {
        parent[b] = a;
    }
}

bool solve() {
    size_t n;
    cin >> n;

    unordered_map<ll, ll> var_val;
    unordered_map<ll, ll> parent;

    var_val.reserve(n * 2);
    parent.reserve(n * 2);

    static Element a[MAX_N], b[MAX_N];
    for (size_t i = 0; i < n; ++i) cin >> a[i];
    for (size_t i = 0; i < n; ++i) cin >> b[i];

    for (size_t i = 0; i < n; ++i) {
        if (a[i].is_variable() != b[i].is_variable())  continue;

        if (!a[i].is_variable() && a[i].value != b[i].value) {
            return false;
        }

        if (a[i].is_variable()) {
            union_sets(a[i].value, b[i].value, parent);
        }
    }

    for (size_t i = 0; i < n; ++i) {
        if (a[i].is_variable() == b[i].is_variable()) {
            continue;
        }

        auto number = a[i].value;
        auto var_id = b[i].value;
        if (a[i].is_variable()) {
            swap(number, var_id);
        }
        var_id = find_set(var_id, parent);

        if (var_val.count(var_id) && var_val[var_id] != number) {
            return false;
        }
        var_val[var_id] = number;
    }

    return true;
}

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

    while (t--) {
        cout << (solve() ? 'Y' : 'N');
    }

    cout << endl;
}

SqStr

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

По-перше відмітимо, що якщо число є повним квадратом, то кількость усіх простих дільників у факторизації такого числа будуть парними. По-друге, коли ми множимо два числа - кількості їх простих дільників додаються. Наприклад, 12 (2^2 * 3^1) * 18 (2^1 * 3^2) = 216 (2^3 * 3^3). Таким чином, ми можемо звести задачу пошуку підмасивів з "квадратним добутком" до задачі пошуку підмасивів з парною сумою.
Отже, першим кроком - проводимо факторизацію елементів вхідного масиву. Оскільки обмеження на елементи невеликі (до 255) - можна забити прості числа, менші за 255, у статичний масив і використовувати його. Отримали 2-мірний масив factor такий, що factor[i​][j​] - кількість j-го простого дільника у факторизації i-го вхідного числа.

Далі для простоти розглянемо тільки один простий дільник (наприклад, 2). Тобто у масиві factor розглядаємо тільки один стовпчик. Нам треба знайти у цьому стовпчику кількість підмасивів з парною сумою. Для початку помітимо, що шукати суми взагалі значно зручніше і швидше не на початковому масиві, а на масиві з кумулятивними сумами. Тобто коли prefix_sum[i​] - це сума усіх елементів масиву factor від 0 до i-го. У такому випадку сумою елементів factor від i-го до j-го буде значення prefix_sum[j​] - prefix_sum[i​]. Нам треба, щоб ця сума була парною. Різниця двох чисел буде парною тоді і тільки тоді, коли і зменшуване і від'ємник або обидва парні, або обидва непарні. Отже кількістю парних сум буде кількість пар парних елементів масиву плюс кількість пар непарних елементів масиву. У цьому місці можна помітити, що нам і кумулятивні суми виявилися не дуже-то й потрібними. Нас цікавить тільки парність цих сум.

Тепер ми могли б розв'язати задачу, якби в початковому масиві були лише степені двійки. Але у нас, нажаль, там можуть бути й інші значення. Тож повернемось тепер до повної задачі. Тут ситуаця дуже схожа. Єдина відмінність - тепер нам треба, щоб парною на проміжку була сума не одного масиву, а одразу декількох. Як ми з'ясували, початковий масив factor нам не треба. І навіть масив кумулятивних сум prefix_sum нам не потрібен. Будемо зберігати лише масив парностей кумулятивних сум: prefix_parity[i​][j​] зберігає значення 1 або 0. 1 означає, що сума кількостей j-го простого дільника для елементів від 0-го до i-го - непарна. Відповідно, 0 означає, що ця сума парна. Тепер ми могли б розв'язати нашу задачу за квадрат. Псевдокод:

Код:

результат = 0
для кожного i​ від 0 до n:
    для кожного j​ від i​ + 1 до n:
        якщо prefix_parity[i​][k​] == prefix_parity[j​][k​] для усіх k:
            результат = результат + 1

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

Код:

результат = 0
для кожного i​ від 0 до n:
    для кожного j​ від i​ + 1 до n:
        якщо prefix_parity[i​] == prefix_parity[j​]:
            результат = результат + 1

2. Тепер можна помітити, що ми по суті просто рахуємо кількість пар однакових чисел у масиві prefix_parity. Але ми робимо це "в лоб". Можна рахувати швидше за допомогою комбінаторної формули комбінацій з n по 2: n*(n - 1) / 2. Тобто виходить, що нам навіть масив prefix_parity не потрібен. Нам потрібні лише кількості різних значень у цьому масиві для обчислення відповіді.

Асимптотика.
По часу: O(N)
По пам'яті: O(N)

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

Код:

#include <iostream>
#include <unordered_map>

using namespace std;

typedef unsigned long long ull;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    const size_t N_PRIMES = 54;

    int primes[N_PRIMES] {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
        83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
        173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251};

    size_t n;
    cin >> n;

    ull parity = 0;
    unordered_map<ull, ull> parity_count;
    parity_count.reserve(n);

    for (size_t i = 0; i < n; ++i) {
        int a;
        cin >> a;

        for (size_t j = 0; j < N_PRIMES && a != 1; ++j) {
            while (a % primes[j] == 0) {
                a /= primes[j];
                parity ^= 1ULL << j;
            }
        }

        ++parity_count[parity];
    }

    auto result = parity_count[0];

    for (auto kv : parity_count) {
        result += kv.second * (kv.second - 1) >> 1;
    }

    cout << result << endl;
}

Megacube

Задача полягає в знаходженні (ну або не-знаходженні) протиріч у вхідних даних. Якщо протиріччя є, то відповідь - N. Якщо немає - Y.

Кожне число з вхідних даних дає нам наступну інформацію:
1. Координати одного не з'їденого квадрату (якщо це число не -1).
2. Одне з обмежень для відповідного стовпчика чи рядка:
2.1. Інформація про те, що цей рядок (стовпчик) пустий.
2.2. Мінімальна можлива координата у рядку (стовпчику).
2.3. Максимальна можлива координата у рядку (стовпчику).

Таким чином, читаємо вхідні дані, зберігаючи координати не з'їдених плиток і всі обмеження. Після цього проходимося по плитках (їх буде не більше, ніж 4N) і перевіряємо, чи відповідає кожна з них обмеженням для своїх координат (обмежень всього 6 штук).

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


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

Код:

#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

bool solve() {
    const int MAX_N = 10000;

    int n;
    cin >> n;

    int min_x[MAX_N], max_x[MAX_N], min_y[MAX_N], max_y[MAX_N];
    bool empty_row[MAX_N] {}, empty_col[MAX_N] {};
    int n_cells = 0;
    pair<int, int> cells[MAX_N * 4];

    const auto input = [&cells, n, &n_cells](bool *empty_arr, int *opt_arr, bool is_max, bool is_y) {
        for (int i = 0; i < n; ++i) {
            int d;
            cin >> d;
            if (d == -1) {
                empty_arr[i] = true;
            } else {
                opt_arr[i] = is_max ? n - d - 1 : d;
                auto cell = make_pair(opt_arr[i], i);
                if (is_y) swap(cell.first, cell.second);
                cells[n_cells++] = cell;
            }
        }
    };

    input(empty_row, min_x, false, false);
    input(empty_row, max_x, true , false);
    input(empty_col, min_y, false, true);
    input(empty_col, max_y, true , true);

    for (int i = 0; i < n_cells; ++i) {
        int x = cells[i].first;
        int y = cells[i].second;

        if (
                x < min_x[y] ||
                x > max_x[y] ||
                y < min_y[x] ||
                y > max_y[x] ||
                empty_col[x] ||
                empty_row[y])
        {
            return false;
        }
    }

    return true;
}

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

    while (t--) {
        cout << (solve() ? 'Y' : 'N');
    }

    cout << endl;
}

Bracket2019

Просто жадібний алгоритм. Завжди міняємо місцями самі крайні "неправильні" дужки.

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

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

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

Код:

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    char buf[1000002];
    fgets(buf, sizeof (buf), stdin);
    char *end = buf + strlen(buf) - 1;
    if (*end == '\n') --end;

    int cnt_l = 0;
    int cnt_r = 0;
    int res = 0;

    char *l = buf;
    char *r = end;

    while (l <= end && r >= buf) {
        while(l <= end && cnt_l >= 0) {
            cnt_l += *l == ')' ? -1 : 1;
            ++l;
        }
        while(r >= buf && cnt_r >= 0) {
            cnt_r += *r == '(' ? -1 : 1;
            --r;
        }

        if ((cnt_l < 0) != (cnt_r < 0)) break;

        if (cnt_l < 0 && cnt_r < 0) {
            --l;
            ++r;
            swap(*l, *r);
            cnt_l = cnt_r = 0;
            ++res;
        }
    }

    if (cnt_l || cnt_r) res = -1;

    printf("%d\n", res);
}

Відредаговано Dim_ov (2019-12-30 23:47:28)

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt