Candale Silviu (silviu) Pentru a putea ţine evidenţa mai uşor, administratorul unui magazin întocmeşte o listă cu produsele care se găsesc în magazin la începutul zilei. El scrie numele produselor, folosind cuvinte de aceeaşi lungime, formate doar din literele mici ale alfabetului englez. Îndată finalizată lista, el îi asociază un cod reprezentând cel mai mic cuvânt în sens lexicografic, obţinut prin preluarea unei litere din fiecare nume de produs, în ordinea în care acestea au fost scrise pe listă.
El observă că acest cod poate fi obţinut în mai multe moduri. Doreşte însă să identifice varianta în care literele alese sunt cât mai apropiate, altfel spus, distanţa, reprezentând numărul de poziţii, între poziţia cea mai mică şi poziţia cea mai mare pe care sunt plasate caracterele alese, este minimă. De exemplu:
Pentru lista care cuprinde produsele de mai jos:
| c | a | i | e | t |
| l | a | p | t | e |
| m | i | e | r | e |
| c | a | f | e | a |
Codul asociat este: aaea
O variantă de obţinere în care distanţa este 4. Poziţia literei a din al doilea cuvânt este 2 iar a lui e, ales în al treilea cuvânt este 5:
| c | a |
i | e | t |
| l | a |
p | t | e |
| m | i | e | r | e |
| c | a |
f | e | a |
Varianta optimă este caracterizată de distanţa 2. deoarece, poziţia minimă a unui caracter ales este 2 iar cea maximă este 3:
| c | a |
i | e | t |
| l | a |
p | t | e |
| m | i | e |
r | e |
| c | a |
f | e | a |
Cerința
Scrieţi un program care să determine codul asociat listei de produse şi distanţa minimă prin care poate fi obţinut.
Date de intrare
Fișierul de intrare minime.in conține pe prima linie o pereche de numere naturale N şi M reprezentând numărul de produse scrise pe listă şi numărul de litere ale fiecărui nume de produs. Pe următoarele N linii se găsesc şiruri de câte M caractere litere mici reprezentând numele produselor, în ordinea în care au fost scrise în listă.
Date de ieșire
Fișierul de ieșire minime.out va conține 2 linii:
a) pe prima linie, se va afişa un şir de caractere format din N litere mici reprezentând codul asociat listei;
b) pe a doua linie, se va scrie un număr natural reprezentând distanţa minimă în care poate fi obţinut;
Restricții și precizări
1 ≤ N ≤ 100 0001 ≤ M ≤ 255
- numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât
1.000.000.000
Exemplu:
minime.in
5 5 inele cacao ardei lapte peste
minime.out
eaaae 3
Explicație
Distanţa minimă este 3 şi se obţine astfel:
| i | n | e |
l | e |
| c | a |
c | a | o |
a |
r | d | e | i |
| l | a |
p | t | e |
| p | e |
s | t | e |