#include <cstdio> #include <algorithm> const long long INFTY = 10000000000000; int f [1000000]; short int cycle [1000000]; long long nwd (long long a, long long b) { if (b == 0) return a; return nwd (b, a % b); } long long nww (long long a, long long b) { return (a * b) / nwd (a, b); } int main () { int n, m; scanf ("%d", &n); for (int i = 0; i < n; ++ i) { scanf ("%d", &f [i]); } scanf ("%d", &m); char tmp; scanf ("%c", &tmp); for (int i = 0; i < m; ++ i) { scanf ("%c", &tmp); if (tmp == 'W') cycle [i] = 1; else cycle [i] = -1; } long long ans = INFTY; long long cLen = nww (n, m) / n; for (int i = 0; i < n; ++ i) { int pos = i; long long sum = 0; bool flag = 0; for (long long j = 1; j <= cLen; ++ j) { pos %= m; f [i] += cycle [pos]; sum += cycle [pos]; if (f [i] == 0) { ans = std::min (ans, n * j); flag = 1; break; } pos += n; } if (sum >= 0) continue; for (long long j = cLen + 1; !flag; ++ j) { pos %= m; f [i] += cycle [pos]; if (f [i] == 0) { ans = std::min (ans, n * j); flag = 1; } pos += n; } } if (ans == INFTY) printf ("-1\n"); else printf ("%lli\n", ans); 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 | #include <cstdio> #include <algorithm> const long long INFTY = 10000000000000; int f [1000000]; short int cycle [1000000]; long long nwd (long long a, long long b) { if (b == 0) return a; return nwd (b, a % b); } long long nww (long long a, long long b) { return (a * b) / nwd (a, b); } int main () { int n, m; scanf ("%d", &n); for (int i = 0; i < n; ++ i) { scanf ("%d", &f [i]); } scanf ("%d", &m); char tmp; scanf ("%c", &tmp); for (int i = 0; i < m; ++ i) { scanf ("%c", &tmp); if (tmp == 'W') cycle [i] = 1; else cycle [i] = -1; } long long ans = INFTY; long long cLen = nww (n, m) / n; for (int i = 0; i < n; ++ i) { int pos = i; long long sum = 0; bool flag = 0; for (long long j = 1; j <= cLen; ++ j) { pos %= m; f [i] += cycle [pos]; sum += cycle [pos]; if (f [i] == 0) { ans = std::min (ans, n * j); flag = 1; break; } pos += n; } if (sum >= 0) continue; for (long long j = cLen + 1; !flag; ++ j) { pos %= m; f [i] += cycle [pos]; if (f [i] == 0) { ans = std::min (ans, n * j); flag = 1; } pos += n; } } if (ans == INFTY) printf ("-1\n"); else printf ("%lli\n", ans); return 0; } |