eolymp
bolt
Try our new interface for solving problems
Məsələlər

Map Generator

Map Generator

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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 и j (1i < jN) a random real number X_ij (0X_ij1) is generated. Uniform distribution is used to generate random numbers and numbers X_ij are generated independently. Next, if X_ijP, 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.

Giriş verilənləri

Input file consists of two lines. The first line contains an integer number N (1N20), while the second line contains a real number P (0P1).

Çıxış verilənləri

Output file 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}.

Nümunə

Giriş verilənləri #1
3
0.5
Çıxış verilənləri #1
0.500000000000000
Mənbə ACM Programming Contest 2005, Minsk, October 2005