Soldier and Bananas

Soldier and Bananas
Codeforces easy

A soldier wants to buy \(w\) bananas. The first banana costs \(k\) dollars, the second costs \(2k\) dollars, and in general the \(i\)-th banana costs \(i \cdot k\) dollars.

The soldier has \(n\) dollars. How many dollars does he need to borrow from a friend to buy all \(w\) bananas?

Constraints:

  • \(1 \le k, w \le 1000\)
  • \(0 \le n \le 10^9\)

Input:

  • One line: three integers \(k\), \(n\), \(w\).

Output:

  • One integer — the number of dollars to borrow, or \(0\) if he does not need to borrow.

Example:

Input:

3 17 4

Output:

13
Solution

We simulate the purchase: for each banana \(i\) from \(1\) to \(w\), we add its price \(i \cdot k\) to the total cost.

If the total cost is larger than \(n\), the soldier borrows the difference; otherwise he borrows \(0\).

For the example: \(3 + 6 + 9 + 12 = 30\) dollars, and \(30 - 17 = 13\).

The largest total cost is \(1000 \cdot (1 + 2 + \ldots + 1000) = 500500000\), which fits in int.

#include <iostream>
using namespace std;

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

    int cost = 0;
    for (int i = 1; i <= w; i++) {
        cost += i * k;  // the i-th banana costs i * k dollars
    }

    if (cost > n) {
        cout << cost - n << "\n";
    } else {
        cout << 0 << "\n";
    }
}