Problem S. 89. (April 2014)

S. 89. A school has \(\displaystyle N\) students, standing in a big circle on the last school day before vacation. Each student should be given a certain number of chocolate bars: the number of chocolate bars is equal to the number of reward points (denoted by \(\displaystyle a_i\)) they had collected during the school year. Unfortunately, due to a flaw in the logistic system, they mixed up these numbers. So the chocolate bars were just somehow distributed along the circle in \(\displaystyle N\) heaps: the \(\displaystyle i^\mathrm{th}\) heap contained \(\displaystyle b_i\) bars. Although the total number of distributed chocolate bars was correct, yet the probability that each student would get the correct number of bars this way is quite low. Therefore one student reorders the heap so that the \(\displaystyle i^\mathrm{th}\) heap contains \(\displaystyle a_i\) bars. During this reordering process, he can grasp some bars from a heap and can put them into another, arbitrary heap. The number of seconds needed to relocate a particular chocolate bar is equal to the distance of the corresponding two heaps along the perimeter. By performing such steps, the chocolate bars are finally rearranged as originally planned. The goal is to do this as quickly as possible. Your task is to give the minimal time needed to complete the redistribution.

Bounds:

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

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

Your program should read the value of \(\displaystyle N\) from the first line of the standard input, then the integers \(\displaystyle a_i\), \(\displaystyle b_i\) (separated by a space) from the following \(\displaystyle N\) lines. Your program should write the necessary minimal time to properly hand out the chocolate bars to the first and only line of the standard output.

In the example, ``Példa bemenet'' is a possible input and ``Példa kimenet'' is the corresponding output.

Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any arbitrary valid input within 1 second of running time. Partial points can be obtained if your program yields a solution

\(\displaystyle \bullet\) for \(\displaystyle N\le 200\), or

\(\displaystyle \bullet\) for \(\displaystyle N\le 5000\).

The source code (s89.pas, s89.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s89.txt, s89.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file s89.zip.

(10 pont)

Deadline expired on May 12, 2014.

Sorry, the solution is available only in Hungarian. Google translation

Mintamegoldás: sol.cpp

Statistics:

7 students sent a solution.
10 points:	Makk László, Somogyvári Kristóf, Szécsi Péter, Weisz Ambrus, Zalavári Márton.
1 point:	1 student.
0 point:	1 student.

Problems in Information Technology of KöMaL, April 2014