#include <iostream> using namespace std; const int MAX_N = 1000001; #define REP(x,n) for(__typeof(n) x=0;x<(n);++x) int money[MAX_N]; char cycle[MAX_N]; int change[MAX_N]; int maxFall[MAX_N]; int n, m; long long cycleLength; template<typename _T> _T NWD(_T a, _T b) { return a ? NWD(b%a, a) : b; } unsigned long long timeToLose(int id) { // cout << "# time to lose for player " << id << endl; long long fullRounds = (money[id]+maxFall[id])/(-change[id]); // cout << " fullRounds: " << fullRounds << endl; long long base = fullRounds*cycleLength; // cout << " base: " << base << endl; int curPhase = id; int tempMoney = money[id]+change[id]*fullRounds; int delta = n%m; REP(i, m) { ++base; if(cycle[curPhase] == 'W') ++tempMoney; else if(--tempMoney == 0) break; curPhase += delta; if(curPhase>=m) curPhase -= m; } return base; } long long program() { cycleLength = n*(long long)m/NWD(n,m); int curPlayer=0, curPhase=0; // cout << "NWD " << NWD(n,m) << "; length: " << cycleLength << endl; REP(i, cycleLength) { // cout << "phase " << curPhase << "\tplayer " << curPlayer << "\tmoney "<<money[curPlayer]-change[curPlayer] << endl; if(cycle[curPhase] == 'W') ++change[curPlayer]; else if(--change[curPlayer] + money[curPlayer] == 0) return i+1; else maxFall[curPlayer] = min(maxFall[curPlayer], change[curPlayer]); if(++curPlayer == n) curPlayer = 0; if(++curPhase == m) curPhase = 0; } unsigned long long minRounds = -1; REP(i, n) if(change[i]<0) { unsigned long long roundsToLose = timeToLose(i); //cout << "player " << i << " has " << roundsToLose << " rounds to lose; change " << change[i] <<"; maxfall " << maxFall[i] << endl; if(roundsToLose < minRounds) minRounds = roundsToLose; } return minRounds; } int main() { cin >> n; REP(x,n) cin >> money[x]; cin >> m >> cycle; cout << program() << 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> using namespace std; const int MAX_N = 1000001; #define REP(x,n) for(__typeof(n) x=0;x<(n);++x) int money[MAX_N]; char cycle[MAX_N]; int change[MAX_N]; int maxFall[MAX_N]; int n, m; long long cycleLength; template<typename _T> _T NWD(_T a, _T b) { return a ? NWD(b%a, a) : b; } unsigned long long timeToLose(int id) { // cout << "# time to lose for player " << id << endl; long long fullRounds = (money[id]+maxFall[id])/(-change[id]); // cout << " fullRounds: " << fullRounds << endl; long long base = fullRounds*cycleLength; // cout << " base: " << base << endl; int curPhase = id; int tempMoney = money[id]+change[id]*fullRounds; int delta = n%m; REP(i, m) { ++base; if(cycle[curPhase] == 'W') ++tempMoney; else if(--tempMoney == 0) break; curPhase += delta; if(curPhase>=m) curPhase -= m; } return base; } long long program() { cycleLength = n*(long long)m/NWD(n,m); int curPlayer=0, curPhase=0; // cout << "NWD " << NWD(n,m) << "; length: " << cycleLength << endl; REP(i, cycleLength) { // cout << "phase " << curPhase << "\tplayer " << curPlayer << "\tmoney "<<money[curPlayer]-change[curPlayer] << endl; if(cycle[curPhase] == 'W') ++change[curPlayer]; else if(--change[curPlayer] + money[curPlayer] == 0) return i+1; else maxFall[curPlayer] = min(maxFall[curPlayer], change[curPlayer]); if(++curPlayer == n) curPlayer = 0; if(++curPhase == m) curPhase = 0; } unsigned long long minRounds = -1; REP(i, n) if(change[i]<0) { unsigned long long roundsToLose = timeToLose(i); //cout << "player " << i << " has " << roundsToLose << " rounds to lose; change " << change[i] <<"; maxfall " << maxFall[i] << endl; if(roundsToLose < minRounds) minRounds = roundsToLose; } return minRounds; } int main() { cin >> n; REP(x,n) cin >> money[x]; cin >> m >> cycle; cout << program() << endl; return 0; } |