Nasser's Five#12478

Nasser's Five (Editorial)

Problem Author:	Mohammad Nasser (MOAGEZA)
Prepared by:	Mohammad Nasser (MOAGEZA)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea: We need to append the digit $5$ to $x$ until $x > y$ x > y.

Each time we append $5$ to a number with $d$ digits, the new number becomes:

new_x = old_x \times 10 + 5

\text{new\_x} = \text{old\_x} \times 10 + 5

We simply simulate this process: keep appending $5$ and count the operations until $x > y$ x > y.

Since each operation multiplies $x$ by $10$ and adds $5$ , the number grows exponentially. After $k$ operations:

x_{k} = x_{0} \times 1 0^{k} + 5 \times \frac{1 0 ^{k} - 1}{9}

x_k = x_0 \times 10^k + 5 \times \frac{10^k - 1}{9}

However, for the given constraints, simulation is sufficient because the answer is always small (at most $lo g_{10} (y)$ \log_{10}(y) operations).

The solution runs in $O (d)$ time per test case, where $d = ⌊ lo g_{10} y ⌋ + 1$ d = \lfloor \log_{10} y \rfloor + 1 is the number of digits in $y$ .

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

void solve() {
    long long x, y;
    cin >> x >> y;
    
    int cnt = 0;
    while (x <= y) {
        x = x * 10 + 5;
        cnt++;
    }
    
    cout << cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}