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
259
260
261
262
263
264
265
266
267
268
269
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <list>

using namespace std;
#define DEBUGLEVEL 10
#undef _HOME_
#ifdef _HOME_
		#include "debug.h"
#else
    #define DEBUG(level,x)
#endif
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x,n) for(__typeof(n.begin()) x = (n).begin(); x != (n).end(); ++x)
#define RESULT(x) {cout<<(x);return 0;}
const int MAX_N = 200001;
const int INT_INF = 1000000000; // 1e9
const long double EPS = 1e-15L;

bool inline isZero(const long double& d) {
	return d >= -EPS && d <= EPS;
}
bool inline isGreater(const long double& a, const long double& b) {
	return (a-b)>EPS;
}
bool inline isLess(const long double& a, const long double& b) {
	return (b-a)>EPS;
}

int L,v_k;
string road[3];
struct Gap {
	int pos;
	int length;
	long double inline posAtTime(long double time, long double v) {
		return pos+v*time;
	}
	long double inline endAtTime(long double time, long double v) {
		return pos+length-1 + v*time;
	}
};
ostream& operator<<(ostream& os, const Gap& g) {
	return os << "{"<<g.pos<<", len="<<g.length<<"}";
}
struct GapData {
	Gap gaps[MAX_N];
	Gap* next = gaps;
	Gap* last = 0;
	void inline add(const Gap& gap) {
		if (last)
			*(++last) = gap;
		else
			*(last=gaps) = gap;
	}
	bool inline isAtEnd() const {
		return next>=last;
	}
};
GapData gapData[3];
int v[3];

struct Pos {
	long double pos;
	long double time;
	void inline set(long double p, long double t) {
		pos=p; time=t;
	}
};
Pos pos[3];

void adjustGaps(int x) {
	GapData& data = gapData[x];
	while (data.next != data.last && (data.next+1)->posAtTime(pos[x].time, v[x]) <= pos[x].pos) {
		++data.next;
		DEBUG(8, cerr<<"adjust gap #"<<x<<" to "<<*data.next<<" at time "<<pos[x].time<<" and pos "<<pos[x].pos<<endl;)
	}
	DEBUG(8,
		if (data.next == data.last)
			cerr<<"cannot adjust gap #"<<x<<" - already at end"<<endl;
		else
			cerr<<"cannot adjust gap #"<<x<<" ("<< *(data.next+1) <<") at time "<<pos[x].time<<" - pos "<<pos[x].pos<<" not enough for "<<(data.next+1)->posAtTime(pos[x].time, v[x])<<endl;
	)
}

void tryMove(const long double& currentPos, const long double& maxPos, const long double& currentTime, const long double& targetTime, const long double& speed, int index) {
	if (index<0 || index>2)
		return;
	Gap* currentGap = gapData[index].next;
	long double currentEndAtTime = currentGap->endAtTime(targetTime, v[index]);
	if (currentEndAtTime > maxPos) {
		if (isGreater(maxPos, pos[index].pos + v_k*(targetTime - pos[index].time))) {
			DEBUG(8, cerr<<"still at the same gap #"<<index<<" but can improve ("<<pos[index].pos<<","<<pos[index].time<<")->("<<maxPos<<","<<targetTime<<"); diff is "<<(maxPos - (pos[index].pos + v_k*(targetTime - pos[index].time)))<<endl;)
			pos[index].pos = maxPos;
			pos[index].time = targetTime;
		}
		else {
			DEBUG(8, cerr<<"still at the same gap #"<<index<<" and no improvement" << endl;)
		}
		return;
	}
	for(Gap* nextGap = currentGap+1; nextGap <= gapData[index].last; ++nextGap) {
		long double nextEndAtTime = nextGap->endAtTime(targetTime, v[index]);
		if (isLess(nextEndAtTime, currentPos)) {
			DEBUG(7, cerr<<"gap #"<<index<<" before everything - skipping..."<<endl;)
			continue;
		}
		long double nextStartAtTime = nextGap->posAtTime(targetTime, v[index]);
		if (!isGreater(nextStartAtTime, maxPos)) { // next start < target pos
			long double endAtTime = nextGap->endAtTime(targetTime, v[index]);
			DEBUG(8, cerr<<"trying to reach gap #"<<index<<" at time "<<targetTime<<", our pos is "<<currentPos<<"->"<<maxPos<<", gap is "<<nextStartAtTime<<"->"<<endAtTime<<endl;)
			if (!isGreater(endAtTime, maxPos)) { // next end < maxPos
				long double minusTime = (maxPos-endAtTime) / speed;
				DEBUG(7, cerr<<"need to step back at distance "<<(maxPos-endAtTime)<<" which will require "<<minusTime<<" time"<<endl;);
				pos[index].pos = nextGap->endAtTime(targetTime - minusTime, v[index]);
				DEBUG(10, cerr<<"   nextGap->endAtTime("<<targetTime<<"-"<<minusTime<<"="<<(targetTime-minusTime)<<", "<<v[index]<<") = "<<pos[index].pos<<endl;);
				pos[index].time = targetTime - minusTime;
				DEBUG(7, cerr<<"can reach next gap #"<<index<<" at end - pos at endTime is "<<pos[index].time<<", can reach "<<pos[index].pos<<endl;)
			}
			else {
				DEBUG(7, cerr<<"can reach next gap #"<<index<<" - pos at endTime is "<<nextStartAtTime<<", can reach "<<maxPos<<endl;)
				pos[index].pos = maxPos;
				pos[index].time = targetTime;
			}
			adjustGaps(index);
		}
		else {
			DEBUG(8, cerr<<"will not reach next gap #"<<index<<" need "<<nextStartAtTime<<", got "<<maxPos<<", diff="<<(maxPos-nextStartAtTime)<<endl;)
			break;
		}
	}
}

// go to faster road
bool tryUp(int from, int to) {
	DEBUG(8, cerr<<"TRY UP"<<endl;)
	return false;
}
//go to slower road
bool tryDown(int from, int to) {
	if (gapData[to].last == gapData[to].next) {
		DEBUG(8, cerr<<"canot go down from "<<from<<" to "<<to<<" - already at end"<<endl;)
		return false;
	}
	Gap* g = gapData[to].next;
	long double realNextStart = (++g)->posAtTime(pos[from].time, v[to]);
	long double timeTillNextStart = max(0.0L, (realNextStart-pos[from].pos) / (v[from]-v[to]));
	DEBUG(8, cerr<<"can go from "<<from<<" to "<<to<<" on time "<<pos[from].time+timeTillNextStart<<endl;)
	if (pos[to].pos < realNextStart) {
		long double posWhenReach = realNextStart + timeTillNextStart*v[to];
		long double timeWhenReach = pos[from].time + timeTillNextStart;
		DEBUG(8, cerr<<"   and will do - pos="<<posWhenReach<<", time="<< timeWhenReach <<endl;)
		pos[to].pos = posWhenReach;
		pos[to].time = timeWhenReach;
		adjustGaps(to);
		tryMove(posWhenReach, posWhenReach, timeWhenReach, timeWhenReach, 0.0L, to+1);
		return true;
	}
	else {
		DEBUG(8, cerr<<"cannot go down - "<<pos[to].pos << " >= "<<realNextStart<<endl;)
	}
	return false;
}

long double runToEnd(int x) {
	DEBUG(4, cerr<<"can exit using road "<<x<<" on time "<<pos[x].time<<" and pos "<<pos[x].pos<<endl;)
	long double maxTime = pos[x].time;
	long double p = pos[x].pos;
	REP(y,3)
		if (gapData[y].next != gapData[y].last) {
			Gap* last = gapData[y].last;
			long double distanceToBeat = last->posAtTime(pos[x].time, v[y]) - p;
			long double timeToBeat = distanceToBeat / (v_k-v[y]);
			DEBUG(5, cerr<<"need "<<timeToBeat<<" to bypass all at "<<y<<" - pos diff is "<< distanceToBeat <<", v diff is "<<(v_k-v[y])<<endl;)
			maxTime = max(maxTime, pos[x].time + timeToBeat);
		}
	return maxTime;
}

long double solve() {
	int ttt=0;
	while(true) {
		bool anyChange = false;
		REP(x,3) {
			Gap* gap = gapData[x].next;
			DEBUG(9, cerr<<"road "<<x<<" - current pos is {"<<pos[x].pos<<", "<<pos[x].time<<"}, current gap is "<<*gap<<endl;)
			if (gapData[x].isAtEnd()) {
				DEBUG(9, cerr<<"road "<<x<<" - already at the end, nothing to do "<<endl;)
				continue;
			}
			long double gapStart = gap->posAtTime(pos[x].time, v[x]);
			long double timeTillEnd = (gap->length-1 - (pos[x].pos-gapStart)) / (v_k-v[x]);
			if (isZero(timeTillEnd)) {
				DEBUG(9, cerr<<"road "<<x<<" - still at end - nothing to do"<<endl;)
				continue;
			}
			anyChange = true;
			long double timeAtEnd = pos[x].time + timeTillEnd;
			long double posAtEnd = pos[x].pos + timeTillEnd*v_k;
			DEBUG(6, cerr<<"road "<<x<<" - will reach end of gap at time "<<timeAtEnd<<" and pos "<<posAtEnd<<" - pos diff is "<<(gap->length - (pos[x].pos-gapStart))<<", v diff is "<<(v_k-v[x])<<endl;)
			tryMove(pos[x].pos, posAtEnd, pos[x].time, timeAtEnd, v_k, x+1);
			tryMove(pos[x].pos, posAtEnd, pos[x].time, timeAtEnd, v_k, x-1);
			DEBUG(9, cerr<<"   change pos to "<<posAtEnd<<", time to "<<timeAtEnd<<endl;)
			pos[x].pos = posAtEnd;
			pos[x].time = timeAtEnd;
		}
		if (anyChange)
			continue;
		REP(x,3)
			if (gapData[x].isAtEnd()) {
				return runToEnd(x);
			}
		if (!tryUp(2,1))
			tryDown(1,2);
		if (!tryUp(1,0))
			if (tryDown(0,1))
				tryDown(1,2);
		if (++ttt > 30000000)
			return -100;
	}
}

void preprocess(GapData& gapData, const string& road) {
	Gap currentGap{0,0};
	FOREACH(it, road)
		switch(*it) {
			case '.':
				if (currentGap.length == 0)
					currentGap.pos = it-road.begin();
				++currentGap.length;
				break;
			case '#':
				if (currentGap.length != 0) {
					gapData.add(currentGap);
					currentGap.length = 0;
				}
				break;
		}
	if (currentGap.length == 0)
		currentGap.pos = road.size();
	currentGap.length = INT_INF;
	gapData.add(currentGap);
}

int main() {
	cin>>L>>v_k>>v[0]>>v[1]>>v[2];
	REP(x,3)
		cin>>road[x];
	road[2][0] = '.';
	REP(i,3) {
		preprocess(gapData[i], road[i]);
		DEBUG(5,
			for(Gap* g = gapData[i].next; g <= gapData[i].last; ++g)
				cerr<<*g<<" ";
			cerr<<endl;
		)
	}

	pos[0].set(0, 0);
	pos[1].set(0, 0);
	pos[2].set(0, 0);
	long double result = solve();
	cout.precision(17);
	cout << fixed << result << endl;
	return 0;
}