#include<iostream> #define N 100000 using namespace std; long nwd(long a, long b) { while(a!=b) if(a>b) a-=b; //lub a = a - b; else b-=a; //lub b = b-a return a; // lub b - obie zmienne przechowują wynik NWD(a,b) } int main() { long liczbaKolesi; cin >> liczbaKolesi; long piniaze[N]; for(int i = 0; i< liczbaKolesi; i++) cin>>piniaze[i]; long int cykl; cin>> cykl; char gry[N]; for(int i = 0; i < cykl; i++) cin >> gry[i]; int gryZyski [N]; for(long int i = 0; i < cykl; i++) { if(gry[i] == 'W') gryZyski[i] = 1; else gryZyski[i] = -1; } long long int ilePowtorzen = (liczbaKolesi * cykl) / nwd(liczbaKolesi, cykl); long int piniazeTmp[N]; for(int i = 0; i< liczbaKolesi; i++) piniazeTmp[i] = piniaze[i]; for(long long int i = 0; i<ilePowtorzen; i++) { piniazeTmp[i % liczbaKolesi] += gryZyski[i % cykl]; } long int roznica[N]; for(int i = 0; i< liczbaKolesi; i++) { roznica[i] = 0; if(piniaze[i] > piniazeTmp[i]) roznica[i] = piniaze[i] - piniazeTmp[i]; } for(int i = 0; i< liczbaKolesi; i++) { if(roznica[i] > 0) continue; cout << -1; return 0; } long int ktoMaNajmniej = 0; long int ileNajmniej = piniazeTmp[0]; for(int i = 1; i<liczbaKolesi; i++) { if(ileNajmniej > piniazeTmp[i]) { ileNajmniej = piniazeTmp[i]; ktoMaNajmniej = i; } } long int ileRund = 1; while (ileNajmniej > 0) { ileNajmniej -= roznica[ktoMaNajmniej]; ileRund++; } if(ileNajmniej == 0 ) { cout << (ileRund * ilePowtorzen); return 0; } long int ilePiniezyNaPoczatku = roznica[ktoMaNajmniej]+ileNajmniej; cout<<ileRund<<endl; cout<<ilePowtorzen<<endl; for(long long int i = 0; i<ilePowtorzen; i++) { if(i % liczbaKolesi == ktoMaNajmniej) ilePiniezyNaPoczatku += gryZyski[i%cykl]; if(ilePiniezyNaPoczatku == 0) { ileRund--; cout << (ileRund * ilePowtorzen + i+1); return 0; } } 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 117 118 119 120 121 122 | #include<iostream> #define N 100000 using namespace std; long nwd(long a, long b) { while(a!=b) if(a>b) a-=b; //lub a = a - b; else b-=a; //lub b = b-a return a; // lub b - obie zmienne przechowują wynik NWD(a,b) } int main() { long liczbaKolesi; cin >> liczbaKolesi; long piniaze[N]; for(int i = 0; i< liczbaKolesi; i++) cin>>piniaze[i]; long int cykl; cin>> cykl; char gry[N]; for(int i = 0; i < cykl; i++) cin >> gry[i]; int gryZyski [N]; for(long int i = 0; i < cykl; i++) { if(gry[i] == 'W') gryZyski[i] = 1; else gryZyski[i] = -1; } long long int ilePowtorzen = (liczbaKolesi * cykl) / nwd(liczbaKolesi, cykl); long int piniazeTmp[N]; for(int i = 0; i< liczbaKolesi; i++) piniazeTmp[i] = piniaze[i]; for(long long int i = 0; i<ilePowtorzen; i++) { piniazeTmp[i % liczbaKolesi] += gryZyski[i % cykl]; } long int roznica[N]; for(int i = 0; i< liczbaKolesi; i++) { roznica[i] = 0; if(piniaze[i] > piniazeTmp[i]) roznica[i] = piniaze[i] - piniazeTmp[i]; } for(int i = 0; i< liczbaKolesi; i++) { if(roznica[i] > 0) continue; cout << -1; return 0; } long int ktoMaNajmniej = 0; long int ileNajmniej = piniazeTmp[0]; for(int i = 1; i<liczbaKolesi; i++) { if(ileNajmniej > piniazeTmp[i]) { ileNajmniej = piniazeTmp[i]; ktoMaNajmniej = i; } } long int ileRund = 1; while (ileNajmniej > 0) { ileNajmniej -= roznica[ktoMaNajmniej]; ileRund++; } if(ileNajmniej == 0 ) { cout << (ileRund * ilePowtorzen); return 0; } long int ilePiniezyNaPoczatku = roznica[ktoMaNajmniej]+ileNajmniej; cout<<ileRund<<endl; cout<<ilePowtorzen<<endl; for(long long int i = 0; i<ilePowtorzen; i++) { if(i % liczbaKolesi == ktoMaNajmniej) ilePiniezyNaPoczatku += gryZyski[i%cykl]; if(ilePiniezyNaPoczatku == 0) { ileRund--; cout << (ileRund * ilePowtorzen + i+1); return 0; } } return 0; } |