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


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

Ви не зайшли.

#1 2017-12-24 05:20:19

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

Розбори задач

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

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

Chess22k17

На перший погляд може здатися, що задача розв'язується аналогічно до задачі Chess2k17 з першого туру. Але насправді все трохи складніше. Для неквадратних дошок просте розділення дошки навпіл по горизонталі і вертикалі не завжди дасть оптимальне розміщення тур. Простий приклад, щоб переконатися: дошка 10х15. Оптимальне розміщення тур виглядає ось так:
https://www.dropbox.com/s/w68o0n4svcbgo0q/Untitled%20spreadsheet%20-%20Google%20Sheets%20-%20Google%20Chrome%202017-12-23%2002.38.26.png?dl=1
Розміщено 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) smile

Код "чесного" рішення на С++.
Структура 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

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

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

До формули.
https://www.dropbox.com/s/2wzcw7dif3fg6lj/Pulley_Problem.png?dl=1
Пряма 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)

Поза форумом

 

#2 2017-12-24 14:09:57

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

Re: Розбори задач

Четвертая задача намного легче. Задачу можно переформулировать так: "Сколькими способами можно добраться до последней ступеньки, прыгаю на следующюю или через (k-1), но нельзя прыгать прыжком одного вида."

Код:

 var
 a:array[-10..100] of qword;
 n,k,i:longint;
begin
 readln(n,k);
 a[1]:=1;
 for i:=1 to k-1 do
 a[i]:=1;
 a[k]:=2;
 for i:=k+1 to n do
  a[i]:=a[i-1]+a[i-k];
 dec(a[n]);
 if (n mod k=0) then dec(a[n]);
 writeln(a[n]);
end.

Рома, не пиши на Питоне

Поза форумом

 

#3 2017-12-25 02:44:35

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

Re: Розбори задач

Все решения на python, набирают максимальный результат.

Сhess22k17

Код:

M, N = map(int,raw_input().split())
if M%2==0 and N%2==0: 
    print M*N>>2
else:
    a, b = min(M,N), max(M,N)
    limit = int(((a+b-1)/4.0*a/b)**0.5)
    z = [max((a-i)*(b*i/a), i*(b*(a-i)/a)) for i in xrange(a/2-limit,a/2+1)]
    print max(z)

Решение удалось провести за O(sqrt(min(M,N)) доказав, что точный максимум на прямой, смещенной относительно центра больше, чем на limit (т.е. максимум min(a * b, (n - a) * (m - b)) при фиксированном a=n/2-limit и непрерывном b), меньше, чем число тур, соответсвующее имеющимся точкам около центра. При M=N=1e6 limit=sqrt(500000)~700.

Br2k17

Код:

N = input()
C_2 = [1]#C_2[i] = Catalan(i)*2**i
C_3 = [1]#3 types of braces
for i in xrange(1,N+1):
    nxt2, nxt3 = 0, 0
    for j in xrange(i):
        nxt2 += C_2[j]*C_2[i-j-1]*2
        nxt3 += (2*C_3[i-j-1]+C_2[i-j-1])*C_3[j]
    C_2.append(nxt2)
    C_3.append(nxt3)    
print C_3[-1]

Решение вытекает из википедийного доказательства рекуррентного соотношения для чисел Каталана, обобщением на три типа скобок.
Его можно ускорить почти в 2 раза, если не считать nxt2, а использовать более простое рекуррентное соотношение
C_2.append(C2[-1]*4*(2*i-1)/(i+1)).
Итого, самое труЪ решение будет таким:

Код:

N = input()
C_2 = [1]+N*[0]#C_2[i] = Catalan(i)*2**i
C_3 = [1]+N*[0]#3 types of braces
for i in xrange(N):
    for j in xrange(i):
        C3[i+1] += (2*C_3[j]+C_2[j])*C_3[i-j]
    C_2[i+1] = C_2[i]*4*(2*i+1)/(i+2)
print C_3[-1]

Отправляю порцию печенек на темную сторону силы для FordPerfect.

Pal2017

Решение некрасивое. Питон дает преимущество только при четной длине входных данных

Код:

S = raw_input()
digits=[list(S[0::2]), list(S[1::2])]

def merge(even, odd):#valid only for odd full length!!!
    ans = ""
    for i in xrange(len(odd)):
        ans += even[i]+odd[i]
    ans += even[-1]
    return ans
    
def counts(digs):#count number of digits' occurrences
    ret = [0]*10
    for s in digs:
        ret[int(s)] += 1
    return ret
        
def not_ok(digs):#returns True if input is not palindromizable
    return sum(map(lambda x:x%2, counts(digs))) != len(digs)%2
    
def palize(digs):#palindromize a string
    cnts = counts(digs)
    half, center = "", ""
    for i in xrange(10):
        half += cnts[i]/2*str(i)
        center += cnts[i]%2*str(i)
    return half + center + half[::-1]
  
if len(S)%2:
    if not_ok(digits[0]) or not_ok(digits[1]):
        print "-1"
    else:
        print merge(palize(digits[0]), palize(digits[1]))
else:
    digits[0].sort()
    digits[1].sort()
    if digits[0] !=  digits[1]:
        print "-1"
    else:
        print ''.join(digits[0]+digits[0][::-1])

Robotsway

Код:

n,k = map(int,raw_input().split())
R = [1]*k
while len(R)<=n:
    R.append(R[-1]+R[-k])
print R[-1] - 1 - int(not n%k)

Transmission

Нелинейное уравнение решай методом Ньютона! Для этого уравнения этот метод особенно хорош, так как производная невязки является няшной алгебраической функцией

Код:

from math import pi, asin, sqrt
R1, R2, L = map(float, raw_input().split()) 
    
def residual(dist):
    phi = asin((R1-R2)/dist)
    return pi*(R1+R2)+2.0*sqrt(dist*dist-(R1-R2)*(R1-R2))+2.0*(R1-R2)*phi-L

tmp1 = (L-pi*(R1+R2))/2.0
init = sqrt(tmp1*tmp1-(R1-R2)*(R1-R2))
precision = L*1e-14
x = residual(init)
while abs(x) > precision:
    tmp = (R1-R2)/init
    der = 2*sqrt(1-tmp*tmp)
    init -= x/der
    x = residual(init)    
print repr(init)

Ответ с относительной погрешностью 1e-14 находит за 3-4 итерации, а может даже и максимум за 3 для моего initial guess, уже не помню. Дальше не мудрил.
PS Да, этот код работает даже при while x>precision: вместо while abs(x) > precision: , но никому так делать не советую - чревато.

Відредаговано andervish (2017-12-25 19:28:34)

Поза форумом

 

#4 2017-12-25 23:21:16

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

Re: Розбори задач

не понятно

andervish написав:

т.е. максимум min(a * b, (n - a) * (m - b)

, а в коде у вас два раза максимум. Так же вы используете извлечение корня который не будет работать с длинной арифметикой.

Ну и по-поводу асимптотической сложности, если я не ошибаюсь функция в задаче допускает тернарный поиск, соответственно можно добиться O(log(min(N,M))), что то по типу:

Код:

M, N = map(int,raw_input().split())

def solve(M,N):
    if M%2==0 and N%2==0:
        return M*N>>2
    else:
        a, b = min(M,N), max(M,N)

        def f (i):
            return min((a-i)*(b*i/a), i*(b*(a-i)/a))

        l,r = 0, a/2
        while (r-l)>=3:
            m1 = l+(r-l)/3
            m2 = r-(r-l)/3
            if f(m1)<f(m2):
                l=m1
            else:
                r=m2
        return max(f(l),f(l+1),f(r))

print solve(M,N)

Відредаговано ikovrigin (2017-12-25 23:43:05)

Поза форумом

 

#5 2017-12-28 16:40:44

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

Re: Розбори задач

ikovrigin написав:

два раза максимум

Очень хороший вопрос. После переименования сторон в a и b я рассматриваю задачу в постановке max(min(i*(b-j),(a-i)*j)). При фиксированном i максимум находится в одной из целых точек, приближающих дробь b*i/a сверху или снизу. Если взять точку сверху, то j>=b*i/a, следовательно min[i*(b-j), (a-i)*j]= i*(b-j), если снизу, то j<=b*i/a, и min[i*(b-j), (a-i)*j]sada-i)*j. Для точки сверху b-j = (a-i)*b//a, для точки снизу j = b*i//a. Итого искомый максимум при фиксированном i равен max(i*(b*(a-i)//a)), (a-i)*(b*i//a)), что и считается в коде.

ikovrigin написав:

извлечение корня который не будет работать с длинной арифметикой

Тут не совсем понял, что имется в виду. При ограничениях, наложенных на входные данные limit не больше 1000. Да и корень с длинными целыми работает адекватно.

Код:

>>> sqrt(1000000000000000000000000000000000000000000000000000000000)
3.1622776601683795e+28
>>> 1000000000000000000000000000000000000000000000000000000000**0.5
3.1622776601683795e+28
>>> int(1000000000000000000000000000000000000000000000000000000000**0.5)
31622776601683794750641012736L

Идея с тернарным поиском очень красивая. Нужно только показать, что z(i) =  max(i*(b*(a-i)//a)), (a-i)*(b*i//a)) является унимодальной, что неочевидно.

UPD z(i) не унимодальна. http://rextester.com/ECELB82622 (c) известно кто.

PS Поскольку выражения в max в z(i) переходят друг в друга при замене i->a-i, то можно чуть-чуть упростить код за счет симметризации интервала.

Код:

M, N = map(int,raw_input().split())
if M%2==0 and N%2==0: 
    print M*N>>2
else:
    a, b = min(M,N), max(M,N)
    limit = int(((a+b-1)/4.0*a/b)**0.5)
    z = [(a-i)*(b*i/a) for i in xrange(a/2-limit,a/2+2+limit)]
    print max(z)

Новое z(i) тоже не унимодально.

Відредаговано andervish (2017-12-29 23:37:34)

Поза форумом

 

#6 2018-01-25 15:20:22

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

Re: Розбори задач

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

from math import sqrt
i = 111111111111111111
i = int(sqrt(i*i))
print i

Результат не радует 111111111111111120

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt