Starving Priority Queue
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
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
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.
You are to generate input data for this problem using Linear Congruential Generator
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
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.
input data: 7 0 answer: 7572
Note that result in most cases will not fit into standard
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