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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <algorithm>

using std::min;

const int kMaxChildren = 1000000;
const int kMaxCasinoCycleLength = 1000000;
const int kMaxCycles = 1000000;

int total_children;
int children_money[kMaxChildren];
int casino_cycle_length;
int casino_cycle_profit[kMaxCasinoCycleLength];
int total_cycles;
int cycle_length;
int cycle_offset;
int cycle_profit[kMaxCycles];
int cycle_idx_map[kMaxCasinoCycleLength];
int64_t children_endurance[kMaxChildren];

int gcd(int a, int b) { // rosetta code
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

int lcm(int a, int b) { // rosetta code
    int c = gcd(a, b);
    return c == 0 ? 0 : a / c * b;
}

int casino_idx(int cycle, int cycle_idx) {
    int casino_idx = (cycle + cycle_idx * cycle_offset) % casino_cycle_length;
    return casino_idx;
}

class PowerNode {
  public:
    PowerNode(int from_, int to_, int cycle) {
        from = from_;
        to = to_;
        if (from != to) {
            int interval_length = to - from + 1;
            int left_from = from;
            int left_to = from + (interval_length / 2) - 1;
            int right_from = left_to + 1;
            int right_to = to;

            left = new PowerNode(left_from, left_to, cycle);
            right = new PowerNode(right_from, right_to, cycle);

            profit = left->profit + right->profit;
            max_deficit = min(left->max_deficit, left->profit + right->max_deficit);
        } else {
            int cidx = casino_idx(cycle, from);
            profit = casino_cycle_profit[cidx];
            max_deficit = casino_cycle_profit[cidx];
        }
//        printf("%d : cycle | %d : from | %d : to | %d : profit | %d : max deficit", cycle, from, to, profit, max_deficit);
//        if (from == to) {
//            printf(" | %d : casino idx\n", casino_idx(cycle, from));
//        } else {
//            printf("\n");
//        }
    }
    int from; // inclusive
    int to; // inclusive
    PowerNode *left = NULL;
    PowerNode *right = NULL;
    int max_deficit;
    int profit;
    int FindMaxDeficit(int from_, int to_) {
        if (from == from_ && to == to_) {
            return max_deficit;
        } else if (to_ < right->from) {
            return left->FindMaxDeficit(from_, to_);
        } else if (from_ > left->to) {
            return right->FindMaxDeficit(from_, to_);
        } else {
            int left_deficit = left->FindMaxDeficit(from_, left->to);
            int left_profit = left->FindProfit(from_, left->to);
            int right_deficit = right->FindMaxDeficit(right->from, to_);
            return min(left_deficit, left_profit + right_deficit);
        }
    }
    int FindProfit(int from_, int to_) {
        if (from == from_ && to == to_) {
            return profit;
        } else if (to_ < right->from) {
            return left->FindProfit(from_, to_);
        } else if (from_ > left->to) {
            return right->FindProfit(from_, to_);
        } else {
            int left_profit = left->FindProfit(from_, left->to);
            int right_profit = right->FindProfit(right->from, to_);
            return left_profit + right_profit;
        }
    }
};

PowerNode *cycles[kMaxCycles];

int FindMaxDeficit(int cycle, int from, int length) {
    if (from + length > cycle_length) {
        int first_deficit = cycles[cycle]->FindMaxDeficit(from, cycle_length - 1);
        int first_profit = cycles[cycle]->FindProfit(from, cycle_length - 1);
        int second_deficit = cycles[cycle]->FindMaxDeficit(0, (from + length) % cycle_length - 1);
        return min(first_deficit, first_profit + second_deficit);
    } else {
        int deficit = cycles[cycle]->FindMaxDeficit(from, from + length - 1);
        return deficit;
    }
}

int FindProfit(int cycle, int from, int length) {
    if (from + length > cycle_length) {
        int first_profit = cycles[cycle]->FindProfit(from, cycle_length - 1);
        int second_profit = cycles[cycle]->FindMaxDeficit(0, (from + length) % cycle_length - 1);
        return first_profit + second_profit;
    } else {
        int profit = cycles[cycle]->FindProfit(from, from + length - 1);
        return profit;
    }
}

int main() {
    scanf("%d", &total_children);
    for (int i = 0; i < total_children; i++) {
        scanf("%d", &children_money[i]);
    }
    scanf("%d\n", &casino_cycle_length);
    for (int i = 0; i < casino_cycle_length; i++) {
        char code;
        scanf("%c", &code);
        if (code == 'W') {
            casino_cycle_profit[i] = 1;
        } else {
            casino_cycle_profit[i] = -1;
        }
    }
    // Cycle characteristics
//    printf("lcm(%d, %d) = %d\n", 4, 3, lcm(4, 3));
//    printf("gcd(%d, %d) = %d\n", 6, 10, gcd(6, 10));
    total_cycles = gcd(total_children, casino_cycle_length);
    cycle_length = lcm(total_children, casino_cycle_length) / total_children;
    cycle_offset = total_children > casino_cycle_length
        ? total_children % casino_cycle_length
        : total_children - (casino_cycle_length % total_children);
//    printf("%d : total children | %d : casino cycle length\n", total_children, casino_cycle_length);
//    printf("%d : total cycles\n", total_cycles);
//    printf("%d : cycle length\n", cycle_length);
//    printf("%d : cycle offset\n", cycle_offset);
    for (int i = 0, j = 0; i < cycle_length; i++, j = (j + cycle_offset) % cycle_length) {
        cycle_idx_map[j] = i;
    }
//    for (int i = 0; i < cycle_length; i++) {
//        printf("%d ", cycle_idx_map[i]);
//    }
//    printf(": cycle idx map\n");
    for (int i = 0; i < total_cycles; i++) {
        cycles[i] = new PowerNode(0, cycle_length - 1, i);
        cycle_profit[i] = cycles[i]->profit;
    }
    int current_cycle = 0;
    int current_cycle_idx;
    int64_t games_till_first_broke = INT64_MAX;
    for (int i = 0; i < total_children; i++, current_cycle++) {
        current_cycle = current_cycle % total_cycles;
        int tmp_cycle_idx = (i / total_cycles) % cycle_length;
        current_cycle_idx = cycle_idx_map[tmp_cycle_idx];
        int max_deficit = FindMaxDeficit(current_cycle, current_cycle_idx, cycle_length);
        if (max_deficit + children_money[i] > 0 && cycle_profit[current_cycle] >= 0) {
            children_endurance[i] = -1;
        } else {
            int full_cycles;
            if (max_deficit + children_money[i] <= 0) {
                full_cycles = 0;
            } else {
                full_cycles = (max_deficit + children_money[i]) / cycle_profit[current_cycle] * -1;
            }
            int last_cycle_money = children_money[i] + full_cycles * cycle_profit[current_cycle];
            int start = current_cycle_idx;
            // int end = (current_cycle_idx + cycle_length) % cycle_length;
            int interval_length = cycle_length;
            int money = last_cycle_money;
            while (interval_length > 1) {
                int first_part_length = interval_length / 2;
                int first_deficit = FindMaxDeficit(current_cycle, start, first_part_length);
                if (first_deficit + money <= 0) {
                    // end = start + first_part_length - 1;
                    interval_length = first_part_length;
                } else {
                    money = money + FindProfit(current_cycle, start, first_part_length);
                    start = (start + first_part_length) % cycle_length;
                    interval_length = interval_length - first_part_length;
                }
            }
            if (start < current_cycle_idx) {
                start = start + cycle_length;
            }
            int steps_in_last_cycle = start - current_cycle_idx + 1;
            children_endurance[i] = (int64_t)full_cycles * (int64_t)cycle_length + (int64_t)steps_in_last_cycle;
            int64_t games_till_broke = (int64_t)1 + (int64_t)i + (int64_t)total_children * (children_endurance[i] - 1);
            if (games_till_broke < games_till_first_broke) {
                games_till_first_broke = games_till_broke;
            }
        }
    }
//    for (int i = 0; i < total_children; i++) {
//        printf("%ld ", children_endurance[i]);
//    }
//    printf(": children endurance\n");
    if (games_till_first_broke == INT64_MAX) {
        printf("-1\n");
    } else {
        printf("%ld\n", games_till_first_broke);
    }
    return 0;
}