Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <climits>
- #include <cmath>
- using namespace std;
- int main(int argc, char const *argv[])
- {
- int size = 10*10*10*10*10*10 + 1;
- int binarios[] = {1,10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111,10000,10001,10010,10011,10100,10101,10110,10111,11000,11001,11010,11011,11100,11101,11110,11111,100000,100001,100010,100011,100100,100101,100110,100111,101000,101001,101010,101011,101100,101101,101110,101111,110000,110001,110010,110011,110100,110101,110110,110111,111000,111001,111010,111011,111100,111101,111110,111111,1000000};
- vector<int> optimos(size + 1, INT_MAX);
- optimos[1] = 1;
- int size_binarios = 65;
- for(int i = 0; i < binarios.size(); i++){
- int binario = binarios[i];
- for(int j = binario ; j + binario < size; j++){
- optimos[binario + j] = min(optimos[binario+j], 1 + optimos[j]);
- }
- }
- int n; cin >> n;
- string res = "";
- int pasos_original = optimos[n];
- while(n > 0){
- int pasos = optimos[n];
- for(int i = 0; binarios[i] < n; i++){
- int binario = binarios[i];
- if(optimos[n - binario] == pasos - 1){
- n = n - binario;
- res += to_string(binario) + " ";
- }
- }
- }
- cout << pasos_original << endl;
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement