Pump up Batteries
Time Limit: 1 Second Memory Limit: 32768 KB
Bill is a boss of security guards. He has pride in that his men put on wearable
computers on their duty. At the same time, it is his headache that capacities
of commercially available batteries are far too small to support those computers
all day long. His men come back to the office to charge up their batteries and
spend idle time until its completion. Bill has only one battery charger in
the office because it is very expensive.
Bill suspects that his men spend much idle time waiting in a queue for the charger.
If it is the case, Bill had better introduce another charger. Bill knows that
his men are honest in some sense and blindly follow any given instructions or
rules. Such a simple-minded way of life may lead to longer waiting time, but
they cannot change their behavioral pattern.
Each battery has a data sheet attached on it that indicates the best pattern
of charging and consuming cycle. The pattern is given as a sequence of pairs
of consuming time and charging time. The data sheet says the pattern should
be followed cyclically to keep the battery in quality. A guard, trying to follow
the suggested cycle strictly, will come back to the office exactly when the
consuming time passes out, stay there until the battery has been charged for
the exact time period indicated, and then go back to his beat.
The guards are quite punctual. They spend not a second more in the office than
the time necessary for charging up their batteries. They will wait in a queue,
however, if the charger is occupied by another guard, exactly on first-come-first-served
basis. When two or more guards come back to the office at the same instance
of time, they line up in the order of their identification numbers, and, each
of them, one by one in the order of that line, judges if he can use the charger
and, if not, goes into the queue. They do these actions in an instant.
Your mission is to write a program that simulates those situations like Bill's
and reports how much time is wasted in waiting for the charger.
Input
The input consists of one or more data sets for simulation.
The first line of a data set consists of two positive integers separated by
a space character: the number of guards and the simulation duration. The number
of guards does not exceed one hundred. The guards have their identi.cation numbers
starting from one up to the number of guards. The simulation duration is measured
in minutes, and is at most one week, i.e., 10080 (min.).
Patterns for batteries possessed by the guards follow the first line. For each
guard, in the order of identification number, appears the pattern indicated
on the data sheet attached to his battery. A pattern is a sequence of positive
integers, whose length is a multiple of two and does not exceed fifty. The numbers
in the sequence show consuming time and charging time alternately. Those times
are also given in minutes and are at most one day, i.e., 1440 (min.). A space
character or a newline follows each number. A pattern is terminated with an
additional zero followed by a newline.
Each data set is terminated with an additional empty line. The input is terminated
with an additional line that contains two zeros separated by a space character.
Output
For each data set your program should simulate up to the given duration. Each
guard should repeat consuming of his battery (i.e., being on his beat) and charging
of his battery according to the given pattern cyclically. At the beginning,
all the guards start their cycle simultaneously, that is, they start their beats
and, thus, start their first consuming period.
For each data set, your program should produce one line containing the total
wait time of the guards in the queue up to the time when the simulation duration
runs out. The output should not contain any other characters.
For example, consider a data set:
3 25
3 1 2 1 4 1 0
1 1 0
2 1 3 2 0
The guard 1 tries to repeat 3 min. consuming, 1 min. charging, 2 min. consuming,
1 min. charging, 4 min. consuming, and 1 min. charging, cyclically. Yet he has
to wait sometimes to use the charger, when he is on his duty together with the
other guards 2 and 3. Thus, the actual behavior of the guards looks like:
0
10 20
| |
| | | |
guard 1: ***.**.****.***.**-.****.
guard 2: *.*-.*-.*-.*.*.*.*--.*.*-
guard 3: **.***--..**-.***..**.***
where "*" represents a minute spent for consuming, "." for
charging, and "-" for waiting in the queue. At time 3, the guards
1 and 2 came back to the office and the guard 1 started charging while the guard
2 went into the queue. At time 6, all the guards came back to the office and
the guard 1 started charging while the others went to the queue. When the charger
got available at time 7, the guard 2 started charging, leaving the guard 3 in
the queue. All those happened are consequences of rules stated above. And the
total time wasted in waiting for the charger becomes 10 minutes.
Sample Input
3 25 3 1 2 1 4 1 0 1 1 0 2 1 3 2 0 4 1000 80 20 80 20 80 20 80 20 0 80 20 0 80 20 90 10 80 20 0 90 10 0 0 0
Sample Output
10 110Submit
Source: Asia 2000, Tsukuba (Japan)