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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <cstdio>
#include <climits>
#include <cstdint>
#include <cassert>
#include <utility>
using namespace std;

#define DEBUG(fmt, args...) do {\
	if (debug) {\
		fprintf(stderr, "%s: " #args " " fmt, __func__, args);\
		fflush(stderr);\
	} } while(0)


const static bool debug = false;
const static uint32_t MAX_N = 1000000;
const static uint32_t MAX_M = 1000000;

int32_t A[MAX_N];	// początkowy stan
int8_t C[MAX_M];	// wzorzec
int32_t R[MAX_M];	// suma na cyklu
int32_t M[MAX_M];	// minimum na każdym cyklu
pair<int32_t, uint64_t> dR[MAX_M];	// suma dojścia do cyklu i liczba tur
int32_t dM[MAX_M];	// minimum na dojściu do cyklu
bool visited[MAX_M];

uint32_t nwd(uint32_t a, uint32_t b) {
	if (b != 0)
		return nwd(b, a % b);
	return a;
}

int main() {
	uint32_t n, m, i, s;
	char c;
	scanf("%lu", &n);
	for (i = 0; i < n; ++i)
		scanf("%lu", A + i);
	scanf("%lu\n", &m);
	for (i = 0; i < m; ++i) {
		scanf("%c", &c);
		C[i] = (c == 'W') ? 1 : -1;
	}
	uint32_t cyclesNum = nwd(n, m);

	uint32_t **steps = new uint32_t *[cyclesNum];
	uint32_t cycleLength = m / cyclesNum;
	for (i = 0; i < cyclesNum; ++i) {
		steps[i] = new uint32_t [cycleLength];
		for (uint32_t j = 0; j < cycleLength; ++j)
			steps[i][j] = 0;
	}

	uint32_t jump = n % m;	// skok przy przejściu
	for (s = 0; s < m; ++s) {
		if (visited[s])
			continue;

		// idziemy w przód
		i = s;
		int32_t sum = 0;
		int32_t min = 0;
		uint32_t stepsNum = 0;
		cycleLength = 0;
		do {
			visited[i] = true;
			sum += C[i];
			++stepsNum;
			if (sum < min) {
				steps[s][-sum] = stepsNum;
				min = sum;
			}
			i += jump;
			if (i >= m)
				i -= m;
			++cycleLength;
		} while (i != s);
		R[s] = sum;	// suma na cyklu
		M[s] = min;	// osiągalne minimum na cyklu

		DEBUG("%u %d\n", s, R[s]);
		DEBUG("%u %d\n", s, M[s]);

		uint32_t k = 0;
		dR[s] = make_pair(0, 0);
		int32_t prev = 0;
		dM[s] = min = 0;
		i = s;
		do {
			if (i < jump)
				i += m - jump;
			else
				i -= jump;
			if (i == s)
				break;
			dR[i] = make_pair(prev += C[i], ++k); // dojście na początek cyklu
			if (prev < min)
				min = prev;			// minimalna suma na dojściu do cyklu
			dM[i] = min;
			DEBUG("%u %d\n", i, dM[i]);
		} while (i != s);
	}

	DEBUG("%d %d\n", cycleLength, jump);

	uint64_t games, minGames = ULLONG_MAX;
	for (i = 0; i < n; ++i) {
		games = i;		// początkowe i gier, i + 1 jest nasza
		s = i % m;		// początkowa pozycja w cyklu
		uint32_t t = s;
		DEBUG("\na. %u\n", i);
		if (s >= cyclesNum) {
			// nie jesteśmy na początku cyklu
			if ((int32_t)A[i] + dM[s] <= 0) {
				// koniec gry na dojściu do początku cyklu
				while (s >= cyclesNum && A[i] > 0) {
					DEBUG("%u, %d\n", s, A[i]);
					A[i] += C[games % m];
					games += n;
					s += jump;
					if (s >= m)
						s -= m;
				}
				games -= n - 1;
//				assert(s == t % cyclesNum);
			} else {
				// dochodzimy do początku cyklu
				A[i] += dR[s].first;
				games += dR[s].second * n;
				s = s % cyclesNum;
			}
		}
		if (A[i] > 0) {
			DEBUG("b. %u %d %d %d %d\n", s, A[i], M[s], -R[s], games);
			if (R[s] < 0) {
				// cykl ujemny
				uint64_t tours = (A[i] + M[s] + (-R[s] - 1)) / (-R[s]);
				games += tours * cycleLength * n;
				A[i] += R[s] * tours;
				DEBUG("%d %d\n", tours, A[i]);
			}
			if (M[s] < 0 && A[i] <= -M[s]) {
				DEBUG("%d\n", steps[s][A[i]]);
				games += (uint64_t) steps[s][A[i]] * n - n + 1;
				A[i] = 0;
			}
			DEBUG("%d\n", games);
		}
		if (A[i] <= 0 and games < minGames)
			minGames = games;
	}

	if (minGames == ULLONG_MAX)
		printf("-1");
	else
		printf("%llu", minGames);

	for (i = 0; i < cyclesNum; ++i)
		delete [] steps[i];
	delete [] steps;

	return 0;
}