#include <iostream> #include <climits> #define EACH_PLAYER(iter) (iter = 1; iter <= n; iter++) using namespace std; typedef signed long INT; const INT MAX = 10e6 + 1; struct player { INT id; INT cash; }; struct variant { INT balance; INT max_lose; }; struct slot_machine { bool program[MAX * 2]; INT len; INT games_to_lcm; INT program_step; INT variants_count; variant variants[MAX]; void load_program(INT len, const char* program_str); void analyze(INT players_count); void analyze_variant(INT variant_id); INT games_before_defeat(player p, INT variant_id); INT solve(player players[]); }; INT n, m; player players[MAX]; slot_machine slots; char program_buf[MAX]; long long gcd(int a, int b) { for (;;) { if (a == 0) return b; b %= a; if (b == 0) return a; a %= b; } } long long lcm(int a, int b) { int temp = gcd(a, b); return temp ? (a / temp * b) : 0; } void input() { INT i; cin >> n; for EACH_PLAYER(i) { players[i].id = i; cin >> players[i].cash; } cin >> m >> program_buf; slots.load_program(m, program_buf); slots.analyze(n); } void slot_machine::load_program(INT len, const char* program_str) { INT i; this->len = len; for (i = 0; i < len; i++) { program[i] = program[i + m] = (program_str[i] == 'W'); } } void slot_machine::analyze(INT players_count) { INT i; variants_count = min(players_count, len); // long long lcm = players_count * variants_count; // TODO true LCM, prevent int overflow games_to_lcm = lcm(variants_count, players_count) / players_count; // long long lcm = players_count * variants_count; // TODO true LCM, prevent int overflow // games_to_lcm = variants_count; program_step = players_count; for (i = 0; i < variants_count; i++) { analyze_variant(i); // TODO possibly early exit if everyone wins } } void slot_machine::analyze_variant(INT variant_id) { INT idx = variant_id; variant *v = &variants[variant_id]; v->balance = v->max_lose = 0; do { v->balance += program[idx] ? 1 : -1; if (v->balance < v->max_lose) { v->max_lose = v->balance; } idx = (idx + program_step) % len; // TODO program can be reordered before analysys } while (idx != variant_id); v->max_lose *= -1; } INT slot_machine::solve(player players[]) { INT i, gtd, before_defeat; INT games = INT_MAX; for EACH_PLAYER(i) { before_defeat = games_before_defeat(players[i], (i - 1) % variants_count); gtd = before_defeat * program_step + players[i].id; if (before_defeat >= 0 && gtd < games) { games = gtd; } } return games < INT_MAX ? games : -1; } INT slot_machine::games_before_defeat(player p, INT variant_id) { INT idx, counter, cash, cycles; variant *v = &variants[variant_id]; if (p.cash <= v->max_lose) { // Lose at this cycle idx = variant_id; cash = p.cash; for (counter = 0;; counter++) { cash += program[idx] ? 1 : -1; if (cash <= 0){ return counter; } idx = (idx + program_step) % len; } } else if (v->balance < 0) { // Lose after some cycles // TODO divmod at once: http://linux.die.net/man/3/div cycles = (p.cash - v->max_lose) / (-1 * v->balance); p.cash += cycles * v->balance; return cycles * games_to_lcm + games_before_defeat(p, variant_id); } else { // Never ever lose return -1; } } int main(int argc, char **argv) { input(); cout << slots.solve(players); 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 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 | #include <iostream> #include <climits> #define EACH_PLAYER(iter) (iter = 1; iter <= n; iter++) using namespace std; typedef signed long INT; const INT MAX = 10e6 + 1; struct player { INT id; INT cash; }; struct variant { INT balance; INT max_lose; }; struct slot_machine { bool program[MAX * 2]; INT len; INT games_to_lcm; INT program_step; INT variants_count; variant variants[MAX]; void load_program(INT len, const char* program_str); void analyze(INT players_count); void analyze_variant(INT variant_id); INT games_before_defeat(player p, INT variant_id); INT solve(player players[]); }; INT n, m; player players[MAX]; slot_machine slots; char program_buf[MAX]; long long gcd(int a, int b) { for (;;) { if (a == 0) return b; b %= a; if (b == 0) return a; a %= b; } } long long lcm(int a, int b) { int temp = gcd(a, b); return temp ? (a / temp * b) : 0; } void input() { INT i; cin >> n; for EACH_PLAYER(i) { players[i].id = i; cin >> players[i].cash; } cin >> m >> program_buf; slots.load_program(m, program_buf); slots.analyze(n); } void slot_machine::load_program(INT len, const char* program_str) { INT i; this->len = len; for (i = 0; i < len; i++) { program[i] = program[i + m] = (program_str[i] == 'W'); } } void slot_machine::analyze(INT players_count) { INT i; variants_count = min(players_count, len); // long long lcm = players_count * variants_count; // TODO true LCM, prevent int overflow games_to_lcm = lcm(variants_count, players_count) / players_count; // long long lcm = players_count * variants_count; // TODO true LCM, prevent int overflow // games_to_lcm = variants_count; program_step = players_count; for (i = 0; i < variants_count; i++) { analyze_variant(i); // TODO possibly early exit if everyone wins } } void slot_machine::analyze_variant(INT variant_id) { INT idx = variant_id; variant *v = &variants[variant_id]; v->balance = v->max_lose = 0; do { v->balance += program[idx] ? 1 : -1; if (v->balance < v->max_lose) { v->max_lose = v->balance; } idx = (idx + program_step) % len; // TODO program can be reordered before analysys } while (idx != variant_id); v->max_lose *= -1; } INT slot_machine::solve(player players[]) { INT i, gtd, before_defeat; INT games = INT_MAX; for EACH_PLAYER(i) { before_defeat = games_before_defeat(players[i], (i - 1) % variants_count); gtd = before_defeat * program_step + players[i].id; if (before_defeat >= 0 && gtd < games) { games = gtd; } } return games < INT_MAX ? games : -1; } INT slot_machine::games_before_defeat(player p, INT variant_id) { INT idx, counter, cash, cycles; variant *v = &variants[variant_id]; if (p.cash <= v->max_lose) { // Lose at this cycle idx = variant_id; cash = p.cash; for (counter = 0;; counter++) { cash += program[idx] ? 1 : -1; if (cash <= 0){ return counter; } idx = (idx + program_step) % len; } } else if (v->balance < 0) { // Lose after some cycles // TODO divmod at once: http://linux.die.net/man/3/div cycles = (p.cash - v->max_lose) / (-1 * v->balance); p.cash += cycles * v->balance; return cycles * games_to_lcm + games_before_defeat(p, variant_id); } else { // Never ever lose return -1; } } int main(int argc, char **argv) { input(); cout << slots.solve(players); return 0; } |