Facebook Hacker Cup 2016 Round 2.3

LiveCode is the premier environment for creating multi-platform solutions for all major operating systems - Windows, Mac OS X, Linux, the Web, Server environments and Mobile platforms. Brand new to LiveCode? Welcome!

Moderators: Klaus, FourthWorld, heatherlaine, kevinmiller, robinmiller

Post Reply
Posts: 1577
Joined: Tue May 28, 2013 2:20 pm
Location: Italy

Facebook Hacker Cup 2016 Round 2.3

Post by MaxV » Thu Jan 28, 2016 2:48 pm


A rich, retired programmer has decided to invest his (possibly) massive savings into constructing custom yachts for himself.

Initially, he has a real amount of dollars, chosen uniformly at random from the range [A, B]. Constructing a yacht consists of N sequential steps, with the ith step requiring Ci dollars.

The programmer blindly pays for the steps in order, until he's either completed all of them, or can't afford the cost of the next step. If the former occurs, he puts his completed yacht aside and restarts the process from the first step with his remaining money - he wants as many yachts as possible! Otherwise, in the latter case, he immediately stops his project entirely, without spending any additional money on other steps.

What's the expected amount of money which the programmer will be left with once he stops spending it on yachts? Your output should have at most 10-6 absolute or relative error.

Input begins with an integer T, the number of times the programmer embarks on a yacht-creation spree. For each spree, there is first a line containing the space-separated integers N, A, and B in that order, then a line containing N space-separated integers, the ith of which is Ci.

For the ith spree, print a line containing "Case #i: " followed by the expected amount of money the programmer will have left.

1 ≤ T ≤ 50
0 ≤ A < B ≤ 1,000,000,000
1 ≤ N ≤ 100,000
1 ≤ Ci ≤ 1,000,000,000

Explanation of Sample
In the first case, the programmer starts with between 5 and 8 dollars. The programmer's initial amount of money will fall into one of the ranges [5, 6), or [6, 8), or [8, 8]. If it falls into the first range, the programmer will end with [1, 2) dollars. If it falls into the second range, the programmer will end with [0, 2) dollars. If the programmer starts with exactly 8 dollars, he'll end with 0 dollars.

Sample input

Code: Select all

1 5 8
1 0 777777777
1 777777 7777777
2 9 20
8 2
5 40 140
4 9 1 12 7
Sample output

Code: Select all

Case #1: 1.166666667
Case #2: 3.500000000
Case #3: 4277777.000000000
Case #4: 3.227272727
Case #5: 4.400000000
Livecode Wiki: http://livecode.wikia.com
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w

Post Reply

Return to “Getting Started with LiveCode - Experienced Developers”