問題一覧 > 教育的問題

No.3235 Cyclic Subtraction

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 76
作問者 : 👑 p-adic / テスター : YY-otter
お気に入りにしたユーザー ProblemId : 10687 / 自分の提出
問題文最終更新日: 2025-02-14 00:22:12
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 478 オムニバス (順位表) の他の問題:

Note

The time limit for this problem is 10000[ms]. Depending on the solution, the time limit may be tight, so using a fast language is recommended.

For reference, the execution time of the writer's solution is 1355[ms] in c++, 4923[ms] in PyPy3, and over 10000[ms] in Python3 (that is, TLE).

Problem Statement

For an $8$-dimensional vector $a$ with integer coefficients, the $8$-dimensional vector $a$ with integer coefficients obtained by moving the $1$-st component of $a$ to the end of $a$ is called the cyclic vector of $a$.

For example, the cyclic vector of $(\textcolor{red}{0},1,2,3,4,5,6,7)$ is $(1,2,3,4,5,6,7,\textcolor{red}{0})$.

　

You are given as input $8$ vectors $A_1,A_2,A_3,A_4,A_5,A_6,A_7,A_8$, each of dimension $8$ with non-negative integer coefficients.

For each positive integer $i$ from $2$ to $8$ inclusive, in ascending order of $i$, $A_1$ is updated by performing the following process. Determine whether the final $A_1$ can be made the zero vector.

  1. First, replace $A_1$ with the cyclic vector of $A_1$ any number of times, $0$ or more.
  2. Next, replace $A_1$ with $A_1 - A_i$.

Constraints

For each pair of positive integers at most $8$, $i,j$, the $j$-th component of $A_i$ is denoted by $A_{i,j}$.

Then the input satisfies the following constraints:

  • For any positive integers at most $8$, $i,j$, $A_{i,j}$ is an integer satisfying $0 \leq A_{i,j} \leq 9$.

Input

The input is given from standard input in $8$ lines in the following format:

  • For each positive integer $i$ at most $8$, line $i$ contains $A_{i,j}$ for each positive integer $j$ at most $8$, in ascending order of $j$ (without separators).
$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}$

Output

Print Yes if the final $A_1$ can be made the zero vector, and No otherwise.

Print a newline at the end.

Sample

Sample 1
Input
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
Output
Yes

No matter how the operations are performed, the final $A_1$ is the zero vector.

Sample 2
Input
01111111
10000000
10000000
10000000
10000000
10000000
10000000
10000000
Output
Yes

Initially, $A_1 = (0,1,1,1,1,1,1,1)$ is given. For example, operate as follows:

  • When $i=2$,
    • Replace $A_1$ with the cyclic vector $(1,1,1,1,1,1,1,0)$ of $A_1$.
    • Replace $A_1$ with $A_1 - A_2 = (0,1,1,1,1,1,1,0)$.
  • When $i=3$,
    • Replace $A_1$ with the cyclic vector $(1,1,1,1,1,1,0,0)$ of $A_1$.
    • Replace $A_1$ with $A_1 - A_3 = (0,1,1,1,1,1,0,0)$.
  • When $i=4$,
    • Replace $A_1$ with the cyclic vector $(1,1,1,1,1,0,0,0)$ of $A_1$.
    • Replace $A_1$ with $A_1 - A_4 = (0,1,1,1,1,0,0,0)$.
  • When $i=5$,
    • Replace $A_1$ with the cyclic vector $(1,1,1,1,0,0,0,0)$ of $A_1$.
    • Replace $A_1$ with $A_1 - A_5 = (0,1,1,1,0,0,0,0)$.
  • When $i=6$,
    • Replace $A_1$ with the cyclic vector $(1,1,1,0,0,0,0,0)$ of $A_1$.
    • Replace $A_1$ with $A_1 - A_6 = (0,1,1,0,0,0,0,0)$.
  • When $i=7$,
    • Replace $A_1$ with the cyclic vector $(1,1,0,0,0,0,0,0)$ of $A_1$.
    • Replace $A_1$ with $A_1 - A_7 = (0,1,0,0,0,0,0,0)$.
  • When $i=8$,
    • Replace $A_1$ with the cyclic vector $(1,0,0,0,0,0,0,0)$ of $A_1$.
    • Replace $A_1$ with $A_1 - A_8 = (0,0,0,0,0,0,0,0)$.

By operating in this way, the final $A_1$ can be made the zero vector.

Sample 3
Input
90000009
10000000
10000000
00100000
00100000
00001000
00001000
00000039
Output
Yes

Initially, $A_1 = (9,0,0,0,0,0,0,9)$ is given. For example, operate as follows:

  • When $i=2$,
    • Repeat the operation of replacing $A_1$ with the cyclic vector of $A_1$ $7$ times, updating $A_1$ to $(9,9,0,0,0,0,0,0)$.
    • Replace $A_1$ with $A_1 - A_2 = (8,9,0,0,0,0,0,0)$.
  • When $i=3$,
    • Repeat the operation of replacing $A_1$ with the cyclic vector of $A_1$ $0$ times.
    • Replace $A_1$ with $A_1 - A_3 = (7,9,0,0,0,0,0,0)$.
  • When $i=4$,
    • Repeat the operation of replacing $A_1$ with the cyclic vector of $A_1$ $6$ times, updating $A_1$ to $(0,0,7,9,0,0,0,0)$.
    • Replace $A_1$ with $A_1 - A_4 = (0,0,6,9,0,0,0,0)$.
  • When $i=5$,
    • Repeat the operation of replacing $A_1$ with the cyclic vector of $A_1$ $0$ times.
    • Replace $A_1$ with $A_1 - A_5 = (0,0,5,9,0,0,0,0)$.
  • When $i=6$,
    • Repeat the operation of replacing $A_1$ with the cyclic vector of $A_1$ $6$ times, updating $A_1$ to $(0,0,0,0,5,9,0,0)$.
    • Replace $A_1$ with $A_1 - A_6 = (0,0,0,0,4,9,0,0)$.
  • When $i=7$,
    • Repeat the operation of replacing $A_1$ with the cyclic vector of $A_1$ $0$ times.
    • Replace $A_1$ with $A_1 - A_7 = (0,0,0,0,3,9,0,0)$.
  • When $i=8$,
    • Repeat the operation of replacing $A_1$ with the cyclic vector of $A_1$ $6$ times, updating $A_1$ to $(0,0,0,0,0,0,3,9)$.
    • Replace $A_1$ with $A_1 - A_8 = (0,0,0,0,0,0,0,0)$.

By operating in this way, the final $A_1$ can be made the zero vector.

Sample 4
Input
88888888
88888888
88888888
88888888
88888888
88888888
88888888
88888888
Output
No

No matter how the operations are performed, the final $A_1$ is $(-56,-56,-56,-56,-56,-56,-56,-56)$.

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