#include <iostream> using namespace std; long long int NWD(long long int a, long long int b) { long long int pom; while(b!=0) { pom = b; b = a%b; a = pom; } return a; } long long int NWW(long long int a,long long int b){ return a/NWD(a, b)*b; } long long int n, m, index=-1; long long int koledzy[1000001]; long long int cykl[1000001]; long long int cykl2[1000001]; long long int minimum=9223372036854775807; long long int odp=1; long long int kol=0, cyk=0; long long int nww; char x; int main(){ ios_base::sync_with_stdio(0); cin>>n; for(int i=0;i<n;i++){ cin>>koledzy[i]; cykl2[i]=0; } cin>>m; //mozna odrrazu tu zrobić czesc z nastepnej petli for(int i=0;i<m;i++){ cin>>x; if(x=='W')cykl[i]=1; else cykl[i]=-1; } // for(int i=0;i<n;i++)cout<<koledzy[i]<<" "; // cout<<"\n"<<NWW(n, m)<<"\n"; // for(int i=0;i<m;i++)cout<<cykl[i]<<" "; nww=NWW(n, m); for(;odp<=nww;odp++){ if(kol>=n)kol=0; if(cyk>=m)cyk=0; koledzy[kol]+=cykl[cyk]; cykl2[kol]+=cykl[cyk]; if(koledzy[kol]<=0){ cout<<odp<<"\n"; return 0; } kol++; cyk++; } //cout<<odp<<" "<<minimum; for(int i=0;i<n;i++){ if(cykl2[i]>0) { continue; } else{ if(koledzy[i]/(-cykl2[i])<minimum){ //cout<<"testy"<<minimum<<" "<<cykl2[i]<<endl ; minimum=koledzy[i]/(-cykl2[i]); index=i; } } } if(index==-1){cout<<"-1";return 0;} long long int roznica=n-m; koledzy[index]-=(minimum-1)*(-cykl2[index]); for(int i=0;i<nww/n;i++){ koledzy[index]+=cykl[roznica*i+index%m]; odp++; if(koledzy[index]<=0){ break; } } //tutaj wybieram jedynie tego co najszybciej dojdzie //a dalej dla tego jednego zobaczyc ile mu to zajmie cout<<odp+((minimum-1)*nww/n); //cout<<endl; //for(int i=0;i<n;i++)cout<<koledzy[i]<<" "; 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 | #include <iostream> using namespace std; long long int NWD(long long int a, long long int b) { long long int pom; while(b!=0) { pom = b; b = a%b; a = pom; } return a; } long long int NWW(long long int a,long long int b){ return a/NWD(a, b)*b; } long long int n, m, index=-1; long long int koledzy[1000001]; long long int cykl[1000001]; long long int cykl2[1000001]; long long int minimum=9223372036854775807; long long int odp=1; long long int kol=0, cyk=0; long long int nww; char x; int main(){ ios_base::sync_with_stdio(0); cin>>n; for(int i=0;i<n;i++){ cin>>koledzy[i]; cykl2[i]=0; } cin>>m; //mozna odrrazu tu zrobić czesc z nastepnej petli for(int i=0;i<m;i++){ cin>>x; if(x=='W')cykl[i]=1; else cykl[i]=-1; } // for(int i=0;i<n;i++)cout<<koledzy[i]<<" "; // cout<<"\n"<<NWW(n, m)<<"\n"; // for(int i=0;i<m;i++)cout<<cykl[i]<<" "; nww=NWW(n, m); for(;odp<=nww;odp++){ if(kol>=n)kol=0; if(cyk>=m)cyk=0; koledzy[kol]+=cykl[cyk]; cykl2[kol]+=cykl[cyk]; if(koledzy[kol]<=0){ cout<<odp<<"\n"; return 0; } kol++; cyk++; } //cout<<odp<<" "<<minimum; for(int i=0;i<n;i++){ if(cykl2[i]>0) { continue; } else{ if(koledzy[i]/(-cykl2[i])<minimum){ //cout<<"testy"<<minimum<<" "<<cykl2[i]<<endl ; minimum=koledzy[i]/(-cykl2[i]); index=i; } } } if(index==-1){cout<<"-1";return 0;} long long int roznica=n-m; koledzy[index]-=(minimum-1)*(-cykl2[index]); for(int i=0;i<nww/n;i++){ koledzy[index]+=cykl[roznica*i+index%m]; odp++; if(koledzy[index]<=0){ break; } } //tutaj wybieram jedynie tego co najszybciej dojdzie //a dalej dla tego jednego zobaczyc ile mu to zajmie cout<<odp+((minimum-1)*nww/n); //cout<<endl; //for(int i=0;i<n;i++)cout<<koledzy[i]<<" "; return 0; } |