prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem D:</font> Pump up Batteries</H1>3 4<p>5Bill is a boss of security guards. He has pride in that his men put on wearable computers on their6duty. At the same time, it is his headache that capacities of commercially available batteries are7far too small to support those computers all day long. His men come back to the office to charge8up their batteries and spend idle time until its completion. Bill has only one battery charger in9the office because it is very expensive.10</p>11<p>12Bill suspects that his men spend much idle time waiting in a queue for the charger. If it is the13case, Bill had better introduce another charger. Bill knows that his men are honest in some14sense and blindly follow any given instructions or rules. Such a simple-minded way of life may15lead to longer waiting time, but they cannot change their behavioral pattern.16</p>17<p>18Each battery has a data sheet attached on it that indicates the best pattern of charging and19consuming cycle. The pattern is given as a sequence of pairs of consuming time and charging20time. The data sheet says the pattern should be followed cyclically to keep the battery in quality.21A guard, trying to follow the suggested cycle strictly, will come back to the office exactly when22the consuming time passes out, stay there until the battery has been charged for the exact time23period indicated, and then go back to his beat.24</p>25<p>26The guards are quite punctual. They spend not a second more in the office than the time27necessary for charging up their batteries. They will wait in a queue, however, if the charger is28occupied by another guard, exactly on first-come-first-served basis. When two or more guards29come back to the office at the same instance of time, they line up in the order of their identifi-30cation numbers, and, each of them, one by one in the order of that line, judges if he can use the31charger and, if not, goes into the queue. They do these actions in an instant.32</p>33<p>34Your mission is to write a program that simulates those situations like Bill’s and reports how35much time is wasted in waiting for the charger.36</p>37 38<H2>Input</H2>39 40<p>41The input consists of one or more data sets for simulation.42</p>43<p>44The first line of a data set consists of two positive integers separated by a space character: the45number of guards and the simulation duration. The number of guards does not exceed one46hundred. The guards have their identification numbers starting from one up to the number of47guards. The simulation duration is measured in minutes, and is at most one week, i.e., 1008048(min.).49 50</p>51 52<p>53Patterns for batteries possessed by the guards follow the first line. For each guard, in the order54of identification number, appears the pattern indicated on the data sheet attached to his battery.55A pattern is a sequence of positive integers, whose length is a multiple of two and does not exceed56fifty. The numbers in the sequence show consuming time and charging time alternately. Those57times are also given in minutes and are at most one day, i.e., 1440 (min.). A space character or58a newline follows each number. A pattern is terminated with an additional zero followed by a59newline.60</p>61<p>62Each data set is terminated with an additional empty line. The input is terminated with an63additional line that contains two zeros separated by a space character.64 65</p>66<H2>Output</H2>67 68<p>69For each data set your program should simulate up to the given duration. Each guard should70repeat consuming of his battery (i.e., being on his beat) and charging of his battery according71to the given pattern cyclically. At the beginning, all the guards start their cycle simultaneously,72that is, they start their beats and, thus, start their first consuming period.73</p>74<p>75For each data set, your program should produce one line containing the total wait time of the76guards in the queue up to the time when the simulation duration runs out. The output should77not contain any other characters.78</p>79<p>80For example, consider a data set:81</p>82 83<pre>843 25853 1 2 1 4 1 0861 1 0872 1 3 2 088</pre>89 90<p>91The guard 1 tries to repeat 3 min. consuming, 1 min. charging, 2 min. consuming, 1 min.92charging, 4 min. consuming, and 1 min. charging, cyclically. Yet he has to wait sometimes to93use the charger, when he is on his duty together with the other guards 2 and 3. Thus, the actual94behavior of the guards looks like:95</p>96 97<pre>98         0         10        2099         |    |    |    |    |    |100guard 1: ***.**.****.***.**-.****.101guard 2: *.*-.*-.*-.*.*.*.*--.*.*-102guard 3: **.***--..**-.***..**.***103</pre>104 105<p>106where “*” represents a minute spent for consuming, “.” for charging, and “-” for waiting in the107queue. At time 3, the guards 1 and 2 came back to the office and the guard 1 started charging108while the guard 2 went into the queue. At time 6, all the guards came back to the office and the109guard 1 started charging while the others went to the queue. When the charger got available110at 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 charger111becomes 10 minutes.112</p>113 114<H2>Sample Input</H2>115<pre>1163 251173 1 2 1 4 1 01181 1 01192 1 3 2 0120 1214 100012280 20 80 20 80 20 80 20 01238012420125012680 20 9012710 8012820129013090 101310132 1330 0134</pre>135 136<H2>Output for the Sample Input</H2>137<pre>13810139110140</pre>141 142