#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <string.h> /* PA-2015 R3 */ /* Brute force, please do not expect too much :) */ using namespace std; typedef vector<int> VI; typedef long long LL; #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second int na [1000100]; int orig [1000100]; char inp [1000100]; int mx_desc [1000100]; int nwdf(int a, int b) { while(b) swap(a %= b, b); return a; } int main() { int n, k; scanf("%d", &n); REP(i, n) { scanf("%d", &(na[i])); orig[i] = na[i]; } scanf("%d", &k); int read = 0; scanf("%s", inp); int nwd = nwdf(k, n); if(strstr(inp, "P") == NULL) { printf("%d\n", -1); return 0; } int cnt = 0; while(1) { na[cnt % n] += inp[cnt % k] == 'W' ? 1 : -1; if(na[cnt % n ] == 0) { goto exit; } cnt++; if (cnt == k * n / nwd) { bool impr = false; REP(i, n) { if(na[i] < orig[i]) { impr = true; break; } } if(!impr) { printf("%d\n", -1); return 0; } } if(cnt == 200000000) { printf("%d\n", -1); return 0; } } exit: printf("%d\n", cnt + 1); 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 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <string.h> /* PA-2015 R3 */ /* Brute force, please do not expect too much :) */ using namespace std; typedef vector<int> VI; typedef long long LL; #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second int na [1000100]; int orig [1000100]; char inp [1000100]; int mx_desc [1000100]; int nwdf(int a, int b) { while(b) swap(a %= b, b); return a; } int main() { int n, k; scanf("%d", &n); REP(i, n) { scanf("%d", &(na[i])); orig[i] = na[i]; } scanf("%d", &k); int read = 0; scanf("%s", inp); int nwd = nwdf(k, n); if(strstr(inp, "P") == NULL) { printf("%d\n", -1); return 0; } int cnt = 0; while(1) { na[cnt % n] += inp[cnt % k] == 'W' ? 1 : -1; if(na[cnt % n ] == 0) { goto exit; } cnt++; if (cnt == k * n / nwd) { bool impr = false; REP(i, n) { if(na[i] < orig[i]) { impr = true; break; } } if(!impr) { printf("%d\n", -1); return 0; } } if(cnt == 200000000) { printf("%d\n", -1); return 0; } } exit: printf("%d\n", cnt + 1); return 0; } |