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
#include <iostream>
#include <vector>

using namespace std;

long long int nwd(long long int a, long long int b){
    if (b == 0) return a;
    if (a < b) return nwd(b,a);
    return nwd(b,a%b);
}

int main()
{
    long long int n;
    cin >> n;
    int K[n];
    for (int i=0; i<n; i++){
        cin >> K[i];
    }

    long long int m;
    cin >> m;

    int L[m];
    for (int i=0; i<m; i++){
        char c;
        cin >> c;
        if (c == 'W') L[i] = 1;
        else L[i] = -1;
    }

    long long int NWD = nwd(n,m);
    int sum[NWD];
    int dod[m];
    vector < vector <int> >minima(NWD, vector <int>() );
    vector < vector <int> >newminima(NWD, vector <int>() );

    for (long long int i=0; i<NWD; i++){
        long long int s = 0;
        long long mini = 0;
        minima[i].push_back(0);
        for (long long int j=0; j<m/NWD; j++){
            dod[(j*n+i)%m] = s;
            s += L[(j*n+i)%m];
            if (s < mini){
                mini = s;
                minima[i].push_back(j+1);
            }
        }
        sum[i] = s;
    }
    long long int wynik = -1;
    for (long long int i=0; i<NWD; i++){
        for (long long int j=0; j<n/NWD; j++){
            long long int pocz = K[NWD*j+i]-dod[(j*n+i)%m];
            if (!(pocz > minima[i].size()-1 && sum[i] >= 0)){
                long long int tury = 0;
                if (pocz <= minima[i].size()-1){
                    tury = minima[i][pocz];
                }
                else{
                    long long int k = (long long)(pocz-minima[i].size()+1)/abs(sum[i]);
                    if ((long long)(abs(sum[i])*k) != (pocz-minima[i].size()+1)){
                        k++;
                    }
                    tury = (long long)(k*(m/NWD)+minima[i][(long long)(pocz - k*abs(sum[i]))]);
                }
                long long int gry = n*(tury-1)+NWD*j+i+1;
                if (wynik > gry || wynik == -1) wynik = gry;
            }
            long long int nast = (NWD*(j+1)+i)%m;
            if (nast < 0) nast += m;
        }
    }
    cout << wynik;
}