Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- (№ 2416) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч три камня или увеличить количество камней в куче в два раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 75. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 75 или больше камней.
- В начальный момент в первой куче было 9 камней, во второй куче – S камней, 1 ≤ S ≤ 65. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
- Ответьте на следующие вопросы:
- Вопрос 3. Найдите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Найденные значения запишите в ответе в порядке возрастания.
- */
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- #define int int64_t
- using namespace std;
- vector <pair <int, int>> gen (int a, int b) {
- vector <pair <int, int>> d;
- d.push_back ({a + 3, b});
- d.push_back ({a * 2, b});
- d.push_back ({a, b + 3});
- d.push_back ({a, b * 2});
- return d;
- }
- int dp[100][100];
- const int maxs = 65;
- const int maxsum = 75;
- const int start = 9;
- int calc (int a, int b) {
- if (a + b >= maxsum) return 0;
- if (dp[a][b] != -1) return dp[a][b];
- auto t = gen (a, b);
- int cnt = 0;
- for (auto& x: t) cnt += calc (x.first, x.second);
- if (cnt == t.size ()) return dp[a][b] = 0;
- return dp[a][b] = 1;
- }
- signed main () {
- for (auto& v: dp) for (auto& x: v) x = -1;
- for (int i = 1; i <= maxs; ++i) {
- if (!calc (i, start)) {
- int cnt1 = 0;
- auto t = gen (i, start);
- vector <int> used (t.size ());
- int j = 0;
- for (auto& x: t) {
- auto tt = gen (x.first, x.second);
- int f = 0;
- for (auto& xx: tt) {
- if (xx.first + xx.second >= maxsum) f = 1;
- }
- cnt1 += f;
- used[j] = f;
- ++j;
- }
- if (cnt1 > 0 && cnt1 < t.size ()) {
- j = 0;
- for (auto& x: t) {
- if (!used[j]) {
- auto tt = gen (x.first, x.second);
- int f = 0;
- for (auto& xx: tt) {
- if (calc (xx.first, xx.second)) continue;
- auto ttt = gen (xx.first, xx.second);
- int c = 0;
- for (auto& xxx: ttt) {
- auto tttt = gen (xxx.first, xxx.second);
- int ff = 0;
- for (auto& xxxx: tttt) {
- if (xxxx.first + xxxx.second >= maxsum) ff = 1;
- }
- c += ff;
- }
- if (c == ttt.size ()) f = 1;
- }
- cnt1 += f;
- }
- ++j;
- }
- if (cnt1 == t.size ()) {
- cout << i << ' ';
- }
- }
- }
- }
- }
Add Comment
Please, Sign In to add comment