POJ 1406 - Starship Hakodate-maru

http://poj.org/problem?id=1406

概要

2つの燃料容器があり，1つは立方数 n^3 の燃料しか入れられず，もう1つは四面体数 n(n+1)(n+2)/6 の燃料しか入れられない．

N 個の燃料が与えられたとき，2つの燃料容器で合わせて最大でどれだけの燃料を入れることができるかを答える．

制約

• N <= 151200

解法

全通り試して最大の数を答える．

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int tetra(int m) { return m*(m+1)*(m+2)/6; }
 6 
 7 int main()
 8 {
 9   int N;
10   while (cin >> N && N != 0) {
11     int ans = 0;
12     for (int m = 0; tetra(m) <= N; m++) {
13       const int n = cbrt(N - tetra(m));
14       ans = max(ans, n*n*n + tetra(m));
15     }
16     cout << ans << endl;
17   }
18   return 0;
19 }