Woburn Challenge 2002

Problem 8: Deploying Troops

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, 1 ≤ N ≤ 10000, 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. Note that he only assigns positive numbers to the cows. As he continues to indoctrinate the cows, he wonders how many consecutive subsequences of cows have a total rating equal to some number X, 1 ≤ X ≤ 214783647, 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

The first line of input contains a single integer N that is the total number of cows.
The next line contains N integers separated by a single space, indicating the values of the cows.
The next line contains a single integer, T, indicating the number of test cases.
The next line contains T integers, indicating the values of X, the target sum.

Output

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

All Submissions
Best Solutions


Point Value: 10
Time Limit: 0.50s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Is it just me, or is the new VPS server significantly faster than the old Judge servers? I have practically the same code as everyone else, but mine is the fastest.
Maybe to be fair, we should have rejudging of very old submissions whenever the Judge has no load?
(My idea above sounds a bit absurd even to myself, but currently, the 'time' aspect of ranking submissions really isn't very accurate...)

It is significantly faster in "CPU time" (although in "real time" it is slower, because our host is actually pretty bad and does some wacky things with the CPU, which is why programs take so damn long to compile). I think it would take waaay too long to rejudge everything, but I could rejudge some problems where it seems to make a difference.

How many test cases are there? Value of T?

T is 24 in our test data. Why does it matter? You're not supposed to read all the test data at once and then print all the answers; you're supposed to read one case, print one answer, read the next case, print the next answer, and so on.

i really hate these cause they always tell a wierd story before the actual problem to mess up our minds.

Almost all contests are like this, so I guess you can say this is useful preparation. And by the way, "weird" is an exception to that i-before-e-except-after-c-or-when-sounded-as-a rule...

well CCC ones are nowhere near as long-winded as WC's.