No.3235 巡回減算
タグ : / 解いたユーザー数 74
作問者 : 👑
p-adic
/ テスター :
YY-otter
注意
この問題の実行時間制限は10000[ms]です。解法によっては実行時間制限が厳しいので高速な言語の使用を推奨します。
参考までに、writer解の実行時間はc++で1355[ms]、PyPy3で4923[ms]、Python3で 10000[ms]以上（つまり TLE）です。
問題文
$8$ 次元整数係数ベクトル $a$ に対し、$a$ の $1$ 個目の成分を $a$ の末尾に移動させることで得られる $8$ 次元整数係数ベクトル $a$ を $a$ の巡回ベクトルと呼びます。
例えば $(\textcolor{red}{0},1,2,3,4,5,6,7)$ の巡回ベクトルは $(1,2,3,4,5,6,7,\textcolor{red}{0})$ です。
入力に $8$ 個の $8$ 次元非負整数係数ベクトル $A_1,A_2,A_3,A_4,A_5,A_6,A_7,A_8$ が与えられます。
$2$ 以上 $8$ 以下の各正整数 $i$ に対し、$i$ が小さい順に以下の処理を行うことで $A_1$ を更新した結果、最終的な $A_1$ を零ベクトルにできるかを判定してください。
- まず $0$ 回以上の好きな回数、$A_1$ を $A_1$ の巡回ベクトルに置き換える。
- 次に $A_1$ を $A_1 - A_i$ に置き換える。
制約
$8$ 以下の各正整数 $i,j$ に対する $A_i$ の $j$ 個目の成分を $A_{i,j}$ と書き表します。
この時、入力は以下の制約を満たします：
- $8$ 以下の任意の正整数 $i,j$ に対し、$A_{i,j}$ は $0 \leq A_{i,j} \leq 9$ を満たす整数である。
入力
入力は以下の形式で標準入力から $8$ 行で与えられます：
- $8$ 以下の各正整数 $i$ に対し、$i$ 行目に $8$ 以下の各正整数 $j$ に対する $A_{i,j}$ が $j$ の小さい順に（区切り文字なしで）与えられます。
$A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1,5} A_{1,6} A_{1,7} A_{1,8}$
$A_{2,1} A_{2,2} A_{2,3} A_{2,4} A_{2,5} A_{2,6} A_{2,7} A_{2,8}$
$A_{3,1} A_{3,2} A_{3,3} A_{3,4} A_{3,5} A_{3,6} A_{3,7} A_{3,8}$
$A_{4,1} A_{4,2} A_{4,3} A_{4,4} A_{4,5} A_{4,6} A_{4,7} A_{4,8}$
$A_{5,1} A_{5,2} A_{5,3} A_{5,4} A_{5,5} A_{5,6} A_{5,7} A_{5,8}$
$A_{6,1} A_{6,2} A_{6,3} A_{6,4} A_{6,5} A_{6,6} A_{6,7} A_{6,8}$
$A_{7,1} A_{7,2} A_{7,3} A_{7,4} A_{7,5} A_{7,6} A_{7,7} A_{7,8}$
$A_{8,1} A_{8,2} A_{8,3} A_{8,4} A_{8,5} A_{8,6} A_{8,7} A_{8,8}$
出力
最終的な $A_1$ を零ベクトルにできる場合はYesと出力し、そうでない場合はNoと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
出力
Yes
どのように操作をしても、最終的な $A_1$ は零ベクトルです。
サンプル2
入力
01111111 10000000 10000000 10000000 10000000 10000000 10000000 10000000
出力
Yes
最初は $A_1 = (0,1,1,1,1,1,1,1)$ として与えられています。例えば
- $i=2$ の時、
- $A_1$ を $A_1$ の巡回ベクトル $(1,1,1,1,1,1,1,0)$ に置き換える。
- $A_1$ を $A_1 - A_2 = (0,1,1,1,1,1,1,0)$ に置き換える。
- $i=3$ の時、
- $A_1$ を $A_1$ の巡回ベクトル $(1,1,1,1,1,1,0,0)$ に置き換える。
- $A_1$ を $A_1 - A_3 = (0,1,1,1,1,1,0,0)$ に置き換える。
- $i=4$ の時、
- $A_1$ を $A_1$ の巡回ベクトル $(1,1,1,1,1,0,0,0)$ に置き換える。
- $A_1$ を $A_1 - A_4 = (0,1,1,1,1,0,0,0)$ に置き換える。
- $i=5$ の時、
- $A_1$ を $A_1$ の巡回ベクトル $(1,1,1,1,0,0,0,0)$ に置き換える。
- $A_1$ を $A_1 - A_5 = (0,1,1,1,0,0,0,0)$ に置き換える。
- $i=6$ の時、
- $A_1$ を $A_1$ の巡回ベクトル $(1,1,1,0,0,0,0,0)$ に置き換える。
- $A_1$ を $A_1 - A_6 = (0,1,1,0,0,0,0,0)$ に置き換える。
- $i=7$ の時、
- $A_1$ を $A_1$ の巡回ベクトル $(1,1,0,0,0,0,0,0)$ に置き換える。
- $A_1$ を $A_1 - A_7 = (0,1,0,0,0,0,0,0)$ に置き換える。
- $i=8$ の時、
- $A_1$ を $A_1$ の巡回ベクトル $(1,0,0,0,0,0,0,0)$ に置き換える。
- $A_1$ を $A_1 - A_8 = (0,0,0,0,0,0,0,0)$ に置き換える。
と操作することで、最終的な $A_1$ を零ベクトルにできます。
サンプル3
入力
90000009 10000000 10000000 00100000 00100000 00001000 00001000 00000039
出力
Yes
最初は $A_1 = (9,0,0,0,0,0,0,9)$ として与えられています。例えば
- $i=2$ の時、
- $A_1$ を $A_1$ の巡回ベクトルに置き換える操作を $7$ 回繰り返すことで $A_1$ を $(9,9,0,0,0,0,0,0)$ に更新する。
- $A_1$ を $A_1 - A_2 = (8,9,0,0,0,0,0,0)$ に置き換える。
- $i=3$ の時、
- $A_1$ を $A_1$ の巡回ベクトルに置き換える操作を $0$ 回繰り返す。
- $A_1$ を $A_1 - A_3 = (7,9,0,0,0,0,0,0)$ に置き換える。
- $i=4$ の時、
- $A_1$ を $A_1$ の巡回ベクトル操作を $6$ 回繰り返すことで $A_1$ を $(0,0,7,9,0,0,0,0)$ に更新する。
- $A_1$ を $A_1 - A_4 = (0,0,6,9,0,0,0,0)$ に置き換える。
- $i=5$ の時、
- $A_1$ を $A_1$ の巡回ベクトルに置き換える操作を $0$ 回繰り返す。
- $A_1$ を $A_1 - A_5 = (0,0,5,9,0,0,0,0)$ に置き換える。
- $i=6$ の時、
- $A_1$ を $A_1$ の巡回ベクトル操作を $6$ 回繰り返すことで $A_1$ を $(0,0,0,0,5,9,0,0)$ に更新する。
- $A_1$ を $A_1 - A_6 = (0,0,0,0,4,9,0,0)$ に置き換える。
- $i=7$ の時、
- $A_1$ を $A_1$ の巡回ベクトルに置き換える操作を $0$ 回繰り返す。
- $A_1$ を $A_1 - A_7 = (0,0,0,0,3,9,0,0)$ に置き換える。
- $i=8$ の時、
- $A_1$ を $A_1$ の巡回ベクトル操作を $6$ 回繰り返すことで $A_1$ を $(0,0,0,0,0,0,3,9)$ に更新する。
- $A_1$ を $A_1 - A_8 = (0,0,0,0,0,0,0,0)$ に置き換える。
と操作することで、最終的な $A_1$ を零ベクトルにできます。
サンプル4
入力
88888888 88888888 88888888 88888888 88888888 88888888 88888888 88888888
出力
No
どのように操作をしても、最終的な $A_1$ は $(-56,-56,-56,-56,-56,-56,-56,-56)$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。