2017.07.01 P8 Mr.W 数
题目描述
王老师闲来无事,创造了一种数叫做 Mr.W 数。当 a 能通过某种特定的变换方式变成 b,则将 b 称作 a 的 Mr.W 数。你可以进行两种操作:
1、 将当前的数的二进制最右边加一个 0(将 x 变为 2x)
2、 在当前的数的十进制最右边加一个 1(将 x 变为 10x + 1)
王老师发明了 Mr.W 数之后突然想研究一个问题,他给出了两个数 a 和 b,如果 b 是 a 的 Mr.W 数,他想知道将 a 通过这两种操作变为 b 并输出最小的操作次数与中间过程的操作序列,或者说 b 不是 a 的 Mr.W 数。
王老师很想快一些知道这个问题的答案,但由于他自己太强,不屑于解决这个问题,所以找到了你。
输入格式
输入数据共一行两个正整数 a,b。
输出格式
如果 b 不是 a 的 Mr.W 数,输出“NO”(不含引号)。
否则输出三行,第一行输出“YES”(不含引号)。
第二行有一个整数 k—最小的操作序列长度。
第三行输出操作序列 x1, x2, x3 … xk。x1 = a, xk = b。xi 由 xi - 1通过上述两种操作变化而来。
样例输入
2 162
样例输出
YES
5
2 4 8 81 162
数据范围
对于30%的数据 1 <= a < b <= 1e3
对于80%的数据 1 <= a < b <= 1e9
对于100%的数据1 <= a < b < 1e18
限制
1s
样例解释
输出数据即样例解释。
来源
CWOI水题欢乐赛