1 // 2008 ACM Mid-Central USA Regional Programming Contest
  2 // Solution to Problem D: "The Bridges of San Mochti" [easy/moderate]
  3 // Eric Shade, Missouri State University
  4 
  5 #include <iostream>
  6 #include <fstream>
  7 #include <algorithm>
  8 using namespace std;
  9 
 10 const int MAX_BRIDGES = 20 + 1;
 11 const int MAX_CROSSING_TIME = 100;
 12 
 13 int crossTime[MAX_BRIDGES]; // crossing time in seconds for bridge b
 14 int capacity[MAX_BRIDGES];  // max number of people who can cross bridge b
 15 int waiting[MAX_BRIDGES];   // number of people waiting to cross bridge b
 16 int unit[MAX_BRIDGES];      // people in unit currently crossing bridge b
 17 int timeLeft[MAX_BRIDGES];  // remaining time for unit crossing bridge b
 18 
 19 int bridges, people;
 20 
 21 
 22 void dumpState(int delta = 0, int total = 0) {
 23     for (int b = 0; b < bridges; b++) {
 24         cerr << waiting[b];
 25         if (unit[b] > 0)
 26             cerr << " /" << unit[b] << ":" << timeLeft[b] << "/ ";
 27         else
 28             cerr << " ";
 29     }
 30     cerr << waiting[bridges];
 31     if (delta > 0) cerr << " [+" << delta << " = " << total << "]";
 32     cerr << endl;
 33 }
 34 
 35 
 36 int main() {
 37     ifstream in("bridges.in");
 38 
 39     for (int config = 1; ; config++) {
 40         in >> bridges >> people;
 41 
 42         if (bridges == 0) break;
 43 
 44         bridges = -bridges;
 45 
 46         cerr << "CONFIGURATION " << config << endl;
 47 
 48         for (int b = 0; b < bridges; b++) {
 49             in >> capacity[b] >> crossTime[b];
 50             waiting[b] = unit[b] = timeLeft[b] = 0;
 51         }
 52 
 53         int seconds = 0;
 54         int crossing = 0;
 55 
 56         // everyone is initially waiting to cross the first bridge
 57         waiting[0] = people;
 58 
 59         // the bridges are numbered 0..(bridges-1), so waiting[bridges]
 60         // is really the number of people who have *crossed* the last bridge
 61         waiting[bridges] = 0;
 62 
 63         dumpState();
 64 
 65         while (waiting[bridges] < people) {
 66             int minTimeLeft = MAX_CROSSING_TIME;
 67 
 68             // put units on bridges, calculate minimum crossing time left
 69             for (int b = 0; b < bridges; b++) {
 70                 if (waiting[b] > 0 && unit[b] == 0) {
 71                     unit[b] = min(waiting[b], capacity[b]);
 72                     waiting[b] -= unit[b];
 73                     timeLeft[b] = crossTime[b];
 74                 }
 75                 if (timeLeft[b] > 0)
 76                     minTimeLeft = min(timeLeft[b], minTimeLeft);
 77             }
 78 
 79             seconds += minTimeLeft;
 80 
 81             // decrease crossing times by minTimeLeft, completing
 82             // crossings when time drops to zero
 83             for (int b = 0; b < bridges; b++) {
 84                 if (timeLeft[b] > 0) {
 85                     timeLeft[b] -= minTimeLeft;
 86                     if (timeLeft[b] == 0) {
 87                         waiting[b+1] += unit[b];
 88                         unit[b] = 0;
 89                     }
 90                 }
 91             }
 92 
 93             dumpState(minTimeLeft, seconds);
 94         }
 95 
 96         cout << seconds << endl;
 97     }
 98 
 99     in.close();
100 }