Nombres sense prefixos prohibits X07174
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.
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 ----------
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- Unknown.
- User solutions
- C++