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
// ale syf
// ale jeżeli to rzeczywiście przechodzi Dijkstrą (a raczej tak), to pomysł miałem dobry xD

#include <bits/stdc++.h>
using namespace std;

int64_t L;
vector<pair<int,int>> v1[3];
vector<pair<int,int>>& auta(char c) {
	return v1[c-'a'];
}
double v2[4];
double& pred(char c='0') {
	if(c=='0') return v2[3];
	return v2[c-'a'];
}

vector<pair<int,int>> wez_przedzialy() {
	int l=-1, r=-1;
	vector<pair<int,int>> v;
	string s;
	cin >> s;
	for(int i=0; i<L; ++i) {
		if(i+1!=L&&s[i+1]=='#') {
			if(l==-1) l = i;
			r = i;
		} else {
			if(l!=-1) {
				v.push_back({l,r});
				l = -1;
			}
		}
	}
	//cerr << s.substr(1) << endl;
	//for(auto &&e : v) cerr << e.first << ' ' << e.second << endl; cerr << endl;
	return v;
}
struct pos {
	double t;
	char tor; // abc
	int i;
	bool operator<(const struct pos &r) const {
		return this->t > r.t; // ~priorytet
	}
};
double off(char c, double t0) {
	return t0 * pred(c);
}
double droga(char c, double t0, int i) {
	return off(c, t0) + i;
}
double policz_wynik(double t0, double s0) {
	// t0 + s-s0
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed << showpoint << setprecision(15);
	cin >> L >> pred('0') >> pred('a') >> pred('b') >> pred('c');
	auta('a') = wez_przedzialy();
	auta('b') = wez_przedzialy();
	auta('c') = wez_przedzialy();
	if(auta('a').size()==0||auta('b').size()==0||auta('c').size()==0) {
		double max_czas = 0;
		for(auto &&e : {'a', 'b', 'c'})
			if(auta(e).size()!=0) {
				// cerr << e << endl;
				// cerr << (1+auta(e)[auta(e).size()-1].second-(-1)) << ' ' << (pred('0')-pred(e)) << endl;
				max_czas = max(max_czas, ((double)(1+(auta(e)[auta(e).size()-1].second/*i1*/-(-1)))/((double)pred('0')-pred(e))));
				}
		
		cout << max_czas << '\n';
		return 0;
		
	}
	pair<double, char> minimum = min({
		(pair<double, char>){((double)(auta('a')[0].first-0))/((double)(pred('0')-pred('a'))), 'a'},
		(pair<double, char>){((double)(auta('b')[0].first-0))/((double)(pred('0')-pred('b'))), 'b'},
		(pair<double, char>){((double)(auta('c')[0].first-0))/((double)(pred('0')-pred('c'))), 'c'}
	});
	//cerr << minimum.first << ' ' << minimum.second << ' ' << auta(minimum.second)[0].first-1 << endl;
	priority_queue<struct pos> pq;
	unordered_set<size_t> vis; // tor, indeks
	pq.push({minimum.first, minimum.second, auta(minimum.second)[0].first-1});
	while(pq.size()) {
		auto &&v = pq.top();
		size_t id = v.i<<8 | v.tor;
		if(vis.find(id)!=vis.end()) {pq.pop(); continue;}
		vis.insert(id);
		// końcowe
		if('A'<=v.tor&&v.tor<='C') {
			cout << v.t << '\n';
			return 0;
		}
		//cerr << v.t << ' ' << v.i << ' ' << v.tor << endl;
		vector<struct pos> temporary; // indeksowanie się pieprzy przy pushu
		if(v.tor!='a') { // próbuję iść do góry
			char D = 1;
			int i_f = v.i + ((int)-v.t*(pred(v.tor-D)/*v_f*/-pred(v.tor)/*v_e*/)/*cast w dół*/); // -(-(v))
			//cerr << i_f << endl;
			auto &&af = auta(v.tor-D);
			// chcę większy lub równy koniec
			auto it = lower_bound(af.begin(), af.end(), (pair<int,int>){0, i_f}, [](const pair<int,int> &l, const pair<int,int> &r) -> bool { return l.second < r.second; }); // ściśle większa
			if(it == af.end()) {
				double max_czas;
				for(auto &&e : {'a', 'b', 'c'})
					max_czas = max(max_czas, ((double)(1+v.t*(pred(v.tor)-pred(e))+v.i-auta(e)[auta(e).size()-1].second)/((double)pred('0')-pred(e))));
				temporary.push_back({v.t+max_czas, 'A', 0});
			} else {
				i_f = it->first;
				//cerr << v.i << ' ' << i_f << ' ' << pred('0') << ' ' << pred(v.tor-D) << ' ' << v.t << endl;
				double dt = abs(((double)(1+v.i-i_f))/((double)(pred('0')-pred(v.tor-D))));
				//cerr << "idę do góry i znajdę się na torze " << (char)(v.tor-D) << " w miejscu " << i_f-1 << " w czasie " << v.t+dt << endl;
				temporary.push_back({v.t+dt, v.tor-D, i_f-1});
			}
			if(v.tor=='c') { // drugi raz
				D = 2;
				int i_f = v.i + ((int)-v.t*(pred(v.tor-D)/*v_f*/-pred(v.tor)/*v_e*/)/*cast w dół*/); // -(-(v))
				//cerr << i_f << endl;
				auto &&af = auta(v.tor-D);
				// chcę większy lub równy koniec
				auto it = lower_bound(af.begin(), af.end(), (pair<int,int>){0, i_f}, [](const pair<int,int> &l, const pair<int,int> &r) -> bool { return l.second < r.second; }); // ściśle większa
				if(it == af.end()) {
					double max_czas;
					for(auto &&e : {'a', 'b', 'c'})
						max_czas = max(max_czas, ((double)(1+v.t*(pred(v.tor)-pred(e))+v.i-auta(e)[auta(e).size()-1].second)/((double)pred('0')-pred(e))));
					temporary.push_back({v.t+max_czas, 'A', 0});
				} else {
					i_f = it->first;
					//cerr << v.i << ' ' << i_f << ' ' << pred('0') << ' ' << pred(v.tor-D) << ' ' << v.t << endl;
					double dt = abs(((double)(1+v.i-i_f))/((double)(pred('0')-pred(v.tor-D))));
					//cerr << "idę do góry i znajdę się na torze " << (char)(v.tor-D) << " w miejscu " << i_f-1 << " w czasie " << v.t+dt << endl;
					temporary.push_back({v.t+dt, v.tor-D, i_f-1});
				}
			}
		}
		if(v.tor!='c') { // próbuję iść na dół
			// a tutaj złapać wszystkie w przedziale od aktualnej drogi do końca i pododować kolejne wierzchołki grafu do kolejki...
			// tak miało być
		}
		pq.pop();
		for(auto &&e : temporary)
			pq.push(e);
		
	}
	
}