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
Definition
- Class:
- FloorTile
- Method:
- mincost
- Parameters:
- int
- Returns:
- int
- Method signature:
- int mincost(int k)
- (be sure your method is public)
Constraints
- k will be between 0 and 10 inclusive
Examples
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
0
Returns: 1
3
Returns: 22
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
6
Returns: 1366
7
Returns: 5462
9
Returns: 87382
8
Returns: 21846
0
Returns: 1
4
Returns: 86
8
Returns: 21846
0
Returns: 1
4
Returns: 86
8
Returns: 21846
0
Returns: 1
4
Returns: 86