#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAX = 1000001; int n, m, p[MAX]; bool c[MAX]; int mini[MAX], kon[MAX], kol[MAX]; int NWD (int a, int b) { if (a > b) swap(a, b); if (a == 0) return b; else return NWD(a, b % a); } int main() { ios_base::sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) cin >> p[i]; cin >> m; for (int i = 1; i <= m; i++) { char a; cin >> a; if (a == 'W') c[i] = 1; else c[i] = 0; } int d = NWD(n, m); int lala = n / d; int ela = m / d; int e = lala * ela; for (int i = 1; i <= n; i++) { int nr = i % m; if (nr == 0) nr = m; kon[i] = 0; mini[i] = 0; do { if(c[nr]) kon[i]++; else kon[i]--; if (mini[i] > kon[i]) mini[i] = kon[i]; nr = nr + n; nr = nr % m; if (nr == 0) nr = m; } while(nr != i % m && nr != i % m + m); } c[0] = c[m]; for (int i = 1; i <= n; i++) { p[i] += mini[i]; if (p[i] <= 0) { kol[i] = 1; p[i] -= mini[i]; continue; } if (kon[i] >= 0) { kol[i] = -1; p[i] -= mini[i]; continue; } kon[i] = -kon[i]; if (p[i] % kon[i] == 0) kol[i] = p[i] / kon[i] + 1; else kol[i] = p[i] / kon[i] + 2; p[i] -= mini[i]; } int pierw = -1; for (int i = 1; i <= n; i++) { if (pierw == -1 && kol[i] != -1) pierw = kol[i]; if (kol[i] != -1 && kol[i] < pierw) pierw = kol[i]; } long long int wynik = -1; if (pierw == -1) { cout << - 1; return 0; } for (int i = 1; i <= n; i++) { if (kol[i] != pierw) continue; int stan = p[i] - (pierw - 1) * kon[i]; long long int temp = (kol[i] - 1) * n / d; temp = temp * m; temp = temp - n + i; int nr = i % m; while (stan > 0) { temp += n; if (c[nr]) stan++; else stan--; nr += n; nr = nr % m; } if (temp < wynik || wynik == -1) wynik = temp; } cout << wynik; }
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 | #include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAX = 1000001; int n, m, p[MAX]; bool c[MAX]; int mini[MAX], kon[MAX], kol[MAX]; int NWD (int a, int b) { if (a > b) swap(a, b); if (a == 0) return b; else return NWD(a, b % a); } int main() { ios_base::sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) cin >> p[i]; cin >> m; for (int i = 1; i <= m; i++) { char a; cin >> a; if (a == 'W') c[i] = 1; else c[i] = 0; } int d = NWD(n, m); int lala = n / d; int ela = m / d; int e = lala * ela; for (int i = 1; i <= n; i++) { int nr = i % m; if (nr == 0) nr = m; kon[i] = 0; mini[i] = 0; do { if(c[nr]) kon[i]++; else kon[i]--; if (mini[i] > kon[i]) mini[i] = kon[i]; nr = nr + n; nr = nr % m; if (nr == 0) nr = m; } while(nr != i % m && nr != i % m + m); } c[0] = c[m]; for (int i = 1; i <= n; i++) { p[i] += mini[i]; if (p[i] <= 0) { kol[i] = 1; p[i] -= mini[i]; continue; } if (kon[i] >= 0) { kol[i] = -1; p[i] -= mini[i]; continue; } kon[i] = -kon[i]; if (p[i] % kon[i] == 0) kol[i] = p[i] / kon[i] + 1; else kol[i] = p[i] / kon[i] + 2; p[i] -= mini[i]; } int pierw = -1; for (int i = 1; i <= n; i++) { if (pierw == -1 && kol[i] != -1) pierw = kol[i]; if (kol[i] != -1 && kol[i] < pierw) pierw = kol[i]; } long long int wynik = -1; if (pierw == -1) { cout << - 1; return 0; } for (int i = 1; i <= n; i++) { if (kol[i] != pierw) continue; int stan = p[i] - (pierw - 1) * kon[i]; long long int temp = (kol[i] - 1) * n / d; temp = temp * m; temp = temp - n + i; int nr = i % m; while (stan > 0) { temp += n; if (c[nr]) stan++; else stan--; nr += n; nr = nr % m; } if (temp < wynik || wynik == -1) wynik = temp; } cout << wynik; } |