Fișierul intrare/ieșire monede.in, monede.out Sursă ONI 2014 baraj gimnaziu
Autor Dana Lica Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1 sec Limită de memorie 10240 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in monede.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici