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

using namespace std;

struct A {
    A() : minimum(LLONG_MAX) {}
    long long minimum;
    long long po_calosci;
};

vector<unsigned> oszczednosci;
vector<int> cykl;
vector<A*> wyniki;



long long ObliczDlugoscCalegoCyklu(unsigned ile_kolegow, unsigned dlugosc_cyklu)
{
    long long dlugosc = 0;
    unsigned n = 0;
    do {
        n = (n + ile_kolegow) % dlugosc_cyklu;
        ++dlugosc;
    } while(n != 0);
    return dlugosc;
}

void ObliczCykl(unsigned n, unsigned ile_kolegow, long long dlugosc_calosci, unsigned dlugosc_cyklu) {
    A* a = new A();
    long long wartosc = 0;
    if (wyniki[n])
        return;
    for (long long i = 0; i < dlugosc_calosci; ++i) {
        wartosc += cykl[n];
        n = (n + ile_kolegow) % dlugosc_cyklu;
        if (wartosc < a->minimum)
            a->minimum = wartosc;
        wyniki[n] = a;
    }
    a->po_calosci = wartosc;
    cerr << n << " min: " << a->minimum << " po: " << a->po_calosci << "\n";
}

long long ObliczIleDoZera(unsigned n, long long wartosc) {
    long long ile = 0;
    while (wartosc) {
        wartosc += cykl[n];
        n = (n + oszczednosci.size()) % cykl.size();
        ++ile;
    }
    return ile;
}

long long ObliczIloscGier(unsigned k, long long dlugosc) {
    long long ile_calosci = 0;
    long long n = k % cykl.size();
    if (oszczednosci[k] <= wyniki[n]->minimum) {
        ile_calosci = 0;
    } else if (wyniki[n]->po_calosci <= 0) {
        return LLONG_MAX;
    } else {
        ile_calosci = ceil(((double)(oszczednosci[k] - wyniki[n]->minimum)) / wyniki[n]->po_calosci);
    }
    long long ile = ObliczIleDoZera(n, oszczednosci[k] - (ile_calosci * wyniki[n]->po_calosci));

    cerr << k <<"\n";
    return k + 1 + (ile_calosci * dlugosc + ile - 1) * oszczednosci.size();
}

int main() {
    unsigned ile_kolegow, dlugosc_cyklu;
    cin >> ile_kolegow ;

    oszczednosci.reserve(ile_kolegow);
    for (unsigned k = 0; k < ile_kolegow; ++k) {
        unsigned o;
        cin >> o;
        oszczednosci.push_back(o);
    }

    cin >> dlugosc_cyklu;

    wyniki.resize(dlugosc_cyklu);
    cykl.reserve(dlugosc_cyklu);
    for (unsigned c = 0; c < dlugosc_cyklu; ++c) {
        char ch;
        cin >> ch;
        if (ch == 'P')
            cykl.push_back(-1);
        else
            cykl.push_back(1);
    }

    long long dlugosc = ObliczDlugoscCalegoCyklu(ile_kolegow, dlugosc_cyklu);
    cerr << dlugosc << "\n";

    for (unsigned n = 0; n < dlugosc_cyklu; ++n) {
        ObliczCykl(n, ile_kolegow, dlugosc, dlugosc_cyklu);
    }

    cerr << "juz\n";

    for (A* a : wyniki) {
        a->minimum *= -1;
        a->po_calosci *= -1;
    }

    long long minimum = LLONG_MAX;
    for (unsigned k = 0; k < ile_kolegow; ++k) {
        long long ile_gier = ObliczIloscGier(k, dlugosc);
        if (ile_gier < minimum)
            minimum = ile_gier;
    }
    if (minimum == LLONG_MAX)
        cout << -1 << "\n";
    else
        cout << minimum << "\n";

}