시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB15121280.000%

문제

The epidemiologist W. Andy wants to find the index case of an ongoing crisis. To do this, he modelled the city of the outbreak and its $n$ residents with a cellular automaton. The city is represented by $n$ cells numbered from $1$ to $n$ and each cell has two neighbouring cells, one to its left and one to its right. The left neighbour of cell $i$ is cell $i-1$ and the right neighbour is cell $i+1$. Additionally, the left neighbour of cell $1$ is cell $n$ and the right neighbour of cell $n$ is cell $1$. Thus, the city and the corresponding automaton form a simple cycle.

Each cell contains an integer between $1$ and $m$ which represents how likely it is that this person is infected. Since the virus can only be transmitted by personal contact, the value in the $i$th cell on day $d$ only depends on the values of its neighbours and itself on the previous day. If we denote this value by $s_{d}[i]$, then the outbreak can be simulated by a function $f$ using the formula: \[s_{d}[i]=f\big(s_{d-1}[i-1],s_{d-1}[i],s_{d-1}[i+1]\big).\] Note that as the city is cyclic both $i+1$ and $i-1$ are calculated modulo $n$.

Andy wants to find the index case, so he first has to find $s_0$, the state of the city on day zero. This poses a problem, however, as it is not known on which day the crisis started. Right now, Andy believes that he accomplished the task and found the state $s_0$, but you are not convinced. Therefore, you want to check if there may be a state previous to the initial state proposed by Andy, i.e. whether there exists any state $s_{-1}$ that gets transformed into $s_0$ by applying $f$.

입력

The input consists of:

  • One line with two integers $n$ and $m$ $(3\leq n \leq 200, 2\leq m \leq 10)$, the number of cells and the number of states.
  • $m^3$ lines describing the values $f(x,y,z)$ ($1 \le f(x,y,z) \le m$ for each $1 \le x,y,z \le m$) of the function $f$ modelling the automaton. The values are given in lexicographic order of the arguments: The first value is $f(1,1,1)$, the next is $f(1,1,2)$, and so on until $f(1,1,m)$, followed by $f(1,2,1)$ and so forth. The last value is $f(m,m,m)$.
  • One line with $n$ integers $s_0[1],\dots,s_0[n]$ ($1 \le s_0[i] \le m$ for each $i$), the initial state that has been proposed by Andy.

출력

Output yes if there exists at least one possible previous state and no otherwise.

예제 입력 1

4 2
1
2
1
2
2
1
2
1
1 2 1 2

예제 출력 1

yes

예제 입력 2

6 2
1
2
1
2
2
1
2
1
1 2 1 2 1 2

예제 출력 2

no

예제 입력 3

10 2
1
2
1
1
2
2
2
2
1 2 2 2 1 2 1 2 1 2

예제 출력 3

yes

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2021 I번

  • 문제를 만든 사람: Michael Zündorf