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
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 5, INF = 1000000000;
const long double eps = 0.0000000001;
int L;
long double v[3], V;
string pas[3];
int far[3];

struct State {
	long double s;
	int track;
	const bool operator < (const State & other) const {
		return make_pair(s, track) < make_pair(other.s, other.track);
	}
};


priority_queue<pair<long double, State>>PQ;
map<State, long double> dp;

bool valid(int track, long double s, long double t) {
	if(track < 0 || track > 2) return false;
	for(int i = 0; i < L; ++i) {
		if(pas[track][i] == '#') {
			if(abs(t * v[track] + i - s) < 1.0) {
				return false;
			}
		}
	}
	return true;
}

bool winning_condition(State s, long double t) {
	for(int i = 0; i < 3; ++i) {
		if(t * v[i] + far[i] > s.s - 1.0) {
			return false;
		}
	}
	return true;
}

void transition(State s, long double t) {
	int x = s.s + 1.0 - t * v[s.track];
	long double vel = V;
	//cerr << x << "\n";
	if(abs(s.s - (x + t * v[s.track] - 1.0)) < eps && x >= 0 && x < L && pas[s.track][x] == '#') {
		vel = v[s.track];
	}
	//cerr << vel << " " << v[s.track] << "\n";
	long double dt = INF;
	for(int i = 0; i < L; ++i) {
		if(vel == v[s.track]) continue;
		if(pas[s.track][i] == '#') {
			//cerr << i << "\n";
			if(t * v[s.track] + i > s.s && (t * v[s.track]-s.s-1.0 + (long double)i)/(vel-v[s.track]) > 0.0)
			dt = min(dt, (t * v[s.track]-s.s-1.0 + (long double)i)/(vel-v[s.track]));
		}
	}
	//cerr << s.s << " " << s.track << " " << t << ": " << dt << " " << vel << "\n";
	for(int i = 0; i < 3; ++i) {
		if(v[i] == vel) continue;
		for(int j = 0; j < L; ++j) {
			if(pas[i][j] == '.') {
				//(t + dt) * v[i] + j = s.pos + dt * vel;
				long double t2 = (s.s - t*v[i]-j)/(v[i]-vel);
				if(t2 > 0.0 && t2 <= dt && vel > v[i]) {
					s.s += vel * t2;
					if(!dp.count(s) || dp[s] > t + t2) {
						dp[s] = t + t2;	
						PQ.push({-dp[s], s});
					}
					s.s -= vel * t2;
				}
			}
		}
	}
	//s.s += vel * dt;
	//if(!dp.count(s) || dp[s] > t + dt) {
		//dp[s] = t + dt;
		//PQ.push({-t-dt, s});
	//}
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> L >> V >> v[0] >> v[1] >> v[2];
	V -= v[2]; v[0] -= v[2]; v[1] -= v[2]; v[2] = 0;
	for(int i = 0; i < 3; ++i) {
		cin >> pas[i];
		pas[i] += ".";
		far[i] = -INF;
		for(int j = 0; j < L; ++j) {
			if(pas[i][j] == '#') {
				far[i] = j;
			}
		}
	}
	L++;
	PQ.push({0.0, {0.0, 2}});
	while(!PQ.empty()) {
		auto [t, pos] = PQ.top();
		PQ.pop();
		if(dp.count(pos) && dp[pos] > -t) {
			continue;
		}
		t = -t;
		//cerr << pos.s << " " << pos.track << ": " << t << "\n";
		if(winning_condition(pos, t)) {
			cout << setprecision(15);
			cout << fixed;
			cout << t << "\n";
			return 0;
		}
		for(int dt : {-1, 1}) {
			State nbh = {pos.s, pos.track + dt};
			if(valid(pos.track + dt, pos.s, t) && (!dp.count(nbh) || dp[nbh] > t)) {
				dp[nbh] = t;
				PQ.push({-t, nbh});
			}
		}
		transition(pos, t);
	}
	
	
}