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

Задача Sum2020.

#include <bits/stdc++.h>

using namespace std;


int main()
{
    const int MOD=1000000007;
    int n, s;
    cin >> n >> s;
    int *prev, *cur, *sw;
    prev = new int[1 + s];
    cur = new int[1 + s];
    for(int j=1; j<=s; j++)
        prev[j]=(j<=9)%MOD;
    for(int i=2; i<=n; i++){
        for(int j=1; j<=s; j++){
            cur[j]=0;
            for(int c=0; c<=9 && j-c>0; c++)
                cur[j]=(cur[j]+prev[j-c])%MOD;
        }
        //поменяли массивы местами
        sw=prev;
        prev=cur;
        cur=sw;
    }
    cout << prev[s];
    return 0;
}

Ну давайте разберём эту задачу: прежде всего - это ДП. Причём двумерное.
Давайте скажем, что dp[count][sum] - это количество чисел длины count и с суммой цифр sum.
Ну тогда инициализируем: Очевидно, что в строчке номер 1(одноцифровые числа) будет так: в столбиках 1-9 будет 1, дальше нули.
Ну понятно: ведь существует всего 1 одноцифровое число с суммой цифр, например, 5 - это 5.))) А вот одноцифровых чисел с суммой цифр больше 9 не существует - тоже весьма очевидно. Всё это - в следующей строчке.

 for(int j=1; j<=s; j++)
        prev[j]=(j<=9)%MOD;

//И да, у меня в коде нет слова dp, но причина чуть-чуть позже.
Так. Дальше формула пересчёта.
dp[i][j]=<здесь должна быть сигма)>jє[0;9] : dp[i-1][j-c].
Ну типа суммируем все dp[i][j-c], где с - это все возможные цифры(ну 10 штук.)
Ок. А почему так, спросите? Резонно. Ну тут идея такова: будем продливать число длины (i-1) различными цифрами от 0 до 9. Тогда число будет иметь длину i и, что важно, сумма цифр увеличится на значение этой цифры. Так вот: если взять число , в котором кол-во цифр
и их сумма равны i-1 и j-c соответственно, то прибавив в конец данного числа цифру с, получим число с кол-вом цифр i и их суммой, равной j. А их количество равно dp[i][j]. Таким образом нам нужно просто просуммировать все КОЛИЧЕСТВА(наша динамика!) чисел длины i-1 и суммами цифр, на значение всех допустимых цифр "с" меньше текущего j.
Надеюсь, тут всё понятно. Не понятно - пишите в чат, ответим.)
Теперь почему нет двумерного массива.
Ну просто нам пришлось бы держать массив dp[1000][9000], что не представляется возможным (на заметку:  можно где-то 1000х1000 как правило. Иначе - ошибка. Но у меня на компе даже 500х500 не тянет))) Поэтому, если Вы тестируете задачу у себя на компе, то не переживайте, что она вылетает от переполнения памяти: в проверочной системе компы - что надо).
Но эту проблему довольно легко решить: мы ведь при вычислении dp[i][j] использовали лишь значения из предыдущей строки(dp[i-1][...]),
значит и будем хранить лишь 2 строчки(линейных массива): prev - предыдущую и cur - текущую, как не трудно догадаться. Вычислив значение текущей, можем обменять местами указатели на динамические массивы за O(1) и использовать массивы повторно уже в другом "амплуа": на предыдущем шаге это был по факту массив предыдущей строчки, а на текущем - уже текущей.
Короче говоря, просто вместо хранения всей матрицы используем две её строки.
Как-то так. Надеюсь, что мои опусы были Вам интересны. Буду очень рад, если здесь ниже появятся вопросы(с радостью на них отвечу) и решения других задач, так как, окромясь этих двух, я не решил ничего(времени не хватило))) ).



PS: С наступающим 2021-м годом!!! Желаю всем, что бы сбылись все ваши мечты и осуществились планы на 21-й!!!

Відредаговано GeniusDP (2020-12-31 19:11:38)

Повнобальні рішення з короткими розборами. Частково повторюють ті, що вже викладені вище, але для повноти - нехай буде

Plant

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

В процесі перебору враховуумо наступні незалежні змінні:

- Кожна з будівель може бути в оригінальній орієнтації, або повернутою на 90 градусів (2 варіанта для кожної з будівель, кожен вибір незалежний, тож всього 2^3=8 варіантів)
- коли "склеюємо" 2 перші будівлі, ми можемо їх склеїти по вертикалі, або по горизонталі (2 варіанти)
- аналогічно, коли приклеюємо третю будівлю - можемо приклеїти по вертикалі, або по горизонталі (2 варіанти).
- порядок склеювання. Які будівлі клеїмо перші, а яку потім ліпимо до них. 3 варіанти: ((1, 2), 3), ((2, 3), 1), ((3, 1), 2)

Таким чином, всього маємо 96 варіантів розміщення. Їх і перевіряємо.

Асимптотика.

Час: O(1)
Пам'ять: O(1)

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

#include <iostream>
#include <limits>
#include <functional>

using namespace std;

typedef pair<int, int> rect;

int area(rect r) {
    return r.first * r.second;
}

rect rotated(rect r) {
    return {r.second, r.first};
}

rect get_v_bounding_box(rect a, rect b) {
    return {max(a.first, b.first), a.second + b.second};
}

rect get_h_bounding_box(rect a, rect b) {
    return {a.first + b.first, max(a.second, b.second)};
}

int get_min_bounding_box_area(rect a, rect b, rect c) {
    function<rect (rect, rect)> bb_functions[] {
        get_v_bounding_box,
        get_h_bounding_box
    };

    int res = numeric_limits<int>::max();

    for (auto f1 : bb_functions) {
        for (auto f2 : bb_functions) {
            rect boxes[] = {
                f1(f2(a, b), c),
                f1(f2(b, c), a),
                f1(f2(c, a), b),
            };

            for (auto r : boxes) {
                res = min(res, area(r));
            }
        }
    }

    return res;
}

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

    rect rects[3];

    for (auto &r : rects) {
        cin >> r.first >> r.second;
    }

    int res = numeric_limits<int>::max();

    for (int rotation_mask = 0; rotation_mask < 1 << 3; ++rotation_mask) {
        auto bb_area = get_min_bounding_box_area(
                rotation_mask >> 0 & 1 ? rotated(rects[0]) : rects[0],
                rotation_mask >> 1 & 1 ? rotated(rects[1]) : rects[1],
                rotation_mask >> 2 & 1 ? rotated(rects[2]) : rects[2]
          );

        res = min(res, bb_area);
    }

    cout << res << endl;
}

Pixels2020

Нехай A - оригінальна вхідна матриця, так що A[i​][j​] - це колір пікселя в i-му рядку і j-му стовпчику.

Заведемо допоміжну матрицю S, елементи якої зберігатимуть суму значень пікселів у фрагменті з початку координат до поточного пікселя:


За допомогою цієї матриці ми можемо за константний час знаходити суму значень пікселів у будь-якому фрагменті. Сума значень пікселів у фрагменті з лівим верхнім кутом у координаті (x; y), та розмірами (h; w) дорівнюватиме


Обчислювати значення елементів допоміжної матриці можна прямо находу, по мірі зчитування вхідних даних, так само за константний час (для одного елемента).

Після того, як отримали цю допоміжну матрицю - пробігаємося по ній і шукаємо фрагмент з мінімальною та максимальними яскравостями відповідно. Оскільки розміри фрагмента фіксовані, пробігтися достатньо один раз.

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


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

#include <limits>
#include <iostream>

using namespace std;

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

    const int MAX_N = 640;
    const int MAX_M = 480;

    int m, n, a, b;

    cin >> m >> n >> a >> b;

    static int s[MAX_M + 1][MAX_N + 1] = {};

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> s[i][j];

            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
        }
    }

    int max_s = numeric_limits<int>::min();
    int min_s = numeric_limits<int>::max();

    for (int i = 0; i <= m - a; ++i) {
        for (int j = 0; j <= n - b; ++j) {
            auto sum =
                    s[i + a][j + b] -
                    s[i]    [j + b] -
                    s[i + a][j]     +
                    s[i]    [j];
            max_s = max(max_s, sum);
            min_s = min(min_s, sum);
        }
    }

    cout << min_s << " " << max_s << endl;
}

Sum2020

Розглянемо функцію g(k, s), таку, що g(k, s) дорівнює кількості k-цифрових чисел з сумою цифр s. Нехай ми знаємо значення цієї функції для усіх s при k = n-1. У такому разі ми можемо обчислити значення функції для k = n та довільного s наступним чином:


Тобто отримали рекурсивну формулу. Базою рекурсії будуть наступні випадки:



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

Рішення нижче реалізує ДП.

Асимптотика.
По часу: O(N * S)
По пам'яті: O(N * S), але при бажанні можна зробити O(S), оскільки у кожний момент часу нам потрібен лише попередній рядок матриці ДП.

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

#include <iostream>
#include <algorithm>

using namespace std;

const long long MOD = 1000000007;

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

    const int MAX_N = 1000;
    const int MAX_S = MAX_N * 9;

    int n, s;
    cin >> n >> s;

    static int dp[MAX_N + 1][MAX_S + 1];

    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        dp[i][0] = 0;
    }

    for (int i = 1; i <= s; ++i) {
        dp[0][i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= s; ++j) {
            auto val = 0LL;

            for (int digit = 0, end = min(9, j); digit <= end; ++digit) {
                val += dp[i - 1][j - digit];
            }

            dp[i][j] = val % MOD;
        }
    }

    cout << dp[n][s] << endl;
}

Parket0

Візерунок можна умовно розділити на 4 зони:



- Центральна (зелена). Зона, яка повністю складається з "повних" блоків 5х5.
- Бокові (жовті). 4 стрічки, які прилягають до зеленої зони. Вздовж однієї з осей їх довжина кратна 5 і вони складаються з цілого числа "повних" блоків. Вдовж іншої осі - їх довжина строго менша 5.
- Кутові (червоні). Не містять жодного повного блока, п обох осях менші за 5. Одним кутом прилягають до зеленої зони.

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

Будемо рахувати кількості дощечок у кожній зоні окремо.

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

Після цього підрахунок дощечок у кожній зоні - доволі прямолінійний.

Центральна зона:
Рахуємо кількість блоків 5х5 у зоні (їх ціла кількість, бо усі координати кратні 5). Кожна з цих зон містить 5 дощечок 5х1.

Стрічки:
Для кожної стрічки важливо знати 3 речі: довжина (та, що кратна 5), ширина (та, що менша 5), та з яких дощечок "починається" смужка - з повних 5х1, чи з порізаних. Наприклад на картинці ліва смужка починається з порізаних дощечок, а права - з повних.
Довжина та ширина знаходяться тривіально. А порізаність, чи не-порізаність першого блоку залежить від парності координат "округленого" кута (будь якого з двох), та від орієнтації смужки.
Вертикальні смужки починаються з порізаних дощечок, якщо координати кута мають різну парність. Горизонтальні - навпаки, якщо парність однакова.

Знаючи цю інформацію нескладно підрахувати дощечки в смужці. Нехай w - ширина смужки, а l - довжина в блоках (тобто довжина, поділена на 5).
Тоді якщо довжина парна - повних і порізаних блоків - однакова кількість. Інакше тих блоків, з якого почалася стрічка (порізаний, чи непорізаний) - на 1 більше.
Тобто повних дощечок 5х1 - (l + 1 - x)/2 * w, а порізаних дощечок w х 1 - (l + x)/2 * 5.
Де x = 1, якщо смужка починається з порізаних дощечок, або x = 0, якщо з цілих. Ділення мається на уваці цілочисельне (з округленням до цілих у напрямку до нуля).

І врешті решт, кути:
Для кутів достатньо знати розміри та напрямок дощечок. Розміри рахуютсья тривіально, напрямок - по аналогії з підрахунком "порізаності" першого блоку смужок.


Граничний випадок.

У випадку, коли увесь візерунок лежить всередині одного блоку вздовж будь-якої з координат - все поламається. Адже під час округлення у нас правий кут вийде лівішим за лівий, а верхній - нижчим за нижній. Наприклад, якщо лівий нижній куток візерунка лежав у координатах (7; 11), а правий верхній - у (9; 12), то після округлення виявиться, що у центральної частини координати лівого нижнього кута - (10; 15), а правого верхнього - (5; 10). Що, очевидно, нонсенс.

Щоб цього не сталося - у такому випадку ми просто "посунемо" увесь візерунок до границі блоку і переконаємось, що усі координати отримали адекватні значення (і розміри центральної частини стали нульовими, а не від'ємними).

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

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

#include <iostream>

using namespace std;

typedef unsigned long long ull;

void countStripe(ull width, ull length, bool startsCut, ull *res) {
    if (!width) return;

    auto cnt5 = length / 5;

    auto cntCut  = (cnt5 +  startsCut) / 2 * 5;
    auto cntFull = (cnt5 + !startsCut) / 2 * width;

    res[4] += cntFull;
    res[width - 1] += cntCut;
}

void countCorner(ull width, ull height, bool horizontal, ull *res) {
    if (!width || !height) return;

    if (horizontal) {
        res[width - 1] += height;
    } else {
        res[height - 1] += width;
    }
}

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

    ull xmin, xmax, ymin, ymax;
    ull res[5] = {0, 0, 0, 0, 0};

    cin >> xmin >> xmax >> ymin >> ymax;

    auto xminRound = (xmin + 4) / 5 * 5;
    auto yminRound = (ymin + 4) / 5 * 5;
    auto xmaxRound = xmax / 5 * 5;
    auto ymaxRound = ymax / 5 * 5;

    auto fixNarrow = [](ull &minRound, ull &maxRound, ull &min, ull &max){
        if (minRound > maxRound) {
            minRound = maxRound;
            max -= min - minRound;
            min = minRound;
        }
    };

    fixNarrow(xminRound, xmaxRound, xmin, xmax);
    fixNarrow(yminRound, ymaxRound, ymin, ymax);

    res[4] = (xmaxRound - xminRound) * (ymaxRound - yminRound) / 5;

    countStripe(xminRound - xmin, ymaxRound - yminRound,  (xminRound ^ yminRound) & 1, res);
    countStripe(yminRound - ymin, xmaxRound - xminRound, ~(xminRound ^ yminRound) & 1, res);
    countStripe(xmax - xmaxRound, ymaxRound - yminRound,  (xmaxRound ^ ymaxRound) & 1, res);
    countStripe(ymax - ymaxRound, xmaxRound - xminRound, ~(xmaxRound ^ ymaxRound) & 1, res);

    countCorner(xminRound - xmin, yminRound - ymin, ~(xminRound ^ yminRound) & 1, res);
    countCorner(xmax - xmaxRound, yminRound - ymin,  (xmaxRound ^ yminRound) & 1, res);
    countCorner(xmax - xmaxRound, ymax - ymaxRound, ~(xmaxRound ^ ymaxRound) & 1, res);
    countCorner(xminRound - xmin, ymax - ymaxRound,  (xminRound ^ ymaxRound) & 1, res);

    for (auto n : res) {
        cout << n << " ";
    }

    cout << endl;
}

Fixshow

Розглянемо функцію f(x, y), яка показує мінімальний час, через який будуть чутися всі звуки одночасно у точці з координатами (x; y):



Наша задача - знайти мінімум цієї функції.

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

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

Асимптотика.
Час: O(N), але формально там ще два логарифма: O(Log(D_X) * Log(D_Y) * N), де D_X і D_Y - різниця між максимальною та мінімальною X- та Y-координатами синтезаторів відповідно.
Пам'ять: O(N)

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

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

using namespace std;
using std::placeholders::_1;

double ternary_search(double l, double r, double eps, function<double (double)> f){
    while (r - l > eps) {
        auto m1 = l + (r - l) / 3;
        auto m2 = r - (r - l) / 3;

        auto r1 = f(m1);
        auto r2 = f(m2);

        if (r1 > r2) {
            l = m1;
        } else {
            r = m2;
        }
    }

    return (l + r) / 2;
}

struct Synth {
    double x;
    double y;
    double t;
};

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

    const double MIN_COORD = -1e6;
    const double MAX_COORD = 1e6;
    const double EPS = 1e-6;

    Synth s[555];
    int n;
    double c;

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

    cin >> c;

    auto getTime = [=](double x, double y) {
        double res = 0;

        for (int i = 0; i < n; ++i) {
            res = max(res, s[i].t + hypot(s[i].x - x, s[i].y - y) / c);
        }

        return res;
    };

    auto getY = [=](double x) {
        return ternary_search(MIN_COORD, MAX_COORD, EPS, bind(getTime, x, _1));
    };

    auto x = ternary_search(MIN_COORD, MAX_COORD, EPS, [=](double x) { return getTime(x, getY(x)); });
    auto y = getY(x);
    auto t = getTime(x, y);

    cout << fixed << setprecision(6) << x << ' ' << y << ' ' << t << endl;
}

Формули відрендерені за допомогою https://quicklatex.com/

Відредаговано Dim_ov (2021-01-01 03:06:25)

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

#include <cstdio>
#include <algorithm>

using std::scanf;
using std::printf;
using std::min;
using std::max;

int main()
{
    int c[6],t[6];
    int b=1000000000;
    for(int j=0;j<6;++j) scanf("%d",&(c[j]));
    for(int i=0;i<24;++i)
    {
        for(int j=0;j<6;++j) t[j]=c[((j+(i/8)*2)^((i>>(j/2))&1))%6];
        b=min(b,(t[0]+t[2]+t[4])*max(max(t[1],t[3]),t[5]));
        b=min(b,(max(t[0],t[2])+t[4])*max(t[1]+t[3],t[5]));
    }
    printf("%d",b);
    return 0;
}

Sum2020
Если и здесь использовать кумулятивную сумму, то от суммирования по 10 цифрам можно избавиться: в таблице хранится "количество i-значных числел с суммой цифр, не превышающей j".

#include <cstdio>

using std::scanf;
using std::printf;

unsigned t[2][10000];

int main()
{
    const unsigned M=1000000007u;
    int n,s;
    unsigned *p,*c;
    scanf("%d%d",&n,&s);
    for(int i=0;i<=n;++i)
    {
        p=t[i&1]+10;
        c=t[(i+1)&1]+10;
        c[0]=1;
        for(int j=1;j<=s;++j)
            c[j]=(c[j-1]+p[j]-p[j-10]+M)%M;
    }
    printf("%d",((c[s]-c[s-1])-(p[s]-p[s-1])+2*M)%M);
    return 0;
}

Parket0

#include <cstdio>
#include <algorithm>

using std::scanf;
using std::min;
using std::max;

int main()
{
    long long xmin,ymin,xmax,ymax;
    long long ret[5]={0,0,0,0,0};
    scanf("%lld%lld%lld%lld",&xmin,&xmax,&ymin,&ymax);
    long long X0=xmin/5,Y0=ymin/5,X1=(xmax-1)/5,Y1=(ymax-1)/5;
    for(long long X=X0,dX=1;X<=X1;X+=dX)
    {
        dX=((X>X0&&X<X1)?X1-X0-1:1);
        for(long long Y=Y0,dY=1;Y<=Y1;Y+=dY)
        {
            dY=((Y>Y0&&Y<Y1)?Y1-Y0-1:1);
            long long D=dX*dY,P=(X^Y)&1;
            long long D1=(D+P)/2,D0=D-D1;
            long long x0=max(xmin-5*X,0LL),y0=max(ymin-5*Y,0LL),x1=min(xmax-5*X,5LL),y1=min(ymax-5*Y,5LL);
            int d0=(y1-y0),d1=(x1-x0);
            ret[d0-1]+=D1*d1;
            ret[d1-1]+=D0*d0;
        }
    }
    printf("%lld %lld %lld %lld %lld",ret[0],ret[1],ret[2],ret[3],ret[4]);
    return 0;
}