SPOJ.com - Problem AMR12H

AMR12H - Wormtongues Mind

Wormtongue looked from face to face. In his eyes was the hunted look of a beast seeking some gap in the ring of his enemies.

'Nay, Eomer, you do not fully understand the mind of Master Wormtongue,' said Gandalf, turning his piercing glance upon him. 'He is bold and cunning. Even now he plays a game with peril and wins a throw.' - Gandalf, trying to figure out Wormtongue's mind.

In fact, Wormtongue's mind is a complicated system of evaluating various variables and parameters. In essence, each parameter is a uniform random floating point variable between 0 and 1 (inclusive). Further, his mind works on calculating best and worst-case values, which are equivalent to min/max of 2 expressions.

For example, right now Wormtongue is calculating :

'Chances of escaping' = max('Theoden letting me go', 'Me killing everyone')

'Theoden letting me go' = max('Theoden is forgiving by nature', 'Gandalf advises him to let me go').

'Me killing everyone' = min('Me killing Gandalf', 'Me killing Theoden').

So, you are given an expression consisting of independent uniform [0, 1] random variables, on which you have an expression consisting of "min", and "max" alone. Help Gandalf figure out Wormtongue's mind by finding the expected value of this expression.

Input (STDIN):

The first line contains T, the number of test cases.

Each test case consists of a single line describing the expression. The characters of the string are derived from the set {'M','m','x'}, where 'M' stands for max, 'm' stands for min, and 'x' is a random variable

Formally, in the expression tree, each node which asks for max is labeled as 'M', each node which asks for min is labelled 'm', and all the leaves are labeled 'x'. The description of the expression is preorder traversal of this tree.

For example, Mxmxx describes the expression max(x1, min(x2, x3)).

Output (STDOUT):

For each test case, output one line which contains the expected value of the expression. The results should be accurate within an error range of 10^-6.

Constraints:

1 <= T <= 1,000

1 <= input string length <= 100

Sample Input:

mxx

Mxx

MmxxMxx

Sample Output:

0.500000

0.333333

0.666667

0.700000

Notes/Explanation of Sample Input:

For the first test case, it asks for the mean of a random number between 0 and 1, which is 0.5.

Note:

It is recommended to use long long and long double data types in calculation to avoid precision errors.

Wormtongue looked from face to face. In his eyes was the hunted look of a beast seeking some gap in the ring of his enemies.

For example, right now Wormtongue is calculating :

'Chances of escaping' = max('Theoden letting me go', 'Me killing everyone')

'Theoden letting me go' = max('Theoden is forgiving by nature', 'Gandalf advises him to let me go').

'Me killing everyone' = min('Me killing Gandalf', 'Me killing Theoden').

Input (STDIN):

The first line contains T, the number of test cases.

For example, Mxmxx describes the expression max(x1, min(x2, x3)).

Output (STDOUT):

For each test case, output one line which contains the expected value of the expression. The results should be accurate within an error range of 10^-6.

Constraints:

1 <= T <= 1,000

1 <= input string length <= 100

Sample Input:

mxx

Mxx

MmxxMxx

Sample Output:

0.500000

0.333333

0.666667

0.700000

Notes/Explanation of Sample Input:

For the first test case, it asks for the mean of a random number between 0 and 1, which is 0.5.

Note:

It is recommended to use long long and long double data types in calculation to avoid precision errors.

Submit solution!

Added by:	Varun Jalan
Date:	2012-12-22
Time limit:	1s-4s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Utkarsh Lath - ICPC Asia regionals, Amritapuri 2012

hide comments



2017-12-13 16:23:54 Thomas Dybdahl Ahle I didn't quite understand the Gandal/Wormtounge thing, but the problem itself is beautiful! Thank you for posing this on Spoj! And thank you for making the time limit such that a simple O(n^2) python3 solution would pass :-) I managed to get accepted in python, using the `fractions.Fraction` class to get unlimited precision, and then only converting to float at print time. I'm very surprised that this actually made a difference, since I did nearly all my arithmetic in integers already. Last edit: 2017-12-13 16:31:55
2013-05-07 21:08:48 Ravi Kiran I just used long long and long double as data types for intermediate results. And "cout" for the output. My output for the sample case is printed as: 0.5 0.333333 0.666667 0.7 Hope it helps others.
2013-03-04 11:01:08 Aditya Muraletharan I love pen-and-paper problems:) Watch out for precision issues. I just needed to change the order of certain operations to get AC after many WA's.
2013-01-11 13:40:11 (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†) I'm weak on floating number and precision, so 0.02s is my best after many WA because of precision error... Curious, how to get AC in 0.00s... Also this problem doesn't need any precomputation to solve, just math formula and logic (need only 1.6MB of memory in C)...
2013-01-10 22:10:26 :D I assume you understand how input formatting works here. You have a "min-max" expression. Every variable is independently, randomly generated from [0;1] range. With some specific variable values, you can easily count value of the entire expression. Now the expected value, to put is simply, is the average among all possible values of that expression. The best way to visualize it, is to make a simulation. It is also a great way to debug such problems. Generate all the variables and count the expressions value. Repeat that a large number of times (10^6 - 10^8) and simply count the average of results. You should get values very close to the correct answer. Now you just need to work out the math to do it in the precise, not approximate manner. Personally I find such problems very hard, since probabilistic is so counter-intuitive. Good luck :)
2012-12-27 15:54:27 :C++: Can anyone help me to understand the problem. I cant get it...