Biến đổi từ A sang B
Đề bài
Mô tả
Cho hai số nguyên dương và . Bạn muốn biến số thành số bằng cách áp dụng liên tiếp một trong hai phép biến đổi sau lên số hiện tại :
- Nhân đôi: thay bởi .
- Ghép chữ số 1 vào bên phải: thay bởi .
Hãy tìm một dãy biến đổi bất kỳ đưa về , hoặc chỉ ra rằng điều đó là không thể. Không yêu cầu số phép biến đổi nhỏ nhất.
Dữ liệu vào
Một dòng chứa hai số nguyên và .
Dữ liệu ra
Nếu không thể biến thành , in ra NO.
Ngược lại, in ra ba dòng:
- Dòng đầu in YES.
- Dòng thứ hai in số nguyên là độ dài dãy biến đổi (số phần tử của dãy).
- Dòng thứ ba in dãy trong đó , , và mỗi () thu được từ bằng một trong hai phép biến đổi trên.
Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 162 | YES 5 2 4 8 81 162 |
: nhân đôi ba lần, ghép 1, rồi nhân đôi. |
| 4 42 | NO | Không có dãy phép biến đổi nào đưa 4 về 42. |
| 100 40021 | YES 5 100 200 2001 4002 40021 |
Nhân đôi, ghép 1, nhân đôi, ghép 1. |
Bình luận