#include <iostream> #include <cmath> using namespace std; int gr[1000003]; int au[1000003]; int main() { int n, m; cin>>n; int sum = 0; for ( int i = 1 ;i <= n ; i++ ) { cin>>gr[i]; } cin>>m; for ( int i = 1; i <= m; i++ ) { char c; cin>>c; if ( c == 'W' ) { au[ i%m ] = 1; sum++; } else if ( c == 'P' ) { au[ i%m ] = -1; sum--; } } int wsk = 1; int sw = wsk % n; wsk += n; int dl = 1; int cykl = au[sw]; while ( wsk % m != sw ) { dl++; wsk += n; cykl += au[ wsk % m ]; } //cout<<dl<<" "<<cykl<<endl; long long int wynik = 100000000000000; int SW = 0; for ( int i = 1 ;i <= n ; i++ ) { if ( cykl >= 0 ) { long long int gra = i; while ( gr[i] > 0 && gra <= (cykl - 1) * n + i ) { gr[i] += au[ gra % m ]; gra += n; } gra -= n; if ( gr[i] ==0 ) { SW = 1; wynik = min ( wynik, gra ); } } else if ( cykl < 0 ) { int cykl2 = abs( cykl ); long long int gra = gr[i] / cykl2; if ( gra != 0 ) { gr[i] = gr[i] % cykl2; gra *= dl; gra--; gra *= n; gra += i; } while ( gr[i] > 0 && gra <= (cykl - 1) * n + i ) { gr[i] += au[ gra % m ]; gra += n; } //gra -= n; if ( gr[i] ==0 ) { SW = 1; wynik = min ( wynik, gra ); } //cout<<gr[i]<<" "<<gra<<" "; } } if ( SW ) { cout<<wynik; } else { cout<<"-1"; } /*for ( int i = 1 ;i <= n ; i++ ) { cout<<gr[i]<<" "; } cout<<endl; for ( int i = 1; i <= m; i++ ) { cout<<au[i%m]<<" "; }*/ return 0; }
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 | #include <iostream> #include <cmath> using namespace std; int gr[1000003]; int au[1000003]; int main() { int n, m; cin>>n; int sum = 0; for ( int i = 1 ;i <= n ; i++ ) { cin>>gr[i]; } cin>>m; for ( int i = 1; i <= m; i++ ) { char c; cin>>c; if ( c == 'W' ) { au[ i%m ] = 1; sum++; } else if ( c == 'P' ) { au[ i%m ] = -1; sum--; } } int wsk = 1; int sw = wsk % n; wsk += n; int dl = 1; int cykl = au[sw]; while ( wsk % m != sw ) { dl++; wsk += n; cykl += au[ wsk % m ]; } //cout<<dl<<" "<<cykl<<endl; long long int wynik = 100000000000000; int SW = 0; for ( int i = 1 ;i <= n ; i++ ) { if ( cykl >= 0 ) { long long int gra = i; while ( gr[i] > 0 && gra <= (cykl - 1) * n + i ) { gr[i] += au[ gra % m ]; gra += n; } gra -= n; if ( gr[i] ==0 ) { SW = 1; wynik = min ( wynik, gra ); } } else if ( cykl < 0 ) { int cykl2 = abs( cykl ); long long int gra = gr[i] / cykl2; if ( gra != 0 ) { gr[i] = gr[i] % cykl2; gra *= dl; gra--; gra *= n; gra += i; } while ( gr[i] > 0 && gra <= (cykl - 1) * n + i ) { gr[i] += au[ gra % m ]; gra += n; } //gra -= n; if ( gr[i] ==0 ) { SW = 1; wynik = min ( wynik, gra ); } //cout<<gr[i]<<" "<<gra<<" "; } } if ( SW ) { cout<<wynik; } else { cout<<"-1"; } /*for ( int i = 1 ;i <= n ; i++ ) { cout<<gr[i]<<" "; } cout<<endl; for ( int i = 1; i <= m; i++ ) { cout<<au[i%m]<<" "; }*/ return 0; } |