#include <iostream> #include <cstring> using namespace std; int gcd(int a, int b) { int t; while(b != 0){ t = a; a = b; b = t%b; } return a; } void debug(int *tab, int size){ for(int i=0; i<size; ++i) cout<<tab[i]<<" "; cout<<endl; } const int GAME_INFINITE = -1; int main() { //Reading string cycle; int n,m; cin>>n; int *cash = new int[n]; for(int i=0; i<n; ++i){ cin>>cash[i]; } cin>>m; cin>>cycle; bool *game_win = new bool[m]; for(int i=0; i<m; ++i){ if(cycle[i] == 'W'){ game_win[i] = true; } else{ game_win[i] = false; } } //Preparing cycle_diff int com_div = gcd(n,m); int *cycle_diff = new int[com_div]; bool cycle_diffs_positive = true; for(int i=0; i<com_div; ++i){ cycle_diff[i] = 0; int j=i; do{ //cout<<"Cycle diff: "<<j<<" "<<i<<endl; if(game_win[j]) cycle_diff[i]++; else cycle_diff[i]--; j += com_div; j %= m; }while(j!=i); if(cycle_diff[i] < 0) cycle_diffs_positive = false; } //debug(cycle_diff, com_div); //Lowest bound count. subject to optimalization. int *lowest_bound = new int[n]; int step = n % m;//How much is to lose in next step for(int i=0; i<n; ++i){ lowest_bound[i] = 0; int j= i % m; int sum = 0; do{ //cout<<"Lowest bound: "<<j<<" "<<i<<endl; if(game_win[j]) sum--; else sum++; if(sum > lowest_bound[i]) lowest_bound[i] = sum; j += step; j %= m; }while(j != i%m); } //debug(lowest_bound, n); //Count games before reaching critical point games_played = nm/gcd(m,n) long long games_played = 0; long long game_delta = n*m; game_delta /= com_div; if(cycle_diffs_positive){ bool game_infinite = true; for(int i=0;i<n;i++){ if(lowest_bound[i] >= cash[i]){ game_infinite = false; break; } } if(game_infinite){ cout<<GAME_INFINITE<<endl; return 0; } } else{ bool simulate_end_game = false; while(true){ for(int i=0;i<n;i++){ if(lowest_bound[i] >= cash[i]){ simulate_end_game = true; break; } } if(simulate_end_game) break; for(int i=0;i<n;++i){ cash[i] += cycle_diff[i % com_div]; } games_played += game_delta; } } //debug(cash, n); //Simulate end_game Optimalization int index = 0; for(int i=0; i<n; ++i){ for(int j=0; j<m; ++j){ //cout<<"END simulation"<<endl; if(cash[index] == 1 && game_win[j]==false){ games_played++; cout<<games_played<<endl; return 0; } if(game_win[j]) cash[index]++; else cash[index]--; index++; index %= n; games_played++; } } cout<<games_played<<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 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 | #include <iostream> #include <cstring> using namespace std; int gcd(int a, int b) { int t; while(b != 0){ t = a; a = b; b = t%b; } return a; } void debug(int *tab, int size){ for(int i=0; i<size; ++i) cout<<tab[i]<<" "; cout<<endl; } const int GAME_INFINITE = -1; int main() { //Reading string cycle; int n,m; cin>>n; int *cash = new int[n]; for(int i=0; i<n; ++i){ cin>>cash[i]; } cin>>m; cin>>cycle; bool *game_win = new bool[m]; for(int i=0; i<m; ++i){ if(cycle[i] == 'W'){ game_win[i] = true; } else{ game_win[i] = false; } } //Preparing cycle_diff int com_div = gcd(n,m); int *cycle_diff = new int[com_div]; bool cycle_diffs_positive = true; for(int i=0; i<com_div; ++i){ cycle_diff[i] = 0; int j=i; do{ //cout<<"Cycle diff: "<<j<<" "<<i<<endl; if(game_win[j]) cycle_diff[i]++; else cycle_diff[i]--; j += com_div; j %= m; }while(j!=i); if(cycle_diff[i] < 0) cycle_diffs_positive = false; } //debug(cycle_diff, com_div); //Lowest bound count. subject to optimalization. int *lowest_bound = new int[n]; int step = n % m;//How much is to lose in next step for(int i=0; i<n; ++i){ lowest_bound[i] = 0; int j= i % m; int sum = 0; do{ //cout<<"Lowest bound: "<<j<<" "<<i<<endl; if(game_win[j]) sum--; else sum++; if(sum > lowest_bound[i]) lowest_bound[i] = sum; j += step; j %= m; }while(j != i%m); } //debug(lowest_bound, n); //Count games before reaching critical point games_played = nm/gcd(m,n) long long games_played = 0; long long game_delta = n*m; game_delta /= com_div; if(cycle_diffs_positive){ bool game_infinite = true; for(int i=0;i<n;i++){ if(lowest_bound[i] >= cash[i]){ game_infinite = false; break; } } if(game_infinite){ cout<<GAME_INFINITE<<endl; return 0; } } else{ bool simulate_end_game = false; while(true){ for(int i=0;i<n;i++){ if(lowest_bound[i] >= cash[i]){ simulate_end_game = true; break; } } if(simulate_end_game) break; for(int i=0;i<n;++i){ cash[i] += cycle_diff[i % com_div]; } games_played += game_delta; } } //debug(cash, n); //Simulate end_game Optimalization int index = 0; for(int i=0; i<n; ++i){ for(int j=0; j<m; ++j){ //cout<<"END simulation"<<endl; if(cash[index] == 1 && game_win[j]==false){ games_played++; cout<<games_played<<endl; return 0; } if(game_win[j]) cash[index]++; else cash[index]--; index++; index %= n; games_played++; } } cout<<games_played<<endl; return 0; }/**/ |