fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. char dp1[1000001],dp2[1000001];
  7.  
  8. int main(){
  9.     int t[181];
  10.  
  11.     for(int i = 1;i <= 180;++i)
  12.         t[i] = i * (i + 1) * (i + 2) / 6;
  13.  
  14.     dp1[0] = dp2[0] = 0;
  15.  
  16.     for(int i = 1;i <= 1000000;++i)
  17.         dp1[i] = dp2[i] = 40;
  18.  
  19.     for(int i = 1;i <= 180;++i){
  20.         int x = t[i];
  21.  
  22.         for(int j = x;j <= 1000000;++j)
  23.             if(1 + dp1[j - x] < dp1[j]) dp1[j] = 1 + dp1[j - x];
  24.     }
  25.  
  26.     for(int i = 1;i <= 180;++i){
  27.         int x = t[i];
  28.  
  29.         if(x & 1)
  30.             for(int j = x;j <= 1000000;++j)
  31.                 if(1 + dp2[j - x] < dp2[j]) dp2[j] = 1 + dp2[j - x];
  32.     }
  33.  
  34.     int n;
  35.  
  36.     while(true){
  37.         scanf("%d",&n);
  38.  
  39.         if(n == 0) break;
  40.  
  41.         printf("%d %d\n",dp1[n],dp2[n]);
  42.     }
  43.  
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0.52s 4680KB
comments (?)
stdin
copy 
40
14
5
165
120
103
106
139
0
stdout
copy 
2 6
2 14
2 5
1 1
1 18
5 35
4 4
3 37
https://ideone.com/XN4td
language:
C++ (gcc 8.3)
created:
11 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!