UVA340 猜数字游戏的提示 Master-Mind Hints
UVA340 猜数字游戏的提示 Master-Mind Hints
题目描述
输入格式
输出格式
输入输出样例 #1
输入 #1
4 1 3 5 5 1 1 2 3 4 3 3 5 6 5 5 1 6 1 3 5 1 3 5 5 0 0 0 0 10 1 2 2 2 4 5 6 6 6 9 1 2 3 4 5 6 7 8 9 1 1 1 2 2 3 3 4 4 5 5 1 2 1 3 1 5 1 6 1 9 1 2 2 5 5 5 6 6 6 7 0 0 0 0 0 0 0 0 0 0 0输出 #1
Game 1: (1,1) (2,0) (1,2) (1,2) (4,0) Game 2: (2,4) (3,2) (5,0) (7,0)题目大意
MasterMind 是一个双人游戏。其中一名玩家 “设计者” 选定一串密码，另一名玩家 “破译者” 尝试破解密码。密码是一排彩色圆点。游戏开局时，双方约定好密码的长度 N 以及可用的颜色种类。破译者会多次给出猜测串，每一轮猜测结束后，设计者会给出提示，说明本次猜测和真实密码的匹配程度。
本题给定真实密码s₁…sₙ和猜测串g₁…gₙ，要求计算对应的提示信息。匹配规则定义如下：
一对下标(i,j)满足sᵢ = gⱼ就构成一次匹配。当i=j时，这是强匹配；否则为弱匹配。两组匹配(i,j)和(p,q)互相独立的条件是：i=p和j=q必须同时成立。一个匹配集合里任意两组匹配都互相独立，就称这个集合是独立匹配集。
设计者要选出一个独立匹配集 M，使得集合内总匹配数尽可能大，同时强匹配的数量也要尽可能大。最终提示由集合 M 里强匹配数量在前、弱匹配数量在后组成，这两个数值是唯一确定的。如果提示为(n,0)，说明猜测串和密码完全一致。
输入格式
输入包含多组游戏数据。每组游戏以整数 N（密码长度）开头，紧接着是由 N 个 1~9 整数组成的真实密码。之后会有多组猜测串，每组猜测串同样是 N 个 1~9 的整数。每组游戏的最后一行是 N 个 0，这一行不作为猜测串。一组游戏结束后会继续下一组游戏（如果还有数据），下一组依然以新的 N 开头。当单独输入一个 0 时，代表所有游戏输入结束。N 的最大取值为 1000。
输出格式
按顺序输出每组猜测对应的提示，每行一条。提示用括号包裹两个整数，中间用逗号隔开。每组游戏的输出开头要打印游戏编号，游戏从 1 开始顺序编号，严格参照样例格式输出。
解题思路
先算出强匹配的数量，逐个位置对照密码和猜测串，如果下标相同并且数字一致，就给强匹配计数加一，同时把这两个位置标记成已经占用，不让它们再参与后面弱匹配的计算。找弱匹配时，把两边剩下还没被占用的数字分别统计好每个数字出现了多少次，对于每一个数字，能形成弱匹配的对数就取两边数量里的小值，把所有数字的匹配数量加在一起，最终得到弱匹配总数。
完整代码
importjava.util.Scanner;publicclassMasterMindHints{publicstaticvoidmain(Stringargs[]){Scannersc=newScanner(System.in);intgame=1;while(true){intn=sc.nextInt();if(n==0){break;}int[]password=newint[n];for(inti=0;i<n;i++){password[i]=sc.nextInt();}System.out.println("Game "+game+":");game++;while(true){int[]guess=newint[n];booleanendLine=true;for(inti=0;i<n;i++){guess[i]=sc.nextInt();if(guess[i]!=0){endLine=false;}}if(endLine){break;}intstrong=0;boolean[]pas=newboolean[n];boolean[]gue=newboolean[n];for(inti=0;i<n;i++){if(password[i]==guess[i]){strong++;pas[i]=true;gue[i]=true;}}int[]pass=newint[10];int[]gues=newint[10];for(inti=0;i<n;i++){if(!pas[i]){pass[password[i]]++;}}for(inti=0;i<n;i++){if(!gue[i]){gues[guess[i]]++;}}intweak=0;for(inti=1;i<=9;i++){weak=weak+Math.min(pass[i],gues[i]);}System.out.println("("+strong+","+weak+")");}}sc.close();}}