ShrooksOnTheBoard
TCO10 Wildcard · 2010-04-11 · by dkorduban
TCO10 Wildcard · 2010-04-11 · by dkorduban · Dynamic Programming, Math
Problem Statement
Problem Statement
A K-shrook is a fairy chess piece that can move horizontally in both directions for at most K squares. Here is an illustration of 2-shrook possible moves:
Two K-shrooks attack each other if one of them can reach the other shrook's square in one move. You are given a board with H rows and W columns. Find out the number of ways to place an arbitrary positive amount of K-shrooks on this board so that no two of them attack each other. Return this number modulo 100003.
Two K-shrooks attack each other if one of them can reach the other shrook's square in one move. You are given a board with H rows and W columns. Find out the number of ways to place an arbitrary positive amount of K-shrooks on this board so that no two of them attack each other. Return this number modulo 100003.
Constraints
- K will be between 1 and 1,000,000,000, inclusive.
- H will be between 1 and 1,000,000,000, inclusive.
- W will be between 1 and 1,000,000,000, inclusive.
Examples
0)
1 1 3 Returns: 4
The possible placements are "S..", ".S.", "..S" and "S.S".
1)
1 2 2 Returns: 8
There can not be more than 1 shrook in a row.
2)
3 4 9 Returns: 56963
3)
34 83489 98433 Returns: 98118
random medium test
4)
65 93284923 819847362 Returns: 94567
random big test for MatrixMul
5)
212 187342874 992837462 Returns: 92273
random big test for DP
Submissions are judged against all 178 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ShrooksOnTheBoard with a public method int count(int K, int H, int W) · 178 test cases · 2 s / 256 MB per case