EXFOR - Explicit Formula

no tags 

 

Consider 10 Boolean variables x1, x2, x3, x4, x5, x6, x7, x8, x9, and x10. Consider all pairs and triplets of distinct variables among these ten. (There are 45 pairs and 120 triplets.) Count the number of pairs and triplets that contain at least one variable equal to 1. Set f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = 1 if this number is odd and f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = 0 if this number is even.

 

 

Here’s an explicit formula that represents the function f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) correctly:

 

f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = (x1 || x2)^(x1 || x3)^(x1 || x4)^(x1 || x5)^(x1 || x6)^(x1 || x7)^(x1 || x8)^(x1 || x9)^(x1 || x10)^(x2 || x3)^(x2 || x4)^(x2 || x5)^(x2 || x6)^(x2 || x7)^(x2 || x8)^(x2 || x9)^(x2 || x10)^(x3 || x4)^(x3 || x5)^(x3 || x6)^(x3 || x7)^(x3 || x8)^(x3 || x9)^(x3 || x10)^(x4 || x5)^(x4 || x6)^(x4 || x7)^(x4 || x8)^(x4 || x9)^(x4 || x10)^(x5 || x6)^(x5 || x7)^(x5 || x8)^(x5 || x9)^(x5 || x10)^(x6 || x7)^(x6 || x8)^(x6 || x9)^(x6 || x10)^(x7 || x8)^(x7 || x9)^(x7 || x10)^(x8 || x9) ^ (x8 || x10) ^ (x9 || x10) ^ (x1 || x2 || x3) ^ (x1 || x2 || x4) ^ (x1 || x2 || x5) ^ (x1 || x2 || x6) ^(x1 || x2 || x7) ^ (x1 || x2 || x8) ^ (x1 || x2 || x9) ^ (x1 || x2 || x10) ^ (x1 || x3 || x4) ^ (x1 || x3 || x5) ^(x1 || x3 || x6) ^ (x1 || x3 || x7) ^ (x1 || x3 || x8) ^ (x1 || x3 || x9) ^ (x1 || x3 || x10) ^ (x1 || x4 || x5) ^(x1 || x4 || x6) ^ (x1 || x4 || x7) ^ (x1 || x4 || x8) ^ (x1 || x4 || x9) ^ (x1 || x4 || x10) ^ (x1 || x5 || x6) ^(x1 || x5 || x7) ^ (x1 || x5 || x8) ^ (x1 || x5 || x9) ^ (x1 || x5 || x10) ^ (x1 || x6 || x7) ^ (x1 || x6 || x8) ^(x1 || x6 || x9) ^ (x1 || x6 || x10) ^ (x1 || x7 || x8) ^ (x1 || x7 || x9) ^ (x1 || x7 || x10) ^ (x1 || x8 || x9) ^(x1 || x8 || x10) ^ (x1 || x9 || x10) ^ (x2 || x3 || x4) ^ (x2 || x3 || x5) ^ (x2 || x3 || x6) ^ (x2 || x3 || x7) ^(x2 || x3 || x8) ^ (x2 || x3 || x9) ^ (x2 || x3 || x10) ^ (x2 || x4 || x5) ^ (x2 || x4 || x6) ^ (x2 || x4 || x7) ^(x2 || x4 || x8) ^ (x2 || x4 || x9) ^ (x2 || x4 || x10) ^ (x2 || x5 || x6) ^ (x2 || x5 || x7) ^ (x2 || x5 || x8) ^(x2 || x5 || x9) ^ (x2 || x5 || x10) ^ (x2 || x6 || x7) ^ (x2 || x6 || x8) ^ (x2 || x6 || x9) ^ (x2 || x6 || x10) ^(x2 || x7 || x8) ^ (x2 || x7 || x9) ^ (x2 || x7 || x10) ^ (x2 || x8 || x9) ^ (x2 || x8 || x10) ^ (x2 || x9 || x10) ^(x3 || x4 || x5) ^ (x3 || x4 || x6) ^ (x3 || x4 || x7) ^ (x3 || x4 || x8) ^ (x3 || x4 || x9) ^ (x3 || x4 || x10) ^(x3 || x5 || x6) ^ (x3 || x5 || x7) ^ (x3 || x5 || x8) ^ (x3 || x5 || x9) ^ (x3 || x5 || x10) ^ (x3 || x6 || x7) ^(x3 || x6 || x8) ^ (x3 || x6 || x9) ^ (x3 || x6 || x10) ^ (x3 || x7 || x8) ^ (x3 || x7 || x9) ^ (x3 || x7 || x10) ^(x3 || x8 || x9) ^ (x3 || x8 || x10) ^ (x3 || x9 || x10) ^ (x4 || x5 || x6) ^ (x4 || x5 || x7) ^ (x4 || x5 || x8) ^(x4 || x5 || x9) ^ (x4 || x5 || x10) ^ (x4 || x6 || x7) ^ (x4 || x6 || x8) ^ (x4 || x6 || x9) ^ (x4 || x6 || x10) ^(x4 || x7 || x8) ^ (x4 || x7 || x9) ^ (x4 || x7 || x10) ^ (x4 || x8 || x9) ^ (x4 || x8 || x10) ^ (x4 || x9 || x10) ^(x5 || x6 || x7) ^ (x5 || x6 || x8) ^ (x5 || x6 || x9) ^ (x5 || x6 || x10) ^ (x5 || x7 || x8) ^ (x5 || x7 || x9) ^(x5 || x7 || x10) ^ (x5 || x8 || x9) ^ (x5 || x8 || x10) ^ (x5 || x9 || x10) ^ (x6 || x7 || x8) ^ (x6 || x7 || x9) ^(x6 || x7 || x10) ^ (x6 || x8 || x9) ^ (x6 || x8 || x10) ^ (x6 || x9 || x10) ^ (x7 || x8 || x9) ^ (x7 || x8 || x10) ^(x7 || x9 || x10) ^ (x8 || x9 || x10)

 

In this formula || stands for logical or, and ^ stands for exclusive or (xor). Remember that in C++ and Java these two binary operators are denoted as “||” and “^”.

 

Given the values of x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, calculate the value of f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10).

 

Input

The first line of the input file contains T, the number of test cases. The next T lines contain 10 numbers each, x1, x2, x3, x4, x5, x6, x7, x8, x9, and x10. Each of these numbers is either 0 or 1.

 

Output

For each test case output a single line with the value f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10).

 

Example

Input:
1
1 0 0 1 0 0 1 0 0 1

Output:
0

hide comments
karthik1997: 2015-07-15 06:58:14

for c users use int for all variables and output the res of f using a function
ac ijn 1st go 0.0s

pvkcse: 2014-05-28 09:52:22

yeah...CTRL + C and CTRL + v is enough...found bit hard to change all || to or in python...but in c it's just a minute work...!!!

Last edit: 2014-05-28 10:03:59
Ravi Kiran: 2010-11-12 07:20:27

I think it can be moved to challenge incase you want to limit code length.
The problem is too simple for Classical Section.

.::Manish Kumar::.: 2010-11-09 13:54:37

It would be very nice..if u could reduce source code length.

Fidel Schaposnik: 2010-11-09 12:37:05

Note that in the original contest, the problems were printed so you couldn't just copy & paste the formula. It still was the "a+b problem" that everyone was supposed to solve ;-)

Seshadri R: 2010-11-09 11:58:18

This problem cannot even qualify to be a tutorial example. If this trend continues, we can soon see problems like "print the result of x+y+z where x, y and z can be either 0 or 1"


Added by:Fidel Schaposnik
Date:2010-11-07
Time limit:2.990s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC 2010, NEERC, Northern Subregional Contest