51 lines
989 B
Java
51 lines
989 B
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.Arrays;
|
|
import java.util.List;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class Task2 extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
List<Integer> piramidSizes = new ArrayList<>();
|
|
int max = 300_001;
|
|
int[] dp = new int[max];
|
|
|
|
{
|
|
piramidSizes.add(0);
|
|
for (int i = 1; true; i++) {
|
|
piramidSizes.add(piramidSizes.get(i - 1) + (1 + i) * i / 2);
|
|
if (piramidSizes.get(i) >= max) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
Arrays.fill(dp, max);
|
|
dp[0] = 0;
|
|
for (int i = 1; i < max; i++) {
|
|
for (int j : piramidSizes) {
|
|
if (j > i) {
|
|
break;
|
|
}
|
|
dp[i] = Math.min(dp[i], dp[i - j] + 1);
|
|
}
|
|
}
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
|
|
int x = in.nextInt();
|
|
out.println(dp[x]);
|
|
|
|
}
|
|
}
|