Elearning CodePath – CTP Online Judge

Transformation: from A to B

GEN039

🟢 Hard #BFS/DFS

---

### 📝 Bài toán
Vasily có một số a, và anh ấy muốn biến nó thành số b. Để làm điều này, anh ấy có thể thực hiện hai loại phép toán sau:

1. Nhân số hiện tại với 2 (tức là thay số x bằng 2·x).
2. Gắn chữ số 1 vào bên phải của số hiện tại (tức là thay số x bằng 10·x + 1).

Nhiệm vụ của bạn là giúp Vasily biến đổi số a thành số b chỉ bằng các phép toán trên, hoặc xác định rằng việc này là không thể.

⚠️ **Lưu ý:** Trong bài này không cần tối ưu số bước biến đổi. Chỉ cần tìm bất kỳ cách nào hợp lệ để biến a thành b là đủ.

---

### 📥 Định dạng Đầu vào
* Dòng duy nhất chứa hai số nguyên dương a và b (1 ≤ a < b ≤ 10⁹) — lần lượt là số ban đầu và số cần đạt tới.

**Giới hạn:**
* 1 ≤ a < b ≤ 10⁹

---

### 📤 Định dạng Đầu ra
* Nếu không có cách nào để biến a thành b, in ra: NO
* * Nếu có cách, in ra:
  1. Dòng 1: `YES`
  2. Dòng 2: số nguyên k — độ dài của dãy biến đổi
  3. Dòng 3: dãy số x₁, x₂, ..., xₖ, trong đó:
     * x₁ = a
     * xₖ = b
     * Mỗi xᵢ (với i > 1) được tạo từ xᵢ₋₁ bằng một trong hai phép toán đã cho

Nếu có nhiều lời giải, in ra bất kỳ lời giải nào.

---

### ✨ Ví dụ

**Ví dụ 1:**
| Input | Output |
| :---: | :---: |
| `2 162` | `YES`<br>`5`<br>`2 4 8 81 162` |

**Giải thích Ví dụ 1:**
* 2 → 4 (nhân 2)
* 4 → 8 (nhân 2)
* 8 → 81 (gắn chữ số 1: 8×10+1 = 81)
* 81 → 162 (nhân 2)

---

**Ví dụ 2:**
| Input | Output |
| :---: | :---: |
| `4 42` | `NO` |

**Giải thích Ví dụ 2:**
Không có cách nào biến đổi 4 thành 42 bằng các phép toán cho phép.

---

**Ví dụ 3:**
| Input | Output |
| :---: | :---: |
| `100 40021` | `YES`<br>`5`<br>`100 200 2001 4002 40021` |

**Giải thích Ví dụ 3:**
* 100 → 200 (nhân 2)
* 200 → 2001 (gắn chữ số 1: 200×10+1 = 2001)
* 2001 → 4002 (nhân 2)
* 4002 → 40021 (gắn chữ số 1: 4002×10+1 = 40021)

---

### 🏷 Ràng buộc
| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | b ≤ 10⁶ | 40% |
| 2 | b ≤ 10⁹ | 60% |

✅ Đã AC: 2 / 7 submissions