Randomly Testing CircuitsProblem code: CIRCUITS |
All submissions for this problem are available.
AND gates and OR gates are basic components used in building digital circuits. Both gates have two input lines and one output line. The output of an AND gate is 1 if both inputs are 1, otherwise the output is 0. The output of an OR gate is 1 if at least one input is 1, otherwise the output is 0.
You are given a digital circuit composed of only AND and OR gates where one node (gate or input) is specially designated as the output. Furthermore, for any gate G and any input node I, at most one of the inputs to G depends on the value of node I.
Now consider the following random experiment. Fix some probability p in [0,1] and set each input bit to 1 independently at random with probability p (and to 0 with probability 1-p). The output is then 1 with some probability that depends on p. You wonder what value of p causes the circuit to output a 1 with probability 1/2.
Input
The first line indicates the number of test cases to follow (about 100).
Each test case begins with a single line containing a single integer n with 1 ? n ? 100 indicating the number of nodes (inputs and gates) in the circuit. Following this, n lines follow where the i'th line describes the i'th node. If the node is an input, the line simply consists of the integer 0. Otherwise, if the node is an OR gate then the line begins with a 1 and if the node is an AND gate then the line begins with a 2. In either case, two more integers a,b follow, both less than i, which indicate that the outputs from both a and b are used as the two input to gate i.
As stated before, the circuit will be such that no gate has both of its inputs depending on the value of a common input node.
Test cases are separated by a blank line including a blank line preceding the first test case.
Output
For each test case you are to output a single line containing the value p for which the output of node n is 1 with probability exactly 1/2 if the inputs are independently and randomly set to value 1 with probability p. The value p should be printed with exactly 5 digits after the decimal.
Example
Input: 4 1 0 3 0 0 1 1 2 3 0 0 2 1 2 5 0 0 0 2 1 2 1 3 4 Output: 0.50000 0.29289 0.70711 0.40303
| Author: | friggstad |
| Date Added: | 7-06-2010 |
| Time Limit: | 2 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
can u explain the last test
can u explain the last test case?
Please explain testcases.
Please explain testcases.
Acc. to the problem
Acc. to the problem statement:-
"You are given a digital circuit composed of only AND and OR gates where one node (gate or input) is specially designated as the output"
Does this mean that there will be a unique output node and that we are supposed to identify it?
That confused me a little as
That confused me a little as well - it should really have been mentioned somewhere in the input section. But if you continue reading the output section, you'll find it says you should consider the output of node n.
can i assume that input on
can i assume that input on i'th node will depend only on node that are less that i?
(5 6 8) this is invalid or it may be?
sorry for previous 5 means 5
sorry for previous
5 means 5 th line with 1,or 2.
That is specifically
That is specifically mentioned in the problem statement.
@ Stephen Merriman thanks.
@ Stephen Merriman
thanks.
pragyan
pragyan
anyone explain the third test
anyone explain the third test cast?
m GETTING ALL CORRECT ANSWERS
m GETTING ALL CORRECT ANSWERS FOR MY CODE ....BUT CODECHEF JUDGE SAY IT WRONG ANSWER......ANY SUGESSIONS.....
can a gate have two inputs
can a gate have two inputs that are output form other gate??
Eg:
0
0
1 1 2
0
0
2 4 5
1 3 6
here last gate has input as outputs from previous or and and gates
please explain this
please explain this statement:
Furthermore, for any gate G and any input node I, at most one of the inputs to G depends on the value of node I.
Vishwa, for your first
Vishwa, for your first question, yes.
For your second question, it basically means you can't have loops, ex. output of the gate goes back to affect it's inputs.
can anyone tell me as to why
can anyone tell me as to why there can never be two solutions of p in the given range? though i have an idea of the solution but i dont want to implement till i am sure of this.
I've got "Wrong Answer'. I'm
I've got "Wrong Answer'.
I'm printing result with:
DecimalFormat myFormatter = new DecimalFormat("0.00000");
String output = myFormatter.format(res);
out.println(output);
I do know, that it's rounding things up. How can I avoid it?
It's in Java 6..
It's in Java 6..
@Atish You are right in
@Atish
You are right in thinking that there is only one correct p. I am not going to explain the proof, because it has to do with the solution (the correct one, I think) to this problem.
@Gurtej Thanks :)
@Gurtej Thanks :)
The correct question I should
The correct question I should have asked is: whether I should round answer up or just cut it off after 5th digit after the point?
@Ilya I believe you are
@Ilya I believe you are supposed to round to the fifth decimal place, i.e. .000005 -> .00001 and .000004 -> .00000
@Gurtej Thanx a lot! Default
@Gurtej Thanx a lot! Default rounding approach was 'HALF_EVEN' - so now I changed it to 'HALF_UP'.
I've written, checked and ran my implementation and for every test I devised - results are as expected. Somehow, I receive 'wrong answer' when I submit. Is there anything I can do except waiting till the end of contest, when solutions will be published? Any help would be greatly appreciated..