Connection Status:
Competition Arena > SchoolTrip

SchoolTrip

SRM 384 · 2007-12-19 · by rasto6sk

SRM 384 · 2007-12-19 · by rasto6sk · Dynamic Programming, Math, Recursion
Class Name: SchoolTrip
Return Type: double
Method Name: duration
Arg Types: (vector<int>)
Problem Statement

Problem Statement

There are n students standing in a circle and playing a game with a ball. The students are numbered from 0 to n-1 in clockwise order. On each turn, a student must take the ball and throw it at another student in the circle. Student i has a probability[i] percent chance of hitting the target student, and if he is successful, the student who is hit must leave the circle. Turns go in clockwise order, and student 0 gets the first turn. They are not allowed to skip turns. The game ends when there is only one student left in the circle.

The students are playing this game against their will, so their common goal is to finish the game in the least number of turns. Return the expected number of turns the game will last.

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.
  • Each student does not worry about how long he will stay in the circle, only the total game time matters.

Constraints

  • probability will contain between 2 and 6 elements, inclusive.
  • Each element of probability will be between 10 and 100, inclusive.
Examples
0)
{100,23}
Returns: 1.0

The first student will certainly hit the second one, so the game will be finished after 1 turn.

1)
{50,50}
Returns: 2.0

With probability 1/2 the game will be finished after 1 turn, with probability 1/4 after 2 turns, .. with probability 1/2^k after k turns. The infinite sum 1*1/2 + 2*1/4 + 3*1/8 +.. n*1/2^n = 2.

2)
{25,50,75}
Returns: 3.892383478590375
3)
{100,100,100,42,11}
Returns: 4.0

The first two students will start out by hitting the last two students. After that, there will be three students remaining, and all of them always hit their targets, so only two more turns will be required for the game to end.

4)
{10,10,10,12,13,13}
Returns: 41.70202803691314

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

Coding Area

Language: C++17 · define a public class SchoolTrip with a public method double duration(vector<int> probability) · 56 test cases · 2 s / 256 MB per case

Submitting as anonymous