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.         char *p1 = &dp1[0],*p2 = &dp1[x];
  23.  
  24.         for(int j = x;j <= 1000000;++j,++p1,++p2)
  25.             if(1 + *p1 < *p2) *p2 = 1 + *p1;
  26.     }
  27.  
  28.     for(int i = 1;i <= 180;++i){
  29.         int x = t[i];
  30.  
  31.         if(x & 1){
  32.             char *p1 = &dp2[0],*p2 = &dp2[x];
  33.  
  34.             for(int j = x;j <= 1000000;++j,++p1,++p2)
  35.                 if(1 + *p1 < *p2) *p2 = 1 + *p1;
  36.         }
  37.     }
  38.  
  39.     int n;
  40.  
  41.     while(true){
  42.         scanf("%d",&n);
  43.  
  44.         if(n == 0) break;
  45.  
  46.         printf("%d %d\n",dp1[n],dp2[n]);
  47.     }
  48.  
  49.     return 0;
  50. }
  51.  
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/cWhNR
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!