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:
4
x
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.
hide comments
Thomas Dybdahl Ahle:
2017-12-13 16:23:54
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 :-)
|
|
Ravi Kiran:
2013-05-07 21:08:48
I just used long long and long double as data types for intermediate results.
|
|
Aditya Muraletharan:
2013-03-04 11:01:08
I love pen-and-paper problems:)
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2013-01-11 13:40:11
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)... |
|
:D:
2013-01-10 22:10:26
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.
|
|
:C++::
2012-12-27 15:54:27
Can anyone help me to understand the problem. I cant get it... |
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 |