Constraints 1 ≤ N ≤ 5000 1 ≤ M ≤ 10 1 ≤ Si ≤ 20 Output Format For each test case, output a single integer indicating the team’s final score. If more than one final score can lead to the given number of pushups, output the largest one. If no final score can lead to the given number of pushups, then your friend must have miscounted. In this case, output ‘-1’. Output no extra spaces. Example Output: 14 Sample Input 0
Using C++, code the following problem:
A friend of yours is on the cheer squad for their football team. Each time the team scores, the cheer squad does pushups — one for each point the team has scored so far. If the teams scores a touchdown (7 points), the squad does 7 pushups. If the team then scores a field goal (3 points), the cheer squad does 10 pushups. If the team then scores a safety (2 points), the squad will do 12 pushups. At the end of that game, the squad will end up having done 7+10+12=29 pushups!
You meet your friend after a game, and they say “Boy, am I tired! I did a total of n pushups at the game today!” and promptly collapse from exhaustion. Given n, the number of pushups, can you figure out how the team scored? More than one score may be possible. For example, for 29 pushups, the team could have scored 3, then 2, then 2, then 7, for a total of 14 points. If so, find the highest possible score.
Input Format
There are multiple test cases. Each test case will begin with two integers N and M, 1 ≤ N ≤ 5000, 1 ≤ M ≤ 10, where N is the number of pushups the cheer squad did, and M is the number of ways a team can score points in that sport. On the next line will be M unique integers Si , 1 ≤ Si ≤ 20, with a single space between them, indicating the number of points the team gets for each kind of score. The scores are independent; a team can accrue scores in any order.
Example Input:
Constraints
1 ≤ N ≤ 5000
1 ≤ M ≤ 10
1 ≤ Si ≤ 20
Output Format
For each test case, output a single integer indicating the team’s final score. If more than one final score can lead to the given number of pushups, output the largest one. If no final score can lead to the given number of pushups, then your friend must have miscounted. In this case, output ‘-1’. Output no extra spaces.
Example Output:
Sample Input 0
Sample Output 0
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
