Решения — уровень 3: находим закономерность и строим модель#

9. Фонарики на фестивале#

Строим модель#

Число фонариков в последнем ряду равно A + (N - 1) * D: от первого до последнего ряда ровно N - 1 переходов, каждый добавляет D фонариков.

Получаем арифметическую последовательность от первого ряда A до последнего ряда last. Сумма равна числу рядов, умноженному на среднее первого и последнего:

sum = N * (A + last) / 2.

Чтобы не потерять точность целочисленного деления, сначала делим на 2 тот множитель, который гарантированно чётный: если N чётно — делим N, иначе A + last чётно.

Проверка#

Ряды содержат 3, 5, 7 и 9 фонариков. Сумма: 3 + 5 + 7 + 9 = 24.

C++#

#include <iostream>
using namespace std;

int main() {
    long long n, first, difference;
    cin >> n >> first >> difference;

    long long last = first + (n - 1) * difference;
    long long total;

    if (n % 2 == 0) {
        total = (n / 2) * (first + last);
    } else {
        total = n * ((first + last) / 2);
    }

    cout << total << '\n';
    return 0;
}

10. Панели для выставки#

Строим модель#

Сначала убираем поля по краям: полезная ширина равна W - 2M, полезная высота — H - 2M.

Рассмотрим одно направление. Чтобы поставить k панелей шириной P, нужно место для панелей и промежутков между ними:

k * P + (k - 1) * G ≤ available.

Перегруппируем:

k * (P + G) ≤ available + G.

Значит, максимальное число панелей в этом направлении — целая часть (available + G) / (P + G). Если доступное место меньше размера одной панели, в этом направлении помещается 0.

Вычисляем число панелей по ширине и высоте и перемножаем. Поворот запрещён, поэтому размеры панели не меняем местами.

Проверка#

После полей остаётся 90 × 60 см. По ширине помещается (90 + 5) / (20 + 5) = 3 панели, по высоте — (60 + 5) / (15 + 5) = 3. Всего 3 * 3 = 9.

C++#

#include <iostream>
using namespace std;

long long fit(long long available, long long panel, long long gap) {
    if (available < panel) {
        return 0;
    }
    return (available + gap) / (panel + gap);
}

int main() {
    long long w, h, margin, panelW, panelH, gap;
    cin >> w >> h >> margin >> panelW >> panelH >> gap;

    long long insideW = w - 2 * margin;
    long long insideH = h - 2 * margin;

    long long columns = fit(insideW, panelW, gap);
    long long rows = fit(insideH, panelH, gap);

    cout << columns * rows << '\n';
    return 0;
}

11. Огород у стены#

Строим модель#

Для выбранной ширины x две стороны забора используют 2x метров. Оставшиеся метры можно отдать третьей стороне: y = L - 2x. Поскольку площадь при фиксированном x растёт вместе с y, выгодно использовать весь доступный остаток.

Тогда площадь:

area = x * (L - 2x).

Раскроем зависимость или посмотрим на параболу: это выражение достигает максимума около x = L / 4. Но x должен быть целым, поэтому достаточно проверить целые значения по обе стороны от L / 4: floor(L / 4) и floor(L / 4) + 1. Также проверяем, что x ≥ 1 и для стороны вдоль стены остаётся хотя бы 1 метр (2x < L).

Проверка#

При L = 10 можно взять x = 2, y = 6, площадь 12; либо x = 3, y = 4, тоже площадь 12. Большей площади получить нельзя.

C++#

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

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

    long long candidate = max(1LL, fence / 4);
    long long bestArea = 0;

    for (long long x = candidate; x <= candidate + 1; ++x) {
        if (2 * x < fence) {
            long long y = fence - 2 * x;
            bestArea = max(bestArea, x * y);
        }
    }

    cout << bestArea << '\n';
    return 0;
}

12. Сложенный лист#

Строим модель#

Каждый сгиб удваивает толщину. После одного сгиба она равна 2T, после двух — 4T, после трёх — 8T. После k сгибов толщина будет T * 2^k.

Нужно найти минимальное k, для которого толщина стала не меньше H. Удобно начать с исходной толщины и выполнять сгибы, пока порог не достигнут. Каждый сгиб увеличивает счётчик на 1.

При заданных ограничениях даже удвоение значения, меньшего H, остаётся не больше 2H, а H ≤ 10^18, поэтому тип long long безопасен.

Проверка#

3 → 6 → 12 → 24 → 48. Порог 40 достигнут после четырёх сгибов.

C++#

#include <iostream>
using namespace std;

int main() {
    long long thickness, target;
    cin >> thickness >> target;

    int folds = 0;
    while (thickness < target) {
        thickness *= 2;
        ++folds;
    }

    cout << folds << '\n';
    return 0;
}

Что важно заметить#

В задачах этого уровня формула не всегда сразу дана словами. Её можно получить через несколько примеров, закономерность, ограничение на число объектов или перебор небольшой окрестности математического максимума. Сначала обоснуй, почему модель верна, и только потом переноси её в код.