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!
InputThe 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.
OutputFor 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.
12 2 5 4 3 11 1 2 7 2 3 41 1 3 2 11 1000
3 3 0
Point Value: 10
Time Limit: 0.50s
Memory Limit: 16M
Added: Sep 30, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3