122 lines
2.3 KiB
Java
122 lines
2.3 KiB
Java
package chelper;
|
|
|
|
import java.util.Arrays;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.GCJSolution;
|
|
|
|
|
|
public class TaskB extends GCJSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
|
|
boolean ok(int a0, int b0, int a1, int b1) {
|
|
int t = Integer.compare(a0, a1);
|
|
if (t != 0) {
|
|
return t > 0;
|
|
}
|
|
return Integer.compare(b0, b1) > 0;
|
|
}
|
|
|
|
int[][] dp;
|
|
int n = 510;
|
|
|
|
void precalc() {
|
|
dp = new int[n][n];
|
|
int[][][] lastDelta = new int[n][n][2];
|
|
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
Arrays.fill(dp[i], -1);
|
|
}
|
|
|
|
dp[0][0] = 0;
|
|
|
|
long sum = 0;
|
|
|
|
for (int a = 0; a < n; a++) {
|
|
for (int b = 0; b < n; b++) {
|
|
if (a > b) {
|
|
dp[a][b] = dp[b][a];
|
|
lastDelta[a][b] = lastDelta[b][a];
|
|
continue;
|
|
}
|
|
|
|
for (int aa = 0; aa <= a; aa++) {
|
|
for (int bb = 0; bb <= b; bb++) {
|
|
if (dp[a - aa][b - bb] * 1.1 + 5 < dp[a][b]) {
|
|
break;
|
|
}
|
|
|
|
if (dp[a - aa][b - bb] + 1 <= dp[a][b]) {
|
|
continue;
|
|
}
|
|
|
|
if (aa < lastDelta[a - aa][b - bb][0]) {
|
|
continue;
|
|
}
|
|
|
|
if (aa == lastDelta[a - aa][b - bb][0] && bb <= lastDelta[a - aa][b - bb][1]) {
|
|
continue;
|
|
}
|
|
|
|
dp[a][b] = dp[a - aa][b - bb] + 1;
|
|
lastDelta[a][b][0] = aa;
|
|
lastDelta[a][b][1] = bb;
|
|
}
|
|
}
|
|
|
|
|
|
}
|
|
}
|
|
|
|
|
|
for (int a = 0; a < n; a++) {
|
|
for (int b = 0; b < n; b++) {
|
|
sum += dp[a][b];
|
|
}
|
|
}
|
|
|
|
// System.out.println(dp[88][53]);
|
|
// System.out.println((sum - 16727938));
|
|
// System.out.flush();
|
|
|
|
}
|
|
|
|
{
|
|
precalc();
|
|
|
|
}
|
|
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int a = in.nextInt();
|
|
int b = in.nextInt();
|
|
|
|
out.println(dp[a][b]);
|
|
|
|
// try {
|
|
// OutputWriter log = new OutputWriter("precalc.txt");
|
|
// for (int i = 0; i < n; i++) {
|
|
// for (int j = 0; j < n; j++) {
|
|
// log.print(String.format("%4d ", dp[i][j]));
|
|
//
|
|
// double x = Math.pow(i + j, 0.7);
|
|
//
|
|
// out.println(String.format("%4d %4d: %4d %.2f", i, j, dp[i][j], x));
|
|
// }
|
|
// log.println();
|
|
// }
|
|
// } catch (FileNotFoundException e) {
|
|
// throw new RuntimeException(e);
|
|
// }
|
|
|
|
}
|
|
|
|
}
|