П'ятірка Насера#12478

П'ятірка Насера (Розбір)

Автор задачі:	Mohammad Nasser (MOAGEZA)
Підготував:	Mohammad Nasser (MOAGEZA)
Відредагував:	Hasan Saleh (MathModel)

Розв'язок

Загальна ідея: Нам потрібно дописувати цифру $5$ до $x$ доти, поки $x > y$ x > y.

Щоразу, коли ми дописуємо $5$ до числа з $d$ цифрами, нове число стає:

new_x = old_x \times 10 + 5

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

Ми просто симулюємо цей процес: продовжуємо дописувати $5$ і рахуємо операції, поки $x > y$ x > y.

Оскільки кожна операція множить $x$ на $10$ і додає $5$ , число зростає експоненційно. Після $k$ операцій:

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}

Однак для заданих обмежень симуляція є достатньою, оскільки відповідь завжди мала (щонайбільше $lo g_{10} (y)$ \log_{10}(y) операцій).

Розв'язок працює за час $O (d)$ на один тест, де $d = ⌊ lo g_{10} y ⌋ + 1$ d = \lfloor \log_{10} y \rfloor + 1 — кількість цифр у $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;
}