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

Tác giả:

Dạng bài

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

An là một cậu bé yêu thích Số học. Mỗi khi rảnh, cậu ấy sẽ tự nghĩ ra cho mình những trò chơi thú vị với những con số. Chủ Nhật ngày hôm ấy, cậu đã nghĩ ra trò chơi như sau:

Đầu tiên ta sẽ có một số nguyên không âm \(A\), ta được thực hiện hai thao tác:

Gấp đôi giá trị của \(A\).
Viết thêm số \(1\) ở đằng sau số \(A\) (Số được biểu diễn ở dạng thập phân).

An sau đó là nghĩ ra rất nhiều số \(A\) khác nhau, với mỗi số lại biến đổi một cách khác nhau và viết các con số ấy lên các tờ giấy. Tuy nhiên, vì là một cậu bé đãng trí, An nhanh chóng quên mất mình đã biến đổi con số nào thành con số nào. Bạn hãy trả lời giúp An nhé.

Input

Dòng đầu tiên chứa số nguyên \(Q\) \((1 \leq Q \leq 100)\) là số lượng câu hỏi.
Trong \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\) \((1 \leq A, B \leq 10^{9})\).

Output

In ra \(Q\) dòng, in ra YES nếu từ \(A\) có thể tạo ra \(B\) bằng không, một hay nhiều thao tác nêu trên hoặc NO nếu ngược lại.

Example

Test 1

Input

2
2 162
4 42

Output

YES
NO

Note

Trong câu hỏi đầu tiên, An sẽ thực hiện các thao tác để biến đổi số \(2\) như sau: \(2 \rightarrow 4 \rightarrow 8\rightarrow 81 \rightarrow 162\).
Trong câu hỏi thứ hai, không có cách nào mà An có thể biến đổi được từ số \(4\) thành số \(42\) bằng các thao tác của mình.

Bình luận

Thưa admin 2 code sau, 1 code thì AC còn 1 code bị segmantation fault vậy ạ?

SPOILER ALERT

REFERENCE AC CODE

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

string dq(ll x, ll y)
{
    if (y < x) return "NO";
    if (y == x) return "YES";
    if (y%2 == 1 && y%10 != 1) return "NO";
    string h = "", m ="";
    if (y%10 == 1) m = dq(x,(y-1)/10);
    if (y%2 == 0) h = dq(x,y/2);
    if (h == "YES" | m == "YES") return "YES";
    return "NO";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {   
        ll a,b;
        cin >> a >> b;
        cout << dq(a,b) << '\n';
    }
}

SEGMANTATION FAULT CODE

#include<bits/stdc++.h>
#define ll long long
#define maxN 1000006
#define pb push_back
using namespace std;
vector<int> ans;

string dq(ll x, ll y)
{
    if (y < x) return "NO";
    if (y == x) return ans.pb(x) ,"YES";
    if (y%2 == 1 && y%10 != 1) return "NO";
    string h = "", m ="";
    if (y%10 == 1) m = dq(x,(y-1)/10);
    if (y%2 == 0) h = dq(x,y/2);
    if (h == "YES" | m == "YES") return ans.pb(y) ,"YES";
    return "NO";
}

int solve()
{
    ll a,b;
    cin >> a >> b;
    cout << dq(a,b) << '\n';
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}

1 phản hồi