問題一覧 > 教育的問題

No.3235 巡回減算

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 73
作問者 : 👑 p-adic / テスター : YY-otter
ProblemId : 10687 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-14 00:22:12

注意

この問題の実行時間制限は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$ を零ベクトルにできるかを判定してください。

  1. まず $0$ 回以上の好きな回数、$A_1$ を $A_1$ の巡回ベクトルに置き換える。
  2. 次に $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もしくは右上の雲マークをクリックしてアカウントを作成してください。