Enigmatic Travel

Time limit1sMemory limit128 MB

Summary

For each complete graph size L, compute the average cost of a random walk, a random simple path, and a random simple cycle.

Level: Medium7 of 10
Topics: Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

Suhan and Laina live in a city that has $L$ locations. Every pair of locations lies the same distance apart, and each pair is joined by exactly one two-way road — so the road map is a complete graph on $L$ vertices. Driving along any single road costs exactly $1$ universal joule.

They love wandering the city together and keep every trip secret: no one knows where they start, where they finish, or which roads they take. A trip may begin at any location and end at any location — the end may be the same as the start — and it may follow any sequence of roads they like. (For instance, when the trip is a simple cycle, the start and the end coincide.)

Given the number of locations $L$ , compute the expected (average) cost of a single trip under three different assumptions about what kind of trip it is. You may assume the cost of a trip never exceeds $L$ .

Input

The input consists of several lines. Each line holds a single integer $L$ ( $2 < L \le 15$ ), the number of locations. The input ends with a line containing $0$ , which must not be processed.

Output

For every input line, print one line with three floating-point numbers $F_1$ , $F_2$ , $F_3$ , each rounded to exactly four digits after the decimal point:

$F_1$ is the expected cost of an arbitrary trip (any sequence of roads, i.e. a walk).
$F_2$ is the expected cost of a trip guaranteed to be a simple path (no location is visited twice).
$F_3$ is the expected cost of a trip guaranteed to be a simple cycle (it returns to the start and repeats no other location).

Every cost is measured in universal joules.

Examples4

Example 1

Input

Expected output

2.4286 1.5000 3.0000
3.5500 2.2000 3.5000
4.6716 3.0625 4.2000

Example 2
Input
```
3
0
```
Expected output
```
2.4286 1.5000 3.0000
```
Example 3
Input
```
4
0
```
Expected output
```
3.5500 2.2000 3.5000
```

Example 4

Input

Expected output

5.7504 4.0154 5.0625
6.8000 5.0031 6.0154
9.8750 8.0000 9.0001