WC '02 P8 - Deploying Troops

View as PDF

Submit solution

Points: 7
Time limit: 0.3s
Memory limit: 16M

Problem type
Woburn Challenge 2002

The battle is drawing to an end. Bo Vine has gathered his warriors in front of The Sacred Barn, for some words of inspiration before the final battle. The N cows line up in a single line, face Bo, and listen attentively.

"My loyal servants, we are gathered here to prepare for an epic battle. Today, we go forth and win back SCARBERIA, the most coveted of all lands. Once in our control, we shall live as the lions, the true kings of our land. I have here an APE."

(Panic and chaos…)

"HEY! Get back here! It is not a real ape, just our weapon, with which we shall destroy the monkeys, and reclaim Scarberia for ourselves."

While Bo is continuing with this nonsensical rant, he notices that he can assign a value to each cow that is lined up before him, indicating the overall rating of the cow as a warrior. As he continues to indoctrinate the cows, he wonders how many consecutive subsequences of cows have a total rating equal to some number X that he is thinking of. If he can determine this, then he can assign these groups of cows to particular locations on the battlefield, just according to his brilliant plan!

Input Specification

The first line of input contains a single integer N (1 \le N \le 10^5), indicating the total number of cows.
The next line contains N integers, A_i (1 \le A_i \le 10^4), separated by a single space, indicating the values of the cows.
The next line contains a single integer, T (1 \le T \le 25), indicating the number of test cases.
The next line contains T integers, indicating the values of X (1 \le X \le 10^9), the target sum.

Output Specification

For each test case, output the number of distinct consecutive subsequences of cows that add to the given value of the target sum, all on a single line, separated by a single space.

Sample Input

12
2 5 4 3 11 1 2 7 2 3 41 1
3
2 11 1000

Sample Output

3 3 0

Comments


  • 0
    maxcruickshanks  commented on Feb. 20, 2022, 6:06 a.m.

    Since the original data were weak, the constraints were increased, and 10 more test cases were added.