#include<iostream> #include<cstdio> #include<algorithm> #include<bitset> #include<vector> using namespace std; int dzieci[1000000][2]; bitset<1000000> cykl; char c[1000000]; int zmiana[1000000]; int minim[1000000]; vector<bool> wek[1000000]; int main(){ int n, m; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&dzieci[i][0]); dzieci[i][1]=dzieci[i][0]; } scanf("%d",&m); scanf("%s",&c); for(int j=0;j<m;j++){ if(c[j]=='W') cykl[j]=1; } int gcd=__gcd(n,m); for(int i=0;i<n*m/gcd;i++){ if(cykl[i%m]){ dzieci[i%n][1]++; wek[i%n].push_back(1); }else{ wek[i%n].push_back(0); dzieci[i%n][1]--; minim[i%n]=min(minim[i%n],dzieci[i%n][1]-dzieci[i%n][0]); if(dzieci[i%n][1]==0){ printf("%d",i+1); return 0; } } } for(int i=0;i<n;i++){ zmiana[i]=dzieci[i][0]-dzieci[i][1]; } long long loc; long long odpowiedz=1000000000000000009; int it; //for(int i=0;i<n;i++){ // cout<<zmiana[i]<<" "<<minim[i]<<endl; //} for(int i=0;i<n;i++){ if(zmiana[i]>0){ loc=(n*m/gcd)*((dzieci[i][0]+minim[i]-1)/zmiana[i]+1)+i; //cout<<i<<" "<<loc<<endl; int tmp=dzieci[i][0]-zmiana[i]*((dzieci[i][0]+minim[i]-1)/zmiana[i]+1); //cout<<tmp<<endl; //if(odpowiedz<loc){ it=0; while(tmp>0){ loc+=n; if(wek[i][it]){ tmp++; }else{ tmp--; } it++; } loc-=n-1; //} //cout<<"FINAL "<<loc<<endl; odpowiedz=min(odpowiedz,loc); } } printf("%lld",odpowiedz); }
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 | #include<iostream> #include<cstdio> #include<algorithm> #include<bitset> #include<vector> using namespace std; int dzieci[1000000][2]; bitset<1000000> cykl; char c[1000000]; int zmiana[1000000]; int minim[1000000]; vector<bool> wek[1000000]; int main(){ int n, m; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&dzieci[i][0]); dzieci[i][1]=dzieci[i][0]; } scanf("%d",&m); scanf("%s",&c); for(int j=0;j<m;j++){ if(c[j]=='W') cykl[j]=1; } int gcd=__gcd(n,m); for(int i=0;i<n*m/gcd;i++){ if(cykl[i%m]){ dzieci[i%n][1]++; wek[i%n].push_back(1); }else{ wek[i%n].push_back(0); dzieci[i%n][1]--; minim[i%n]=min(minim[i%n],dzieci[i%n][1]-dzieci[i%n][0]); if(dzieci[i%n][1]==0){ printf("%d",i+1); return 0; } } } for(int i=0;i<n;i++){ zmiana[i]=dzieci[i][0]-dzieci[i][1]; } long long loc; long long odpowiedz=1000000000000000009; int it; //for(int i=0;i<n;i++){ // cout<<zmiana[i]<<" "<<minim[i]<<endl; //} for(int i=0;i<n;i++){ if(zmiana[i]>0){ loc=(n*m/gcd)*((dzieci[i][0]+minim[i]-1)/zmiana[i]+1)+i; //cout<<i<<" "<<loc<<endl; int tmp=dzieci[i][0]-zmiana[i]*((dzieci[i][0]+minim[i]-1)/zmiana[i]+1); //cout<<tmp<<endl; //if(odpowiedz<loc){ it=0; while(tmp>0){ loc+=n; if(wek[i][it]){ tmp++; }else{ tmp--; } it++; } loc-=n-1; //} //cout<<"FINAL "<<loc<<endl; odpowiedz=min(odpowiedz,loc); } } printf("%lld",odpowiedz); } |