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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <iomanip>
using namespace std;

const long double EPSILON = 1e-12;

int main() {
    cout << std::fixed;
    cout << std::setprecision(12);
    
	int L;
	long double v0,v1,v2,v3;
	cin >> L >> v0 >> v1 >> v2 >> v3;
	string s;
	
	cin >> s;
	vector<int> start1, end1;
	start1.push_back(0);
	for(int i = 1; i < L; i++) {
		if(s[i-1] == '.' && s[i] == '#')
			end1.push_back(i-1);
		if(s[i-1] == '#' && s[i] == '.')
			start1.push_back(i);
	}
	if(s[L-1] == '#')
		start1.push_back(L);
	
	cin >> s;
	vector<int> start2, end2;
	start2.push_back(0);
	for(int i = 1; i < L; i++) {
		if(s[i-1] == '.' && s[i] == '#')
			end2.push_back(i-1);
		if(s[i-1] == '#' && s[i] == '.')
			start2.push_back(i);
	}
	if(s[L-1] == '#')
		start2.push_back(L);
	
	cin >> s;
	s[0] = '.';
	vector<int> start3, end3;
	start3.push_back(0);
	for(int i = 1; i < L; i++) {
		if(s[i-1] == '.' && s[i] == '#')
			end3.push_back(i-1);
		if(s[i-1] == '#' && s[i] == '.')
			start3.push_back(i);
	}
	if(s[L-1] == '#')
		start3.push_back(L);
	
	
	if(end1.size() == 0 || end2.size() == 0 || end3.size() == 0) {
		long double res = max(max( start1.back()/(v0-v1), start2.back()/(v0-v2)), start3.back()/(v0-v3));
		cout  << res << endl;
		return 0;
	}
	
/*	for(auto x: start2)
	  cout << x << ' ';
	cout << endl;
	for(auto x: end2)
	  cout << x << ' ';
	cout << endl;*/
	
	int etap = 0;
	long double t_start = 0; // czas dotarcia do poczatku przedzialu
	while(true) {
	    //cout << "t_start: " << t_start << endl;
		if(end2.size() == etap) {
			long double t_1 = t_start + (start1.back() + t_start * v1 - start2[etap] - t_start*v2)/(v0-v1);
			long double t_3 = t_start + (start3.back() + t_start * v3 - start2[etap] - t_start*v2)/(v0-v3);
			if(t_start >= t_1 && t_start >= t_3) {
				cout << t_start << endl;
			}
			else if(t_1 >= t_3) {
				cout << t_1 << endl;
			}
			else {
				cout << t_3 << endl;
			}
			return 0;
			
		}
		
		long double t_end = t_start + (end2[etap]-start2[etap])/(v0-v2);
		//cout << "t_end: " << t_end << endl;
		
		long double best_inc = (start2[etap+1]-end2[etap])/(v0-v2);
		long double best_next = t_end + best_inc;
		
		
		long double pos1 = end2[etap]+ t_end*(v2-v1) + EPSILON;
		auto lower1 = lower_bound(start1.begin(), start1.end(), pos1);
		lower1--;
		int idx1 = lower1 - start1.begin();		
		
		long double pos3 = end2[etap]+ t_end*(v2-v3) + EPSILON;
		auto lower3 = lower_bound(start3.begin(), start3.end(), pos3);
		lower3--;
		int idx3 = lower3 - start3.begin();
		
		if(idx1 >= end1.size() || end1[idx1]+best_next*v1 + EPSILON >= start2[etap+1] + best_next*v2 ||
		   idx3 >= end3.size() || end3[idx3]+best_next*v3 + EPSILON >= start2[etap+1] + best_next*v2)
			t_start = best_next;
		else {
			long double propozycja = (start2[etap+1]-end1[idx1]) / (v1-v2);
			
			while(true) {
				idx3++;
				long double t_overtake = (start3[idx3]-end2[etap])/(v2-v3);
				long double t_prop2 = t_overtake + best_inc;
				if(t_prop2 > propozycja)
					break;
				else
					if(idx3 >= end3.size() ||  end3[idx3]+t_prop2*v3 + EPSILON >= start2[etap+1] + t_prop2*v2) {
						propozycja = t_prop2;
						break;
					}
						
				
			}
			
			t_start = propozycja;
		}
		
		etap++;
	}
	
	
	
	return 0;
}