/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
数列 (a_1,... ,a_n) の 美しさ を、隣り合う 2 項の組であって、 差の絶対値が d であるものの個数として定義します。 例えば、d=1 であるとき、数列 (3, 2, 3, 10, 9) の美しさは 3 です。
各要素が 1 以上 n 以下の整数である長さ m の数列は全部で n^m 通り存在します。 この n^m 通りの数列すべてに対して美しさを求めて、 それらの平均を出力してください。
制約
- 0 \leq d < n \leq 10^9
- 2 \leq m \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
n m d
出力
各要素が 1 以上 n 以下の整数である長さ m の数列 の美しさの平均を出力せよ。 絶対誤差または相対誤差が 10^{-6} 以下ならば正解となる。
入力例 1
2 3 1
出力例 1
1.0000000000
(1,1,1) の美しさは 0 です。
(1,1,2) の美しさは 1 です。
(1,2,1) の美しさは 2 です。
(1,2,2) の美しさは 1 です。
(2,1,1) の美しさは 1 です。
(2,1,2) の美しさは 2 です。
(2,2,1) の美しさは 1 です。
(2,2,2) の美しさは 0 です。
これらの平均である、 (0+1+2+1+1+2+1+0)/8=1 が答えとなります。
入力例 2
1000000000 180707 0
出力例 2
0.0001807060
Score : 300 points
Problem Statement
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
Output
Print the average of the beauties of the sequences of length m where each element is an integer between 1 and n. The output will be judged correct if the absolute or relative error is at most 10^{-6}.
Sample Input 1
2 3 1
Sample 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.
Sample Input 2
1000000000 180707 0
Sample Output 2
0.0001807060