Connection Status:
Competition Arena > GameOfLifeDivOne

GameOfLifeDivOne

SRM 511 · 2011-05-25 · by rng_58

SRM 511 · 2011-05-25 · by rng_58 · Dynamic Programming, Math
Class Name: GameOfLifeDivOne
Return Type: long
Method Name: theCount
Arg Types: (string, int, int)
Problem Statement

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.

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)
"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.

1)
"?????????"
0
1
Returns: 511

There are 512 ways to replace '?' cells with '0' or '1'. All of them except "000000000" satisfy the condition.

2)
"??0???????"
58
6
Returns: 151
3)
"?????????1"
47
3
Returns: 453
4)
"??01??110?"
100
3
Returns: 29

Submissions are judged against all 121 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GameOfLifeDivOne with a public method long long theCount(string init, int T, int K) · 121 test cases · 2 s / 256 MB per case

Submitting as anonymous