시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 15 | 12 | 12 | 80.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:
Output yes
if there exists at least one possible previous state and no
otherwise.
4 2 1 2 1 2 2 1 2 1 1 2 1 2
yes
6 2 1 2 1 2 2 1 2 1 1 2 1 2 1 2
no
10 2 1 2 1 1 2 2 2 2 1 2 2 2 1 2 1 2 1 2
yes
ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2021 I번