Investments (Editorial)

Solution Explanation

Sashko starts with an initial balance of $100$ hryvnias. Each year the bank adds $1\%$ interest, but the fractional part of the new balance is discarded. In other words, after each year the balance becomes:

We are given a target value $X$, and we must determine the minimum number of years needed for the balance to reach at least $X$.

Key Observation

The value increases slowly because each year the added amount is:

Since $B$ grows at most by $1\%$ per year, the number of years is on the order of a few thousand even for X = 10^9.

The process can be simulated year by year because:

• At most a few thousand iterations are needed.

• Each iteration is constant time.

Thus a direct loop is efficient.

Algorithm

• Read $X$.

• Set B = 100 and years = 0.

• While B < X:

  • Compute inc = \left\lfloor B/100 \right\rfloor.

  • Update B := B + inc.

  • Increment $years$.

• Output $years$.

Complexity

The loop runs approximately $1700$ iterations for the largest input, so the time complexity is:

and memory usage is constant.

Reference Implementation

#include <bits/stdc++.h>
using namespace std;

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

    long long X;
    cin >> X;

    long long B = 100;
    long long years = 0;

    while (B < X) {
        long long inc = B / 100;  // integer division, drop fractions
        B += inc;
        years++;
    }

    cout << years << "\n";
    return 0;
}