|Online Judge||Problem Set||Authors||Online Contests||User|
Map Generator returns (MG-II)
You have just finished your research of FAMI algorithm (see task “Map Generator”). You are very proud of yourself and even expect being paid bonus this month. Your boss, whose nickname is Dean, asks you to come over to his office for a moment. You expect thanks and even promotion. But …
‘What is this?’ asks Dean and shows you your latest report.
‘Well, h-m-m, these are results of my FAMI algorithm research, a-a-a,’ you answer. It seems that your dreams about soon promotion are … just dreams. But you still do not understand what is wrong about your report.
‘I can read, by the way,’ continues Dean. ‘I am talking about the absolute error. Why it is so big? I require better results!’
When you argue with your boss, the best argument is silence. So, now instead of bonuses and promotions you need to rewrite your program.
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.
The input, as in the previous task, 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).
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−8.
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