Save The Princess
All submissions for this problem are available.
Shiro is leading an army to save the princess of his kingdom "Abra". The princess has been made a prisoner by the neighboring kingdom "Kadabra". Kadabra is a magical land and is full of challenges. Shiro's army has to pass N levels before they can get to the princess. After each level, the army gets a few flags to carry along. The flags can either all be of kindom Abra OR all of kingdom Kadabra. The magic of Kadabra forces Shiro's army to carry the flags irrespective of which kingdom they belong to. The princess doesn't know Shiro or anyone from his army. She will not escape with them unless she can trust them. She will trust them only if the number of Abra's flags they are carrying is atleast as much as the number of Kadabra's flags.
The army gets ai flags at the end of the ith level. Probability that flags received at the end of the ith level will be Abra's flags is pi. Your task is to tell Shiro what is the probability that the princess will trust him once they reach her.
Input:First line of input contains a single integer T, the number of test cases.
Each test starts with a single line having an integer, N, the number of levels in Kadabra.
Next line contains contains N integers with the ith integer being ai as described above.
Next line contains contains N integers with the ith integer being pi as described above. Note that the probabilities given will be in percents.
Output:For each test case, output a line containing the required probability. The answer will be accepted if the relative error is not more than 10-6.
1 ≤ T ≤ 100 1 ≤ N ≤ 100 1 ≤ ai ≤ 100 0 ≤ pi ≤ 100
2 5 1 2 3 4 4 0 100 100 0 50 2 5 5 50 60Output:
Difference in answer upto 1e-6 will be ignored.
|Tags||aug13, dynamic-programming, easy, simple-math, vamsi_kavala|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.