Java实现蓝桥杯算法训练 My Bad（暴力）

忘是亡心i 2023-07-25 06:28 43阅读 0赞

## 试题 算法训练 My Bad ##

问题描述  
　　一个逻辑电路将其输入通过不同的门映射到输出，在电路中没有回路。输入和输出是一个逻辑值的有序集合，逻辑值被表示为1和0。我们所考虑的电路由与门（and gate，只有在两个输入都是1的时候，输出才为1）、或门（or gate，只要两个输入中有一个是1，输出就是1）、异或门（exclusive or（xor）gate，在两个输入中仅有一个是1，输出才是1）和非门（not gate，单值输入，输出是输入的补）组成。下图给出两个电路。  
![在这里插入图片描述][20200413145055127.png]  
　　不幸的是，在实际中，门有时会出故障。虽然故障会以多种不同的方式发生，但本题将门会出现的故障限于如下三种形式之一：  
　　1）总是与正确的输出相反；  
　　2）总是产生0；  
　　3）总是产生1；  
　　在本题给出的电路中，最多只有一个门出故障。  
　　请编写一个程序，对一个电路进行分析，对多组输入和输出进行实验，看电路运行是正确的还是不正确的。如果至少有一组输入产生了错误的输出，程序要确定唯一的出故障的门，以及这个门出故障的方式。但这也可能是无法判断的。  
输入格式  
　　输入由多组测试数据组成，每组测试用例描述了一个电路及其输入和输出。每个测试数据按序给出下述部分。  
　　1. 一行给出3个正整数：在电路中输入的数量（N ≤ 8），门的数量（G ≤ 19）和输出的数量（U ≤ 19）。  
　　2. 每行一个门，第一行描述g1门，如果有若干个门，则下一行描述g2门，以此类推。每行给出门类型（a = and，n = not，o = or，x = exclusive or）和对这个门的所有输入的标识符，对这个门的输入来自电路输入（i1, i2, …）或来自另一个门的输出（g1, g2, …）。  
　　3. 一行给出与U个输出u1, u2, ….所关联的门的编号。例如，如果有三个输出，u1来自g5，u2来自g1，u3来自g4，那么这一行为：5 1 4。  
　　4. 一行给出一个整数，表示对电路的进行实验的次数（B）。  
　　5. 最后给出B行，每行(N+U)个值（1和0），给出实验的输入值和相应的输出值。不存在有两个相同输入的情况。  
　　输入中的标识符或数字以空格分开，输入以包含3个0的一行结束。  
输出格式  
　　对于输入数据中的每个电路，输出测试数据的编号（从1开始），然后输出一个冒号和一个空格，再输出电路分析，内容为如下之一（用\#代替相应的门的编号）：

No faults detected  
　　Gate \# is failing; output inverted  
　　Gate \# is failing; output stuck at 0  
　　Gate \# is failing; output stuck at 1  
　　Unable to totally classify the failure  
　　在图1和图2 中给出的电路图是第一个和最后一个测试数据。

样例输入
    2 2 1
    o i1 i2
    n g1
    2
    2
    1 0 0
    0 0 1
    2 1 1
    a i1 i2
    1
    1
    1 0 1
    2 1 1
    a i1 i2
    1
    2
    1 0 1
    1 1 1
    1 1 1
    n i1
    1
    2
    1 1
    0 0
    3 4 4
    n g4
    a i1 i2
    o i2 i3
    x i3 i1
    2 3 4 1
    4
    0 1 0 0 1 0 1
    0 1 1 0 1 1 0
    1 1 1 0 1 0 1
    0 0 0 0 0 0 1
    0 0 0
    样例输出
    Case 1: No faults detected
    Case 2: Unable to totally classify the failure
    Case 3: Gate 1 is failing; output stuck at 1
    Case 4: Gate 1 is failing; output inverted
    Case 5: Gate 2 is failing; output stuck at 0
    数据规模和约定
    　　N<=8;G,U<=19

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;
    
    public class Main {  
    	public static void main(String[] args) throws IOException {   
    	// 转自: https://blog.csdn.net/a1439775520 
    		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    		StringTokenizer tokenizer = new StringTokenizer("");
    		int kk = 0;
    		while (true) { 
    			tokenizer = new StringTokenizer(reader.readLine());
    			int in = Integer.parseInt(tokenizer.nextToken());
    			int door = Integer.parseInt(tokenizer.nextToken());
    			int out = Integer.parseInt(tokenizer.nextToken());
    			if (in == 0 && door == 0 && out == 0)
    				break;
    			kk++;
    			System.out.printf("Case %d: ", kk);
    			Door d[] = new Door[20];
    			for (int i = 1; i <= door; i++) { 
    				tokenizer = new StringTokenizer(reader.readLine());
    				String kind = tokenizer.nextToken();
    				int incont = 2;
    				if (kind.equals("n"))
    					incont = 1;
    				int kinda = -1;
    				if (kind.equals("a"))
    					kinda = 1;
    				else if (kind.equals("o"))
    					kinda = 2;
    				else if (kind.equals("x"))
    					kinda = 3;
    				else if (kind.equals("n"))
    					kinda = 4;
    				String aa = tokenizer.nextToken();
    				int ina = Integer.parseInt(aa.substring(1));
    				// System.out.println("ina :" + ina);
    				if (aa.charAt(0) == 'i')
    					ina = -ina;
    				int inb = 0;
    				if (incont == 2) { 
    					String bb = tokenizer.nextToken();
    					inb = Integer.parseInt(bb.substring(1));
    					// System.out.println("inb :" + inb);
    					if (bb.charAt(0) == 'i')
    						inb = -inb;
    				}
    				d[i] = new Door(i, kinda, ina, inb);
    			}
    			boolean[] visit = new boolean[60];
    			for (int i = 0; i <= 3 * door; i++)
    				visit[i] = true;
    			int[] s = new int[20];
    			int[] o = new int[20];
    			int conts = 0;
    			for (int i = 1; i <= door; i++) { 
    				int inta = d[i].ina;
    				int intb = d[i].inb;
    				if (inta > 0)
    					d[inta].addout(i);
    				if (intb > 0)
    					d[intb].addout(i);
    				if (inta <= 0 && intb <= 0)
    					s[conts++] = i;
    			}
    			tokenizer = new StringTokenizer(reader.readLine());
    			for (int i = 0; i < out; i++)
    				o[i] = Integer.parseInt(tokenizer.nextToken());
    			int test = Integer.parseInt(reader.readLine());
    			int[] ins = new int[10];
    			String outs = "";
    			String res = "";
    			for (int i = 0; i < test; i++) { 
    				tokenizer = new StringTokenizer(reader.readLine());
    				for (int j = 1; j <= in; j++)
    					ins[j] = Integer.parseInt(tokenizer.nextToken());
    				outs = "";
    				for (int j = 0; j < out; j++)
    					outs += tokenizer.nextToken();
    				for (int cas = 0; cas <= 3 * door; cas++) { 
    					if (visit[cas]) { 
    						for (int j = 1; j <= door; j++)
    							d[j].cont = d[j].have = 0;
    						for (int j = 0; j < conts; j++) { 
    							int id = s[j];
    							d[id].cal(ins, d, cas);
    						}
    						res = "";
    						for (int j = 0; j < out; j++)
    							res += String.valueOf(d[o[j]].value);
    						if (outs.equals(res) == false)
    							visit[cas] = false;
    					}
    				}
    			}
    			if(visit[0] == true)
    				System.out.println("No faults detected");
    			else { 
    				int one = -1;
    				boolean mark = true;
    				for(int i = 0; i<=3*door; i++) { 
    					if(visit[i] == true)
    					{ 
    						if(one == -1)
    							one = i;
    						else
    						{ 
    							mark = false;
    							break;
    						}
    					}
    				}
    				if(mark) { 
    					int id = (one-1)/3 + 1;
    					int r = one%3;
    					if(r == 0)
    						r+=3;
    					if(r == 1)
    						System.out.printf("Gate %d is failing; output inverted\n", id);
    					else if(r == 2)
    						System.out.printf("Gate %d is failing; output stuck at 0\n", id);
    					else if(r == 3)
    						System.out.printf("Gate %d is failing; output stuck at 1\n", id);
    				}
    				else
    					System.out.println("Unable to totally classify the failure");
    			}
    		}
    	}
    }
    
    class Door { 
    	int id;
    	int incont;
    	int cont;
    	int ina, inb;
    	int kind;
    	int outcont;
    	int va, vb, value;
    	int[] out = new int[20];
    	int have;
    
    	public Door(int id_, int kind_, int ina_, int inb_) { 
    		id = id_;
    		kind = kind_;
    		ina = ina_;
    		inb = inb_;
    		incont = 0;
    		if (ina > 0)
    			incont++;
    		if (inb > 0)
    			incont++;
    		outcont = cont = have = 0;
    	}
    
    	public void addout(int num) { 
    		out[outcont++] = num;
    	}
    
    	public void cal(int[] ins, Door[] d, int cas) { 
    		if (ina < 0)
    			va = ins[-ina];
    		else if (ina > 0)
    			va = d[ina].value;
    		if (inb < 0)
    			vb = ins[-inb];
    		else if (inb > 0)
    			vb = d[inb].value;
    		if (kind == 1)
    			value = va & vb;
    		else if (kind == 2)
    			value = va | vb;
    		else if (kind == 3)
    			value = va ^ vb;
    		else if (kind == 4)
    			value = va == 0 ? 1 : 0;
    		if (cas != 0 && (cas - 1) / 3 + 1 == id) { 
    			int r = cas % 3;
    			if (r == 0)
    				r = 3;
    			if (r == 1)
    				value = value == 0 ? 1 : 0;
    			else if (r == 2)
    				value = 0;
    			else if (r == 3)
    				value = 1;
    		}
    		update(ins, d, cas);
    	}
    
    	public void update(int[] ins, Door[] d, int r) { 
    		for (int i = 0; i < outcont; i++) { 
    			d[out[i]].cont++;
    			if (d[out[i]].cont == d[out[i]].incont) { 
    				d[out[i]].cal(ins, d, r);
    			}
    		}
    	}
    }

[20200413145055127.png]: /images/20230528/c293de146fcd425ea605d58724790738.png