問題一覧 > 通常問題

No.2015 Stair Counter

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 116
作問者 : ShirotsumeShirotsume / テスター : ramdosramdos
8 ProblemId : 7651 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-05 23:47:19

問題文

$N$ 段からなる階段があります。初め、$M$ 人の人が上り口である $0$ 段目にいます。それぞれの人は、$1$ 歩で $1$ 段または $2$ 段上ることで $N$ 段目まで上がりました。

長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。 $M$ 人の上り方であって、すべての $i$ $(1 \leq i \leq N)$ について $i$ 段目を踏んだ人の数が $A_i$ と等しくなるものが存在するか判定してください。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 入力は全て整数
  • $1 \leq T \leq 10^4$
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq M \leq 10^9$
  • $0 \leq A_i \leq M$ $(1 \leq i \leq N - 1)$
  • $A_N = M$
  • $1$ つの入力ファイルにおいて、 $N$ の総和は $2 \times 10^5$ 以下

入力

入力は標準入力から与えられる。 $1$ 行目は以下の形式で与えられる。

$T$

以下、 $T$ 個のテストケースがそれぞれ以下の形式で与えられる。

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

出力

$T$ 行にわたって出力せよ。$i$ $(1 \leq i \leq T)$ 行目には、 $i$ 番目のテストケースについて、各段を踏んだ人の数が $A$ と一致する上り方が存在するならYes、存在しないならNoと出力せよ。

最後に改行すること。

サンプル

サンプル1
入力
6
3 3
1 2 3
5 1
0 1 1 0 1
5 5
3 1 4 1 5
20 9
9 8 3 9 2 8 6 4 6 7 2 9 9 4 8 8 3 7 5 9
5 392594829
63454038 307305345 98813758 258579949 392594829
9 724640070
515364178 287107703 719086324 652644278 450996113 447939354 349844586 541137464 724640070
出力
Yes
Yes
No
Yes
No
Yes

$6$ つのテストケースが与えられています。

$1$ つめのテストケースでは、 $3$ 段からなる階段を $3$ 人が上ります。例えば、 $1$ 人が $0 \rightarrow 1 \rightarrow 3$ 、 $2$ 人が $0 \rightarrow 2 \rightarrow 3$ という上り方をすると、各段を踏んだ人の数と $A$ が一致します。

$2$ つめのテストケースでは、 $5$ 段からなる階段を $1$ 人が上ります。 $0 \rightarrow 2 \rightarrow 3 \rightarrow 5$ という上り方をすれば $A$ と一致します。

$3$ つめのテストケースでは、どのように上っても各段を踏んだ人の数と $A$ を一致させることはできません。

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