RANDOM ORDER

• Problem Description

  
  Petr, Nikita G. and Nikita are the most influential music critics in Saint-Petersburg. They have recently downloaded their favorite band's new album and going to listen to it. Nikita claims that the songs of entire album should be listened strictly in the same order as they are given, because there is the secret message from the author in the songs' order. Petr, being chaotic, does not think so, hence he loves listening to songs in a random order. Petr is pretty good in convincing other people, so after a two-hours discussion Nikita accepted listening in random order(the discussion's duration was like three times longer than the album's one). In this context random order means following: There are N songs in the album. In the very beginning random song is chosen(here and further "random song" means that every song has equal probability to be chosen). After some song is over the next one is chosen randomly and independently of what have been played before. Nikita G., being the only one who is not going to drop out from the university, wonders, what is the expected number of songs guys have to listen to until every song is played at least once.

• CODING ARENA

• #include <stdio.h>

  #include<stdlib.h>

  int main()

  {

    int n,t,i;

    double x;

    scanf("%d",&t);

    while(t--)

    {

      scanf("%d",&n);

      x=1;

      for(i=2;i<=n;i++)

        x+=(1.0)/i;

      printf("%1f\n",n*x);

    }

    return 0;

  }

  
  

• Test Case 1

  
  Input (stdin)

  3
  
  1
  
  2
  
  3
  
  

  Expected Output

  1.000000
  
  3.000000
  
  5.500000

• Test Case 2

  
  Input (stdin)

  5
  
  4
  
  6
  
  3
  
  9
  
  7
  
  

  Expected Output

  8.333333
  
  14.700000
  
  5.500000
  
  25.460714
  
  18.150000