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
#include <cstdio>
#include <limits>
#include <list>
#include <vector>

struct Car
{
    long double /* tył */ start, /* przód */ end;

    Car(int start, int end) : start(start), end(end) { }
};

bool tmp[200000]; // temporary buffer
int L;
long double v0, v1, v3; // przyjmujemy że v2=0
std::list<Car> cars1, cars2, cars3;

std::list<Car> read_cars() {
    getchar(); getchar(); // pierwszy znak z linii pomijamy
    std::list<Car> cars;
    Car* last_car = nullptr;
    for (int i=1; i<L; ++i) {
        if (getchar() == '#') {
            if (last_car) {
                last_car->end = i+1;
            } else {
                cars.push_back({i, i+1});
                last_car = &cars.back();
            }
        } else {
            last_car = nullptr;
        }
    }
    return cars;
}

long double calculate() {
    long double t = 0.0; // TODO Rational
    long double x_start = 0.0; // pozycja TYŁU samochodu

    auto next1 = cars1.begin();
    auto next2 = cars2.begin();
    auto next3 = cars3.begin();

    // zaczynamy z pasa środkowego
    while (true) {
        if (next2 == cars2.end()) {
            // nie ma aut na środkowym pasie
            long double t_end = t;
            if (next1 != cars1.end()) {
                t_end = std::max(t_end, t + (cars1.back().end + t * v1 - x_start) / (v0 - v1));
//                printf("t_end(1) = %Lf", t_end);
            }
            if (next3 != cars3.end()) {
                t_end = std::max(t_end, t + (cars3.back().end + t * v3 - x_start) / (v0 - v3));
//                printf("t_end(2) = %Lf", t_end);
            }
            return t_end;
        }

        // dojeżdżamy do pierwszego auta na środkowym pasie
        long double dt = (next2->start - x_start - 1) / v0;
//        printf("tutaj n2start=%Lf xstart=%Lf\n", next2->start, x_start);
        t += dt;
//        printf("dojechaliśmy do auta na środkowym: t=%Lf\n", t);
        x_start += v0 * dt;
        // teraz jesteśmy tuż za pierwszym autem na środkowym pasie
        // i chcemy je ominąć z lewej lub z prawej

        // pomijamy wszystkie auta, które nam już nie przeszkadzają
        while (next1 != cars1.end() && next1->end + t * v1 <= x_start) {
            ++next1;
        }
        while (next3 != cars3.end() && next3->end + t * v3 <= x_start) {
            ++next3;
        }
        if (next1 == cars1.end() || next3 == cars3.end()) {
            // nie ma aut na pierwszym lub trzecim pasie
            long double t_end = t;
            if (next1 != cars1.end()) {
                t_end = std::max(t_end, t + (cars1.back().end + t * v1 - x_start) / (v0 - v1));
            }
            if (next2 != cars2.end()) {
                t_end = std::max(t_end, t + (cars2.back().end - x_start) / v0);
            }
            if (next3 != cars3.end()) {
                t_end = std::max(t_end, t + (cars3.back().end + t * v3 - x_start) / (v0 - v3));
            }
            return t_end;
        }

        // next1 to pierwsze auto, które może nam przeszkadzać
        // liczymy kiedy start auta1 osiągnie end auta2 + 1 czyli moment kiedy można wrócić na pas 2
        dt = (next2->end + 1 - next2->start) / v0;
        long double dt1, dt3;
//        printf("gdyby nie inne auta wyprzedzilibysmy je w t=%Lf\n", dt);
        if (next1->start + (t + dt) * v1 >= next2->end + 1) {
            // to auto nam nie przeszkadza
            dt1 = dt;
        } else {
            long double t_wyprz_1 = (next2->end + 1 - next1->start) / v1 - t;
            dt1 = std::max(dt, t_wyprz_1);
//            printf("z uwagi na auto na 1 pasie bedzie to t=%Lf\n", dt1);
        }

        // z prawej auta jadą do tyłu
        // więc może trzeba będzie najpierw przeczekać kilka aut aż pojawi się takie,
        // które można wyprzedzić
        if (next3->start + (t + dt) * v3 >= next2->end + 1) {
            // to auto nam nie przeszkadza
            dt3 = dt;
        } else {
            // musimy poczekać aż next3 przejedzie i dopiero potem
            long double min_separation = dt * (v0 - v3);
            auto n3a = next3;
            auto n3b = next3;
            n3b++;
            while (n3a != cars3.end()) {
                dt3 = (next2->start - 1 - n3a->end) / v3 - t;
                if (dt3 > dt1) {
                    break;
                }
                if (n3b == cars3.end() || n3b->start - n3a->end <= min_separation) {
                    break;
                }
                ++n3a;
                ++n3b;
            }
            dt3 = std::max(dt3, dt);
//            printf("z uwagi na auto na 3 pasie bedzie to t=%Lf\n", dt3);
        }

        t += std::min(dt1, dt3);
//        printf("teraz t=%Lf\n", t);
        x_start = next2->end;
        ++next2;
    }
}

int main() {
    long double v2;
    scanf("%d%Lf%Lf%Lf%Lf", &L, &v0, &v1, &v2, &v3);
    v0 -= v2; v1 -= v2; v3 -= v2;
    cars1 = read_cars();
    cars2 = read_cars();
    cars3 = read_cars();
    printf("%.15Lf\n", calculate());
}