1161 - 1 DartChallenge

Time Limit : 10 Second

Memory Limit : 128 MB

Submission: 117

Solved: 61

Description
Clark and Harry are siblings. As they had been rivals since their early childhood, their father decided that

both should concentrate on a different sport when they were thirteen. That way, they would not have to

compete for success. Now both are twenty years old and excel in different fields: Clark plays chess while

Harry participates in dart-tournaments.

Having won a series of three tournaments in a row, Harry started teasing Clark about not having as much

success. Clark retorted that chess was less luck-based and thus more difficult. That offended Harry and led

him to the reply that in order to play darts optimally, a lot of combinatorics are necessary. Clark returned an

icy smile and the comment that memorizing all different late-games could hardly be called “combinatorics”.

This is how it came to the wager. Harry bets that he can find all possible late-games for generalized

dart-boards where memorized late-games do not help him. When Clark showed him a list of possible dart-

boards, Harry had to admit that he probably bit off more than he can chew. As his friend, you have to help

him!



A dart-board consists of different areas. Each area has an assigned score for hitting it. Each area also has

a double- and a triple-field that are worth twice and three times the score of the area. The only exception

is the area for the highest score: It has only a double- and no triple-field! Given the values of the different

areas you have to find the number of possible scores that can be obtained with a given number of darts.
Input
The inputs start with a line containing a single integer n. Each of the n following lines contains one test

case. Each test case starts with two integers 1 ≤ a ≤ 100, 1 ≤ k ≤ 50, the number of different areas on the

dart-board and the number of darts. a integers 1 ≤ si ≤ 100 follow. si is the score for hitting area i. All

scores are distinct. Remember that each area has a double- and, with exception of the area with the highest

score, a triple-field. It is always possible to score 0 with any given dart by not hitting the board.
Output
The output for every test case begins with a line containing “Scenario #i:”, where i is the number of

the scenario counting from 1. After that, output a single line containing the number of different scores that

can be obtained with k darts on the given board. Terminate each test case with an empty line.
sample input
3 
21 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 
2 2 20 10 
1 50 1 
sample output
Scenario #1:
172

Scenario #2:
9

Scenario #3:
101
hint
source
TU-Darmstadt Programming Contest Team Contest 2008
© 2015 HUST ACMICPC TEAM. All Right Reserved.