Разбор задачи «Фонарики для тропы»

Идея задачи

Нам даны три числа:

• k — стоимость первого фонарика,
• n — количество монет, которое уже есть,
• w — количество фонариков, которые нужно купить.

По условию:

• первый фонарик стоит k,
• второй стоит 2 · k,
• третий стоит 3 · k,
• ...
• w-й стоит w · k.

Нужно определить, сколько монет не хватает. Если денег хватает, ответ должен быть 0.

Как посчитать общую стоимость

Если выписать стоимость всех фонариков, получится:

k + 2k + 3k + ... + wk

Вынесем k за скобку:

k · (1 + 2 + 3 + ... + w)

Теперь задача сводится к нахождению суммы чисел от 1 до w.

Это стандартная формула:

1 + 2 + 3 + ... + w = w · (w + 1) / 2

Тогда общая стоимость равна:

total = k · w · (w + 1) / 2

После этого остается сравнить эту сумму с количеством имеющихся монет n.

• Если total <= n, занимать ничего не нужно, ответ 0.
• Иначе ответ равен total - n.

Пример разбора

Пусть:

k = 3, n = 17, w = 4

Тогда стоимости фонариков такие:

• 1-й: 3
• 2-й: 6
• 3-й: 9
• 4-й: 12

Общая стоимость:

3 + 6 + 9 + 12 = 30

Уже есть 17 монет.

Значит, не хватает:

30 - 17 = 13

Ответ: 13.

Почему решение именно такое

В этой задаче можно было бы использовать цикл и по очереди прибавлять стоимость каждого фонарика:

• прибавить k,
• прибавить 2k,
• прибавить 3k,
• и так далее.

Такое решение тоже было бы правильным.

Но здесь есть более короткий и аккуратный путь: использовать формулу суммы первых w натуральных чисел.

Это дает сразу несколько плюсов:

• код получается проще,
• решение работает очень быстро,
• меньше шансов ошибиться в цикле.

Пошаговый алгоритм

1. Считать k, n, w.
2. Вычислить общую стоимость: total = k * w * (w + 1) / 2.
3. Найти, сколько не хватает: need = total - n.
4. Если need < 0, вывести 0.
5. Иначе вывести need.

Оценка сложности

Так как мы используем только несколько арифметических операций, сложность решения:

• по времени: O(1)
• по памяти: O(1)

Это означает, что программа работает за константное время и использует константное количество памяти.

Важное замечание про типы данных

Даже если числа в задаче маленькие, в C++ лучше использовать тип long long.

Почему?

Потому что в формуле есть умножение:

k * w * (w + 1)

Если значения достаточно большие, тип int может переполниться. long long делает решение более надежным.

Реализация на C++

#include <iostream>
using namespace std;

int main() {
    long long k, n, w;
    cin >> k >> n >> w;

    long long total = k * w * (w + 1) / 2;
    long long need = total - n;

    if (need < 0) {
        need = 0;
    }

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

Реализация на Python

k, n, w = map(int, input().split())

total = k * w * (w + 1) // 2
need = total - n

if need < 0:
    need = 0

print(need)

Частые ошибки

1. Забывают вывести 0, если денег хватает

Некоторые пишут просто:

print(total - n)

Но если денег хватает, получится отрицательное число, а по условию нужно вывести 0.

2. Считают сумму через цикл, но ошибаются в границах

Например, берут не все числа от 1 до w, а только до w - 1.

Использование формулы помогает избежать этой ошибки.

3. Используют обычное деление вместо целочисленного

В Python нужно писать именно:

// 2

а не / 2, иначе получится число с плавающей точкой.

4. В C++ используют int и получают переполнение

Лучше сразу писать long long для всех вычислений.

Ключевая мысль здесь такая:

стоимость всех покупок — это арифметическая прогрессия, а значит, ее удобно считать по формуле.

После этого остается только вычесть уже имеющееся количество монет и не забыть, что ответ не может быть отрицательным.