#include <stdio.h> #include <stdlib.h> #include <string.h> #define ll long long #define MAX 2000000000000 ll nwd(ll a,ll b) { ll c; while(b!=0) { c = a % b; a = b; b = c; } return a; } ll nww(ll a, ll b) { return a*b/nwd(a,b); } int main() { ll n,m,i,j; ll *ta, *tb, *tc; char *tr; ll nm, mr; scanf("%lld", &n); ta = malloc(n*sizeof(*ta)); tb = malloc(n*sizeof(*tb)); tc = malloc(n*sizeof(*tc)); bzero(tb, n*sizeof(*tb)); bzero(tc, n*sizeof(*tc)); for (i=0; i<n; ++i) { scanf("%lld", ta+i); } scanf("%lld\n", &m); tr = malloc((m+2)*sizeof(*tr)); fgets(tr, m+1, stdin); tr[m] = 0; nm = nww(n,m); for (i=0; i<nm; ++i) { if (tr[i%m] == 'W') { ta[i%n]++; tb[i%n]++; } else { ta[i%n]--; tb[i%n]--; if (tb[i%n] < tc[i%n]) tc[i%n] = tb[i%n]; } if (ta[i%n] == 0) { printf("%lld\n", i+1); free(ta); free(tb); free(tc); free(tr); return 0; } } mr = MAX; for (i=0; i<n; ++i) { if (tb[i] < 0) { j = ta[i] + tc[i]; j /= 0-tb[i]; if (j<mr) mr = j; } } if (mr == MAX) { printf("-1\n"); free(ta); free(tb); free(tc); free(tr); return 0; } for (i=0; i<n; ++i) { ta[i] += mr*tb[i]; } for (i = (mr+1)*nm; ta[(i-1)%n] > 0; i++) { if (tr[i%m] == 'W') { ta[i%n]++; } else { ta[i%n]--; } } printf("%lld\n", i); free(ta); free(tb); free(tc); free(tr); 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 | #include <stdio.h> #include <stdlib.h> #include <string.h> #define ll long long #define MAX 2000000000000 ll nwd(ll a,ll b) { ll c; while(b!=0) { c = a % b; a = b; b = c; } return a; } ll nww(ll a, ll b) { return a*b/nwd(a,b); } int main() { ll n,m,i,j; ll *ta, *tb, *tc; char *tr; ll nm, mr; scanf("%lld", &n); ta = malloc(n*sizeof(*ta)); tb = malloc(n*sizeof(*tb)); tc = malloc(n*sizeof(*tc)); bzero(tb, n*sizeof(*tb)); bzero(tc, n*sizeof(*tc)); for (i=0; i<n; ++i) { scanf("%lld", ta+i); } scanf("%lld\n", &m); tr = malloc((m+2)*sizeof(*tr)); fgets(tr, m+1, stdin); tr[m] = 0; nm = nww(n,m); for (i=0; i<nm; ++i) { if (tr[i%m] == 'W') { ta[i%n]++; tb[i%n]++; } else { ta[i%n]--; tb[i%n]--; if (tb[i%n] < tc[i%n]) tc[i%n] = tb[i%n]; } if (ta[i%n] == 0) { printf("%lld\n", i+1); free(ta); free(tb); free(tc); free(tr); return 0; } } mr = MAX; for (i=0; i<n; ++i) { if (tb[i] < 0) { j = ta[i] + tc[i]; j /= 0-tb[i]; if (j<mr) mr = j; } } if (mr == MAX) { printf("-1\n"); free(ta); free(tb); free(tc); free(tr); return 0; } for (i=0; i<n; ++i) { ta[i] += mr*tb[i]; } for (i = (mr+1)*nm; ta[(i-1)%n] > 0; i++) { if (tr[i%m] == 'W') { ta[i%n]++; } else { ta[i%n]--; } } printf("%lld\n", i); free(ta); free(tb); free(tc); free(tr); return 0; } |