結果

問題 No.250 atetubouのzetubou
ユーザー ynayna
提出日時 2018-07-16 12:15:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,581 bytes
コンパイル時間 2,124 ms
コンパイル使用メモリ 170,260 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-17 00:41:13
合計ジャッジ時間 45,920 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;

bool res[10010];

#ifndef FACT
#define FACT
// return n! mod p
int fact(int n, int p = __INT32_MAX__){
	static vector<int> memo_in_fact(1, 1);
	if ((int) memo_in_fact.size() <= n) {
		int l = memo_in_fact.size();
		memo_in_fact.resize(n+1);
		for(int i = l; i <= n; i++) memo_in_fact[i] = ((ll) memo_in_fact[i-1] * i) % p;
	}
	return memo_in_fact[n];
}
#endif

#ifndef MOD_FACT
#define MOD_FACT
// return a mod p (when n! = a*p^e), o(log_p n)
template<class T>
T modFact(T n, T& e, T p = __INT32_MAX__){
	e = 0;
	if(n == 0) return 1;

	T res = modFact(n / p, e, p);
	e += n / p;

	if((n / p % 2 != 0)) return (long long) res * (p - fact(n % p, p)) % p;
	return (long long) res * fact(n % p, p) % p;
}
#endif

#ifndef GCD
#define GCD
// solve ax+by=gcd(a, b)
// return gcd(a, b)
template<class T>
T gcd(const T a, const T b, T* const px = nullptr, T* const py = nullptr){
	if(py == nullptr){
		if(b == 0) return a;
		return gcd(b, a % b);
	}

	T d = a;
	if(b != 0){
		d = gcd(b, a % b, py, px);
		*py -= (a / b) * *px;
	}else{
		*px = 1; *py = 0;
	}
	return d;
}
#endif

#ifndef MOD_INVERSE
#define MOD_INVERSE
// return a^(-1) (mod m)
template<class T>
 T modInverse(T a, T m){
	 T x, y;
	 assert(gcd(a, m, &x, &y) == 1);
	 if(x % m < 0) return (m + x % m) % m;
	 else return x % m;
 }
#endif

#ifndef COMBINATION
#define COMBINATION
// return nPk mod p
int perm(int n, int k, int p = __INT32_MAX__){
	if(n < 0 or k < 0 or n < k) return 0;
	int e1, e2;
	int a1 = modFact(n, e1, p), a2 = modFact(n - k, e2, p);
	return (long long) a1 * modInverse(a2, p) % p;
}

// return nCk mod p, o(log_p n)
template<class T>
T comb(T n, T k, T p = __INT32_MAX__){
	if(n < 0 or k < 0 or n < k) return 0;
	T e1, e2, e3;
	T a1 = modFact(n, e1, p), a2 = modFact(k, e2, p), a3 = modFact(n - k, e3, p);
	if(e1 > e2 + e3) return 0;
	return (long long) a1 * modInverse((long long) a2 * a3 % p, (long long) p) % p;
}

// return nHk mod p
template<class T>
T hcomb(T n, T k,  T p = numeric_limits<int>::max()){
	if(n < 0 or k < 0) return 0;
	if(n == 0 and k == 0) return 1;
	return comb(n + k - 1, k, p);
}
#endif


int main(void){
	int Q; cin >> Q;
	for(int i = 0; i < Q; i++){
		ll D, X, T; cin >> D >> X >> T;
		ll t = 0;
		for(ll j = 0; j <= X; j++){
			t += hcomb(D-1, j);
		}
		debug(t);
		res[i] = (t <= T);
	}

	for(int i = 0; i < Q; i++){
		if(res[i]) cout << "AC" << '\n';
		else cout << "ZETUBOU" << '\n';
	}

	return 0;
}
0