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

using namespace std;

int ludzie;
long long int kasa[1000005];
vector<long long int> czlowiek[1000005];
vector<long long int> koszt[1000005];
int caly;
long long int kosztcaly;

int suma;
int mini;

int automaty;
int automat[1000005];

long long int ilecalych;
int reszta;

long long int aktual;
long long int wynik;

int main()
{
    scanf("%d",&ludzie);
    for(int i=0; i<ludzie; i++)
        scanf("%d",&kasa[i]);

    char znak;
    scanf("%d\n",&automaty);
    for(int i=0; i<automaty; i++)
    {
        scanf("%c",&znak);
        if(znak == 'P')
            automat[i] = -1;
        if(znak == 'W')
            automat[i] = 1;
    }

    int poz;
    for(int i=0; i<ludzie; i++)
    {
        poz = i%automaty;
        while(1)
        {
            czlowiek[i].push_back(automat[poz]);
            poz = (poz+ludzie)%automaty;
            if(poz == i%automaty)
                break;
        }

        caly = 0;
        kosztcaly = 0;
        suma = 0;
        mini = 0;
        ilecalych = 0;
        reszta = 0;
        aktual = 0;
        for(int j=0; j<czlowiek[i].size(); j++)
        {
            suma += czlowiek[i][j];
            if(suma < mini)
            {
                mini = suma;
                koszt[i].push_back(j+1);
            }
            if(j == czlowiek[i].size()-1)
            {
                caly = -suma;
                kosztcaly = j+1;
            }
        }
        mini *= -1;

        if(caly > 0)
        {
            if(kasa[i] > mini)
            {
                ilecalych = (kasa[i] - mini) / caly;
                if((kasa[i] - mini) * caly != ilecalych)
                    ilecalych++;
                aktual = ilecalych * kosztcaly; // samodzielnie
            }
            reszta = kasa[i] - ilecalych * caly;
            if(reszta != 0)
                aktual += koszt[i][reszta-1]; // samodzielnie
            aktual = (aktual-1)*ludzie + i+1; // liczac ruchy innych

            if(aktual < wynik || wynik == 0)
                wynik = aktual;

            //printf("Ile calych = (%lld), Reszta = (%d), Koszt caly = (%lld)\n",ilecalych,reszta,kosztcaly);
        }
        else
        {
            if(kasa[i] <= mini)
            {
                reszta = kasa[i];
                aktual = koszt[i][reszta-1]; // samodzielnie
                aktual = (aktual-1)*ludzie + i+1; // liczac ruchy innych
                if(aktual < wynik || wynik == 0)
                    wynik = aktual;
            }
        }
    }

    if(wynik == 0)
        printf("-1");
    else
        printf("%lld",wynik);

	return 0;
}