What is the logic behind this challenge?

Question

What is the logic behind this challenge?

Navigation

#1 by (4 votes)
#2 by (0 votes)

0

QUESTION: In American football, teams compete for field space and score points in two different ways: through the touchdown, which can be worth 6 or 7 points and by kicking the goal, 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 that is worth 1 extra point. Finally, game scores are set up by the possibility of making 3, 6 or 7 points, which means that some scorecards are impossible to do like 5, 13 or 22 points. Your task will be to have a collection of a team's flags (array) and to identify if the placards are possible or not.

Ex: 17 → Invalid score, 10 → Invalid score

The conditions that I have achieved were several, but because it is a challenge I believe the code is not great, so I did not put all of them:

I declared an array with the placemarks. The program just needs to say whether they are valid placers 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;
    }
}

c++

asked by anonymous 18.08.2017 / 06:29

2 answers

0

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

Both problems can be solved with methods of Dynamic Programming . .

21.08.2017 / 15:51

Subtleties between Python and C [closed] How to convert bitcoin to real?

score 4 · Accepted Answer

In short, you need to find out if there are nonnegative integers a, b, and c such that "score = 3 * a + 6 * b + 7 * c". Instead of looking for the solution mathematically finding possible a, b, and c, you can use recursion to check placard possibilities along changes (after all the only isolated changes of placers that occur are increases of 3, increase of 6 and increase of 7 points) .

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

Edit1: I forgot to mention that accumulating 6 points is the same as two times accumulating three, so you do not need to branch with six points, the three of you resolve. Branches of +3 and +7 are sufficient.

Edit2: There is another alternative in which you assume possible values of a (mark numbers of +3) from zero to floor(score/3) and calculate c (number of possible markings of +7). 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 is not accepted. With a = 1, we have 3 * a + 7 * b = 15 == > b = 12/7, where b = 12/7 solution is not accepted. From then until find a valid solution that confirms the possibility of the score or check everyone and not find, denying the possibility.