What is the logic behind this challenge?

Question

QUESTION: In football, teams fight over field space and score points in two different ways: through the touchdown, which can be worth 6 or 7 points and through the goal kick, which is worth 3 points. When a team enters the opponent’s touchdown area, it immediately scores 6 points and is entitled to a goal kick worth 1 extra point. Finally, the scoreboards of the games are assembled by the possibility of making 3, 6 or 7 points, which means that some scoreboards are impossible to happen as do 5, 13 or 22 points. Your task will be to have a collection of scoreboards from a team (array) and identify whether or not the scoreboards are achievable.

Ex: 17 invalid score, 10 valid score

The conditions that I achieved were several, but because it is a challenge I believe that the code does not get big, so I did not put all:

declared an array with scores. The program only needs to tell if they are valid scores or not.

 int placarNY[10] = {17, 26, 22, 10, 21, 18, 15, 24, 35, 19};

for(int i = 0; i < 10; i++){
    if((placarNY[i]%3 == 0) ||(placarNY[i]%7 == 0)||(placarNY[i]%10 == 0)){
        cout << placarNY[i] << " <- placar valido !" << endl;
    }else{
        cout << placarNY[i] << " <- placar invalido !" << endl;
    }
}

Answer 1

In short, you need to find out if there are non-negative integers a, b and c such that "score=3*a+6*b+7*c". Instead of seeking the solution mathematically by discovering possible a, b, and c, you can use recursion to check for scoring possibilities throughout the changes (after all the only isolated scoreboard changes that occur are increases of 3, increases of 6, and increases of 7 points).

When on a branch the score is lower than the score that is checked, the lower scores are checked. If instead of smaller is equal, it is over, confirmed the possibility of reaching that score. If it’s bigger instead, get out of this business and check another one. If you run out of branches without finding the sum equal to the score checked, then it is not possible to reach that score.

Edit1: I forgot to mention that accumulating 6 points is the same as twice accumulating three, so you don’t have to branch with six points, the three solves. Branches of +3 and +7 are sufficient.

Edit2: there is another alternative where you assume possible values of a ( +3) mark numbers from zero to floor(score/3) and calculates the c (number of possible +7 markings). For example, to form 15 points, assume a=0.1,...,5 +3 markings. With a=0, we have 3*a+7*b=15 ==> b=15/7, where b=15/7 is not integer and therefore solution does not accept. With a=1, we have 3*a+7*b=15 ==> b=12/7, where b=12/7 is not accepted. From then on until finding a valid solution that confirms the possibility of scoring or checking all and not finding, denying the possibility.

Answer 2

The logic behind this challenge is a variation of Backpack problem and of Problem of Frobenius.

Both problems can be solved with methods of Dynamic Programming.