@cocejah173

Что не так с кодом для решения по математической игре Баше?

Задача:
Есть N предметов, игроки по очереди берут от 1 до K билетов, выигрывает тот, кто возьмет последний билет.
Задача в том, чтобы проанализировать сыгранную партию и для каждого хода определить правильный он или ошибочный. Ошибочный ход - если в этой ситуации можно было сходить иначе, гарантируя себе в дальнейшем выигрыш независимо от игры соперника. Правильный ход - это ход, который не является ошибочным.
К тому же, когда позиция проигрышная, то любой ход верный, т.к. его можно считать оптимальным в силу того, что результат всё равно проигрыш.

Входные данные
В первой строке входного файла INPUT.TXT записаны три целых числа: N, K, P (2 ≤ N ≤ 10000, 2 ≤ K ≤ 100, 2 ≤ P). Здесь P – количество ходов, которые сделали студент и профессор. В последующих P строках записаны числа (по одному числу на строке) в диапазоне от 1 до K.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать P строк по одному символу на строке: «T» (правильный или допустимый ход – от слова True) или «F» (неверный ход – от слова False).

Примеры:
Ввод
10 5 3
3
3
4
Вывод
F
F
T
Ввод
10 5 3
4
3
3
Вывод
Т
Т
T

Вот мой код, который в некоторых случаях выдаёт неправильную оценку действий играющих:
#include <iostream>
#include <vector>

int main()
{
    int tickets = 0, tickets_per_turn = 0, turns = 0;

    std::cin >> tickets;
    std::cin >> tickets_per_turn;
    std::cin >> turns;

    std::vector<int> game(turns);
    for (int i = 0; i < turns; i++) 
    {
        int helper = 0;
        std::cin >> helper;
        game[i] = helper;
    }

    int previous = 0, now = 0;
    for (int i = 0; i < turns; i++) 
    {
        previous = now;
        now += game[i];
        
        if (now == tickets)
        {
            std::cout << "T" << std::endl;
        }
        else if (now > tickets - tickets_per_turn - 1 and now < tickets and previous != (tickets - tickets_per_turn - 1))
        {
            std::cout << "F" << std::endl;
        }
        else if ((tickets - now) == (tickets_per_turn + 1))
        {
            std::cout << "T" << std::endl;
        }        
        else if (previous == tickets - tickets_per_turn - 1) 
        {
            std::cout << "T" << std::endl;
        }
        else if (previous >= tickets - 2 * tickets_per_turn - 1 and now <= tickets - tickets_per_turn - 1)
        {
            std::cout << "F" << std::endl;
        }
        else if (now == tickets - 2 * tickets_per_turn - 1)
        {
            std::cout << "F" << std::endl;
        }
        else
        {
            std::cout << "T" << std::endl;
        }
    }
}
  • Вопрос задан
  • 98 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, гуглер, экс-олимпиадник.
Во-первых, в С++ нет and, надо использовать &&.

Во-вторых, ошибка в алгоритме. Задача - проверить, что шаги оптимальные. Для этого вам надо знать оптимальный шаг и сравнивать его с текущим. Можете сформулировать оптимальную стратегию?

Возьмите, например, k=4,5,6 и порисуйте на бумажке, попробуйте подсчитать, какие позиции выигрышные (из них можно сделать ход в проигрышную позицию), а какие - проигрышные (любой ход ведет в выигрышную позицию). Считайте увеличивая количество предметов. Позиция с 0 предментами - проигрышная - предыдущий игрок придя в нее выиграл. Позиция 1 - выигрышная, потому что можно пойти в проигрышную 0. Найдите закономерность, попытайтесь ее логически обосновать.

Пример для k=3:

0 - проигрышная

1 - выигрышная ( можно взять 1)

2 - выигрышная (можно взять 2)

3 - выигрышная (можно взять 3)

4 - проигрышная

5 - выигрышная (можно попасть в 4, взяв 1)

6 - выигрышная (можно попасть в 4, взяв 2)

7 - выигрышная (можно взять 3 и попасть в проигрышную 4)

8 - проигрышная (любой ход ведеть в выигрышные 5-7)

...
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы