FloorTile | Topcoder Archive

Problem Statement

The new TopCoder building has a huge room; it happens to be 2^k meters by 2^k 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 int k, and returns an int representing the minimum total cost of tiling the floor.

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
```
```
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

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.