Problem #93
Tags:
data-structures
popular-algorithm
sorting
c-1
c-0
Once upon a time there was a famine in the country. Luckily the Friars of the CodeAbbey invented a device producing food from the solar or wind energy. That is how the land was saved.
This story gives us the task on usage of Priority Queue which can be implemented with either Binary Heap or a simple array (though inefficiently).
Imagine that about 10000 hungry visitors came to monastery during the day. Each has some degree of starvation
expressed by the positive integer not exceeding 999.
New visitor arrives each second, so the first comes at the moment t = 0, next at the moment t = 1 etc.
Food machine also starts working at t = 0 and produces new ration each 2 seconds. The ration is given
to one of the persons already arrived with the greatest degree of starvation.
So the example of beginning of the day may look like:
t = 0 - visitor with degree 5 arrives
t = 1 - visitor with degree 7 arrives
t = 2 - a unit of food is produced and is given to visitor with degree 7, he leaves
t = 2 - visitor with degree 2 arrives
t = 3 - visitor with degree 3 arrives
t = 4 - a unit of food is produced and is given to visitor with degree 5, he leaves
t = 4 - visitor with degree 8 arrives
...
Note that on even-numbered seconds monks at first distribute food among the visitors already waiting in the queue and only then receive a newcomer.
By and by the daily flow of people ends, so for example if N visitors are to come, then starting from t = N no
more visitors are added to queue.
However food generator continues working at the same speed, until the last visitor is fed at t = 2 * N.
Friars are interested in improving the routine, so they want to calculate the "total discomfort" of starving people (and perhaps to find a way of reducing it). Your task is to help thim with this computation.
Total discomfort is the sum over each people of their personal discomforts, which in turn are expressed as:
personal_discomfort = starvation_degree * (feeding_time - arrival_time)
So for example if the visitor with degree 7 came at moment t = 1 and was fed at moment t = 2 his personal
discomfort is
7 * (2 - 1) = 7
Another, with degree 5, arriving at t = 0 and fed on t = 4 has discomfort of 20, etc. Of course the degree
of starvation does not increase during the day.
Data generation
You are to generate input data for this problem using Linear Congruential Generator
with parameters A = 445, C = 700001, M = 2097152 - and initial value X0 will be given to you.
For each next visitor generate the random value and convert it using the formula:
starvation_degree = (rnd % 999) + 1
So you will only need the total amount of visitors N and the seed for random generator X0.
Input data contain N - number of visitors and X0 - the seed for randomizer in a single line.
Answer should contain a single value - total discomfort of people who come this day to Abbey.
Example:
input data:
7 0
answer:
7572
Note that result in most cases will not fit into standard 32-bit integer.
Explanations
For the sake of simplicity, let us use in this example starvation_degree in the range 1 ... 9, i.e. generated by
formula with smaller divisor:
starvation_degree = (rnd % 9) + 1
Your randomizer will give you 7 numbers in this case:
700001 1821950 1967079 1537772 1336989 68938 2017283
So timeline will look like:
t = 0 - visitor with degree 9 came
t = 1 - visitor with degree 9 came
t = 2 - visitor with degree 9 left (+18), visitor with degree 4 came
t = 3 - visitor with degree 6 came
t = 4 - visitor with degree 9 left (+27), visitor with degree 4 came
t = 5 - visitor with degree 8 came
t = 6 - visitor with degree 8 left (+8), visitor with degree 6 came
t = 8 - visitor with degree 6 left (+30)
t = 10 - visitor with degree 6 left (+24)
t = 12 - visitor with degree 4 left (+40)
t = 14 - visitor with degree 4 left (+40)
----- -----
total: 187