C
C
cocejah1732021-02-25 17:01:44
Mathematics
cocejah173, 2021-02-25 17:01:44

What's wrong with the code for solving Bache's math game?

Problem:
There are N objects, players take turns taking from 1 to K tickets, the winner is the one who takes the last ticket.
The task is to analyze the played game and for each move to determine whether it is correct or erroneous. An erroneous move - if in this situation it was possible to go differently, guaranteeing yourself a win in the future, regardless of the opponent's game. A correct move is a move that is not erroneous.
In addition, when the position is losing, then any move is correct, because. it can be considered optimal due to the fact that the result is still a loss.

Input data
The first line of the input file INPUT.TXT contains three integers: N, K, P (2 ≤ N ≤ 10000, 2 ≤ K ≤ 100, 2 ≤ P). Here P is the number of moves made by the student and the professor. The following P lines contain numbers (one number per line) in the range from 1 to K.

Output
The output file OUTPUT.TXT should contain P lines, one character per line: "T" (correct or valid move - from the word True) or "F" (wrong move - from the word False).

Examples:
Input
10 5 3
3
3
4
Output
F
F
T
Input
10 5 3
4
3
3
Output
T
T
T

Here is my code, which in some cases gives an incorrect assessment of the actions of the players:

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

Answer the question

In order to leave comments, you need to log in

1 answer(s)
W
Wataru, 2021-02-25
@cocejah173

First, C++ doesn't have and, you have to use &&.
Secondly, an error in the algorithm. The task is to check that the steps are optimal. To do this, you need to know the optimal step and compare it with the current one. Can you formulate an optimal strategy?
Take, for example, k=4,5,6 and draw on a piece of paper, try to calculate which positions are winning (from which you can make a move to a losing position), and which are losing (any move leads to a winning position). Count by increasing the number of items. A position with 0 items is a losing one - the previous player who came into it won. Position 1 is winning, because you can go to losing 0. Find a pattern, try to justify it logically.
Example for k=3:
0 - losing
1 - winning (you can take 1)
2 - winning (you can take 2)
3 - winning (you can take 3)
4 - losing
5 - winning (you can hit 4 by taking 1)
6 - winning (you can get to 4 by taking 2 )
7 - winning (you can take 3 and get into losing 4)
8 - losing (lead any move to winning 5-7)
...

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question