Journey

AtCoder

IDabc194_d

Time2000ms

Memory256MB

Difficulty—

We have a graph with $N$ vertices called Vertex $1$ through $N$. Takahashi is standing on Vertex $1$. The graph has no edges now. Takahashi will repeatedly do the following operation: 1. Choose one of the $N$ vertices (including the one on which Takahashi is standing now). Every vertex is chosen with probability $\frac{1}{N}$, independently from previous operations. 2. Add an edge between the vertex on which Takahashi is standing now and the chosen vertex, and go to the chosen vertex. Find the expected value of the number of times he does the operation until the graph becomes connected. ## Constraints * $2 \le N \le 10^5$ ## Input Input is given from Standard Input in the following format: $N$ [samples]

Samples

Input #1

Output #1

2.00000000000

The graph becomes connected when the operation chooses Vertex $2$ for the first time.  
By considering the case Vertex $2$ is chosen for the first time in the $i$\-th operation for each $i$, the answer is $\sum_{i = 1}^{\infty} (i \times (\frac{1}{2})^i) = 2$.

Input #2

Output #2

4.50000000000

API Response (JSON)

{
  "problem": {
    "name": "Journey",
    "description": {
      "content": "We have a graph with $N$ vertices called Vertex $1$ through $N$. Takahashi is standing on Vertex $1$.   The graph has no edges now.   Takahashi will repeatedly do the following operation: 1.  Choose ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc194_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a graph with $N$ vertices called Vertex $1$ through $N$. Takahashi is standing on Vertex $1$.  \nThe graph has no edges now.  \nTakahashi will repeatedly do the following operation:\n\n1.  Choose ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments