fork download
copy 
  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 3464KB
comments (?)
stdin
copy 
5
stdout
copy 
3
1 3 4 5
https://ideone.com/Ttku2H
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!