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;
}