No.250 atetubouのzetubou

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 169
作問者 : is_eri23is_eri23
11 ProblemId : 302 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:47:46

問題文

atetubouくんはコンテストに参加している真っ最中です。
atetubouくんは実装が重い問題をなんとかコンテスト終了3分前にコーディングしおわりサブミットしようとしているところです。
頑張って書いたコードがTLEすると悲しくなってしまうので改善しようとコード見直すことにしました。
今取り組んでいる問題の時間がかかりそうなところはfor文を何重にも回すところで以下のようになっています。

for i <- 0..$X$
    for j <- 0..$X$
       for k <- 0..$X$
          for l <- 0..$X$
              if i + j + k + l== $X$:
                 //program

atetubouくんはこのコードが以下のように改善できることに気づきました。

for i <- 0..$X$
    for j <- 0..($X$-i)
       for k <- 0..($X$ - i - j)
          l <- $X$ - i - j - k
          //program

atetubouくんは改善したところでコンテスト終了まで残り10秒になりました。
//programの部分に入る回数が$T$回だと間に合うと見積もったatetubouくんはどのくらい入るか調べることにしました。
atetubouくんのコードは無事ACされるのでしょうか。
programの部分では、変数$X$の書き換えは行われず、breakなどでループが抜けることはないとする。

入力

$Q$
$D_1$ $X_1$ $T_1$
$D_2$ $X_2$ $T_2$
$\vdots$
$D_Q$ $X_Q$ $T_Q$

$1 \leq Q \leq 10^{4}$ : クエリの数
$1 \leq D_{i} \leq 1500$ : 改善する前のコードのfor文の深さ,上記の例だとD=4
$1 \leq X_{i} \leq 1500$ : コード中の変数$X$
$0 \leq T_{i} \leq 10^{15}$: //programに入る回数の上限. これより多いとTLEしてしまいます。

出力

ACされるなら"AC"
TLEなら"ZETUBOU" <- (ZETSUBOUではないです!)
を出力してください
最後に改行してください。

サンプル

サンプル1
入力
3
1 3 1
2 4 50
3 3 9
出力
AC
AC
ZETUBOU

クエリ1:最初深さが1ならば改善すればi <- Xの1回のみです
クエリ2:改善後はfor文の深さが1で0~4の5回programに入ります
クエリ3:{i,j,k} = {0,0,3}, {0,1,2}, {0,2,1}, {0,3,0}, {1,0,2}, {1,1,1}, {1,2,0}, {2,0,1}, {2,1,0}, {3,0,0}の10回入ることになりTLEします

サンプル2
入力
3
58 62 1000
12 34 56
987 65 1234
出力
ZETUBOU
ZETUBOU
ZETUBOU

atetubouくんは絶望しました

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。