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


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

Ви не зайшли.

#1 2017-11-13 02:14:09

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

Розв'язки задач

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


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

Картинка:
https://www.dropbox.com/s/54ij44bi37pcm0a/Untitled%20spreadsheet%20-%20Google%20Sheets%20-%20Google%20Chrome%202017-11-12%2022.42.31.png?dl=1

Таким чином, при непарному полі заповненим буде прямокутник розміром 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 учасників отримали повний бал, серед яких журі і дублікат одного з учасників smile.
Задача стає значно простішою, якщо не намагатись розв'язати всю задачу зразу, а розв'язувати її поетапно.

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

Код:

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

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

Код рішення на С++ (з виправленою проблемою. Цей код набирає 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));
}

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

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

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

Поза форумом

 

#2 2017-11-13 18:10:30

ikovrigin
Олімпієць
Зареєстрований: 2017-11-13
Повідомлень: 26

Re: Розв'язки задач

В соревнованиях не предусмотрены взломы, а тесты жюри не полные. Для последней задачи используя double и ceil вы не можете получить верное решение. Попробуйте для примера cout<< ceil(7.0/25.0*50.0); неожиданно будет 15. Хотелось бы увидеть верное решение использующее целочисленную арифметику.

Відредаговано ikovrigin (2017-11-13 18:11:32)

Поза форумом

 

#3 2017-11-13 18:58:34

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

Re: Розв'язки задач

ikovrigin написав:

В соревнованиях не предусмотрены взломы, а тесты жюри не полные. Для последней задачи используя double и ceil вы не можете получить верное решение.

Згоден. Але не треба забувати, що це перший тур. Тестів, які б експлуатували недоліки IEEE 754, по перше, в будь-якому випадку було б небагато (а по факту їх не було взагалі). А по-друге, створення "універсального" тесту, який би 100% ламав усі рішення з double може бути справою непростою, бо в залежності від порядку обчислень точність може втрачатися у різних місцях. І тест, який ламає double-рішення одного учасника не обов'язково поламає double-рішення іншого.

ikovrigin написав:

Хотелось бы увидеть верное решение использующее целочисленную арифметику.

Тримайте.
Python 3.

Код:

from fractions import Fraction as F

INF = 1e300

def solve(n, k, l1, l2, l3, v, w, u):
    time_road = F(l3, u)
    time_to_a = F(l1, v-w) if v > w else INF
    time_from_a = F(l1, v+w)
    time_to_b = F(l2, v+w)
    time_from_b = F(l2, v-w) if v > w else INF

    min_time_to_any = min(time_to_a, time_to_b)

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

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

    k -= 1
    n -= 1
    if n == 0:
        return min_time_to_any
    if k == 0:
        return F(-1, 1)

    n_round_trips = (n - 1) // k

    return n_round_trips * round_trip_time + min_time_to_any

n, k, l1, l2, l3, v, w, u = list(map(int, input().split()))

t = solve(n, k, l1, l2, l3, v, w, u)

print(int(t) + (1 if t.numerator % t.denominator > 0 else 0))

Онлайн-перевірку проходить (іноді на кількох тестах може вилетіти ТЛ. Достатньо натиснути f5 в таких випадках). Офіційну перевірку мабуть не пройшло б, бо там ТЛ-и більш жорсткі (підозрюю, що в районі 0.03 с). Якщо переписати дроби на C/C++/Pascal (по моєму, для тих обмежень, що в задачі навіть довга арифметика не треба, і чисельник і знаменник влізуть в 64-бітний інт), то пройде й офіційну.

Але потенційна втрата 3-5 балів через можливі помилки при роботі з double ні на що не вплине. А при відправці рішення на Python під питанням були б уже всі 20 балів. Так, можна було б написати дроби на мові, що компілюється в машинний код.  Але повторюся, це перший тур. А в задачі і так вийшло доволі багато кроків і нюансів як для задачі першого туру.

Відредаговано Dim_ov (2017-11-13 19:05:20)

Поза форумом

 

#4 2017-11-13 19:47:44

ikovrigin
Олімпієць
Зареєстрований: 2017-11-13
Повідомлень: 26

Re: Розв'язки задач

Дело в том что это решение дает очень много неверных решений. Их поиск делается очень легким перебором
    k = 2;
    l2 = 10000;
    l3 = 10000;
    u = 100000;
    for (n=1; n<100; n++) {
        for (l1=1; l1<100; l1++) {
            for (v = 1; v<100; v++) {
                for (w=1; w<v; w++) {
                    double s = solve(n, k, l1, l2, l3, v, w, u);
                    long long c = (long long)ceil(s);
                    if ((c-s)>0.999999999) {
                        cout<<n<<" "<<l1<<" "<<v<<" "<<w<<endl;
                        cout<< std::setprecision(20)<<c<<" "<<s<<endl;
                    }
                }
            }
        }
    }

можете прогнать свое решение на тестовом примере
    n = 4;    k = 2;    l1 = 5;    l2 = 10;    l3 = 10;    v = 4;    w = 1;    u = 10;

остальные переменные для простоты перебора     k = 2;    l2 = 10000;    l3 = 10000;    u = 100000;
далее только n, l1, v, w  и разница вычислений.

4 5 13 7
4 3.0000000000000004441

4 10 4 1
15 14.000000000000001776

...

99 98 84 63
523 522.00000000000011369
99 98 90 50
309 308.00000000000005684

для моего перебора около 30 000 ошибочных решений только для n меньше 100.
Я не считаю что решение дающее такое кол-во неверных результатов может вообще считаться хотя бы приблизительно верным.
Да вероятно решение с использованием дробей на питоне имеет место быть, обычно же в таких случаях принимают решение с какой то точностью, а не округляют.

И да я не считаю подобные тесты эксплойтами, потому что работая с числами с плавающей точкой участники должны осознавать что накапливается ошибка, если они этого не понимают, значит их решение не может считаться верным.

P.S. Спасибо за разборы, это не попытка "прикопаться", это скорее замечания к неточности постановок.

Відредаговано ikovrigin (2017-11-13 20:00:28)

Поза форумом

 

#5 2017-11-13 21:06:17

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

Re: Розв'язки задач

ikovrigin написав:

P.S. Спасибо за разборы, это не попытка "прикопаться", это скорее замечания к неточности постановок.

Я розумію smile

Взагалі, варто було б просто слідувати звичайним правилам роботи з плаваючою крапкою і віднімати якийсь епсілон (в районі 10^-9 - 10^-6) від результату перед викликом ceil і для більшості випадків (а з обмеженнями з умови можливо і для всіх випадків) проблема б вирішилась. Але як уже було сказано, 100% вірним для будь-яких вхідних даних буде тільки цілочисельне рішення з дробами і довгою арифметикою.

Поза форумом

 

#6 2017-11-13 21:58:03

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 19

Re: Розв'язки задач

Язык python

Chess 2k17

Отправлено это

Код:

N = int(raw_input())
print (N>>1)*((N+1)>>1)

Хотя лучше было бы (благодарю Fordperfect за подсказку)

Код:

N = int(raw_input())
(N*N)>>2

Game2k17

Шел через доказательство того, что Лена выигрывает, если число простое типа 3k-1. Отправлено чуть другое, но потом получил дозу вдохновения от уже упомянутого Fordperfect и поправил.

Код:

print "ML"[int(raw_input()) in [2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89]]

Сolumn

Делим список высот на два куска: до максимума и после него. После заливки водой высоты в первом куске начинают образовывать неубывающую последовательность. Если второй кусок прочитать справа налево, то и в нем тоже.

Код:

a = map(int,raw_input().split())
S = a[1:]
i_max = S.index(max(S))
def Volume(X):
    curr_max = 0
    vol = 0
    for i in xrange(len(X)):
        if X[i]>curr_max:
            curr_max = X[i]
        else:
            vol += curr_max - X[i]
    return vol

print Volume(S[:i_max])+Volume(S[-1:i_max:-1])

Такой код валится на восьмом тесте после 25 секунд работы. Питон не очень шустр.
Попытка передавать в функцию не отрезок списка, а генератор индексов (xrange) не улучшает ситуацию. Ну да и ладно.

Wars

В лоб и без изысков. Работал с исходными числами как со строками из цифр, чем они по сути и являются.

Код:

a = raw_input().split()
N = int(a[0])
codes = a[1:]
l = max(map(len, codes))
for i in xrange(N):
    codes[i] = codes[i].zfill(l)

res = ''
for i in xrange(l):
    freq = [0]*10
    for code in codes:
        freq[int(code[i])] += 1
    fmax = max(freq)
    x = freq.index(fmax)
    if fmax in freq[x+1:]:
        x = 0
    res += str(x)

print int(res)

Evacuation

Спасение состоит из n одинаковых поездок туда-обратно и одной в сторону берега. Сначала рассмотрен экстремальный случай с лодкой, рассчитанной на одного пассажира.
Потом более простой случай со скоростью течения большей скорости лодки, потом добавил возможность движения против течения.

Код:

from math import ceil
N, K, L1, L2, L3, V, W, U = map(int,raw_input().split())
L1, L2, L3, V, W, U = map(float,(L1, L2, L3, V, W, U))

if K == 1:     
    if N > 1: 
        print -1
    else:
        T = L2/(V+W)
        if V>W: T = min(T, L1/(V-W))
        print int(ceil(T))
else: 
    n = (N-2)//(K-1)*(not not(N-1))
    T = (L1+L2)/(V+W)+L3/U 
    T_last = L2/(V+W) 
    if V>W: 
        L = min(L1,L2)
        T = min(T, L/(V+W)+L/(V-W)) 
        T_last = min(T_last, L1/(V-W))
    print int(ceil(n*T + T_last))

Такой код набирает полное число баллов. Однако же, когда вопрос в задаче "найти минимальное время ...", а ниже отмечено, что "искомое время (целое число секунд)", то это понимается именно как гарантия того, что ответ будет целый. Пообщался с другом, принимавшим участие в туре, он тоже так понял условие, отчего есть подозрение, что так поняли и многие другие. На мой взгляд, более корректно было бы явно сформулировать, куда округлять, например так "Найти, минимальное целое число секунд достаточное, чтобы всех эвакуировать". В отправленном коде было int(round(..)), что более логично для целых ответов, и 16/20.

Поза форумом

 

#7 2017-11-15 15:56:37

ASYepifanov
Олімпієць
Зареєстрований: 2017-10-18
Повідомлень: 3

Re: Розв'язки задач

Dim_ov написав:

...обмежень на пам'ять в олімпіаді немає, а виграш по часу не критичний (відсотків 10-15)...

Всего-то? А я неделю сидел мудрил, думал, как от массивов избавиться...

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt