#include <iostream> #include <vector> using namespace std; struct entry { long long step; long mod; }; int main() { long long n, m, i, a, b; long long lcm, j, full, reminder, mini; char c; vector<long long> boys, mods; vector<char> cycle; vector< vector<entry> > history; vector<entry> tmp; entry tmp2; // Read input cin >> n; for (i = 0; i < n; ++i) { cin >> a; boys.push_back(a); mods.push_back(0); history.push_back(tmp); } cin >> m; for (i = 0; i < m; ++i) { cin >> c; if (c == 'W') c = 1; else c = -1; cycle.push_back(c); } // Count LCM(n, m) a = n; b = m; while (b) { i = b; b = a % b; a = i; } lcm = n * m / a; // First loop a = b = 0; for (j = 0; j < lcm; ++j) { boys[a] += cycle[b]; if (boys[a] == 0) break; mods[a] += cycle[b]; tmp2.step = j + 1; tmp2.mod = mods[a]; history[a].push_back(tmp2); ++a; ++b; if (a >= n) a = 0; if (b >= m) b = 0; } // Test for break if (j < lcm) cout << j + 1; else { // Steps till 0 for (i = 0; i < n; ++i) { if (mods[i] >= 0) mods[i] = -1; full = boys[i] / mods[i]; full = lcm * full; reminder = boys[i] % mods[i]; if (reminder > 0) { for (j = 0; j < history[i].size(); ++j) { if (history[i][j].mod == reminder) { reminder = history[i][j].step; break; } } } full += reminder; mods[i] = full; } // Find min mini = mods[0]; for (i = 0; i < n; ++i) { if (mods[i] < mini) mini = mods[i]; } mini += lcm; cout << mini; } 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 | #include <iostream> #include <vector> using namespace std; struct entry { long long step; long mod; }; int main() { long long n, m, i, a, b; long long lcm, j, full, reminder, mini; char c; vector<long long> boys, mods; vector<char> cycle; vector< vector<entry> > history; vector<entry> tmp; entry tmp2; // Read input cin >> n; for (i = 0; i < n; ++i) { cin >> a; boys.push_back(a); mods.push_back(0); history.push_back(tmp); } cin >> m; for (i = 0; i < m; ++i) { cin >> c; if (c == 'W') c = 1; else c = -1; cycle.push_back(c); } // Count LCM(n, m) a = n; b = m; while (b) { i = b; b = a % b; a = i; } lcm = n * m / a; // First loop a = b = 0; for (j = 0; j < lcm; ++j) { boys[a] += cycle[b]; if (boys[a] == 0) break; mods[a] += cycle[b]; tmp2.step = j + 1; tmp2.mod = mods[a]; history[a].push_back(tmp2); ++a; ++b; if (a >= n) a = 0; if (b >= m) b = 0; } // Test for break if (j < lcm) cout << j + 1; else { // Steps till 0 for (i = 0; i < n; ++i) { if (mods[i] >= 0) mods[i] = -1; full = boys[i] / mods[i]; full = lcm * full; reminder = boys[i] % mods[i]; if (reminder > 0) { for (j = 0; j < history[i].size(); ++j) { if (history[i][j].mod == reminder) { reminder = history[i][j].step; break; } } } full += reminder; mods[i] = full; } // Find min mini = mods[0]; for (i = 0; i < n; ++i) { if (mods[i] < mini) mini = mods[i]; } mini += lcm; cout << mini; } return 0; } |