egormerk

19-21

Mar 7th, 2021 (edited)
336
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. // на основе этого видео https://youtu.be/hSbDxT8i1uY
  5.  
  6. // написано для задачи 35 Полякова 2021
  7.  
  8. // функция для 19-й задачи
  9. bool f19 (int x, int y, int p) {
  10.     // P - позиция
  11.     //    0     1     2     3     4
  12.     // (7; s)  Петя  Ваня  Петя  Ваня
  13.     if (x + y >= 61 && p == 2) {
  14.         return true;
  15.     }
  16.     // если мы находимся на нужном ходе (P), а сумма меньше нужной,
  17.     // то возвращаем false, т.к. это нам не подходит
  18.     else {
  19.         if (x + y < 61 && p == 2) {
  20.             return false;
  21.         }
  22.     }
  23.     // рекурсивно вызываем все возможные ходы
  24.     return f19(x + 1, y, p + 1) || f19(x * 2, y, p + 1) || f19(x, y + 1, p + 1) || f19(x, y * 2, p + 1);
  25. }
  26.  
  27. // преобразуем эту же функцию для 20-й задачи
  28. bool f20(int x, int y, int p) {
  29.     // меняем P на нужное
  30.     if (x + y >= 61 && p == 3) {
  31.         return true;
  32.     }
  33.     else {
  34.         // меняем P
  35.         if (x + y < 61 && p == 3) {
  36.             return false;
  37.         }
  38.         else {
  39.             // сумма больше нужной, а P нам не подходит (иначе сработало бы первое условие)
  40.             // возвращаем false
  41.             if (x + y >= 61) {
  42.                 return false;
  43.             }
  44.         }
  45.     }
  46.     // Петя выигрывает вторым ходом независимо от хода Вани,
  47.     // поэтому все ходы Пети после Вани должны быть true
  48.     // ходы Пети нечётные P = 1, 3, 5
  49.     // поэтому оператор И используем на ходах Пети, где значения P нечётные
  50.     // эту часть важно хорошо понимать - если неправильно написать условие,
  51.     // то программа либо ничего не выведет, либо выведет неправильные значения (их будет больше двух)
  52.     if (p % 2 != 0) // P должно "принадлежать" Пете
  53.         return f20(x + 1, y, p + 1) && f20(x * 2, y, p + 1) && f20(x, y + 1, p + 1) && f20(x, y * 2, p + 1);
  54.     else
  55.         return f20(x + 1, y, p + 1) || f20(x * 2, y, p + 1) || f20(x, y + 1, p + 1) || f20(x, y * 2, p + 1);
  56.  
  57. }
  58.  
  59. // преобразуем предыдущую функцию для 21-й задачи
  60. bool f21 (int x, int y, int p) {
  61.     // у нас теперь два P
  62.     if ((x + y >= 61 && p == 2) ||(x + y >= 61 && p == 4)) {
  63.         return true;
  64.     }
  65.     else {
  66.         // проверяем до конца, поэтому P == 4, а не 2
  67.         if (x + y < 61 && p == 4) {
  68.             return false;
  69.         }
  70.         else {
  71.             if (x + y >= 61) {
  72.                 return false;
  73.             }
  74.         }
  75.     }
  76.     // теперь Ваня побеждает при любом ходе Пети,
  77.     // поэтому при чётных ходах (ходах Вани) используем оператор ИЛИ
  78.     // а при нечётных ходах (ходах Пети) оператор И
  79.     if (p % 2 == 0) // тут Ваня
  80.         return f21(x + 1, y, p + 1) && f21(x * 2, y, p + 1) && f21(x, y + 1, p + 1) && f21(x, y * 2, p + 1);
  81.     else
  82.         return f21(x + 1, y, p + 1) || f21(x * 2, y, p + 1) || f21(x, y + 1, p + 1) || f21(x, y * 2, p + 1);
  83. }
  84.  
  85. // проверяем, есть ли такие S, которые работают только для P == 3 (если есть, то они нам не подходят - вычитаем)
  86. // просто копируем предыдущую функцию
  87. bool f21d (int x, int y, int p) {
  88.     // оставляем только P == 3
  89.     if (x + y >= 61 && p == 3) {
  90.         return true;
  91.     }
  92.     else {
  93.         // проверяем до P == 3
  94.         if (x + y < 61 && p == 3) {
  95.             return false;
  96.         }
  97.         else {
  98.             if (x + y >= 61) {
  99.                 return false;
  100.             }
  101.         }
  102.     }
  103.     // оставляем как в предыдущей функции
  104.     if (p % 2 == 0)
  105.         return f21(x + 1, y, p + 1) && f21(x * 2, y, p + 1) && f21(x, y + 1, p + 1) && f21(x, y * 2, p + 1);
  106.     else
  107.         return f21(x + 1, y, p + 1) || f21(x * 2, y, p + 1) || f21(x, y + 1, p + 1) || f21(x, y * 2, p + 1);
  108. }
  109.  
  110. int main() {
  111.     cout << "19: ";
  112.     for (int i = 1; i <= 53; i++) {
  113.         // выводим первое значение (минимальное), которое нам подходит
  114.         if (f19(7, i, 0)) {
  115.             cout << i << endl;
  116.             break;
  117.         }
  118.     }
  119.     cout << "20: ";
  120.     for (int i = 1; i <= 53; i++) {
  121.         // выводим все значения
  122.         if (f20(7, i, 0)) {
  123.             cout << i << " ";
  124.         }
  125.     }
  126.     cout << endl << "21: ";
  127.     for (int i = 1; i <= 53; i++) {
  128.         if (f21(7, i, 0)) {
  129.             cout << i << " ";
  130.         }
  131.     }
  132.     cout << endl << "Не подходят для 21: ";
  133.     // если программа тут что-то находит, то это число нам не подходит
  134.     for (int i = 1; i <= 53; i++) {
  135.         if (f21d(7, i, 0)) {
  136.             cout << i << " ";
  137.         }
  138.     }
  139. }
  140.  
RAW Paste Data