Jaher's suitcase P52363


Statement
 

pdf   zip

html

[r]

Jaher is a brilliant algorithmist, but he is also a bit absent minded. For example, he has some difficulties making things fit into his suitcase. Can you help him?

For simplicity, let us assume a two-dimensional suitcase a × b, where n rectangular objects must fit. Objects can be placed at any position within the suitcase, without overlap, but they can not be rotated. In how many ways can we put the objects?

Input

Input consists of several cases. Each case begins with a, b and n. Follow n pairs of strictly positive natural numbers, which indicate the sizes of the objects. The area of the objects exactly covers the suitcase, and there is always at least one possible solution. (The first case in the sample input corresponds to the picture.)

Output




[r]

For every suitcase, print a line with its number and how many possible solutions exist.

Public test cases

  • Input

    4 5 6
1 5   3 1   1 1   1 4   2 3   1 1

2 3 2
2 2   2 1

1 1 1
1 1

1 5 3
1 1   1 2   1 2

6 8 10
3 4   1 6   2 3   1 1   2 2
1 4   2 1   2 5   1 2   1 1

    Output

    #1: 32
#2: 2
#3: 1
#4: 6
#5: 4384
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++