Az S. 89. feladat (2014. április)

S. 89. Egy iskolába \(\displaystyle N\) gyerek jár, akik az évzáró alkalmával egy nagy körben álltak fel az iskolaudvaron. Minden gyereknek annyi csokit kell kapnia év végén, amennyi piros pontot évközben gyűjtött, legyenek ezek az \(\displaystyle a_i\) számok. Sajnos a beszállító nem tudta megjegyezni, hogy kinek mennyi csoki jár, így a hozott csoki mennyiséget valahogy letette \(\displaystyle N\) kupacba a körben a gyerekek elé. A \(\displaystyle i\)-edik kupacba \(\displaystyle b_i\) darab csokit került. A beszállító annyi csokit hozott, amennyit a gyerekeknek összesen szét kell osztani, de így valószínűleg kevés gyerek kapna annyit, amennyit megérdemel. Ezért a következőt találták ki: a diákönkormányzat vezetője megpróbálja átrendezni a csokikat úgy, hogy az \(\displaystyle i\)-edik kupacban \(\displaystyle a_i\) darab legyen az átrendezés végén. Ehhez felemelhet egy kupacból néhány csokit, és leteheti egy tetszőleges kupachoz. Egy csoki áthelyezése annyi másodpercbe kerül, amennyi a két kupac távolsága a kör kerületén haladva. Ilyen lépések egymásutánjával fogják úgy átrendezni a csokikat, hogy megfeleljen a kívánalmaknak. Sajnos a rendezgetés miatt csúszik az évzáró, így minél gyorsabban meg kell oldani a problémát. Adjuk meg, hogy legalább mennyi időt vesz igénybe az átrendezés.

Korlátok:

\(\displaystyle \bullet\) \(\displaystyle 1 \le N \le 100\;000\);

\(\displaystyle \bullet\) \(\displaystyle 1 \le a_i, b_i \le 1000\).

A program olvassa be a standard input első sorából \(\displaystyle N\)-et, majd a következő N sorból az \(\displaystyle a_i\), \(\displaystyle b_i\) szóközzel elválasztott egészeket. Írja a standard output első és egyetlen sorába a szükséges minimális csoki átadások idejét.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Részpontszámok a következőkre kaphatóak:

\(\displaystyle \bullet\) a program \(\displaystyle N\le 200\)-ra megoldást ad;

\(\displaystyle \bullet\) program \(\displaystyle N\le 5000\)-re megoldást ad.

Beküldendő egy tömörített s89.zip állományban a program forráskódja (s89.pas, s89.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s89.txt, s89.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2014. május 12-én LEJÁRT.

Mintamegoldás: sol.cpp

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Makk László, Somogyvári Kristóf, Szécsi Péter, Weisz Ambrus, Zalavári Márton.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2014. áprilisi informatika feladatai