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

Колись тут було заведено по закінченню туру ділитися рішеннями/розборами і взагалі думками з приводу задач. Спробую відновити традицію) Мені здається, це було доволі корисно. В першу чергу для початківців, але і більш досвідчені учасники часто могли знайти щось цікаве в подібних топіках.


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

Картинка:


Таким чином, при непарному полі заповненим буде прямокутник розміром m * (m + 1), де m = (N - 1) / 2. Можна використати для цього if, а можна обійтись і без нього, якщо згадати особливості ділення цілих чисел. Відповідь можна порахувати формулою (N / 2) * ((N + 1) / 2). Для парного N значення N / 2 і (N + 1) / 2 будуть однаковими (адже при діленні непарного N + 1 на 2, дробова частина відкинеться). Для непарного ж N значення ((N + 1) / 2) буде на 1 більше за значення (N / 2).

Окремо варто звернути увагу на обмеження. При N ≤ 10^6, значення відповіді (N / 2) * ((N + 1) / 2) може досягати 10^12. Числа такого порядку не влізуть в стандартний 32-бітний інт. Тож варто використовувати 64-бітний long long.

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

#include <iostream>
using namespace std;

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

    cout << (n / 2) * ((n + 1) / 2) << endl;
}

Game2k17
Для розв'язку варто зрозуміти, які числа є виграшними (за будь-якої гри супротивника можливо виграти), а які - програшними (супротивник може виграти за будь-якої твоєї гри). Розглянемо остачу від ділення N на 3. Якщо остача = 0, то введене число ділиться на 3. А отже ми можемо відняти від нього 3 і знову отримати число, кратне трьом. Тобто такі позиції є виграшними. Якщо остача дорівнює 1, то ми, знову ж таки, можемо одразу перемогти просто віднявши 1 (адже 1 є дільником будь-якого числа). Таким чином, програшними позиціями можуть бути лише такі N, що діляться на 3 з остачею 2. І дійсно, для N=2, N=5 виграти неможливо. Але як нескладно помітити, для 8 це вже не працює - ця позиція є виграшною. Хоча далі для 11 все знову працює. Розгадка проста. 8 ділиться на 2 (одну з наших попередніх програшних позицій). А віднявши від числа, що ділиться на 3 з остачею 2 інше число, що ділиться на 3 з остачею 2, ми отримаємо число, кратне трьом.

Таким чином, для того, щоб позиція була програшною, потрібно по-перше, щоб саме число ділилося на 3 з остачею 2, а по-друге, щоб це число не ділилося на жодне менше число, що ділиться на 3 з остачею 2.
Такі критерії задають послідовність простих чисел виду 3n-1 (послідовність A003627 в OEIS).

На перший погляд, може здатися, що цих критеріїв може бути недостатньо для визначення програшних позицій, бо зараз враховується тільки неможливість перемогти на поточному ході. Але насправді цього достатньо. Адже як ми визначили, для позицій з остачею 0 і 1 завжди можна перемогти за 1 хід. А з позиції з остачею 2 перейти в іншу позицію з остачею 2 неможливо (для цього треба було б віднімати 3).

Обмеження в задачі дозволяли вирішувати її практично будь-яким способом. Можна моїм способом з перевіркою остачі і дільників з остачею 2. Можна через ДП, можна в лоб пошуком в ширину/глибину з мемоізацією. Врешті решт, просто масивом констант (програшних позицій менших за 100 всього 13 штук).

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

#include <iostream>
using namespace std;

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

    bool res = n % 3 == 2;

    for (int i = 0; i * 3 + 2 < n && res; ++i) {
        res = n % (i * 3 + 2) != 0;
    }

    cout << (res ? "L" : "M") << endl;
}

Column
Відповіддю до задачі буде, очевидно, сума висот стовпчиків води над кожним стовпчиком кубиків. Для цього треба від рівня води в поточному місці віднімати кількість кубиків. Таким чином, єдине питання, що залишилось - це як знайти рівень води.
Розглянемо довільний стовпчик кубиків. Він буде покритим водою, якщо зліва і справа від нього є стовпчики, вищі за нього. При чому, рівень води буде рівним мінімуму висот найвищого стовпчика кубиків зліва від поточного і найвищого стовпчика кубиків справа від поточного.

Тоді ми можемо завести 2 допоміжних масиви. Назвемо їх max_prefix і max_suffix. max_prefix[i] буде зберігати висоту найвищого стовпчика кубиків у проміжку від першого (або нульового, дивлячись, як у вас в голові індексація працює) до i-го включно. А max_suffix[i] - висоту найвищого стовпчика у проміжку від i-го до останнього.

Заповнимо ці 2 масиви.

Далі просто рахуємо суму значень min(max_prefix[i], max_suffix[i]) - s[i], де s[i] - це висота поточного стовпчика кубиків. Варто зазначити, що ця різниця ніколи не буде меншою за 0, адже значення max_prefix та max_suffix рахувалися включно з поточним стовпчиком.

Таке рішення є достатньо швидким. Але варто звернути увагу на введення-виведення, адже тут нам треба прочитати в найгіршому випадку більше 40 мегабайт. В С++ потоки введення-виведення за замовчуванням синхронізуються з сішним введенням-виведенням щоб в одній програмі можна було використовувати як плюсові потоки cin/cout, так і сішні функції scanf/printf і при цьому не виникало ситуацій, типу "cin прочитав те, що назначалося для scanf". На ділі це означає, що cin витягує з системного вхідного потоку інформацію по одному символу. Це дуже неефективно, бо кожне читання з системного потоку потребує системного виклику. Це, в свою чергу, потребує перемикання контексту з режиму користувача на режим ядра. А це є дуже затратною в плані часу операцією. Введення-виведення працюватиме значно швидше, якщо його буферизувати. Тобто читати/писати не по 1 символу за раз, а одразу багато. І такий буферизований IO у С++ є. Для його увімкнення достатньо тільки відключити синхронізацію з сішним IO за допомогою команди

ios_base::sync_with_stdio(false);

Додатково можна відключити синхронізацію між вхідним і вихідним потоком за допомогою

cin.tie(NULL);
cout.tie(NULL);

але від цього уже ефект буде значно менш помітним.

Або ж можна використовувати введення/виведення у стилі сі з функціями scanf та printf. Вони також використовуються буферизоване введення-виведення.

Крім того можна оптимізувати ще й саме рішення. У поточному вигляді воно потребує близько 120 МБайт пам'яті і до того-ж, не дуже ефективно використовує кеш процесора. Можна позбутися допоміжних масивів, знайти висоту найвищого стовпчика, знайти позиції першого зліва та першого справа стовпчиків з такою висотою. Порахувати об'єм води між ними, потім іти зліва до першого максимального і справа до першого максимального, рахуючи максимум по ходу. Таке рішення потребує втричі менше пам'яті і, як я казав, працює трохи швидше через більш локальний доступ до пам'яті і як наслідок, більш ефективне використання кешу. Але воно більш заплутане, обмежень на пам'ять в олімпіаді немає, а виграш по часу не критичний (відсотків 10-15).

Код рішення на С++ (рішення з двома допоміжними масивами).

#include <iostream>
#include <algorithm>
using namespace std;

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

    int n;
    cin >> n;

    static int s[10000000], max_prefix[10000000], max_suffix[10000000];

    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    int cmax;

    for (int i = 0; i < n; ++i) {
        if (i == 0 || s[i] > cmax) {
            cmax = s[i];
        }

        max_prefix[i] = cmax;
    }

    for (int i = n - 1; i >= 0; --i) {
        if (i == n - 1 || s[i] > cmax) {
            cmax = s[i];
        }
        max_suffix[i] = cmax;
    }

    long long res = 0;

    for (int i = 0; i < n; ++i) {
        res += min(max_prefix[i], max_suffix[i]) - s[i];
    }

    cout << res << endl;
}

Wars
Тут особливо і немає чого пояснювати. Задача зрозуміла, обмеження невеликі. Просто в лоб для кожного розряду перебираємо всі введені числа і шукаємо, яка цифра зустрічається найчастіше. Якщо виявилося, що таких цифр більше однієї, то беремо нуль.
Єдиний момент, варто звернути увагу, що за умовою введені числа не більші за 10^9. Тобто ≤ 10^9. Якщо хтось сприйняв це як < і вирішив, що розрядів може бути не більше 9, то залежно від реалізації, могли пролетіти якісь тести (якщо такі були, я не перевіряв).

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

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
    int n;
    int codes[100];
    int maxCode = 0;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> codes[i];
        maxCode = max(maxCode, codes[i]);
    }

    int res = 0;

    for (int divisor = 1; divisor <= maxCode; divisor *= 10) {
        int vals[10];
        memset(vals, 0, sizeof(vals[0]) * 10);

        for (int i = 0; i < n; ++i) {
            int val = (codes[i] / divisor) % 10;
            vals[val]++;
        }

        int maxVal = 0;
        bool ambiguous = false;
        for (int i = 1; i < 10; ++i) {
            if (vals[i] > vals[maxVal]) {
                maxVal = i;
                ambiguous = false;
            } else if (vals[i] == vals[maxVal]) {
                ambiguous = true;
            }
        }

        if (ambiguous) {
            maxVal = 0;
        }

        res += maxVal * divisor;
    }

    cout << res << endl;
}

Evacuation
Виявилася найскладнішою. Всього 6 учасників отримали повний бал, серед яких журі і дублікат одного з учасників .
Задача стає значно простішою, якщо не намагатись розв'язати всю задачу зразу, а розв'язувати її поетапно.

Перш за все, нас не дуже цікавлять швидкості і відстані. Нас цікавить час. Тому для початку переведемо це все в час: рас руху по дорозі, час перепливання від корабля до пристані А, до пристані Б, від пристані А, від пристані Б і т.д.:

double time_road = (double)l3 / u;
double time_to_a = (double)l1 / max(v - w, 0);
double time_from_a = (double)l1 / (v + w);
double time_to_b = (double)l2 / (v + w);
double time_from_b = (double)l2 / max(v - w, 0);

Тут можна помітити ще 2 важливих моменти: 1) цілі числа треба перевести в дійсні, бо час не обов'язково буде цілим; 2) важливо правильно врахувати ситуації коли швидкість течії більша за власну швидкість човна. В такому випадку можна вважати результуючу швидкість нульовою. Також хтось міг злякатися ділення на нуль. Але для дійсних чисел ділення на нуль - цілком валідна операція. При діленні додатного числа результатом буде спеціальне значення +нескінченність (inf). Для від'ємного числа буде -inf. Для ділення нуля на нуль - спеціальне значення nan (Not A Number - не число). Для нашого випадку така поведінка чудово підходить, бо для нульової і від'ємної швидкості час руху якраз має бути нескінченним.

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

double min_time_to_any = min(time_to_a, time_to_b);

double min_time_from_a = min(time_from_a, time_road + time_from_b);
double min_time_from_b = min(time_from_b, time_road + time_from_a);

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

double round_trip_time = min(time_to_a + min_time_from_a, time_to_b + min_time_from_b);

Тепер у нас є усі необхідні нам значення часу. Далі треба продумати загальний алгоритм вивезення людей з корабля.
Якщо всі люди поміщаються в човен, то ми просто пливемо до пристані з найменшим часом, тобто відповіддю буде значення min_time_to_any. Якщо ж ні, то треба буде зробити певну кількість запливів "туди-сюди", але після останнього запливу повертатися на корабель уже не треба буде Тобто відповіддю буде значення n_round_trips * round_trip_time + min_time_to_any, де n_round_trips - це кількість запливів "туди-сюди". Залишилося знайти цю кількість і задача розв'язана.

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

І окремо треба обробити 2 граничні випадки: коли після визначення капітана човна на кораблі нікого не залишилось, і коли після займання капітаном місця в човні, місця для інших пасажирів корабля не залишилось.

Окремим джерелом питань було округлення результату. Як і обіцяв, даю цитати з умови:

Програма виводить ... шуканий час (ціле число секунд) ...

Знайти мінімальний час, за який капітан зможе евакуювати всіх ...

Тобто треба вивести мінімальне ціле число секунд, якого буде достатньо для того, щоб усіх евакуювати. Очевидно, цим вимогам задовольняє округлення догори. Наприклад, ми отримали результат 12.3 секунди. Вивести 12.3 ми не можемо, бо відповідь має бути цілою. Вивести 12 ми теж не можемо, бо 12 секунд недостатньо для евакуації. Правильна відповідь у такому випадку - 13.

Також важливо не забути виводити відповідь саме як ціле число, адже ceil повертає дійсне. Цього можна досягти або приведенням до long long (не int! Існують набори вхідних даних, для яких результат в інт не влізе), або ж налаштуванням формату виводу якось так:

cout << setprecision(0) << fixed

Я втратив частину балів за цю задачу саме на цьому

Код рішення на С++ (з виправленою проблемою. Цей код набирає 20 балів).

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

double solve(int n, int k, int l1, int l2, int l3, int v, int w, int u) {
    double time_road = (double)l3 / u;
    double time_to_a = (double)l1 / max(v - w, 0);
    double time_from_a = (double)l1 / (v + w);
    double time_to_b = (double)l2 / (v + w);
    double time_from_b = (double)l2 / max(v - w, 0);

    double min_time_to_any = min(time_to_a, time_to_b);

    double min_time_from_a = min(time_from_a, time_road + time_from_b);
    double min_time_from_b = min(time_from_b, time_road + time_from_a);

    double round_trip_time = min(time_to_a + min_time_from_a, time_to_b + min_time_from_b);

    k--; n--;

    if (n == 0) {
        return min_time_to_any;
    }

    if (k == 0) {
        return -1;
    }

    int n_round_trips = (n - 1) / k;

    return n_round_trips * round_trip_time + min_time_to_any;
}

int main() {
    int n, k, l1, l2, l3, v, w, u;

    cin >> n >> k >> l1 >> l2 >> l3 >> v >> w >> u;

    cout << (long long)ceil(solve(n, k, l1, l2, l3, v, w, u)) << endl;
}

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

Крім того, можна помітити, як поступово з функції 8 змінних (n, k, l1, l2, l3, v, w, u) задача звелася до функції всього 4 змінних (n, k, round_trip_time, min_time_to_any), а потім і трьох (n_round_trips, round_trip_time, min_time_to_any).

Думаю, багато початківців писали на цю задачу щось у такому стилі:

int main(){
    double  n, k, l1, l2, l3, v, w, u, ans1, ans2, ans3, ans4;
    cin>>n>>k>>l1>>l2>>l3>>v>>w>>u;
    ans1=(n/(k))*l1*(1/(v-w)+1/(v+w));
    ans2=(n/(k))*l2*(1/(v+w)+1/(v-w));
    ans3=(n/(k))*((l1+l2)/(v-w)+l3/u);
    ans4=(n/(k))*((l1+l2)/(v+w)+l3/u);
    cout<<min(min((int)ans1, (int)ans2),min((int)ans3, (int)ans4));
}

Тут уже, скоріш за все, розібратися і пояснити, що відбувається не зможе навіть сам автор коду, не кажучи вже про когось стороннього, чи про те, щоб знайти і виправити помилки

В олімпіадному програмування нечасто це настільки критично. Як правило, писати write-only код - це нормально. Але якщо хтось збирається програмувати професійно, то на це варто звертати увагу. Ваш код повинен бути зрозумілим. В ідеалі - зрозумілим не тільки вам і не тільки під час його написання

Відредаговано Dim_ov (2017-11-13 02:17:11)