GameOfLifeDivOne | Topcoder Archive

Problem Statement

Cat Taro and Rabbit Hanako invented a new variation of "Game Of Life".

N cells are arranged around a circle. The cells are numbered from 0 to N-1. For each i between 0 and N-2, inclusive, the i-th cell and the (i+1)-th cell are adjacent to each other. The (N-1)-th cell and the 0-th cell are adjacent to each other. Each cell has exactly two adjacent cells. Each cell has a state: "live" or "die".

Taro and Hanako can decide the states of the cells at time 0. For time t > 0, the states are determined as follows:

Consider three cells: the i-th cell and the two cells that are adjacent to the i-th cell.
If at least two of the three cells are "live" at time t-1, the state of the i-th cell at time t will be "live".
If at least two of the three cells are "die" at time t-1, the state of the i-th cell at time t will be "die".

You are given a String init. The number of cells in the game (N) is equal to the number of characters in init. The i-th character of init represents the state they assign to the i-th cell at time 0. '1' means "live", '0' means "die", and '?' means undecided. Return the number of ways they can assign states to the undecided cells such that at least K cells will be in the "live" state at time T.

Definition

Class:: GameOfLifeDivOne
Method:: theCount
Parameters:: String, int, int
Returns:: long
Method signature:: long theCount(String init, int T, int K)
(be sure your method is public)

Constraints

init will contain between 3 and 50 characters, inclusive.
Each character in init will be '0' (zero), '1' (one) or '?'.
T will be between 0 and 1,000, inclusive.
K will be between 0 and the number of characters in init, inclusive.

Examples

```
"0?1"
```
```
1
```
```
1
```
```
Returns: 1
```
There are two ways to replace '?' with '0' and '1': "001" and "011". If the state is "001" at time 0, the state will be "000" at time 1. No cell is in the "live" state. If the state is "011" at time 0, the state will be "111" at time 1. 3 cells are in the "live" state. Only the second one satisfies the condition, so the answer is 1.
```
"?????????"
```
```
0
```
```
1
```
```
Returns: 511
```
There are 512 ways to replace '?' cells with '0' or '1'. All of them except "000000000" satisfy the condition.
```
"??0???????"
```
```
58
```
```
6
```
```
Returns: 151
```
```
"?????????1"
```
```
47
```
```
3
```
```
Returns: 453
```

"?????????1???0???1??1??????0??????0??0????1???????"

Returns: 31577324313

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.