#include<iostream> #include<vector> #include<string> #include<algorithm> #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) using namespace std; typedef unsigned long long ULL; int gcd(int a, int b){ for (;;){ if (!a) return b; b %= a; if (!b) return a; a %= b; } } int main(){ int n,m,lowest_cash=1000000; string schema; cin >> n; cerr << "n=" <<n <<endl; vector<int> cash(n); for(int i=0;i<n;i++){ cin >> cash[i]; lowest_cash = MIN( lowest_cash, cash[i] ); } cerr <<"poorest="<<lowest_cash<<endl; cin >> m; cerr << "m="<<m<<endl; cin >> schema; int wins = count(schema.begin(), schema.end(), 'W'); cerr << "#W=" <<wins <<endl; int loses= count(schema.begin(), schema.end(), 'P'); cerr << "#P=" <<loses<<endl; int balance = wins - loses; cerr << "balance="<< balance<<endl; ULL clen = (ULL)n/(ULL)gcd(n,m) * (ULL)m; cerr << "clen=" <<clen<<endl; ULL gamecnt=0; int reductions=0; if (balance<0){ reductions = lowest_cash / (-balance) - 1; cerr << "#reductions="<<reductions<<endl; for(int i=0; i<n; i++) cash[i] += reductions * balance; gamecnt = reductions * clen; } for(ULL i=0;; i++) { ULL player = gamecnt % n; char gameres = schema[ gamecnt % m ]; if ( gameres == 'W' ) cash[player]++; else cash[player]--; gamecnt++; if ( cash[player] == 0 ){ cout<< gamecnt << endl; return 0; } if ((gamecnt==0) || (gamecnt>clen)) break; } cout<<"-1"<<endl; 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 | #include<iostream> #include<vector> #include<string> #include<algorithm> #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) using namespace std; typedef unsigned long long ULL; int gcd(int a, int b){ for (;;){ if (!a) return b; b %= a; if (!b) return a; a %= b; } } int main(){ int n,m,lowest_cash=1000000; string schema; cin >> n; cerr << "n=" <<n <<endl; vector<int> cash(n); for(int i=0;i<n;i++){ cin >> cash[i]; lowest_cash = MIN( lowest_cash, cash[i] ); } cerr <<"poorest="<<lowest_cash<<endl; cin >> m; cerr << "m="<<m<<endl; cin >> schema; int wins = count(schema.begin(), schema.end(), 'W'); cerr << "#W=" <<wins <<endl; int loses= count(schema.begin(), schema.end(), 'P'); cerr << "#P=" <<loses<<endl; int balance = wins - loses; cerr << "balance="<< balance<<endl; ULL clen = (ULL)n/(ULL)gcd(n,m) * (ULL)m; cerr << "clen=" <<clen<<endl; ULL gamecnt=0; int reductions=0; if (balance<0){ reductions = lowest_cash / (-balance) - 1; cerr << "#reductions="<<reductions<<endl; for(int i=0; i<n; i++) cash[i] += reductions * balance; gamecnt = reductions * clen; } for(ULL i=0;; i++) { ULL player = gamecnt % n; char gameres = schema[ gamecnt % m ]; if ( gameres == 'W' ) cash[player]++; else cash[player]--; gamecnt++; if ( cash[player] == 0 ){ cout<< gamecnt << endl; return 0; } if ((gamecnt==0) || (gamecnt>clen)) break; } cout<<"-1"<<endl; return 0; } |