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
// NFY

#include <cstdio>
#include <algorithm>

using namespace std;

static const int maxn = 1000005;

static int m, n;
static int start[maxn];
static int cycle[maxn];
static char raw_cycle[maxn+19];

static bool player_checked[maxn];
static char field_state[maxn];
static long long int best_res = -1;

static inline void process_player(int player)
{
	int have = start[player];
	const int field = player % m;
	int cycle_sum = 0;
	int cycle_min = 0;
	int cycle_moves = 0;

	// get to know about cycle
	for (int i = field; field_state[i] != 1; i = (i + n) % m) {
		cycle_sum += cycle[i];
		cycle_min = min(cycle_min, cycle_sum);
		field_state[i] = 1;
		cycle_moves++;
	}

	for (int j = field; field_state[j] != 0; j = (j + n) % m) {
		// pick lowest have of all players starting at the same field
		for (int i = j % n; i < n; i += m) {
			if (player_checked[i])
				break;
			player_checked[i] = true;
			if (start[i] < have) {
				have = start[i];
				player = i;
			}
		}
		
		// do move and go to next field
		have += cycle[j];
		field_state[j] = 0;
	}

	// now we have player with lowest start val, cycle sum and min.
	if (cycle_min + start[player] > 0 && cycle_sum >= 0)
		return;


	long long int max_cycles = (start[player] + cycle_min > 0) ?
		((start[player] + cycle_min) / ((long long )(-cycle_sum))) : 0;

	long long int moves = max_cycles * ((long long int) cycle_moves);
	int left = start[player] + cycle_sum * max_cycles;
	for (int i = player % m; left > 0; i = (i + n) % m) {
		left += cycle[i];
		moves++;
	}

	moves = moves * ((long long int) n) - ((long long int) (n - 1 - player));
	if (best_res == -1 || moves < best_res)
		best_res = moves;
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &start[i]);
		player_checked[i] = false;
	}
	scanf("%d", &m);
	scanf("%s", raw_cycle);
	for (int i = 0; i < m; i++) {
		cycle[i] = raw_cycle[i] == 'W' ? 1 : -1;
		field_state[i] = 0;
	}

	for (int i = 0; i < n; i++)
		if (!player_checked[i])
			process_player(i);

	printf("%lld\n", best_res);
	return 0;
}