시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 1 1 1 100.000%

문제

Ann is decorating her office with the coolest arrangement of lights ever.  She is using very long LED strips, where each individual cell is switched on or off every second, according to the following simple and pretty algorithm. At each step, the status of each cell (0 for off and 1 for on) is determined from the status of its two neighbor cells on the strip (left and right) and its own status, according to the following table:

Current pattern 111 110 101 100 011 010 001 000
New state for center cell 0 1 1 0 1 1 1 0

Ann is choosing an initial configuration for the cells and she marvels at the resulting animation, which happens to be highly similar to Conway's Game of Life, with interesting behavior on the boundary between stability and chaos.

입력

The input is composed of two lines.

  • The first line contains the initial configuration, as a string of 16 characters 0 and 1. All the cells to the left and to the right of this string are considered to be 0.
  • The second line contains the number $N$ of steps to perform.

출력

The output should contain a single line with a single integer that is the total number of 1-cells in the final configuration.

제한

  • $0 \le N < 2^{60}$
  • The LED strip is considered to be large enough to ensure that no 1-cells will ever reach the ends of the strip.

예제 입력 1

0001001101111100
5

예제 출력 1

11

the output is $11$ since we have the following five steps:

...0000000010011011111000...
...0000000110111110001000...
...0000001111100010011000...
...0000011000100110111000...
...0000111001101111101000...
...0001101011111000111000...

where everything not displayed contains only 0-cells.

출처

ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2020-2021 B번

  • 문제를 만든 사람: Jean-Christophe Filliâtre