Connection Status:
Competition Arena > PlankTiling

PlankTiling

TCO 2014 Semifinal 2 · 2014-03-26 · by snuke

TCO 2014 Semifinal 2 · 2014-03-26 · by snuke · Dynamic Programming, Simple Math
Class Name: PlankTiling
Return Type: int
Method Name: sumup
Arg Types: (int, int)
Problem Statement

Problem Statement

You have a sufficient supply of identical planks. Each plank has the shape of an 1 times H rectangle.


The floor of your room is also a rectangle. Its width is W and its height is 2H-1. You want to use the planks you have to tile the floor. The entire floor must be covered and the planks must not overlap. (The width W is guaranteed to be a multiple of H, so this is always possible.)


You are given the two ints H and W. Return the number of ways to tile the floor, modulo 1,000,000,007.

Constraints

  • H will be between 2 and 1000, inclusive.
  • W will be between 2 and 1000, inclusive.
  • W will be a multiple of H.
Examples
0)
2
4
Returns: 11

We are using 1x2 planks to tile a rectangle of width 4 and height 3. There are eleven different ways to do so:

1)
4
4
Returns: 5
2)
3
9
Returns: 121
3)
29
841
Returns: 193514715
4)
2
1000
Returns: 146530309

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

Coding Area

Language: C++17 · define a public class PlankTiling with a public method int sumup(int H, int W) · 88 test cases · 2 s / 256 MB per case

Submitting as anonymous