#include <cstdio> #include <vector> using namespace std; long long int n,m, mod; char wp[1000100]; long long int kol[1000100]; long long int ile_kol[1000100]; long long int kiedy[1000100]; struct cyklDane{ long long int p; long long int s; long long int d; long long int od; cyklDane(long long int dd, long long int ss, long long int pp):p(pp),s(ss),d(dd),od(1) {} cyklDane():od(0) {} void pisz(); }; cyklDane dane[1000100]; void cyklDane::pisz() {printf("(%d,%d,%d)", d, s, p);} void cykl(long long int poz){ long long int p=poz; long long int suma=0; long long int min=0; long long int dl=0; do{ suma+=(wp[p]=='W'?1:-1); if(min>suma) min=suma; dl+=1; p=(p+mod)%m; }while(p!=poz); dane[p]=cyklDane(dl, suma, min); p=(p+mod)%m; long long int newMin=min; do{ long long int poprz=(p+m-mod)%m; dane[p]=cyklDane(dl, suma, newMin+=(wp[poprz]=='W'?-1:1)); p=(p+mod)%m; }while(p!=poz); } long long int idz(long long int poz, long long int kasa){ long long int out=0; while(kasa>0) { kasa+=(wp[poz]=='W'?1:-1); out+=1; //printf("out %d kasa %d\n", out, kasa); poz=(poz+mod)%m; } return out; } vector <long long int> pauy; int main () { scanf("%d", &n); for(long long int i=0;i<n;++i) scanf("%d", &kol[i]); scanf("%d", &m); scanf("%s", wp); mod=n%m; for(long long int i=0;i<m;++i) { if(dane[i].od==0) cykl(i); } /*for(long long int i=0;i<m;++i) { dane[i].pisz(); } printf("\n");*/ long long int min_ile=1000000000000000000L; for(long long int i=0;i<n;++i) { long long int p=i%m; long long int ile=(-((kol[i]+dane[p].p-1)/dane[p].s) +1)*dane[p].d; ile_kol[i] = (-((kol[i]+dane[p].p-1)/dane[p].s)+1); //printf("ile %d %d\n", i, ile); if(ile<min_ile) { min_ile=ile; pauy.resize(0); pauy.push_back(i); } else if(ile==min_ile) pauy.push_back(i); } //printf("\n"); long long int min_wyn=1000000000000000000L; for(long long int i=0;i<pauy.size();++i) { //printf("%d ", pauy[i]); long long int p=pauy[i]%m; long long int zost=kol[pauy[i]] + ile_kol[pauy[i]]*dane[p].s; long long int wyn=idz(pauy[i]%m, zost); //printf("wyn %d, zost %d %lld\n", wyn, zost, ile_kol[pauy[i]]); long long int wyn_ost=(min_ile+wyn-1)*n + pauy[i]+1; if(min_wyn>wyn_ost) min_wyn=wyn_ost; } //printf("\n"); printf("%lld\n", min_wyn); }
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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 | #include <cstdio> #include <vector> using namespace std; long long int n,m, mod; char wp[1000100]; long long int kol[1000100]; long long int ile_kol[1000100]; long long int kiedy[1000100]; struct cyklDane{ long long int p; long long int s; long long int d; long long int od; cyklDane(long long int dd, long long int ss, long long int pp):p(pp),s(ss),d(dd),od(1) {} cyklDane():od(0) {} void pisz(); }; cyklDane dane[1000100]; void cyklDane::pisz() {printf("(%d,%d,%d)", d, s, p);} void cykl(long long int poz){ long long int p=poz; long long int suma=0; long long int min=0; long long int dl=0; do{ suma+=(wp[p]=='W'?1:-1); if(min>suma) min=suma; dl+=1; p=(p+mod)%m; }while(p!=poz); dane[p]=cyklDane(dl, suma, min); p=(p+mod)%m; long long int newMin=min; do{ long long int poprz=(p+m-mod)%m; dane[p]=cyklDane(dl, suma, newMin+=(wp[poprz]=='W'?-1:1)); p=(p+mod)%m; }while(p!=poz); } long long int idz(long long int poz, long long int kasa){ long long int out=0; while(kasa>0) { kasa+=(wp[poz]=='W'?1:-1); out+=1; //printf("out %d kasa %d\n", out, kasa); poz=(poz+mod)%m; } return out; } vector <long long int> pauy; int main () { scanf("%d", &n); for(long long int i=0;i<n;++i) scanf("%d", &kol[i]); scanf("%d", &m); scanf("%s", wp); mod=n%m; for(long long int i=0;i<m;++i) { if(dane[i].od==0) cykl(i); } /*for(long long int i=0;i<m;++i) { dane[i].pisz(); } printf("\n");*/ long long int min_ile=1000000000000000000L; for(long long int i=0;i<n;++i) { long long int p=i%m; long long int ile=(-((kol[i]+dane[p].p-1)/dane[p].s) +1)*dane[p].d; ile_kol[i] = (-((kol[i]+dane[p].p-1)/dane[p].s)+1); //printf("ile %d %d\n", i, ile); if(ile<min_ile) { min_ile=ile; pauy.resize(0); pauy.push_back(i); } else if(ile==min_ile) pauy.push_back(i); } //printf("\n"); long long int min_wyn=1000000000000000000L; for(long long int i=0;i<pauy.size();++i) { //printf("%d ", pauy[i]); long long int p=pauy[i]%m; long long int zost=kol[pauy[i]] + ile_kol[pauy[i]]*dane[p].s; long long int wyn=idz(pauy[i]%m, zost); //printf("wyn %d, zost %d %lld\n", wyn, zost, ile_kol[pauy[i]]); long long int wyn_ost=(min_ile+wyn-1)*n + pauy[i]+1; if(min_wyn>wyn_ost) min_wyn=wyn_ost; } //printf("\n"); printf("%lld\n", min_wyn); } |