#include <algorithm> #include <iostream> #include <string> using namespace std; const int r = 1e6+5; long long kasa[r]; int odejmij[2][r]; // w 0 wiersz, w 1 kolumna int main(){ int n, dlugosc; cin>>n; for(int i = 1; i<=n; i++) cin>>kasa[i]; cin>>dlugosc; string hazard; cin>>hazard; // koniec wejscia int cykl = 0, reszta = 0; long long wspolczynnik = 0, min_zakonczenie = -1, max_wspolczynnik = 0; // zliczamy dlugosc 1 cyklu while(1){ if(hazard[reszta] == 'W') wspolczynnik++; else wspolczynnik--; cykl++; if(wspolczynnik < 0){ if(wspolczynnik < max_wspolczynnik) max_wspolczynnik = wspolczynnik; wspolczynnik *= -1; if(odejmij[0][wspolczynnik] == 0 || odejmij[0][wspolczynnik] > cykl) odejmij[0][wspolczynnik] = cykl; odejmij[1][wspolczynnik] = 1; wspolczynnik *= -1; } reszta += n; reszta %= dlugosc; if(reszta == 0) break; } for(int i = 1; i<=n;){ // wzorki wzorki if( (max_wspolczynnik*-1) >= kasa[i] ){ long long wch = odejmij[1][kasa[i]] + ((odejmij[0][kasa[i]] - 1) * n); if(min_zakonczenie < 0 || wch < min_zakonczenie) min_zakonczenie = wch; // cout<<wch<<"\n"; } else{ if(wspolczynnik < 0){ long long wch = odejmij[1][max_wspolczynnik*-1] + n * (odejmij[0][max_wspolczynnik*-1] - 1); kasa[i] += max_wspolczynnik; if( kasa[i] % (wspolczynnik*-1) != 0) kasa[i] = (kasa[i] / (wspolczynnik*-1))+1; else kasa[i] /= (wspolczynnik*-1); wch += kasa[i] * cykl * n; // cout<<wch<<"\n"; if(min_zakonczenie < 0 || wch < min_zakonczenie) min_zakonczenie = wch; // cout<<wch<<"\n"; } } i++; for(int k = 1; k<= (max_wspolczynnik*-1); k++) odejmij[0][k] = 0; reszta += 1; wspolczynnik = 0; max_wspolczynnik = 0; reszta %= dlugosc; if(i > n) break; // szukamy sobie rzeczy for(int j = 1; j <= cykl; j++){ if(hazard[reszta] == 'W') wspolczynnik++; else wspolczynnik--; // cout<<hazard[reszta]; if(wspolczynnik < 0){ if(wspolczynnik < max_wspolczynnik) max_wspolczynnik = wspolczynnik; wspolczynnik *= -1; int poz = i; if(poz > n) poz = (poz%n) + 1; if(odejmij[0][wspolczynnik] == 0 || odejmij[0][wspolczynnik] > j) odejmij[0][wspolczynnik] = j; odejmij[1][wspolczynnik] = poz; wspolczynnik *= -1; } reszta += n; reszta %= dlugosc; } } cout<<min_zakonczenie<<"\n"; 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 | #include <algorithm> #include <iostream> #include <string> using namespace std; const int r = 1e6+5; long long kasa[r]; int odejmij[2][r]; // w 0 wiersz, w 1 kolumna int main(){ int n, dlugosc; cin>>n; for(int i = 1; i<=n; i++) cin>>kasa[i]; cin>>dlugosc; string hazard; cin>>hazard; // koniec wejscia int cykl = 0, reszta = 0; long long wspolczynnik = 0, min_zakonczenie = -1, max_wspolczynnik = 0; // zliczamy dlugosc 1 cyklu while(1){ if(hazard[reszta] == 'W') wspolczynnik++; else wspolczynnik--; cykl++; if(wspolczynnik < 0){ if(wspolczynnik < max_wspolczynnik) max_wspolczynnik = wspolczynnik; wspolczynnik *= -1; if(odejmij[0][wspolczynnik] == 0 || odejmij[0][wspolczynnik] > cykl) odejmij[0][wspolczynnik] = cykl; odejmij[1][wspolczynnik] = 1; wspolczynnik *= -1; } reszta += n; reszta %= dlugosc; if(reszta == 0) break; } for(int i = 1; i<=n;){ // wzorki wzorki if( (max_wspolczynnik*-1) >= kasa[i] ){ long long wch = odejmij[1][kasa[i]] + ((odejmij[0][kasa[i]] - 1) * n); if(min_zakonczenie < 0 || wch < min_zakonczenie) min_zakonczenie = wch; // cout<<wch<<"\n"; } else{ if(wspolczynnik < 0){ long long wch = odejmij[1][max_wspolczynnik*-1] + n * (odejmij[0][max_wspolczynnik*-1] - 1); kasa[i] += max_wspolczynnik; if( kasa[i] % (wspolczynnik*-1) != 0) kasa[i] = (kasa[i] / (wspolczynnik*-1))+1; else kasa[i] /= (wspolczynnik*-1); wch += kasa[i] * cykl * n; // cout<<wch<<"\n"; if(min_zakonczenie < 0 || wch < min_zakonczenie) min_zakonczenie = wch; // cout<<wch<<"\n"; } } i++; for(int k = 1; k<= (max_wspolczynnik*-1); k++) odejmij[0][k] = 0; reszta += 1; wspolczynnik = 0; max_wspolczynnik = 0; reszta %= dlugosc; if(i > n) break; // szukamy sobie rzeczy for(int j = 1; j <= cykl; j++){ if(hazard[reszta] == 'W') wspolczynnik++; else wspolczynnik--; // cout<<hazard[reszta]; if(wspolczynnik < 0){ if(wspolczynnik < max_wspolczynnik) max_wspolczynnik = wspolczynnik; wspolczynnik *= -1; int poz = i; if(poz > n) poz = (poz%n) + 1; if(odejmij[0][wspolczynnik] == 0 || odejmij[0][wspolczynnik] > j) odejmij[0][wspolczynnik] = j; odejmij[1][wspolczynnik] = poz; wspolczynnik *= -1; } reszta += n; reszta %= dlugosc; } } cout<<min_zakonczenie<<"\n"; return 0; } |