fork download
copy 
  1.     #include <iostream>
  2.     #include <iomanip>
  3.     #include <limits>
  4.  
  5.     using namespace std;
  6.  
  7.     int pr[110] = { 0 };
  8.  
  9.     int getSol(int N)
  10.     {
  11.         static int v[110] = { 0 };
  12.  
  13.         if (N == 1) { pr[N] = 0; return 1; }
  14.  
  15.         if (N < 1) return numeric_limits<int>::max();
  16.         if (v[N]) return v[N];
  17.         int step = numeric_limits<int>::max();
  18.         if (N%3 == 0)
  19.             step = getSol(N/3);
  20.         int four = getSol(N-4);
  21.         if (four < step)
  22.         {
  23.             pr[N] = N-4;
  24.             return v[N] = four+1;
  25.         }
  26.         pr[N] = N/3;
  27.         return v[N] = step+1;
  28.     }
  29.  
  30.     void print(int * p, int n)
  31.     {
  32.         if (n == 0) return;
  33.         print(p,p[n]);
  34.         cout << n << "  ";
  35.     }
  36.  
  37.  
  38.     int main(int argc, const char * argv[])
  39.     {
  40.         cout << getSol(109) << endl;
  41.  
  42.         print(pr,109);
  43.  
  44.     }
  45.  
  46.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8
1  3  9  27  31  35  105  109
https://ideone.com/qLOhzb
language:
C++14 (gcc 8.3)
created:
5 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!