Bài A - Technocup 2017 - Elimination Round 1 (Div.2)

Bài A:
Đề bài: Vasily có một số a, anh ấy muốn chuyển sang số b. Vì mục đích này, anh ấy có thể hai loại phép biến đổi sau:
+ Nhân số hiện tại với 2 (có nghĩa là, thay số x bởi 2.x)
+ Thêm chữ số 1 vào bên phải của số hiện tại (có nghĩa là, thay số x bởi 10x+1).
Bạn cần giúp Vasily chuyển từ số a sang số b chỉ sử dụng các phép biến đổi trên, hoặc phát hiện rằng chúng không thể.
Chú ý rằng, trong nhiệm vụ này không yêu cầu tối thiểu số phép biến đổi. Nó chỉ cần tìm cách nào đó để chuyển từ số a sang số b.
Đầu vào:
+ Dòng đầu tiên chứa hai số nguyên a và b (1<=a<b<=10^9) - số mà Vasily có và số mà anh ấy muốn có.
Đầu ra:
+ Nếu không có cách nào để lấy được b từ a, ta in ra NO
+ Ngược lại in ra ba dòng: dòng đầu tiên in YES, dòng thứ hai chứa số nguyên k - là chiều dài của chuỗi biến đổi. Dòng thứ 3 in ra chuỗi biến đổi x(1),x(2),...,x(k), trong đó:
- x(1) phải bằng a
- x(k) phải bằng b
- x(i) đạt được từ x(i-1) sử dụng bất kì một trong 2 phép biến đổi trên (1<i<=k).
Nếu có nhiều đáp án, in ra đáp án bất kỳ.
Ví dụ:
Đầu vào:
2 162
Đầu ra:
Yes
5
2 4 8 81 162
/**/
Đầu vào:
4 42
Đầu ra:
No.
/**/
Đầu vào:
100 40021
Đầu ra:
Yes
5
100 200 2001 4002 40021
Hướng dẫn:
Chúng ta sẽ giải quyết bài toán bằng cách đảo ngược - tức là thu giá trị A từ B.
Chú ý rằng, nếu B kết thúc là 1 thì thao tác cuối cùng là nỗi chữ số 1 ở bên phải số hiện tại. Do đó, hãy xóa số cuối cùng của B và chuyển sang số mới.
Nếu chữ số cuối cùng là chẵn thì thao tác cuối cùng là nhân 2 với số hiện tại. Vì vậy ta chia B cho 2 và chuyển sang số mới.
Trường hợp khác (Nếu B kết thúc với tận cùng là số lẻ khác 1) thì kết quả là NO.
Chúng ta cần lặp lại thuật toán được mô tả sau khi chúng ta có được số mới. Nếu ở bước nào đó số đó bằng A thì ta tìm được kết quả, và nếu nhỏ hơn A thì ta in ra NO.
Lời giải:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld EPS = 1e-7;

int run() {
    int a, b;
    cin >> a >> b;
    vector<int> ops;
    ops.push_back(b);
    
    while (b > a) {
        if (b % 2 == 0) {
            b /= 2;
            ops.push_back(b);
        } else if (b % 10 == 1) {
            b /= 10;
            ops.push_back(b);
        } else {
            break;
        }
    }
    
    if (a == b) {
        cout << "YES\n";
        reverse(ops.begin(), ops.end());
        cout << (int) ops.size() << "\n";
        for (int it : ops) {
            cout << it << " ";
        }
        cout << "\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

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

    return run();
}