La maleta d'en Jaher P52363

Statement

thehtml

[r]

En Jaher és un algorismista brillant però bastant distret. Per exemple, li costa posar les coses bé dins de la maleta. El podeu ajudar?

Per simplicitat, suposeu una maleta bidimensional, de mides a × b, on cal encabir-hi n objectes rectangulars. Els objectes es poden posar sense solapaments a qualsevol posició dins de la maleta, però no es poden girar. De quantes maneres es poden posar?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb a, b i ‍n. Segueixen n parells de naturals estrictament positius que indiquen les dimensions dels objectes. La seva superfície cobreix exactament la maleta, i sempre hi haurà com a mínim una possible solució. (El primer cas de l’exemple d’entrada es correspon al dibuix.)

Sortida

[r]

Per a cada maleta, escriviu una línia amb el seu número i el nombre de possibles solucions.

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: Catalan
Other languages: English
Official solutions: C++
User solutions: C++