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
#include <cstdio>

//#define DEBUG

#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif

using namespace std;

const int MAX = 1000005;

int players[MAX];
int results[MAX];

int main() {
  int n, m;

  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%d", players + i);
  }
  
  scanf("%d", &m);
  for(int i = 1; i <= m; i++) {
    char c;
    while((c = getchar()) != 'P' && c != 'W') {
    }
    if(c == 'P') results[i] = -1;
    else results[i] = 1;
  }

  long long min = -1;
  for(int i = 1; i <= n; i++) {
    long long sum = players[i];
    D(printf("Simulating player #%d with sum = %lld.\n", i, sum);)
    long long round = i;
    int current = i % m;
    if(current == 0) current = m;

    long long best_round = round;
    long long best_sum = sum;
    while(true) {
      D(printf("- ROUND %lld, sum = %lld + (%d) = %lld.\n", round, sum, results[current], sum + results[current]);)
      sum += results[current];
      if(sum < best_sum) {
        best_sum = sum;
        best_round = round;
      }

      if(sum == 0) {
        if(min == -1 || round < min) min = round;
        D(printf("-- Lost all money in round %lld.\n", round);)
        break;
      }
      current = (current + n) % m;
      if(current == 0) current = m;
      if(current == i % m) {
        long long diff = sum - players[i];
        D(printf("-- Lost %lld in %lld rounds.\n", diff, round);)
        if(diff < 0) {
          if(players[i] > best_sum) {
            long long best_spot = players[i] - best_sum;
            D(printf("-- Best gain in previous cycle was %lld.\n", -best_spot);)
            if(sum > best_spot) {
              long long additional_cycles = sum / (-diff);
              if(sum % (-diff) == 0) additional_cycles -= 1;
              long long additional_rounds = additional_cycles * round;
              sum += additional_cycles * diff;
              round += additional_rounds;
              D(printf("--- Skipping %lld rounds.\n", additional_rounds);)
            }
          }
        } else {
          D(printf("-- CANNOT LOSE.\n");)
          break;
        }
      }
      round += n;
    }
  }

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

  return 0;
}