#include <cstdio> #include <cstdlib> using namespace std; long long NWD(long long a, long long b) { long long x,y,z; x = a; y = b; if (x < y) { z = x; x = y; y = z; } if (b == 0) return a; else return NWD(y,x % y); } long long NWW(long long a, long long b) { return a * b / NWD(a,b); } int main() { char c; long long i,j,k,N,*n,*t,*d,*in,M,*m,s,f_v,f_u; scanf("%lld\n",&N); n = (long long *) malloc(N*sizeof(long long));//wartosci poczatkowe t = (long long *) malloc(N*sizeof(long long));//wartosci aktualne d = (long long *) malloc(N*sizeof(long long));//max spadek w cyklu in = (long long *) malloc(N*sizeof(long long));//index max spadku for (i = 0; i < N; i++) { scanf("%lld",n+i); t[i] = n[i]; d[i] = 0; } scanf("%lld\n",&M); m = (long long *) malloc(M*sizeof(long long));//wygrane/przegrane for (i = 0; i < M; i++) { scanf("%c",&c); // printf("%c\n",c); if (c == 'W') m[i] = 1; else m[i] = -1; } i = 0; j = NWW(N,M); while (i < j) { //printf("%lld %lld %lld\n",i,t[i%N],m[i%M]); t[i%N] += m[i%M]; if (d[i%N] < n[i%N] - t[i%N]) {d[i%N] = n[i%N] - t[i%N]; in[i%N] = i%M;} if (t[i%N] == 0) break; i++; } if (i < j) {printf("%lld\n",i+1); return 0;} else { s = 0; f_v = 1000000000; for (i = 0; i < N; i++) { if (t[i] >= n[i]) s++; else { k = (long long) (t[i] - d[i]) / (n[i] - t[i]); if (k < f_v) {f_v = k; f_u = i;} // printf("f for %lld = %lld\n",i,(long long) (t[i] - d[i]) / (n[i] - t[i])); } } if (s == N) {printf("-1\n"); return 0;} else { // j : NWW(N,M) // f_u : index usera o najnizszym f_v // f_v : min f dla usera f_u j += f_v * j; k = n[f_u] - t[f_u]; t[f_u] -= f_v * (n[f_u] - t[f_u]); // printf("j:%lld f_u:%lld f_v:%lld t:%lld d:%lld\n",j,f_u,f_v,t[f_u],j%M); while (1) { t[f_u] += m[j%M]; if (t[f_u] == 0) break; j += N; } printf("%lld\n",j+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 | #include <cstdio> #include <cstdlib> using namespace std; long long NWD(long long a, long long b) { long long x,y,z; x = a; y = b; if (x < y) { z = x; x = y; y = z; } if (b == 0) return a; else return NWD(y,x % y); } long long NWW(long long a, long long b) { return a * b / NWD(a,b); } int main() { char c; long long i,j,k,N,*n,*t,*d,*in,M,*m,s,f_v,f_u; scanf("%lld\n",&N); n = (long long *) malloc(N*sizeof(long long));//wartosci poczatkowe t = (long long *) malloc(N*sizeof(long long));//wartosci aktualne d = (long long *) malloc(N*sizeof(long long));//max spadek w cyklu in = (long long *) malloc(N*sizeof(long long));//index max spadku for (i = 0; i < N; i++) { scanf("%lld",n+i); t[i] = n[i]; d[i] = 0; } scanf("%lld\n",&M); m = (long long *) malloc(M*sizeof(long long));//wygrane/przegrane for (i = 0; i < M; i++) { scanf("%c",&c); // printf("%c\n",c); if (c == 'W') m[i] = 1; else m[i] = -1; } i = 0; j = NWW(N,M); while (i < j) { //printf("%lld %lld %lld\n",i,t[i%N],m[i%M]); t[i%N] += m[i%M]; if (d[i%N] < n[i%N] - t[i%N]) {d[i%N] = n[i%N] - t[i%N]; in[i%N] = i%M;} if (t[i%N] == 0) break; i++; } if (i < j) {printf("%lld\n",i+1); return 0;} else { s = 0; f_v = 1000000000; for (i = 0; i < N; i++) { if (t[i] >= n[i]) s++; else { k = (long long) (t[i] - d[i]) / (n[i] - t[i]); if (k < f_v) {f_v = k; f_u = i;} // printf("f for %lld = %lld\n",i,(long long) (t[i] - d[i]) / (n[i] - t[i])); } } if (s == N) {printf("-1\n"); return 0;} else { // j : NWW(N,M) // f_u : index usera o najnizszym f_v // f_v : min f dla usera f_u j += f_v * j; k = n[f_u] - t[f_u]; t[f_u] -= f_v * (n[f_u] - t[f_u]); // printf("j:%lld f_u:%lld f_v:%lld t:%lld d:%lld\n",j,f_u,f_v,t[f_u],j%M); while (1) { t[f_u] += m[j%M]; if (t[f_u] == 0) break; j += N; } printf("%lld\n",j+1); } } return 0; } |