Connection Status:
Competition Arena > BearFills

BearFills

2015 TCO Parallel 3B · 2015-04-08 · by Errichto

2015 TCO Parallel 3B · 2015-04-08 · by Errichto · Greedy, Recursion
Class Name: BearFills
Return Type: long
Method Name: countSets
Arg Types: (int, long long, long long)
Problem Statement

Problem Statement

Bear Limak has a rectangular grid that consist of H times W unit square cells. Limak also has N square stamps. The lengths of the stamps' sides are 2^0, 2^1, ..., 2^(N-1).

A set of stamps is called good if it can be used to cover the entire grid. Each stamp must be placed along the grid lines. I.e., for each stamp each cell is either completely covered by the stamp or not covered at all. The stamps may overlap arbitrarily. The stamps may also cover areas outside of the grid. For example, you may use a 4x4 stamp just to cover a single cell in the corner of the grid.

You are given the int N and the longs H and W. Limak wants to choose a subset of his stamps that will be good. Return the number of ways in which he can do so.

Notes

  • N will be between 1 and 60, inclusive.
  • H and W will be between 1 and 10^18, inclusive.

Constraints

    Examples
    0)
    3
1
3
Returns: 5

    He has a 1x3 rectangle and 3 square stamps. The stamps' sides are 1, 2, and 4. The good sets of stamps are the following ones: (1,2), (1,2,4), (1,4), (2,4), and (4).

    1)
    3
3
5
Returns: 1

    He has a 3x5 rectangle and 3 square stamps. The stamps' sides are 1, 2, and 4. He needs all of them.

    2)
    60
3
2
Returns: 1152921504606846972

    He has a 3x2 rectangle and 60 square stamps. Only four sets are not good: (), (1), (2), and (1,2). The answer is 2^60-4.

    3)
    6
5
4
Returns: 56
    4)
    1
1
1
Returns: 1

    empty tests, could be changed into example

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

    Coding Area

    Language: C++17 · define a public class BearFills with a public method long long countSets(int N, long long W, long long H) · 93 test cases · 2 s / 256 MB per case

    Submitting as anonymous