410226: GYM103987 B Rule 110

The Rule 110 cellular automaton (often called simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.

The Rule 110 is famous for its interesting properties. Among the 88 possible unique elementary cellular automata, Rule 110 is the only one for which Turing completeness has been proven, although proofs for several similar rules should follow as simple corollaries (e.g. Rule 124, which is the horizontal reflection of Rule 110). Rule 110 is arguably the simplest known Turing complete system.

This paragraph will introduce how Rule 110 works. When applying Rule 110 to a pattern, whether each point in the pattern will be 0 or 1 in the new generation depends on its current value, and on the values of its two neighbors. If a point is at the left/right border, then the left/right neighbor of it will be considered as 0. The rules are as follows:

Chipmunk is interested in the automaton but he is not clever enough to solve it quickly. Now Chipmunk gives you the initial pattern, and you need to apply Rule 110 to the pattern once and output the result.

The first line contains an integer $$$n\ (1\le n\le 10^5)$$$, the length of the pattern.

The next line is a string of length $$$n$$$ consisting of only 0s and 1s, representing the initial pattern.

Output a string of length $$$n$$$, the pattern after applying Rule 110.

The problem contains several subtasks. You can get the corresponding score for each passed test case.

• Subtask 1 ($$$40$$$ points): $$$n\le 1000$$$.
• Subtask 2 ($$$60$$$ points): no additional constraints.

1
1

1

8
00111010

01101110

In the first example, there is an only 1 in the initial pattern. The two neighbors of it are both 0, which satisfies pattern 010. According to the table above, the value of the point will stay at 1.