Dígits en ordre òptim P46547


Statement
 

pdf   zip

thehtml

Donat dos naturals m i n, heu de construir un nombre x amb els dígits {1, …, n} (exactament un de cada) de manera que cap prefix (no buit) d’x sigui múltiple d’m. Per exemple, amb m=3 i n=4, x=2314 no és un ordre vàlid, perquè 231 és múltiple de 3. En canvi, x=4312 sí que és un ordre vàlid, perquè ni 4, ni 43, ni 431, ni 4312 són múltiples de 3.

A més, teniu una matriu M[1..n][1..n] tal que M[i][j] indica el premi que s’aconsegueix si es posa el dígit j immediatament a la dreta del dígit i. Maximitzeu la suma total de premis.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb m i n, seguits d’M: n files, cadascuna amb n naturals entre 1 i 106, excepte la diagonal, que conté zeros. Podeu suposar 3 ≤ m ≤ 1000 i 2 ≤ n ≤ 9.

Sortida

Per a cada cas, escriviu el màxim premi possible. Si no es pot construir cap x, escriviu 0.

Public test cases
  • Input

    10 2
    0 4
    3 0
    
    6 2
    0 1000000
    1 0
    
    3 3
    0 7 7
    7 0 7
    7 7 0
    
    3 4
       0  1  2    3
    1000  0  4 2000
       5  6  0    7
       8  9  1    0
    

    Output

    4
    1
    0
    18
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python