Biến đổi từ A sang B

Đề bài

Mô tả

Cho hai số nguyên dương ab. Bạn muốn biến số a thành số b 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 x:

  • Nhân đôi: thay x bởi 2·x.
  • Ghép chữ số 1 vào bên phải: thay x bởi 10·x+1.

Hãy tìm một dãy biến đổi bất kỳ đưa a về b, 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 ab.

Dữ liệu ra

Nếu không thể biến a thành b, 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 k là độ dài dãy biến đổi (số phần tử của dãy).
  • Dòng thứ ba in dãy x1,x2,,xk trong đó x1=a, xk=b, và mỗi xi (1<ik) thu được từ xi1 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

  • 1a<b109

Ví dụ

Input Output Giải thích
2 162 YES
5
2 4 8 81 162
24881162: 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0