Advertisement
Guest User

Untitled

a guest
Apr 26th, 2015
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. int main(int argc, char const *argv[])
  9. {
  10. int size = 10*10*10*10*10*10 + 1;
  11. 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};
  12. vector<int> optimos(size + 1, INT_MAX);
  13. optimos[1] = 1;
  14. int size_binarios = 65;
  15. for(int i = 0; i < binarios.size(); i++){
  16. int binario = binarios[i];
  17. for(int j = binario ; j + binario < size; j++){
  18. optimos[binario + j] = min(optimos[binario+j], 1 + optimos[j]);
  19. }
  20. }
  21.  
  22. int n; cin >> n;
  23. string res = "";
  24. int pasos_original = optimos[n];
  25. while(n > 0){
  26. int pasos = optimos[n];
  27. for(int i = 0; binarios[i] < n; i++){
  28. int binario = binarios[i];
  29. if(optimos[n - binario] == pasos - 1){
  30. n = n - binario;
  31. res += to_string(binario) + " ";
  32. }
  33. }
  34. }
  35. cout << pasos_original << endl;
  36. cout << res << endl;
  37. return 0;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement