A. Transformacja z A do B
limit czasowy dla jednego testu: 1 sekunda
limit pamięci dla jednego testu: 256 megabajtów
wejście: standardowe wejście
wyjście: standardpwe wyjście
limit czasowy dla jednego testu: 1 sekunda
limit pamięci dla jednego testu: 256 megabajtów
wejście: standardowe wejście
wyjście: standardpwe wyjście
Wasilij ma liczbę $latex \displaystyle \mathbf{\mathit{a}} $, którą chce zmienić w liczbę $latex \displaystyle \mathbf{\mathit{b}} $. W tym celu może wykonać dwa rodzaje operacji:
- pomnożyć bieżącą liczbę przez $latex \displaystyle \mathbf{\mathit{2}} $ (to znaczy zastąp liczbę $latex \displaystyle \mathbf{\mathit{x}} $ przez $latex \displaystyle 2\cdot x $);
- dołącz cyfrę 1 z prawej strony bieżącego numeru (to znaczy zamień liczbę $latex \displaystyle \mathbf{\mathit{x}} $ na $latex \displaystyle 10\cdot x+1 $).
Musisz pomóc Vasily’emu w przekształceniu liczby a w liczbę b przy użyciu wyłącznie operacji opisanych powyżej lub przekonać się, że jest to niemożliwe.
Pamiętaj, że w tym zadaniu nie musisz minimalizować liczby operacji. Wystarczy znaleźć sposób na przekształcenie $latex \displaystyle \mathbf{\mathit{a}} $ w $latex \displaystyle \mathbf{\mathit{b}} $.
Wejście
Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $latex \displaystyle \mathbf{\mathit{a}} $ i $latex \displaystyle \mathbf{\mathit{b}} $ gdzie $latex \displaystyle (1\leqslant a \textless b \leqslant 10^{9}) $ – liczbę, którą ma Wasilij i liczbę, którą chce mieć.
Wyjście
Jeśli nie ma sposobu na uzyskanie $latex \displaystyle \mathbf{\mathit{b}} $ z $latex \displaystyle \mathbf{\mathit{a}} $, wypisz „NO” (bez cudzysłowów).
W przeciwnym razie wypisz trzy linie. W pierwszym wierszu wydrukuj „YES” (bez cudzysłowów). Drugi wiersz powinien zawierać jedną liczbę całkowitą $latex \displaystyle\mathbf{\mathit{k}} $ – długość sekwencji transformacji. W trzecim wierszu wydrukuj sekwencję przekształceń $latex \displaystyle x_{1},x_{2},…x_{k} $, gdzie:
- $latex \displaystyle x_{1} $ powinno być równe $latex \displaystyle \mathbf{\mathit{a}} $,
- $latex \displaystyle x_{k} $ powinno być równe $latex \displaystyle \mathbf{\mathit{b}} $,
- $latex \displaystyle x_{i} $ należy uzyskać z $latex \displaystyle x_{i-1} $ przy użyciu dowolnej z dwóch opisanych operacji $latex \displaystyle (1 \textless i\leqslant k) $.
Jeśli istnieje wiele odpowiedzi, wypisz dowolną z nich.
Przykład:
Wejście:
2 162
YES 5 2 4 8 81 162
Wejście:
4 42
NO
Wejście:
100 40021
Wyjście:
YES 5 100 200 2001 4002 40021
Kod źródłowy w C++:
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> operation; bool solve(long long int a, long long int b) { if(a > b) { return false; } if(a == b) { return true; } if(solve(a*2,b)){ operation.push_back(a*2); return true; } if(solve(a*10+1,b)) { operation.push_back(a*10+1); return true; } return false; } int main() { long long int a, b; cin>>a>>b; if(solve(a,b)){ operation.push_back(a); cout<<"YES"<<endl; cout<<operation.size()<<endl; reverse(operation.begin(),operation.end()); for(int i=0; i<operation.size(); ++i) { cout<<operation[i]<<endl; } } else { cout<<"NO"<<endl; } return 0; }
Źródło:
https://codeforces.com/contest/727/problem/A