E - Cellular Messenger 解説 by evima
Solution
As one example, the following output is accepted.
000000010
011111010
3 65
11111111111111111111111111111111111111111111111111111111111111111
00000000000000000000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111111111111111111
1 0 1 63 63
The part sandwiched between \(1\)s becomes a “cable”, and the part within it is Rule90 with both ends fixed at \(0\).
When \((1,0)\) becomes \(1\), after \(63\) update operations \((1,63)\) becomes \(1\), and on the next update operation, all cells return to \(0\).
Also, since the state on the next turn is the XOR of two adjacent cells, the change caused by \(S_i\) and the change caused by a different \(S_j\) can be superimposed without interfering with each other.
Open Problem
\(G (0 \le G \le 50)\) is given as input. Construct a solution that also satisfies \(|R_s - R_t| = G\). \(|C_s-C_t|\) should be at most \(120\), and \(D\) should be at most \(150\).
If we try to solve this version using the approach above, it becomes necessary to realize at least one “bending” mechanism, but we have not yet been able to discover such a construction.
投稿日時:
最終更新: