# Facebook Hacker Cup 2014 Tennison Solution

**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 **K**sets 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 **p _{s}** when it’s sunny, and with probability

**p**when it’s raining. The chance that there will be sun for the first set is

_{r}**p**. Luckily for Tennison, whenever he wins a set, the probability that there will be sun increases by

_{i}**p**with probability

_{u}**p**. Unfortunately, when Tennison loses a set, the probability of sun decreases by

_{w}**p**with probability

_{d}**p**. What is the chance that Tennison will be successful in his match?

_{l}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 **p _{s}, p_{r}, p_{i}, p_{u}, p_{w}, p_{d}, p_{l}** 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 ≤
**p**≤ 1_{s}, p_{r}, p_{i}, p_{u}, p_{w}, p_{d}, p_{l} **p**>_{s}**p**_{r}

## 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