Vasily has a number a, which he wants to turn into a number b. For this purpose, he can do two types of operations:
- multiply the current number by 2 (that is, replace the number x by 2·x);
- append the digit 1 to the right of current number (that is, replace the number x by 10·x + 1).
You need to help Vasily to transform the number a into the number b using only the operations described above, or find that it is impossible.
Note that in this task you are not required to minimize the number of operations. It suffices to find any way to transform a into b.
InputThe first line contains two positive integers a and b (1 ≤ a < b ≤ 109) — the number which Vasily has and the number he wants to have.
OutputIf there is no way to get b from a, print "NO" (without quotes).
Otherwise print three lines. On the first line print "YES" (without quotes). The second line should contain single integer k — the length of the transformation sequence. On the third line print the sequence of transformations x1, x2, ..., xk, where:
- x1 should be equal to a,
- xk should be equal to b,
- xi should be obtained from xi - 1 using any of two described operations (1 < i ≤ k).
If there are multiple answers, print any of them.
Examples input2 162output
YESinput
5
2 4 8 81 162
4 42output
NOinput
100 40021output
YES
5
100 200 2001 4002 40021
题解：此题求的是a变成b的路径，每次数字变化只通过两种操作完成。正常解法，用dfs广度优先搜索，用一个数组来记录路径。我一开始vector容器来装路径，过程很烦，结果还MLE了，
下面，我给出一个ac的代码，一个用vector容器装路径的MLE代码
ac的代码：
#include <iostream>
#include <cstdio>
#define maxn 10000005
using namespace std;
int a, b;
int res;//记录的是总个数
int flag;//记录的是yes和no的状态
int vis[maxn];
int t;
int ans;
void dfs(int x, int t) {
if (x == b) {
flag = 1;
res = t;
return;
}
if (x > b) {
return;
}
vis[t] = 10 * x + 1;
if (x <= 1e8) {
dfs(x * 10 + 1, t + 1);
}
if (flag) {
return;
}
vis[t] = 2 * x;
dfs(x * 2, t + 1);
}
int main() {
//cin >> a >> b;
scanf("%d%d", &a, &b);
t = 0, vis[0] = a;
dfs(a, 1);
if (flag == 1) {
cout << "YES" << endl;
printf("%d\n", res);
for (int i = 0; i < res; i++) {
//cout << vis[i] << " ";
printf("%d ", vis[i]);
}
cout << endl;
}
else {
cout << "NO" << endl;
}
return 0;
}
用vector结果MLE的代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a,b;
vector<int> vec;
vector<int> answer;
void dfs(){
if(a>=b){
return ;
}
for(int i=0;i<2;i++){
if(i==0){
if(a<b){
a=a*2;
vec.push_back(a);
dfs();
a=a/2;
}
}
else if(i==1){
if(a<b){
a=a*10+1;
vec.push_back(a);
dfs();
a=(a-1)/10;
}
}
}
}
int main(){
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
if(b<=a||a==0||b==0){
cout<<"NO"<<endl;
return 0;
}
dfs();
vector<int>::iterator iter,it;
if((iter=find(vec.begin(),vec.end(),b))!=vec.end()){
cout<<"YES"<<endl;
answer.push_back(b);
for(it=iter;it!=vec.begin()-1;it--){
if(*it==b/2||*it==(b-1)/10){
answer.push_back(*it);
if(*it==b/2){
b=b/2;
}
else{
b=(b-1)/10;
}
}
}
cout<<answer.size()+1<<endl;
cout<<a;
for(int i=answer.size()-1;i>=0;i--){
cout<<" "<<answer[i];
}
cout<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}
其实这题还有一个更为简单的做法，仔细观察随便一个样例的路径，会发现，路径中出现的数要么是奇数要么是偶数，奇数必定是经过操作一而来，而偶数必定是通过操作二而得
所以我们可以通过b一直往前推，直到推到a，用vector来存放每次往前推所出现的路径上的值
ac代码：
#include <iostream>
#include <cstdio>
#include <vector>
#define namesapce namespace
using namesapce std;
vector<int> vec;
bool is_true(int a,int b){
while(b>a){
if(b%2==0){
b=b/2;
vec.push_back(b);
}
else if((b-1)%10==0){
b=(b-1)/10;
vec.push_back(b);
}
else{
return false;
}
}
if(b==a){
return true;
}
return false;
}
int main(){
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int a,b;
cin>>a>>b;
if(is_true(a,b)){
cout<<"YES"<<endl;
cout<<vec.size()+1<<endl;
for(int i=vec.size()-1;i>=0;i--){
cout<<vec[i]<<" ";
}
cout<<b<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}
这题就做完了，至于为什么用vector会MLE的情况，我想与vector每次两倍扩容有关