Hướng dẫn cho TRANSFORM (OLP MT&TN 2023 Sơ Loại Không Chuyên)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: ldn694 , BJMinhNhut

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;
}

Bình luận

Không có bình luận nào.