//|[0, X-a]| = |[a, X]| = |(a, X+1]| //0~X+1のうちD-1個を選ぶのと一致しそう。…一致しない! //考察; //{深さi, 今までに足した値}が同じならできることが同じ。これを状態としてDPできる。 //漸化式は //dp[0][0] = 1 //dp[i][j] = {dp[i-1][j] ~ dp[i-1][X+1]の総和} //となり、求める解はdp[D-1][0]~dp[D-1][X]の総和、すなわちdp[D][X]となる。 //実はこの漸化式… //dp[i][j] = dp[i][j-1] + dp[i-1][j]となり、dp[i][j]はi-1回↑、j回→へ行くときの経路の選び方と一致。 //よって、dp[D][X] = (D+X-1)C(X)となる。 #include #include #include #include #include #include #include #include #include #include #include #include #include #define int long long using namespace std; int q; const int INF = 1e+17; signed main() { static int C[4545][4545] = {0}; C[0][0] = 1; for (int i = 1; i < 4545; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) { C[i][j] = C[i-1][j] + C[i-1][j-1]; if (C[i][j] > INF) C[i][j] = INF; } } cin >> q; while (q--) { int d, x, k; cin >> d >> x >> k; if (C[x+d-1][x] <= k) { cout << "AC" << endl; } else { cout << "ZETUBOU" << endl; } } return 0; }