fork(4) download
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <climits>
  5.  
  6. int main() {
  7. int N;
  8. std::cin >> N;
  9. std::vector<int> steps(N + 1, INT_MAX);
  10. steps[N] = 0;
  11. std::vector<int> next_num(N + 1, -1);
  12.  
  13. for (int i = N; i > 1; --i) {
  14. int s = steps[i] + 1;
  15. // 3 * x
  16. if (!(i % 3) && steps[i / 3] > s) {
  17. steps[i / 3] = s;
  18. next_num[i / 3] = i;
  19. }
  20. // 2 * x
  21. if (!(i % 2) && steps[i / 2] > s) {
  22. steps[i / 2] = s;
  23. next_num[i / 2] = i;
  24. }
  25. // x + 1
  26. if (steps[i - 1] > s) {
  27. steps[i - 1] = s;
  28. next_num[i - 1] = i;
  29. }
  30. }
  31.  
  32. std::cout << steps[1] << std::endl;
  33. for (int i = 1; i != -1; i = next_num[i])
  34. std::cout << i << ' ';
  35. std::cout << std::endl;
  36. }
Success #stdin #stdout 0s 3416KB
stdin
1
stdout
0
1