Fişierul intrare/ieşire:monede.in, monede.outSursăONI 2014 baraj gimnaziu
AutorDana LicaAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie10240 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Monede (baraj gimnaziu)

Notă: această problemă are o mică modificare făcută pentru clarificarea enunţului. Textul tăiat face parte din enunţul vechi, nu şi din problema curentă.

Gigel este extrem de pasionat de numismatică şi din această cauză colecţionează monede. Ca să le păstreze el le-a grupat în N şiruri, numerotate de la 1 la N, ce cuprind fiecare câte M teancuri de monede. În cadrul unui şir, teancurile sunt numerotate de la 1 la M în ordine de la stânga la dreapta. Fiecare teanc conţine un număr oarecare de monede. Lui Gigel i se permite un singur tip de operaţie: mutarea unui număr oarecare de monede dintr-un teanc şi plasarea acestora într-un alt teanc, situat în alt şir.

Gigel doreşte ca toate teancurile cu numărul i (pentru orice 1≤i≤M), din toate cele N şiruri, să conţină acelaşi număr de monede. Pentru aceasta poate efectua oricâte operaţii permise doreşte.

Cerinţă

Scrieţi un program care determină numărul minim de monede care trebuie mutate de Gigel prin operaţii permise astfel încât la final toate teancurile să respecte regula descrisă în enunţ.

Date de intrare

Fişierul de intrare monede.in conţine pe prima linie două numere naturale N şi M, separate printr-un spaţiu, reprezentând numărul de şiruri, respectiv numărul de teancuri din fiecare şir. Pe fiecare dintre următoarele N linii se află câte M numere naturale nenule, separate prin câte un spaţiu, reprezentând numărul de monede din fiecare teanc, în ordine de la stânga la dreapta.

Date de ieşire

Fişierul de ieşire monede.out va conţine o singură linie pe care va fi scris numărul minim de monede determinat.

Restricţii

  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 1000
  • 0 ≤ numărul iniţial de monede din fiecare teanc ≤ 10000
  • Se garantează că orice test admite soluţie

Exemplu

monede.inmonede.outExplicaţie
2 4
1 2 7 5
4 2 9 6
3
Se ia o monedă din primul teanc din al doilea şir şi o plasăm pe teancul al patrulea din primul şir. Se obţine:
1 2 7 6
3 2 9 6
Se iau două monede din al treilea teanc din şirul doi şi se plasează în primul teanc din primul şir. Se obţine:
3 2 7 6
3 2 7 6
Observaţi că după efectuarea a două operaţii permise, în care s-au mutat în total 3 monede, teancurile cu acelaşi
număr de ordine conţin acelaşi număr de monede. Există şi alte succesiuni de operaţii permise, prin care se poate
obţine acelaşi număr minim de monede mutate (3).
Trebuie sa te autentifici pentru a trimite solutii. Click aici