Galebickosikasa

Untitled

May 5th, 2021 (edited)
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.41 KB | None | 0 0
  1. /*
  2. (№ 2416) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч три камня или увеличить количество камней в куче в два раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 75. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 75 или больше камней.
  3. В начальный момент в первой куче было 9 камней, во второй куче – S камней, 1 ≤ S ≤ 65. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
  4. Ответьте на следующие вопросы:
  5. Вопрос 3. Найдите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Найденные значения запишите в ответе в порядке возрастания.
  6. */
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <algorithm>
  11. #include <set>
  12.  
  13. #define int int64_t
  14.  
  15. using namespace std;
  16.  
  17. vector <pair <int, int>> gen (int a, int b) {
  18. vector <pair <int, int>> d;
  19. d.push_back ({a + 3, b});
  20. d.push_back ({a * 2, b});
  21. d.push_back ({a, b + 3});
  22. d.push_back ({a, b * 2});
  23. return d;
  24. }
  25.  
  26. int dp[100][100];
  27.  
  28. const int maxs = 65;
  29. const int maxsum = 75;
  30. const int start = 9;
  31.  
  32. int calc (int a, int b) {
  33. if (a + b >= maxsum) return 0;
  34. if (dp[a][b] != -1) return dp[a][b];
  35. auto t = gen (a, b);
  36. int cnt = 0;
  37. for (auto& x: t) cnt += calc (x.first, x.second);
  38. if (cnt == t.size ()) return dp[a][b] = 0;
  39. return dp[a][b] = 1;
  40. }
  41.  
  42. signed main () {
  43. for (auto& v: dp) for (auto& x: v) x = -1;
  44.  
  45. for (int i = 1; i <= maxs; ++i) {
  46. if (!calc (i, start)) {
  47. int cnt1 = 0;
  48. auto t = gen (i, start);
  49. vector <int> used (t.size ());
  50. int j = 0;
  51. for (auto& x: t) {
  52. auto tt = gen (x.first, x.second);
  53. int f = 0;
  54. for (auto& xx: tt) {
  55. if (xx.first + xx.second >= maxsum) f = 1;
  56. }
  57. cnt1 += f;
  58. used[j] = f;
  59. ++j;
  60. }
  61. if (cnt1 > 0 && cnt1 < t.size ()) {
  62. j = 0;
  63. for (auto& x: t) {
  64. if (!used[j]) {
  65. auto tt = gen (x.first, x.second);
  66. int f = 0;
  67. for (auto& xx: tt) {
  68. if (calc (xx.first, xx.second)) continue;
  69. auto ttt = gen (xx.first, xx.second);
  70. int c = 0;
  71. for (auto& xxx: ttt) {
  72. auto tttt = gen (xxx.first, xxx.second);
  73. int ff = 0;
  74. for (auto& xxxx: tttt) {
  75. if (xxxx.first + xxxx.second >= maxsum) ff = 1;
  76. }
  77. c += ff;
  78. }
  79. if (c == ttt.size ()) f = 1;
  80. }
  81. cnt1 += f;
  82. }
  83. ++j;
  84. }
  85. if (cnt1 == t.size ()) {
  86. cout << i << ' ';
  87. }
  88. }
  89.  
  90. }
  91. }
  92.  
  93.  
  94.  
  95.  
  96. }
  97.  
Add Comment
Please, Sign In to add comment