Tile

SRM 114 · 2002-09-24 · by chogyonim

Class Name: Tile

Return Type: int

Method Name: composite

Arg Types: (vector<string>)

Problem Statement

Given a set of tile dimensions, return the number of different combinations of the tiles whose areas add up to 64. The calculation for the area of a tile is:

area = width * height

For example, given 16 2x2 tiles, the only possibility is to use all 16 of the tiles, so there is only 1 combination. Given 17 2x2 tiles, any one of the 17 can be left out, so there are 17 combinations.

The set will be represented as a String[], with each element formatted as (quotes added for clarity):

"#x#", where '#' represents a dimension of the tile (an integer).

If there are more than 100,000 combinations, return -1.

Notes

If there are more than 100,000 combinations, return -1.
Each tile may only be used once.

Constraints

tiles will contain between 1 and 50 elements, inclusive.
each element will be formatted as "#x#" (quotes added for clarity), where each '#' represents an integer between 1 and 4, inclusive, and a single lowercase 'x' is between them.

Examples

{"2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2"}
Returns: 1

{"2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2"}
Returns: 17

{"2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2","2x2","2x2",
 "2x2","2x2"}
Returns: 153

Since there are 18 different tiles and 16 must be chosen, there 153 different combinations.

{"1x1","1x1","1x1","1x1","1x1","1x1","1x1","1x1"}
Returns: 0

There is no way to get an area of 64.

{"4x4","4x3","4x2","4x1",
 "3x4","2x2","2x2","1x4",
 "1x3","4x2","4x3","4x4",
 "3x3","3x3","3x3","3x2",
 "3x4","2x4","2x3","2x1",
 "1x1","1x1"}
Returns: 53725

{"4x4","4x3","4x2","4x1",
 "3x4","2x2","2x2","1x4",
 "1x3","4x2","4x3","4x4",
 "3x3","3x3","3x3","3x2",
 "3x4","2x4","2x3","2x1",
 "1x1","1x1","4x4","4x4",
 "4x4","4x4","1x1","1x1"}
Returns: -1

There are more than 100,000 combinations.

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

Coding Area

Language: C++17 · define a public class Tile with a public method int composite(vector<string> tiles) · 31 test cases · 2 s / 256 MB per case