Show problems as
Classic problem #3130HardDynamic ProgrammingPrefix Sum

Find All Possible Stable Binary Arrays II

Real-world version: Steady Punch Card Layouts
Tracked in this browser only
Read Find All Possible Stable Binary Arrays II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A punch card is a single row of cells. Every cell is either a blank or a mark. A card is steady when all three hold:

  • it carries exactly zero blanks;
  • it carries exactly one marks;
  • no run of limit + 1 cells in a row is all blanks or all marks.

Two cards are different when some position carries a different kind of cell. Return how many steady cards exist, taken modulo 1000000007.

Examples

Example 1

Input
zero = 1, one = 2, limit = 1
Output
1

With a cap of one, no two neighbouring cells may match. Only the card reading mark, blank, mark satisfies that while carrying one blank and two marks.

Example 2

Input
zero = 2, one = 2, limit = 1
Output
2

A cap of one forces the kinds to alternate, so the card either opens with a blank or opens with a mark, giving two steady cards.

Example 3

Input
zero = 3, one = 3, limit = 2
Output
14

Cards such as blank, blank, mark, blank, mark, mark are steady, since no three cells in a row match. Counting every such card gives this many.

Constraints

  • 1 <= zero <= 1000
  • 1 <= one <= 1000
  • 1 <= limit <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def steady_layouts(zero: int, one: int, limit: int) -> int:
Java
public int steadyLayouts(int zero, int one, int limit)

More on the same topics