Connection Status:
Competition Arena > TheTicketsDivTwo

TheTicketsDivTwo

SRM 504.5 · 2011-04-28 · by Vasyl[alphacom]

SRM 504.5 · 2011-04-28 · by Vasyl[alphacom] · Dynamic Programming
Class Name: TheTicketsDivTwo
Return Type: double
Method Name: find
Arg Types: (int, int, int)
Problem Statement

Problem Statement

John has two tickets for the basketball game - one for himself and one for a friend. However, he has n friends who want to go with him. He decides to use the following strategy to choose one of them. First, he tells his friends to form a straight single file line. Then, he repeats the following step until he has made a choice. If there is only one friend in line, John chooses him. Otherwise, he throws a standard six-sided die. If the number 4 is on top, he chooses the friend who is currently first in line. Otherwise, if the number is odd, the first friend in line must move to the end of the line, and if the number is even, the first friend in line must leave the line and go home.

While the initial John's intention is to throw a die until some friend is chosen, in practice he gets tired quickly. If after k throws of a die he still hasn't chosen a friend, he prefers to stop the process and to choose the friend who is currently first in line.

You are given an int m, the 1-based index of a friend in the initial line. The index of the first friend is 1, and the index of the last friend is n. Return the probability that the m-th friend in the initial line is ultimately chosen by John.

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

  • n will be between 1 and 10, inclusive.
  • m will be between 1 and n, inclusive.
  • k will be between 1 and 10, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
2
1
1
Returns: 0.16666666666666666

There is 1/6 probability that John will choose the first friend after the first throw of a die.

1)
2
1
2
Returns: 0.5833333333333334

The first friend will go to the game if John chooses him after the first throw, or if he goes to the end of the line after the first throw and Jonh doesn't choose the second friend after the second throw. The overall probability is 1/6 + 1/2 * 5/6.

2)
7
7
4
Returns: 0.0

There's no chance for the last friend in the line to be chosen.

3)
4
2
10
Returns: 0.25264033564814814
4)
9
1
4
Returns: 0.16666666666666666

Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheTicketsDivTwo with a public method double find(int n, int m, int k) · 65 test cases · 2 s / 256 MB per case

Submitting as anonymous