F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

NAND

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 685    Accepted Submission(s): 246


Problem Description
Xiaoqiang entered the ¡°shortest code¡± challenge organized by some self-claimed astrologists. He was given a boolean function taking n inputs (in C++):

bool f(bool x1, bool x2, bool x3){
//your code goes here
//return something
}


All possible inputs and expected outputs of this function have been revealed:



Xiaoqiang¡¯s code must be like:

bool a = NAND(b, c);

where ¡°a¡± is a newly defined variable,¡°b¡± and ¡°c¡± can be a constant (0/1) or a function parameter (x1/x2/x3) or a previously defined variable. NAND is the ¡°not-and¡± function:

NAND(b, c)=!(b&&c)

Because NAND is universal, Xiaoqiang knew that he could implement any boolean function he liked. Also, at the end of the code there should be a return statement:

return y;

where y can be a constant or a function parameter or a previously defined variable. After staring at the function for a while, Xiaoqiang came up with the answer:

bool a = NAND(x1, x2);
bool b = NAND(x2, x3);
bool y = NAND(a, b); return y;


Xiaoqiang wants to make sure that his solution is the shortest possible. Can you help him?
 

Input
The first line contains an integer T (T ¡Ü 20) denoting the number of the test cases.

For each test case, there is one line containing 8 characters encoding the truth table of the function.
 

Output
For each test case, output a single line containing the minimum number of lines Xiaoqiang has to write.
 

Sample Input
1 00010011
 

Sample Output
4
 

Hint
Due to the small input domain, you can solve all the cases on your computer and submit a program with a table of all the answers.
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-06-17 03:43:29, Gzip enabled