BasePlacement
SRM 789 · 2020-08-28 · by misof
Problem Statement
Time limit for this problem is 3 seconds.
This problem is about a plan-conquering board game. The board is a rectangle divided into R times C cells. The cells have coordinates (0, 0) to (R-1, C-1). Cells are adjacent if they share a side.
Each cell may contain a base. There can be at most one base per cell. Bases cannot be adjacent. Additionally, there cannot be any cell that would be adjacent to more than one base.
It is now our turn. Our strategy for the game dictates that we should place at least B bases in our first turn. In how many ways can we do that? Return that count modulo 10^9 + 7.
Constraints
- R and C will be positive.
- R * C will not exceed 190.
- B will be between 0 and R*C, inclusive.
2 3 1 Returns: 8
We can either place one base (2*3 = 6 options), or two bases. There are two ways to place two bases: they have to go into two opposite corners of the board.
8 10 2 Returns: 744999783
There are exactly 2,744,999,797 ways to place at least two bases onto this board. Remember that 744,999,783 is that count modulo 10^9 + 7.
10 10 47 Returns: 0
There is no way to fit 47 bases onto this board, and it's not even close.
1 1 1 Returns: 1
13 14 1 Returns: 218018740
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BasePlacement with a public method int count(int R, int C, int B) · 81 test cases · 2 s / 256 MB per case