Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Map Generator
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 1760Accepted: 471
Case Time Limit: 2000MSSpecial Judge

Description

The scene of the new computer game “Battles in Space: Unification” (BSU) is laid in far future. Mankind is scattered on N planets hostile to each other. A player of the game is a leader of one the planets. Using diplomatic tricks and military the player needs to occupy the rest of the planets and, doing so, reunite mankind.

Special hyperspace tunnels are used to travel from one planet to another. Each tunnel connects two of the planets and can be used for communication in both directions. Two planets can not be connected by more then one tunnel. The set of all tunnels connecting the planets is called the map of the game.

Currently, developers of BSU are working on generator of maps of the game. It has been decided to use the special algorithm called «Fine Artificial Model of Intelligence» (FAMI) for this purpose. The algorithm operates in the following way. For each pair of planets i and j (1 ≤ i < j N) a random real number Xij (0 ≤ Xij ≤ 1) is generated. Uniform distribution is used to generate random numbers and numbers Xij are generated independently. Next, if Xij P, where parameter P is a real number, then the hyperspace tunnel connecting planets i and j is added into the map being generated.

Developers wish the map generator produced connected maps. A map is said to be connected when between any pair of planets there is a path, consisting of one or more hyperspace tunnels. Unfortunately, it appears that maps generated by FAMI algorithm sometimes are not connected. You are assigned to research this phenomenon.

You need to write a program which being given numbers N and P calculates probability of generating connected map by FAMI algorithm.

Input

The input consists of two lines. The first line contains an integer number N (1 ≤ N ≤ 20), while the second line contains a real number P (0 ≤ P ≤ 1).

Output

The output needs to contain an answer – the single real number which is the probability of generating connected map by FAMI algorithm. Absolute error of the answer must not exceed 10−2.

Sample Input

3
0.5

Sample Output

0.5

Source

Northeastern Europe 2005, Western Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator