La maleta d'en Jaher P52363


Statement
 

pdf   zip

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