Ordinary Beauty

AtCoder

IDsoundhound2018_summer_qual_c

Time2000ms

Memory256MB

Difficulty—

Let us define the _beauty_ of a sequence $(a_1,... ,a_n)$ as the number of pairs of two adjacent elements in it whose absolute differences are $d$. For example, when $d=1$, the beauty of the sequence $(3, 2, 3, 10, 9)$ is $3$. There are a total of $n^m$ sequences of length $m$ where each element is an integer between $1$ and $n$ (inclusive). Find the beauty of each of these $n^m$ sequences, and print the average of those values. ## Constraints * $0 \leq d < n \leq 10^9$ * $2 \leq m \leq 10^9$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $n$ $m$ $d$ [samples]

Samples

Input #1

2 3 1

Output #1

1.0000000000

The beauty of $(1,1,1)$ is $0$.  
The beauty of $(1,1,2)$ is $1$.  
The beauty of $(1,2,1)$ is $2$.  
The beauty of $(1,2,2)$ is $1$.  
The beauty of $(2,1,1)$ is $1$.  
The beauty of $(2,1,2)$ is $2$.  
The beauty of $(2,2,1)$ is $1$.  
The beauty of $(2,2,2)$ is $0$.  
The answer is the average of these values: $(0+1+2+1+1+2+1+0)/8=1$.

Input #2

1000000000 180707 0

Output #2

0.0001807060

API Response (JSON)

{
  "problem": {
    "name": "Ordinary Beauty",
    "description": {
      "content": "Let us define the _beauty_ of a sequence $(a_1,... ,a_n)$ as the number of pairs of two adjacent elements in it whose absolute differences are $d$. For example, when $d=1$, the beauty of the sequence ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "soundhound2018_summer_qual_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let us define the _beauty_ of a sequence $(a_1,... ,a_n)$ as the number of pairs of two adjacent elements in it whose absolute differences are $d$. For example, when $d=1$, the beauty of the sequence ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments