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
#include <bits/stdc++.h>
using namespace std;

// not my style :( but just this time...
array<int, 4> v;

struct Gap {
   int lane; // 1, 2, 3
   int start_at_t0; // gap start in L
   int gap_length; // in L
};

long double time_of_meet(long double pa, long double ta, int va, long double pb, long double tb, int vb) {
   // s_ = p_ + v_ * (t-t_)
   return (pb - pa + va * ta - vb * tb) / (va - vb);
}

pair<long double, long double> timepos2(long double pa, long double ta, int va, long double pb, int vb) {
   long double t = time_of_meet(pa, ta, va, pb, 0.0, vb);
   long double dist = pb + vb * t;
   return {t, dist};
}

pair<long double, long double> gap_open_down(Gap& cgf, Gap& cgs) {
   return timepos2(cgf.start_at_t0 + cgf.gap_length, 0.0, v[cgf.lane], cgs.start_at_t0 + 1, v[cgs.lane]);
}

pair<long double, long double> gap_closes_up(Gap& cgf, Gap& cgs) {
   return timepos2(cgf.start_at_t0 + 1, 0.0, v[cgf.lane], cgs.start_at_t0 + cgs.gap_length, v[cgs.lane]);
}

pair<long double, long double> plus_e(pair<long double, long double> p) {
   long double eps = 1e-6;
   p.first += eps;
   p.second += eps;
   return p;
}

int main() {
   // freopen("D:/szkola/testy/aut/aut_rnd/problems.in", "r", stdin);
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int L;
   cin >> L >> v[0] >> v[1] >> v[2] >> v[3];

   // parse input to Gaps
   array<vector<Gap>, 4> gaps;
   for (int li = 1; li <= 3; li++) {
      string lane;
      cin >> lane;
      auto& gs = gaps[li];

      bool in_gap = true;
      gs.push_back({li, 0, 1});
      for (int i = 1; i < lane.size(); i++) {
         if (lane[i] == '#') {
            in_gap = false;
         } else {
            if (in_gap) {
               gs.back().gap_length++;
            } else {
               in_gap = true;
               gs.push_back({li, i, 1});
            }
         }
      }

      if (!in_gap) {
         gs.push_back({li, lane.size(), 1});
      }
      gs.back().gap_length = 1000000000;
   }


   long double t = 0;
   long double dist = 1;

   array<int, 4> gapi = {0}; // indexes of "nearest" gaps to current car position (t, dist)
   while (true) {
      const int midlane = 2;
      Gap& cg2 = gaps[midlane][gapi[midlane]];
      if (gapi[midlane] == gaps[midlane].size() - 1) {
         pair<long double, long double> end_of_lane2 = {t, dist};
         Gap& lg1 = gaps[1].back();
         Gap& lg3 = gaps[3].back();
         pair<long double, long double> end_of_lane1 = timepos2(dist, t, v[0], gaps[1].back().start_at_t0 + 1, v[1]);
         pair<long double, long double> end_of_lane3 = timepos2(dist, t, v[0], gaps[3].back().start_at_t0 + 1, v[3]);

         pair<long double, long double> result = max(max(end_of_lane1, end_of_lane2), end_of_lane3);

         cout << fixed << setprecision(19) << result.first << endl;
         return 0;
      }

      Gap& ng2 = gaps[midlane][gapi[midlane] + 1];
      pair<long double, long double> timepos_to_next_gap_in_2 = timepos2(dist, t, v[0], ng2.start_at_t0 + 1, v[midlane]);

      // idea: jedziemy srodkowym i on nadaje kroki
      // i wyprzedzamy bocznymi...
      //
      // we can always overtake by lane1 - just take last available gap (need to find it)
      // it's possible we need to wait till "gap opens" to go back on lane 2
      //
      // overtake by lane3 is slightly different - need to find gap that will allow full overtake
      //

      // needed to find last gap on side lanes:
      pair<long double, long double> timepos_we_slow_down_by_obstacle2 = timepos2(dist, t, v[0], cg2.start_at_t0 + cg2.gap_length, v[midlane]);

      // check overtake by lane 1
      while (gapi[1] + 1 < gaps[1].size()) {
         // find last gap up
         gapi[1]++;
         Gap& cg1 = gaps[1][gapi[1]];
         pair<long double, long double> gcu = gap_closes_up(cg1, cg2);
         if (plus_e(gcu) < timepos_we_slow_down_by_obstacle2) {
            gapi[1]--;
            break;
         }
      }

      Gap& cg1 = gaps[1][gapi[1]];
      pair<long double, long double> cg1_end_delay = gap_open_down(cg1, ng2);

      //pair<long double, long double> overtake_up = max(timepos_to_next_gap_in_2, cg1_end_delay);
      if (plus_e(timepos_to_next_gap_in_2) >= cg1_end_delay) {
         // cant be done faster - lets not try
         gapi[midlane]++;
         tie(t, dist) = timepos_to_next_gap_in_2;
         continue;
      }
      pair<long double, long double> overtake_up = cg1_end_delay;
      pair<long double, long double> best_overtake = overtake_up;


      // check overtake by lane3
      while (true) {
         //
         Gap& cg3 = gaps[3][gapi[3]];
         pair<long double, long double> gap3_open = gap_open_down(cg2, cg3);
         //pair<long double, long dlong doubleouble> car_pos = {t, dist};
         pair<long double, long double> car_can_go_down = timepos2(dist, t, v[0], cg3.start_at_t0 + 1, v[3]);
         pair<long double, long double> overtake_start = max(gap3_open, car_can_go_down);

         pair<long double, long double> overtake_lane_3 = timepos2(overtake_start.second, overtake_start.first, v[0], ng2.start_at_t0 + 1, v[2]);
         if (plus_e(overtake_lane_3) >= overtake_up) {
            // too slow and can't be faster
            break;
         }

         pair<long double, long double> gap3_closes = gap_closes_up(ng2, cg3);
         if (plus_e(gap3_closes) < overtake_lane_3) {
            // too small/old gap... could try another
            if (gapi[3] + 1 < gaps[3].size()) {
               gapi[3]++;
               continue;
            } else {
               break;  // possible??
            }

         }

         // good gap... check if better than up
         best_overtake = min(overtake_lane_3, overtake_up);
         break;
      }

      gapi[midlane]++;
      tie(t, dist) = best_overtake;
      // cout << "step: " << t << " " << dist << endl;
   }
}