#include <stdio.h> #define SIZE 1000000 typedef struct { int tot; int min; int pos; } tura_t; tura_t tura[SIZE]; int boys[SIZE]; int divs[SIZE]; char cykl[SIZE+1]; int n_boys; int n_cykl; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int i, g, min; long long int t, k, res, pos, max; scanf("%d", &n_boys); for(i=0; i<n_boys; i++) { scanf("%d", boys+i); } scanf("%d", &n_cykl); fgets(cykl, n_cykl+1, stdin); fgets(cykl, n_cykl+1, stdin); g = gcd(n_boys, n_cykl); t = 1LL * n_boys/g; t *= 1LL * n_cykl; for(i=0; i<n_boys; i++) { for(k=i; k<t; k+=n_boys) { if(cykl[k % n_cykl] == 'W') { (tura+i)->tot++; } if(cykl[k % n_cykl] == 'P') { (tura+i)->tot--; if((tura+i)->tot < (tura+i)->min) { (tura+i)->min = (tura+i)->tot; } } } } min = -1; for(i=0; i<n_boys; i++) { if((tura+i)->tot < 0) { divs[i] = boys[i]/-((tura+i)->tot) - (boys[i]%-((tura+i)->tot) ? 0 : 1 ); if(min == -1) { min = divs[i]; } else { min = divs[i] < min ? divs[i] : min; } } else divs[i] = -1; } if(min == -1) { res = -1LL; } else { res = 1LL * min * t; for(i=0; i<n_boys; i++) { boys[i] += min * (tura+i)->tot; } max = -1LL; for(i=0; i<n_boys; i++) { if(divs[i] == min) { pos = 0; for(k=i; !pos && k<t; k+=n_boys) { if(cykl[k % n_cykl] == 'W') { boys[i]++; } if(cykl[k % n_cykl] == 'P') { boys[i]--; if(boys[i] == 0) { pos = k+1; } } } if(max == -1LL) max = pos; else max = pos < max ? pos : max; } } res += max; } printf("%lld\n", res); 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 | #include <stdio.h> #define SIZE 1000000 typedef struct { int tot; int min; int pos; } tura_t; tura_t tura[SIZE]; int boys[SIZE]; int divs[SIZE]; char cykl[SIZE+1]; int n_boys; int n_cykl; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int i, g, min; long long int t, k, res, pos, max; scanf("%d", &n_boys); for(i=0; i<n_boys; i++) { scanf("%d", boys+i); } scanf("%d", &n_cykl); fgets(cykl, n_cykl+1, stdin); fgets(cykl, n_cykl+1, stdin); g = gcd(n_boys, n_cykl); t = 1LL * n_boys/g; t *= 1LL * n_cykl; for(i=0; i<n_boys; i++) { for(k=i; k<t; k+=n_boys) { if(cykl[k % n_cykl] == 'W') { (tura+i)->tot++; } if(cykl[k % n_cykl] == 'P') { (tura+i)->tot--; if((tura+i)->tot < (tura+i)->min) { (tura+i)->min = (tura+i)->tot; } } } } min = -1; for(i=0; i<n_boys; i++) { if((tura+i)->tot < 0) { divs[i] = boys[i]/-((tura+i)->tot) - (boys[i]%-((tura+i)->tot) ? 0 : 1 ); if(min == -1) { min = divs[i]; } else { min = divs[i] < min ? divs[i] : min; } } else divs[i] = -1; } if(min == -1) { res = -1LL; } else { res = 1LL * min * t; for(i=0; i<n_boys; i++) { boys[i] += min * (tura+i)->tot; } max = -1LL; for(i=0; i<n_boys; i++) { if(divs[i] == min) { pos = 0; for(k=i; !pos && k<t; k+=n_boys) { if(cykl[k % n_cykl] == 'W') { boys[i]++; } if(cykl[k % n_cykl] == 'P') { boys[i]--; if(boys[i] == 0) { pos = k+1; } } } if(max == -1LL) max = pos; else max = pos < max ? pos : max; } } res += max; } printf("%lld\n", res); return 0; } |