| Solutie:
| Se porneste de la cifra de ordin maxim, pe care o marim pana la cea mai mare valoare posibila cu cat mai putine modificari. Daca mai raman modificari disponibile trecem la cifra a doua si asa mai departe pana epuizam modificarile la care avem dreptul sau pana cand nu mai e posibila nici o marire de cifre. Avem nevoie de un tablou in care pentru fiecare cifra sa memoram numarul minim de modificari prin care poate fi transformata in 0,1,2,...9. In termeni de teoria grafurilor trebuie sa aflam distantele minime dintre doua noduri intr-un graf orientat in care nodurile sunt cele 10 cifre iar muchiile sunt date de matricea de adiacenta din fisierul de intrare. Dat fiind numarul mic de noduri se pot afla aceste distante minime si fara algoritmi de teoria grafurilor.
Algoritm concurs
citeste n,k
pt. i=1,n citeste c[i] (cifrele numarului)
pt. i=0,9
pt. j=0,9 citeste Aij sf.
sf.
Construieste matricea D
i=1
repeta
j=9
cat timp D[c[i],j]>=k j=j-1 sf.
daca j>i
k=k-D[c[i],j]; c[i]=j
sf.
i=i+1
pana cand k=0 sau i>n
sf. algoritm
Procedura Construieste matricea D
pt. i=0,9
pt. j=0,9 v[j]=0 sf.
pt. j=0,9
daca Aij=1 Dij=infinit; v[j]=1
altfel Dij=infinit sf.
Dii=0; v[i]=1
sf.
repeta
modif=0
pt. j=0,9
daca 0<Dij<infinit
pt. k=0,9
daca Ajk=1 si Dik=infinit Dik=Dij+1; modif=1 sf.
sf.
sf.
sf.
pana cand modif=0
sf.
|
