Nombres sense prefixos prohibits P83364


Statement
 

pdf   zip

html

Feu un programa que usi backtracking per escriure tots els nombres de n dígits tals que cap dels seus prefixos (ell inclòs) sigui múltiple de cap de m divisors prohibits donats d1, …, dm.

Per exemple, si n = 3, m = 6 i els divisors prohibits són 2, 3, 5, 7, 11 i 19, llavors 137 està permès, perquè cap dels seus tres prefixos 1, 13 i 137 és múltiple de cap di. En canvi, 433 no està permès, perquè dels seus tres prefixos 4, 43 i 433, n’hi ha algun que és múltiple d’algun di (4 és múltiple de 2).

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguits de m enters diferents entre 2 i 1000. Podeu suposar que 1 ≤ n ≤ 9 i 1 ≤ m ≤ 15.

Sortida

Per a cada cas, escriviu tots els nombres que tenen exactament n dígits i no tenen prefixos prohibits, un per línia i de petit a gran. Escriviu una línia amb 10 guions al final de cada cas.

Public test cases
  • Input

    3 6
    2 3 5 7 11 19
    1 1
    2
    2 6
    3 4 7 11 12 13
    2 9
    2 3 5 7 9 11 13 17 19
    9 10
    199 191 193 17 13 11 7 5 3 2
    

    Output

    131
    137
    139
    173
    179
    ----------
    1
    3
    5
    7
    9
    ----------
    10
    17
    19
    23
    25
    29
    50
    53
    58
    59
    ----------
    ----------
    197399999
    197933933
    197933993
    197933999
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++