La o fabrica de bomboane,
sunt puse pe un stand n
cutii de bomboane. Fiecare dintre cele n
cutii contine câte m bomboane
dintr-un singur sortiment. Toate cele n
sortimente sunt distincte. Un muncitor mai distrat începe sa se amuze si amesteca
bomboanele din cutii. Pentru a nu fi observata modificarea, el are grija ca
în fiecare cutie sa ramâna câte mbomboane.
Necazul apare când seful
sau îi cere sa-i aduca câte o bomboana din fiecare cutie, deci o bomboana din
fiecare sortiment. Fiind urmarit de catre acesta, muncitorul nu va avea voie
sa extraga decât o bomboana din fiecare cutie.
Muncitorul a asociat fiecarei
extrageri un grad de risc. Astfel, la extragerea unei bomboane din sortimentul
cu numarul i din cutia
care continea initial sortimentul cu numarul j,
gradul de risc va fi valoarea absoluta a diferentei dintre isi j. Gradul total
de risc este egal cu suma riscurilor tuturor celor n
extrageri.
Cerinta
Sa se determine ce sortiment
de bomboana va trebui sa extraga muncitorul din fiecare cutie pentru ca gradul
de risc total sa fie minim.
Date de intrare
Pe prima linie a fisierului
bomboane.in sunt scrise
numerele n si m
separate printr-un spatiu. Pe fiecare dintre urmatoarele n
linii se gasesc câte m
numere separate prin cate un spatiu. Cele m
numere de pe linia i+1
reprezinta sortimentele bomboanelor ce se gasesc în cutia
i dupa amestecare.
Date de iesire
Fisierul de iesire bomboane.out
va continedoua linii:
- pe prima linie se va scrie un numar natural reprezentând gradul total minim de risc
- pe a doua linie sunt scrise n
numere separate prin cate un spatiu ; al i-lea
numar de pe linie reprezinta numarul de ordine al cutiei din care va fi extrasa
bomboana din sortimentul i.
În cazul în care exista mai multe posibilittati de extragere cu risc total minim, se va afisa una singura.
Restrictii
0 < n < 101
0 < m < 1001
Exemplu
bomboane.in
bomboane.out
7 3
1 2 7
6 6 4
4 7 3
4 2 3
2 1 3
7 5 1
5 5 6
10
1 5 3 4 7 2 6
Prof.
Dana Lica Colegiul Naţional "I.L. Caragiale" Ploieşti Contact:danal182001@yahoo.com