fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define sz (int)1e6
  3. using namespace std;
  4. int getminsteps(int n, int *memo)
  5. {
  6.   if( n == 1) return 0;
  7.   if( memo[n] != -1)  return memo[n];
  8.   int r = 1 + getminsteps(n-1,memo);
  9.   if(n%2 == 0)
  10.     r = min(r,1+getminsteps(n/2,memo));
  11.   if(n%3 == 0)
  12.     r = min(r,1+getminsteps(n/3,memo));
  13.   memo[n] = r;
  14.   return r;
  15. }
  16. int main()
  17. {
  18.     int t,n,i,ans;
  19.     cin >> t;
  20.     int memo[sz];
  21.     memset(memo, -1, sizeof(memo));
  22.     while (t--)
  23.     {
  24.         cin >> n;
  25.         ans = getminsteps(n,memo);
  26.         cout << ans << endl;
  27.     }
  28.     return 0;
  29. }
  30.  
Success #stdin #stdout 0s 19840KB
comments (?)
stdin
copy 
3
1
6
10
stdout
copy 
0
2
3
https://ideone.com/XoanGr
language:
C++14 (gcc 8.3)
created:
6 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!