//Jan Omeljaniuk // #include <list> #include <stack> #include <queue> #include <vector> #include <string> #include <bitset> #include <cassert> #include <iostream> #include <algorithm> #define debug #define debug_btree #define unm unsigned long long int #define nm long long int #define uint unsigned int using namespace std; uint n,m; unm rcyklu, mini = 18446744073700551610ULL; vector<bool> odw; vector<nm> osc; string tekst; unm gcd(unm a, unm b) { return b == 0ULL ? a : gcd(b, a%b); } unm lcm(unm a, unm b) { unm c = __gcd(a, b); return c == 0ULL ? 0ULL : a / c * b; } unm sprawdz(uint x, unm id, unm cur, const bool f){ if(id>=rcyklu) if(osc[x]<=cur) return 18446744073700551610ULL; if(tekst[x]=='W') ++cur; else --cur; //cerr << "x:" << x << " id:" << id << " cur" << cur << "\n"; if(cur == 0 && !f) return id; return sprawdz((x+n)%m, id+n, cur, false); } int main(){ ios_base::sync_with_stdio(false); cin >> n; osc.resize(n); for(uint i=0;i<n;++i) cin >> osc[i]; cin >> m; cin >> tekst; odw.resize(m); rcyklu = lcm(m,n); for(uint i=0;i<n;++i) mini = min(mini, i + 1 + sprawdz(i, 0, osc[i], true)); if(mini==18446744073700551610ULL) cout << "-1\n"; else cout << mini << "\n"; return 0; }
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 | //Jan Omeljaniuk // #include <list> #include <stack> #include <queue> #include <vector> #include <string> #include <bitset> #include <cassert> #include <iostream> #include <algorithm> #define debug #define debug_btree #define unm unsigned long long int #define nm long long int #define uint unsigned int using namespace std; uint n,m; unm rcyklu, mini = 18446744073700551610ULL; vector<bool> odw; vector<nm> osc; string tekst; unm gcd(unm a, unm b) { return b == 0ULL ? a : gcd(b, a%b); } unm lcm(unm a, unm b) { unm c = __gcd(a, b); return c == 0ULL ? 0ULL : a / c * b; } unm sprawdz(uint x, unm id, unm cur, const bool f){ if(id>=rcyklu) if(osc[x]<=cur) return 18446744073700551610ULL; if(tekst[x]=='W') ++cur; else --cur; //cerr << "x:" << x << " id:" << id << " cur" << cur << "\n"; if(cur == 0 && !f) return id; return sprawdz((x+n)%m, id+n, cur, false); } int main(){ ios_base::sync_with_stdio(false); cin >> n; osc.resize(n); for(uint i=0;i<n;++i) cin >> osc[i]; cin >> m; cin >> tekst; odw.resize(m); rcyklu = lcm(m,n); for(uint i=0;i<n;++i) mini = min(mini, i + 1 + sprawdz(i, 0, osc[i], true)); if(mini==18446744073700551610ULL) cout << "-1\n"; else cout << mini << "\n"; return 0; } |