1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>

typedef long long ll;

typedef struct car {
  ll pos;  // The starting position. 
  ll len;  // The length of the car. (all in 1/carlen units). 
} car;

ll T;
std::vector<car> cars[3]; // Cars on 0 (fastest), 1, 2. I store the backs of cars.
ll bestpos[3];  // My best position (of my back) on lane 0 (fastest), 1, 2. Initially 0 on all
ll speed[3];  // Speed of cars on lanes 0 (fastest), 1, 2. How much I move in a unit of time.
ll myspeed;
ll carlen;
char road[200200];
ll inftytime;

// Position of back of car carIndex from lane, after time T.
ll calcPos(int carIndex, int lane, ll T) {
  return T * speed[lane] + cars[lane][carIndex].pos;
}

ll len(int carIndex, int lane) {
  return cars[lane][carIndex].len;
}

// Find the index of the next car that has it's front (the first space it's not)
// after pos at time T on lane. Return -1 if no such car.
int nextCarFront(ll T, ll pos, int lane) {
  if (cars[lane].size() == 0) return -1;
  if (calcPos(0, lane, T) + len(0, lane) > pos) return 0;
  if (calcPos(cars[lane].size() - 1, lane, T) + len(cars[lane].size() - 1, lane) <= pos) return -1;
  int lo = 0;
  int hi = cars[lane].size() - 1;
  while (hi - lo > 1) {
    int med = (hi + lo) / 2;
    if (calcPos(med, lane, T) + len(med, lane) <= pos) {
      lo = med;
    } else {
      hi = med;
    }
  } 
  return hi;
}

// Find the index of the next car that has it's back after pos at time T on lane. 
// Return -1 if no such car.
int nextCarBack(ll T, ll pos, int lane) {
  if (cars[lane].size() == 0) return -1;
  if (calcPos(0, lane, T) > pos) return 0;
  if (calcPos(cars[lane].size() - 1, lane, T) <= pos) return -1;
  int lo = 0;  // Too early: cars[lo].pos <= pos.
  int hi = cars[lane].size() - 1;  // Good enough. cars[hi].pos > pos 
  while (hi - lo > 1) {
    int med = (hi + lo) / 2;
    if (calcPos(med, lane, T) <= pos) {
      lo = med;
    } else {
      hi = med;
    } 
  }
  return hi;
}

ll travelTime(ll dist, int speed) {
  assert ((dist % speed) == 0);
  return dist / speed; 
}

// At any point in time, I know my position on all the three lanes.
// Which always happens to be an integer.
// I'm interested in events that might cause me to change my speed or change lanes.
// Changing speed is easy. I always drive at max speed, unless there's a car in front of
// me, in which case I drive at this car's speed. So, I just need to know the car in front of
// me, and when time advances, my new position on that lane is 
// min(myoldpos + deltaT * myspeed, othercarpos)
// The interesting stuff is changing lanes. If I'm driving with a car in front of me, I might
// change lanes if a new slot opens, which happens if the car in front's back matches the back
// of some other car on the lane above, or my back matches the front of a car on the lane above.
// If I'm driving solo, I'm always fastest, so my back exceeds the front of somebody on the lane
// below or above. We find the earliest event.
// Also, magic fact, if I'm on a lower lane, and I'm behind the best position on the upper lane,
// it never makes sense to switch position to the upper lane. So, that's not an event.
ll findNextEvent() {
  ll next = inftytime;
  for (int mylane = 0; mylane < 3; ++mylane) {
    ll mypos = bestpos[mylane];  // Best position of my back on my lane after time T.
    // Is there a car directly in front of me?
    int carInFront = nextCarBack(T, mypos, mylane);
    // We didn't crash yet!
    assert(carInFront == -1 || calcPos(carInFront, mylane, T) - mypos >= carlen);
    bool drivingBehind = false;
    if (carInFront != -1 && calcPos(carInFront, mylane, T) - mypos == carlen) {
      drivingBehind = true; 
    } 
    // Interesting events if I drive solo are: a) my front hits the back of the guy in my lane.
    // b) my back hits the front of someone in another lane.
    if (!drivingBehind) {
      if (carInFront != -1) {
        next = std::min(next, T + travelTime(calcPos(carInFront, mylane, T) - mypos - carlen, 
                                             myspeed - speed[mylane]));
      }
      if (mylane > 0) {
        // Maybe go up.
        int nextCarInLane = nextCarFront(T, mypos, mylane - 1);
        if (nextCarInLane != -1) {
          next = std::min(next, T + travelTime(
              calcPos(nextCarInLane, mylane - 1, T) + len(nextCarInLane, mylane - 1) - mypos,
                      myspeed - speed[mylane - 1])); 
        } 
      }
      if (mylane < 2 && bestpos[mylane] >= bestpos[mylane + 1]) {
        int nextCarInLane = nextCarFront(T, mypos, mylane + 1);
        if (nextCarInLane != -1) {
          next = std::min(next, T + travelTime(
            calcPos(nextCarInLane, mylane + 1, T) + len(nextCarInLane, mylane + 1) - mypos,
                    myspeed - speed[mylane + 1]));
        }
      }
    } // End of driving behind.
    // Assume car in front of me is C. Interesting events are: a) on the next faster lane, 
    // another car intercepts me (so I can go behind it) - which means it's back matches the back
    // of the car in front of me. b) on the next slower lane, a car falls behind (it's front matches
    // my back).
    if (drivingBehind) {
      if (mylane > 0 && bestpos[mylane] >= bestpos[mylane - 1]) {
        // Find the first car which has it's back equal to or ahead of my front, and move one car back.
        int nextCarInLane = nextCarBack(T, mypos + carlen - 1, mylane - 1) - 1; 
        // -1 means the first car was in front of me. -2 means I'm in front of all of them, in which case
        // there's no point in waiting - I'm already on their lane, and I can just run.
        if (nextCarInLane >= 0) { 
          next = std::min(next, T + travelTime(mypos + carlen - calcPos(nextCarInLane, mylane - 1, T),
                                               speed[mylane - 1] - speed[mylane])); 
        }
      }
      if (mylane < 2) {
        // Now I'm overtaking - so I want my back after someone's front.
        // Find the first car which has it's front strictly behind my back.
        int nextCarInLane = nextCarFront(T, mypos, mylane + 1);
        if (nextCarInLane != -1) {  // -1 means I passed all of them already, won't pass any more. 
          next = std::min(next, T + travelTime(
              calcPos(nextCarInLane, mylane + 1, T) + len(nextCarInLane, mylane + 1) - mypos,
                      speed[mylane] - speed[mylane + 1]));   
        }
      }
    }  
  }
  assert(next < inftytime);
  assert(next > T);
  return next;
}  

void moveTime(ll nextT) {
  assert(nextT > T);
  for (int lane = 0; lane < 3; ++lane) {
    ll mypos = bestpos[lane];
    ll curspeed = myspeed;
    int carInFront = nextCarBack(T, mypos, lane);  
    if (carInFront != -1 && calcPos(carInFront, lane, T) - mypos == carlen) {
      curspeed = speed[lane];
    }
    bestpos[lane] += (nextT - T) * curspeed;
  }
  T = nextT;
}

bool canSwitchTo(int lane, ll pos) {
  // Can I switch? The back of the next car has to be in front of my front.
  // And the front of the previous car has to be at or behind my back.
  int carInFront = nextCarBack(T, pos, lane); // This car has it's back in front of my back.
  if (carInFront != -1 && calcPos(carInFront, lane, T) < pos + carlen) return false;
  // Now look at the car behind.
  if (carInFront == -1) carInFront = cars[lane].size();
  carInFront -= 1;  // That car has it's back at or behind my back.
  if (carInFront != -1 && calcPos(carInFront, lane, T) + len(carInFront, lane) > pos) return false;
  return true; 
}

void switchLanes() { 
  // Switch up.
  for (int mylane = 0; mylane < 2; ++mylane) {
    if (bestpos[mylane] > bestpos[mylane + 1] && canSwitchTo(mylane + 1, bestpos[mylane])) {
      bestpos[mylane + 1] = bestpos[mylane];
    }      
  }
  // Switch down.
  for (int mylane = 2; mylane > 0; --mylane) {
    if (bestpos[mylane] > bestpos[mylane - 1] && canSwitchTo(mylane - 1, bestpos[mylane])) { 
      bestpos[mylane - 1] = bestpos[mylane];
    } 
  }
}

bool IWinAlready() {
  ll besttotalpos = std::max(bestpos[0], std::max(bestpos[1], bestpos[2]));
  for (int lane = 0; lane < 3; ++lane) if (cars[lane].size() > 0) {
    int lastcar = cars[lane].size() - 1;
    if (calcPos(lastcar, lane, T) + len(lastcar, lane) > besttotalpos) return false;   
  }  
  return true;
}

int main() {
  int L, v0, v1, v2, v3;
  scanf("%d %d %d %d %d\n", &L, &v0, &v1, &v2, &v3);
  myspeed = v0;
  speed[0] = v1;
  speed[1] = v2;
  speed[2] = v3;
  carlen = 1;
  for (int i = 0; i < 3; i++) {
    bestpos[i] = 0;
    carlen *= (myspeed - speed[i]); 
    for (int j = 0; j < i; j++) {
      carlen *= (speed[j] - speed[i]);
    }
  } 
  // I measure space in units of 1/carlen, and time in units of 1/carlen.
  // In that measureset, the speeds stay the same, and the length of a car is carlen.
  // Also, at that measure, the point in time when any two cars (except mine) meet is an integer.
  for (int i = 0; i < 3; ++i) {
    scanf("%s", road);
    for (int k = 0; k < L; ++k) {
      if (road[k] == '#' && (k > 0 || i < 2)) {
        if (k == 0 || road[k-1] == '.' || (k == 1 && i == 2)) {
          car c;
          c.pos = carlen * k;
          c.len = carlen;
          cars[i].push_back(c);
        } else {
          cars[i].back().len += carlen;
        }
      }
    }  
  }
  inftytime = carlen * (ll) L * 2LL + 10;
  // Strategy to win in that time: Go to lane 1. Wait for L units of time going at v1.
  // Since v1-v2 >= 1, after l units of time, you are ahead of all the cars on lanes 2 and 3.
  // Change lane to 2, start driving at v1+1 (which is at most v0), again for L units of time,
  // You win.  
  // Note: AFAICT, inftytime * 140 still fits in 63 bits. So, I'm gonna use longlong and hope for the best.
  // Carlen is maximized by speeds 140, 101, 39 and 0; and then inftytime * 140 is ~0.8 * 2**63
  while (true) {
    if (IWinAlready()) {
      double res = T;
      res /= carlen;
      printf("%.15lf\n", res); 
      return 0;
    }
    ll nextEvent = findNextEvent();
    moveTime(nextEvent);
    switchLanes(); 
  }
}