Facebook Hacker Cup 2016 Qualification Round 1.3 (SOLVED)

[MaxV]

The Price is Correct!

You've managed to become a contestant on the hottest new game show, The Price is Correct!

After asking you to come on down to the stage, the show's host presents you with a row of N closed boxes, numbered from 1 to N in order, each containing a secret positive integer. A curtain opens to reveal a shiny, new tricycle — you recognize it as an expensive, top-of-the-line model.

The host then proceeds to explain the rules: you must select a contiguous sequence of the boxes (boxes a..b, for some 1 ≤ a ≤ b ≤ N). Your chosen boxes will then be opened, and if the sum of the numbers inside is no greater than the price of the tricycle, you win it!

You'd sure like to win that tricycle. Fortunately, not only are you aware that its price is exactly P, but you've paid off the host to let you in on the contents of the boxes! You know that each box i contains the number Bi.

How many different sequences of boxes can you choose such that you win the tricycle? Each sequence is defined by its starting and ending box indices (a and b).

Input
Input begins with an integer T, the number of times you appear on The Price is Correct. For each show, there is first a line containing the space-separated integers N and P. The next line contains N space-separated integers, B1 through BN in order.

Output
For the ith show, print a line containing "Case #i: " followed by the number of box sequences that will win you the tricycle.

Constraints
1 ≤ T ≤ 40
1 ≤ N ≤ 100,000
1 ≤ P ≤ 1,000,000,000
1 ≤ Bi ≤ 1,000,000,000
Explanation of Sample
In the first case no sequence adds up to more than 50, so all 10 sequences are winners. In the fourth case, you can select any single box, or the sequences (1, 2), (1, 3), and (2, 3), for 9 total winning sequences.

Input:

Code: Select all

5
4 50
10 10 10 10
4 50
51 51 51 51
3 1000000000
1000000000 1000000000 1000000000
6 6
1 2 3 4 5 6
10 77
12 3 52 25 9 83 45 21 33 3

Output:

Code: Select all

Case #1: 10
Case #2: 0
Case #3: 3
Case #4: 9
Case #5: 18

[MaxV]

That's my solution:

########CODE#######
function fhc myinput
put line 1 of myinput into n
repeat with i=1 to n
put 0 into total #reset counter
put "Case #" & i & ": " after tutto
put line 2 * i of myinput into riga1
put line ((2 * i) + 1) of myinput into riga2
put word 1 of riga1 into nBox
put word 2 of riga1 into prezzo
repeat with j=1 to nBox
repeat with k=j to nBox
put word j to k of riga2 into listaSomma
replace space with comma in listaSomma
if sum(listasomma) <= prezzo then add 1 to total
end repeat
end repeat
put total & return after tutto
end repeat
return tutto
end fhc
#####END OF CODE#####

[Klaus]

I don't even understand the questions in all these Hacker Cups!

[MaxV]

The question in this case is:

• there is a value (the price)
• there is a list of number
• find how many consecutive sequence sums furnish a value lesser than the price.

Example:
price=50
list= 10 10 10 10

sequences less than 50:

1. 1=10
2. 1-2=20
3. 1-2-3=30
4. 1-2-3-4=40
5. 2=10
6. 3=10
7. 4=10
8. 2-3=20
9. 2-3-4=30
10. 3-4=20

[Klaus]

Hi Max,

thanky you, but I really don't want to understand the questions at all!


Best

Klaus