Facebook Hacker Cup 2014 Tennison Solution

by
Tennison             45 points

You may be familiar with the works of Alfred Lord Tennyson, the famous English poet. In this problem we will concern ourselves with Tennison, the less famous English tennis player. As you know, tennis is not so much a game of skill as a game of luck and weather patterns. The goal of tennis is to win Ksets before the other player. However, the chance of winning a set is largely dependent on whether or not there is weather.

Tennison plays best when it’s sunny, but sometimes of course, it rains. Tennison wins a set with probability ps when it’s sunny, and with probability prwhen it’s raining. The chance that there will be sun for the first set is pi. Luckily for Tennison, whenever he wins a set, the probability that there will be sun increases by pu with probability pw. Unfortunately, when Tennison loses a set, the probability of sun decreases by pd with probability pl. What is the chance that Tennison will be successful in his match?

Rain and sun are the only weather conditions, so P(rain) = 1 – P(sun) at all times. Also, probabilities always stay in the range [0, 1]. If P(sun) would ever be less than 0, it is instead 0. If it would ever be greater than 1, it is instead 1.

Input

Input begins with an integer T, the number of tennis matches that Tennison plays. For each match, there is a line containing an integer K, followed by the probabilities ps, pr, pi, pu, pw, pd, pl in that order. All of these values are given with exactly three places after the decimal point.

Output

For each match, output “Case #i: ” followed by the probability that Tennison wins the match, rounded to 6 decimal places (quotes for clarity only). It is guaranteed that the output is unaffected by deviations as large as 10-8.

Constraints

  • 1 ≤ T ≤ 100
  • 1 ≤ K ≤ 100
  • 0 ≤ ps, pr, pi, pu, pw, pd, pl ≤ 1
  • ps > pr

Solution


<?php
#######################################################
##### COMPILED WITH HIPHOP INSTEAD OF RUNNING PHP #####
#######################################################
// get and import the input file
if(isset($_GET['file'])) { $file = $_GET['file']; } else { $file="input.txt"; }
//$input = file("C:\\Users\\NEO\\Downloads\\".$file);
$input = file($file);
$test_cases = reset($input);
$output = '';

//Skip key 0 as it is the number of test cases!, start looping from 1
for ($case_number = 1, $i=1; $i<count($input); $i++) {

list($K, $Ps, $Pr, $Pi, $Pu, $Pw, $Pd, $Pl) = sscanf($input[$i], "%s %s %s %s %s %s %s %s\n");
if($Ps>1) { $Ps=1; }
if($Ps<0) { $Ps=0; }
printf("%.6lf\n",solve(0,$Pi));
}
// Save results to output file
file_put_contents('output.txt', $output);
function solve($idx, $pi){
global $K, $Ps, $Pr, $Pi, $Pu, $Pw, $Pd, $Pl;
if($idx == $K) return 1;

$ret = 0;

$ret += solve($idx+1,$pi+$Pu) * $pi * $Ps * $Pw;
$ret += solve($idx+1,$pi-$Pd) * $pi * $Ps * $Pl;

$ret += solve($idx+1,$pi+$Pu) * (1-$pi) * $Pr * $Pw;
$ret += solve($idx+1,$pi-$Pd) * (1-$pi) * $Pr * $Pl;

return $ret;
}

?>

 

 

5
1 0.800 0.100 0.500 0.500 0.500 0.500 0.500
2 0.600 0.200 0.500 0.100 1.000 0.100 1.000
1 1.000 0.000 1.000 1.000 1.000 1.000 1.000
25 0.984 0.222 0.993 0.336 0.207 0.084 0.478
58 0.472 0.182 0.418 0.097 0.569 0.816 0.711
Case #1: 0.450000
Case #2: 0.352000
Case #3: 1.000000
Case #4: 0.999956
Case #5: 0.000000