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
import java.util.Scanner;

public class haz {

	static int n, m;
	static int[] players;
	static char[] rules;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		players = new int[n];
		for (int i = 0; i < n; ++i) {
			players[i] = sc.nextInt();
		}
		m = sc.nextInt();
		rules = sc.next().toCharArray();

		if (n == m || (n > m && n % m == 0)) {
			calculateSimple();
			return;
		}

		long nww = nww(n, m);
		int steps = (int) (nww / n);

		int[] gains = new int[n];
		int[] maxLoses = new int[n];
		for (int i = 0; i < n; ++i) {
			for (int j = 1; j <= steps; ++j) {
				char r = rules[(int) ((((long) j * n) - (n - i)) % m)];
				if (r == 'P') {
					gains[i] -= 1;
					if (gains[i] < maxLoses[i]) {
						maxLoses[i] = gains[i];
					}
				} else {
					gains[i] += 1;
				}
			}
		}

		long loser = Long.MAX_VALUE;
		for (int i = 0; i < n; ++i) {
			if (players[i] + maxLoses[i] <= 0) {
				// will lose in first iteration
				int sum = players[i];
				for (int j = 1; j <= steps; ++j) {
					char r = rules[(j * n - (n - i)) % m];
					if (r == 'P') {
						sum -= 1;
						if (sum == 0) {
							long newLoser = (j - 1) * n + i;
							if (newLoser < loser) {
								loser = newLoser;
							}
							break;
						}
					} else {
						sum += 1;
					}
				}
			} else if (gains[i] < 0) {
				// will lose later on
				int allowedSum = players[i] + maxLoses[i];
				int iters = allowedSum / -gains[i];
				if (allowedSum % -gains[i] != 0) {
					iters += 1;
				}
				int sum = players[i] + iters * gains[i];
				long itersNww = iters * nww;
				for (int j = 1; j <= steps; ++j) {
					char r = rules[(j * n - (n - i)) % m];
					if (r == 'P') {
						sum -= 1;
						if (sum == 0) {
							long newLoser = (j - 1) * n + i + itersNww;
							if (newLoser < loser) {
								loser = newLoser;
							}
							break;
						}
					} else {
						sum += 1;
					}
				}
			}
		}
		System.out.println(loser == Long.MAX_VALUE ? -1 : (loser + 1));
	}

	static void calculateSimple() {
		int minLoser = Integer.MAX_VALUE;
		int minLoserIdx = -1;
		for (int i = 0; i < n; ++i) {
			int j = i % m;
			if (rules[j] == 'P') {
				if (players[i] < minLoser) {
					minLoser = players[i];
					minLoserIdx = i;
				}
			}
		}
		System.out.println(minLoserIdx == -1 ? -1 : ((minLoser - 1) * n + minLoserIdx + 1));
	}

	static long nww(long a, long b) {
		return a / nwd(a, b) * b;
	}

	static long nwd(long a, long b) {
		long buf;
		while (b != 0) {
			buf = b;
			b = a % b;
			a = buf;
		}
		return a;
	}
}