Múltiples de 7 (1) P45672


Statement
 

pdf   zip

html

Calculeu quants nombres amb n dígits són múltiples de 7 i no tenen dígits adjacents repetits. Per senzillesa, els nombres poden començar en 0. Alguns dels dígits poden estar fixats.

Per exemple, amb n = 2 n’hi ha 13: 07, 14, …, 70, 84, 91, 98. Però si afegim la restricció que el nombre ha de començar en 7, només n’hi ha un: el 70. (Aquests són els dos primers casos de l’Exemple d’entrada.)

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i el nombre de restriccions r. Segueixen r restriccions, cadascuna amb una posició i i un dígit d, indicant que a la posició i del nombre hi ha d’haver el dígit d. Suposeu 1 ≤ n ≤ 30, 0 ≤ rn, 0 ≤ i < n, 0 ≤ d ≤ 9, i que totes les posicions d’un cas són diferents.

Sortida

Per a cada cas, escriviu la quantitat de nombres que compleixen totes les condicions. Aquest nombre sempre estarà entre 1 i 106.

Public test cases
  • Input

    2 0
    2 1  0 7
    1 0
    10 5  1 4  7 8  5 0  9 5  6 4
    20 13  0 3  1 5  2 8  5 7  7 4  8 9  10 6  11 0  13 0  14 3  15 9  18 8  19 1
    

    Output

    13
    1
    2
    6749
    438500
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++