Risc
Limbajele de programare acceptate: Pascal, C și C++
Compilatoarele utilizate: Borland Pascal 7.0 și Borland C++ 3.1
Descrierea problemei
După ce au revenit de la culesul fructelor, elfii au format n grămezi de fructe, fiecare conținând câte m fructe. Fructele dintr-o grămadă sunt de acelați tip, dar fiecare grămadă conține fructe de tipuri diferite.
Un elf mai distrat începe să se amuze și să
amestece fructele din grămezi. În speranța că jocul său nu va fi
observat, el are grijă ca în fiecare dintre grămezi să rămână exact m fructe.
Totuși, un străjer a observat că el s-a jucat
cu fructele și îi cere acestuia să aducă câte un fruct de fiecare tip
(din fiecare grămadă).
Din nefericire pentru elf, străjerul a acoperit
grămezile de fructe pentru ca elful să nu vadă ce fructe alege. Ca
urmare, elful va trebui să aleagă, aproape la întâmplare, câte un fruct
din fiecare grămadă.
Elful acordă fiecărei extrageri un grad de risc. Astfel, la alegerea unui fruct de tipul i din grămada care conținea la început fructe de tipul k, gradul de risc va fi valoarea absolută a diferenței dinre i și j.
Gradul de risc al tuturor alegerilor va fi dat de suma gradelor de risc ale alegerilor individuale.
Elful dorește să determine ce tip de fructe va
trebui să aleagă din fiecare grămadă pentru ca gradul total de risc
(pentru toate alegerile) să fie cât mai mic posibil.
Date de intrare
Prima linie a fișierului de intrare INPUT.TXT conține numărul n al grămezilor de fructe.
Cea de-a doua linie conține numărul m al fructelor din fiecare grămadă.
Fiecare dintre următoarele n linii va conține câte m numere, separate prin câte un spațiu. Cele m numere reprezintă tipurile de fructe care se găsesc în fiecare grămadă, după ce elful s-a jucat cu fructele. Pe
prima linie se vor afla fructele din grămada cu numărul 1, pe a doua
linie se vor afla fructele din grămada cu numărul 2 și așa mai departe
până la grămada cu numărul n.
Date de ieșire
Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie un număr care reprezintă cel mai mic grad total de risc posibil.
Fiecare dintre următoarele n
va conține câte un număr întreg. Acest număr va reprezenta numărul de
ordine al unei grămezi din care se va alege un anumit tip de fructe.
Ordinea liniilor va fi dată de numerele de ordine ale tipurilor de
fructe.
Restricții și precizări
numărul de grămezi este cuprins între 1 și 100;
numărul de fructe din fiecare grămadă este cuprins între 1 și 1000;
tipurile de fructe și grămezile sunt identificate prin numere cuprinse între 1 și n;
în cazul în care există mai multe posibilități de alegere cu risc total minim, se poate determina doar una dintre ele.
Exemplu
INPUT.TXT
7
3
1 2 7
6 6 4
4 7 3
4 2 3
2 1 3
7 5 1
5 5 6
OUTPUT.TXT
10
1
5
3
4
7
2
6
Timp de execuție: 5 secunde/test
|