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

Question

[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;
        }
    }
}

Comments

[Wataru]

Отформатируйте код в теге code (кнопка </> над редактором. Выберите c++ из списка. Расставьте отступы нормально.

[cocejah173]

Илья Николаевский, спасибо! Отступы съехали копирования без использования тега code.

[Армянское Радио]

cocejah173, вы знаете, какое условие должно соблюдаться после выполнения кода, чтобы он был "правильным"?

[cocejah173]

Фокс Йовович, правильный ход - это ход, который не является ошибочным. Ошибочный ход - если в этой ситуации можно было сходить иначе, гарантируя себе в дальнейшем выигрыш независимо от игры соперника.

[Армянское Радио]

cocejah173, у вас есть два варианта - узнать критерий правильного хода из википедии, или самостоятельно найти его.

[VitalyChaikin]

1. Если ход начинается с (магическое число билетов) - ход правильный
2. Если в результате хода остается (магическое число билетов) - ход правильный
(магическое число билетов) - как то зависит от k, и с этим число все время проигрывают :)

Answer 1

[Wataru]

Во-первых, в С++ нет 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)

...

Comments

[cocejah173]

Спасибо за советы!
Теперь вот так получилось, но снова ошибка при сдаче на acmp.ru:

#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 = tickets;
    for (int i = 0; i < turns; i++) 
    {
        previous = now;
        now -= game[i];
        
        if (now % (tickets_per_turn + 1) == 0) 
        {
            std::cout << "T" << std::endl;
        }
        else if (previous == tickets_per_turn + 1) 
        {
            std::cout << "T" << std::endl;
        }
        else
        {
            std::cout << "F" << std::endl;
        }
    }
}

[Wataru]

cocejah173, Почти. Опишите же словами стратегию. Что надо делать, чтобы выиграть, если текущее количество не делится на K+1?

[cocejah173]

Илья Николаевский, точно, спасибо, теперь всё работает верно!