TRUTHORL - Truth Or Lie
Suppose you have m yes or no questions that you want to ask n people. You are allowed to ask each person exactly two different questions. He/she will answer exactly one of them correctly and one of them incorrectly, you don't know which is a correct answer and which is an incorrect one. Given their answers, determine the number of combinations of answers to the m questions that can still be correct (i.e., no contradictions).
Input
First line is the number of inputs. For each set of input, start out with a line of n<=10000 and m<=200, followed by n lines. The i-th line has four integers a b c d. It means that the answer given by the i-th person for question a is b, and for question c is d. Moreover, the answer "1" means yes, and "0" means no.
Output
For each line of input, output "No Inference" if the answers do not help you eliminate any wrong combination of answers or the number of combinations of possible answers is 0, otherwise output the size of the set of combinations of answers still possible.
Sample
Input 2 2 2 1 1 2 0 1 1 2 1 4 4 1 1 2 1 1 1 3 0 2 1 4 1 3 1 4 0 Output No Inference 2
Problem setter --- sy
hide comments
:D:
2009-10-28 17:40:53
Bignum is needed but it's not very hard to implement here ;) |
|
Paranoid Android:
2009-10-22 13:13:49
Do we have to implement bignum implementation or will the answer fit within 64 bit ?? Last edit: 2009-10-22 13:14:09 |
|
Luke Pebody:
2009-02-17 11:06:29
Output description is wrong. Only output "No inference" if the number of combinations is 0. |
Added by: | Chen Xiaohong |
Date: | 2007-11-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |