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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits.h>

using std::vector;
using std::sqrt;
using std::floor;

struct guy {
	long long money;
	//vector<long long> attempt;
	long long expires;

};

long long gcd(long long a, long long b) {
    return b == 0ll ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b)
{
	return a * b / gcd(a, b);
}

int main(void)
{
	long long n, m;
	scanf("%lld", &n);
	vector<struct guy> guy;
	guy.reserve(n);

	for (long long i = 0ll; i < n; i++) {
		long long tmp;
		scanf("%lld", &tmp);
		guy[i].money = tmp;
	}

	scanf("%lld\n", &m);

	vector<signed char> loop;
	loop.reserve(m);

	/* convert each char of the string into a net value */
	for (long long i = 0ll; i < m; i++) {
		char tmp;
		scanf("%c", &tmp);
		switch (tmp) {
			case 'W':
				loop.push_back((signed char) 1);
				break;
			case 'P':
				loop.push_back((signed char) -1);
				break;
		}
	}

	/* each guy has a list of games that's attempts long */
	long long attempts = lcm(n, m) / n;
	bool infinite = true;

	/* the number of the first game in which somebody goes bakrupt */
	long long first = LLONG_MAX;

	for (long long i = 0ll; i < n; i++) {
		//guy[i].attempt.reserve(attempts);

		long long k = 0ll;
		long long net = 0ll;
		long long min = 0ll;
		long long mark;

		/* create a list of games he participates in */
		for (long long j = 0ll; j < attempts; j++) {
			if (k >= m) {
				k -= m;
			}
			//guy[i].attempt.push_back(loop[k]);
			net += loop[k];
			if (net < min) {
				mark = j;
				min = net;
			}
			k += n;
		}
		min = -min;

		/* determine on which game he goes bankrupt */
		if (guy[i].money >= min && net >= 0ll) {
			guy[i].expires = -1ll;
		}
		else if (guy[i].money < min && net >= 0ll) {
			guy[i].expires = mark + 1ll;
		}
		else {
			/* he completes money / net complete games */
			guy[i].expires = guy[i].money / (-net) * attempts;
			/* add what's left over */
			if (guy[i].money % (-net) != 0) {
				long long dosh = guy[i].money % (-net);
				long long l = 0;
				long long o = 0;
				//for (l = 0ll; dosh > 0; l++) {
				while (dosh > 0) {
					if (l >= m)
						l -= m;
					dosh -= loop[l];
					l += n;
					o++;
				}
				guy[i].expires += o;
			}
		}

		/* find the first to go bankrupt */
		if (guy[i].expires != -1ll)
			infinite = false;

		if ((guy[i].expires - 1) * n + i + 1 < first)
			first = (guy[i].expires - 1) * n + i + 1;
	}

	if(infinite) {
		printf("-1\n");
		return 0;
	}

	printf("%lld\n", first);


	return 0;

}