Editorial for TRANSFORM (OLP MT&TN 2023 Sơ Loại Không Chuyên)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Tutorial

Ta có quan sát: Khi thực hiện thao tác loại \(1\) - nhân đôi, thì \(B\) trở thành một số chẵn. Còn khi thực hiện thao tác loại \(2\) - nhân \(10\) cộng \(1\), thì \(B\) trở thành một số có chữ số hàng đơn vị là 1.

Như vậy, tại một giá trị bất kì của \(B\), ta có các trường hợp sau:

Nếu \(B\) là số chẵn, thì chắc chắn thao tác gần nhất sẽ là thao tác loại \(1\).
Ngược lại, nếu số \(B\) là số lẻ, thì ta sẽ có hai trường hợp:
- Chữ số đơn vị là chữ số \(1\). Lúc này ta chắc chắn thao tác gần nhất sẽ là thao tác loại \(2\).
- Ngược lại ta biết rằng không thể thực hiện bất kỳ thao tác nào để tạo ra số hiện tại do các thao tác không thể tạo ra một số lẻ có chữ số hàng đơn vị khác 1.

Do đó, để kiểm tra liệu có thể tạo ra số \(B\) từ số \(A\) hay không, ta sẽ mô phỏng lại quy trình trên, nếu gặp số \(A\) thì in ra YES ngược lại in ra NO.

Độ phức tạp: \(\mathcal{O}(Q \times \log_{2}B)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

int numTest;
int a, b;

bool solve(int a, int b) {
    if (a == b) {
        return true;
    }
    if (a > b) {
        return false;
    }
    while ((b % 2 == 0 || b % 10 == 1) && a < b) {
        if (b % 2 == 0) {
            b /= 2;
        } else {
            b /= 10;
        }
        if (a == b) {
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> numTest;

    while (numTest--) {
        cin >> a >> b;
        cout << (solve(a, b) ? "YES\n" : "NO\n");
    }

    return 0;
}

Comments

There are no comments at the moment.