Разбор олимпиадной задачи — Игра — 2

Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6042
      @admin
      StudLance.ru

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 45%):

      Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.

      Входные данные

      В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.

      Выходные данные

      В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 4
      3 2 5 4
      1
      2 6
      5 5 5 5 5 5
      0
      3 9
      2 1 3 2 9 1 2 3 1
      2
      4 10
      2 5 3 12 4 6 13 7 1 3
      1

      Разбор решения задачи

      Итак, из которого по определенным правилам можно вычеркивать числа. Нужно заметить, что после вычеркивания одного числа задача чуть-чуть упрощается, а все варианты вычеркивания образуют дерево, как показано на рисунке:

      Красным выделены числа, которые можно взять. Серым — уже использованные числа (на выбор следующих чисел они влиять не могут). Дерево — это рекурсивная структура данных, поэтому наиболее простой способ организовать подобный перебор решений — рекурсия:

      #include <fstream>
      #include <vector>
      #include <algorithm>
      using namespace std;
      
      enum Player { First, Second };
      
      Player nextPlayer(Player current) {
        return current == First ? Second : First;
      }
      
      int get(const vector<int>& numbers, size_t pos, Player player) {
        if (player == First)
          return numbers[pos];
        return -numbers[pos];
      }
      
      int step(const vector<int>& numbers, size_t left, size_t right, Player player) {
        if (left > right)
          return 0;
      
        if (left == right)
          return get(numbers, left, player);
      
        int leftResult = step(numbers, left+1, right, nextPlayer(player)) + get(numbers, left, player);
        int rightResult = step(numbers, left, right-1, nextPlayer(player))+ get(numbers, right, player);
      
        if (player == First) {
          return std::max(leftResult, rightResult);
        }
        return std::min(leftResult, rightResult);
      }
      
      int main() {
        std::ifstream ifst("input.txt");
        std::ofstream ofst("output.txt");
        
        size_t n;
        ifst >> n;
      
        vector<int> numbers;
        numbers.resize(n);
        for (size_t i = 0; i < n; ++i) {
          ifst >> numbers[i];
        }
      
        int result = step(numbers, 0, numbers.size()-1, First);
      
        if (result > 0)
          ofst << "1";
        else if (result < 0)
          ofst << "2";
        else
          ofst << "0";
      }
      

      После каждого взятия числа нужно расчитать результат. Результат, выгодный для одного игрока является убыточным для другого — поэтому функция get, выполняющая такое «взятие» добавляет к результату числа, выбранные первым игроком и вычитает — вторым.

      Функция step выполняет расчет результата для конкретной ситуации (текущих левой и правой границ, а также типа игрока). В тривиальных случаях — когда осталось одно число — она возвращает результат сразу. В остальных — выполняет рекурсивные вызовы, приводящие к перебору «дочерних» решений.

      Эта функция прекрасно отработает на примерах данных, приведенных в задаче, однако на больших размерностях работать не будет (не пройдет по времени или памяти) — нужно оптимизировать. Типичным способом сделать это является динамическое программирование, суть которого доступно описана в соседней задаче.

      Коротко, суть динамического программирования, заключается в сохранении результатов вычислений для избежания их повторного выполнения. На приведенном выше рисунке зеленым цветом выделены случаи, к которым можно прийти различными способами. Таких случаев будет очень много, каждый из них является «корнем» к огромному числу «дочерних» вариантов решения.

      В приведенной ниже программе промежуточные результаты сохраняются в квадратной матрице, при этом элемент results[5][3] этой матрицы хранит результат обработки случая, когда левая граница массива равна пяти, а правая — трем.

      #include <fstream>
      #include <vector>
      #include <algorithm>
      using namespace std;
      
      enum Player { First, Second };
      
      Player nextPlayer(Player current) {
        return current == First ? Second : First;
      }
      
      int get(const vector<int>& numbers, size_t pos, Player player) {
        if (player == First)
          return numbers[pos];
        return -numbers[pos];
      }
      
      struct Score {
        bool is_ready;
        int value;
      
        Score() : is_ready(false) {
        }
      };
      
      int step(const vector<int>& numbers, size_t left, size_t right, Player player, vector<vector<Score>>& results) {
        if (results[left][right].is_ready == true)
          return results[left][right].value;
      
        if (left > right)
          return 0;
      
        if (left == right)
          return get(numbers, left, player);
      
        int leftResult = step(numbers, left+1, right, nextPlayer(player), results) + get(numbers, left, player);
        int rightResult = step(numbers, left, right-1, nextPlayer(player), results)+ get(numbers, right, player);
      
        results[left][right].is_ready = true;
        if (player == First) {
          results[left][right].value = std::max(leftResult, rightResult);
        }
        else {
          results[left][right].value = std::min(leftResult, rightResult);
        }
        return results[left][right].value;
      }
      
      int main() {
        std::ifstream ifst("input.txt");
        std::ofstream ofst("output.txt");
        
        size_t n;
        ifst >> n;
      
        vector<int> numbers;
        numbers.resize(n);
        for (size_t i = 0; i < n; ++i) {
          ifst >> numbers[i];
        }
      
        vector<vector<Score>> results;
        results.resize(n);
        for (size_t i = 0; i < n; ++i) {
          results[i].resize(n);
        }
      
        int result = step(numbers, 0, numbers.size()-1, First, results);
      
        if (result > 0)
          ofst << "1";
        else if (result < 0)
          ofst << "2";
        else
          ofst << "0";
      }

      Изначально массив результатов не расчитан (поле is_ready хранит false). Функция step теперь вместо того, чтобы приступать сразу к расчету — проверяет не был ли расчитан такой случай:

      if (results[left][right].is_ready == true)
        return results[left][right].value;

      Оптимизированная таким образом программа, пройдет все тесты на сайте.

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×