TAP2016H - New TAP
[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]
We are considering changing the rules for the Argentinian Programming Tournament starting next year. Before doing that, we would like to evaluate whether the new system is fair, and we need your help to do that.
The new tournament will have N teams competing in N-1 rounds. In each round two teams will face each other competing in order to be the first to solve a problem, the losing team being eliminated. In the first round, two teams will be chosen at random, and the losing team will be placed in the last place of the scoreboard, while the winner remains in the competition. In each of the following rounds, two teams still in the competition will be chosen at random, and the losing team shall be placed in the last remaining place of the scoreboard, being thus eliminated from the tournament.
For example, if the tournament has N=4 teams named "aWArush", "Buen Kilo de Pan Flauta", "Melarita" and "Type Mismatch", the tournament will be held in three rounds. Suppose that in the first round "Buen Kilo de Pan Flauta" faces "Melarita", the former being the winner; in the second round "aWArush" beats "Buen Kilo de Pan Flauta"; and finally in the last round "aWArush" beats "Type Mismatch". Then the placement of the teams in the final scoreboard will be in the following order: 1st "aWArush", 2nd "Type Mismatch", 3rd "Buen Kilo de Pan Flauta" and 4th "Melarita".
To analize just how fair the new tournament format is, we will consider the teams to be numbered from 1 to N, in such a way that lower numbers represent better teams. We will assume that whenever two teams face each other in a given round, the one with the smallest number will invariably win. We would like you to help us answer the following question: What is the probability for team X to be placed at position Y in the final scoreboard?
There are multiple test cases in the input file. Each test case consists of a single line containing three integer numbers N, X and Y. The number N represents the number of teams taking part in the tournament, (2 ≤ N ≤ 1000), X represents the number of the team we are interested in, and Y represents its final position (1 ≤ X,Y ≤ N).
For each test case, print a single line containing a rational number, representing the probability for team number X to be placed at position Y in the final scoreboard. Print the result with exactly 4 digits after the decimal marker, rounding if necessary.
Input: 3 2 2 10 3 6 10 1 5 1000 1 1 1000 1000 1000 Output: 0.6667 0.0946 0.0000 1.0000 0.0020
O(N^2) per test case easily passes, but keep in mind that optimistic complexity for my solution was O(1).