FloorTile
SRM 131 · 2003-01-30 · by pmadden
Problem Statement
The new TopCoder building has a huge room; it happens to be 2k meters by 2k meters. We have to renovate the room before use, by installing floor tiles. There are two types of tiles available: 1 meter square tiles that cost $1 each, and unusual "L" shaped tiles which are also $1 each. The "L" tiles are shaped as shown below.
#
##
The "#" marks indicate tile. You can think of the tiles as 2 meter by 2 meter squares with a 1 meter by 1 meter square removed from a corner. When tiling a floor, we can rotate or flip these tiles any way required.
We want to cover the entire floor with tile for the minimum total cost possible. No two tiles can overlap.
Create a class FloorTile which contains a method mincost that takes an
Constraints
- k will be between 0 and 10 inclusive
1 Returns: 2
With a k of 1, we have a 2 by 2 room to tile. We can use a single square tile, and a single "L" shaped tile. One possible configuration is shown below; "S" indicates the square tile, and "a" indicates part of the "L" tile. Sa aa The "L" shaped tile has been rotated.
2 Returns: 6
With a k of 2, we have a 4 by 4 room. If we place a single square tile in the location indicated, we can cover the remainder of the room with "L" shaped tiles. This example has a capital "S" to indicate the location of the square, and letters "a", "b", "c", ..., to indicate the locations of "L" shaped tiles. ccbS cabb daae ddee
5 Returns: 342
10 Returns: 349526
8 Returns: 21846
4 Returns: 86
An 8 by 8 room can be tiled as shown below; "S" denotes the locations of square tiles. ppllrroo pjjlrkko mjrrnnkt mmrbbntt qquubadd qScuaaed iccgfeeh iiggffhh
Submissions are judged against all 20 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FloorTile with a public method int mincost(int k) · 20 test cases · 2 s / 256 MB per case