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

using namespace std;
typedef long long int LLI;

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

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

LLI tab[1000005];
bool hasWon[1000005];
LLI cycleSum[1000005];

bool badCycle=false;

int main(){
    //printf("nwd: %I64d\n", nww(1000000, 999999));
    LLI n, m;
    scanf("%lld", &n);
    for(int i = 0; i < n; i++){
        scanf("%lld", &tab[i]);
    }
    scanf("%lld", &m);
    for(int i = 0; i < m; i++){
        char c;
        scanf(" %c", &c);
        //printf("%c\n", c);
        if(c=='W')hasWon[i]=true;
        else hasWon[i]=false;
    }
    LLI cycleSize = nww(n, m);
    LLI singleSize = cycleSize/n;
    //printf("cycleSize: %I64d\nsingleSize: %I64d\n", cycleSize, singleSize);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < singleSize; j++){
            int idx = (j*n+i)%m;
            if(hasWon[idx])
                cycleSum[i]++;
            else
                cycleSum[i]--;

            if(tab[i]-cycleSum[i]==0)badCycle=true;
        }
    }
    /*for(int j = 0; j < n; j++){
        printf("cycle sum: %I64d\n", cycleSum[j]);
    }*/
    bool isRealCycle=true;
    for(int i = 0; i < n; i++){
        if(cycleSum[i] < 0){
            isRealCycle=false;
            break;
        }
    }
    if(isRealCycle){
        printf("-1\n");
        return 0;
    }

    LLI time = 1000000000000000000LL;
    for(int i = 0; i < n; i++){
        if(cycleSum[i] < 0){
            LLI result = tab[i]/(-1LL*cycleSum[i]);
            //printf("tab[i]: %I64d, cycleSum[i]: %I64d, result: %I64d\n", tab[i], cycleSum[i]*-1, result);
            time = min(time, result);
        }
    }
    //printf("time: %I64d\n", time);

    LLI numberOfSteps=time*cycleSize;
    for(int i = 0; i < n; i++){
        if(tab[i]+cycleSum[i]*time==0){
            //printf("%I64d\n", cycleSize*(time-1)+1);
            //return 0;
            badCycle=true;
            break;
        }
    }
    if(badCycle){
        //printf("bad cycle\n");
        time--;
        numberOfSteps=time*cycleSize;
    }
    //printf("steps: %I64d\n", numberOfSteps);
    for(int i = 0; i < n; i++){
        tab[i]+=cycleSum[i]*time;
    }
    /*printf("*****\n");
    for(int i = 0; i < n; i++){
        printf("tab[i]=%d\n", tab[i]);
    }*/

    //printf("bad cycle: %d\n", badCycle);
    int keyCtr=0;
    LLI output=0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= singleSize; j++){
            if(tab[j] == 0){
                printf("%lld", output+numberOfSteps);
                return 0;
            }
            if(hasWon[keyCtr]){
                tab[j]++;
            }
            else{
                tab[j]--;
            }
            //printf("i: %d, j: %d, hasWon[i]: %d, tab[j]: %d\n", i, j, hasWon[keyCtr], tab[j]);
            output++;
            if(tab[j] == 0){
                printf("%lld", output+numberOfSteps);
                return 0;
            }
            keyCtr++;
            keyCtr = keyCtr % m;
        }
    }
}