题目描述

Alice\texttt{Alice}Alice和Bob\texttt{Bob}Bob使用一个密钥（即一串密码）进行私密通信。该密钥是从字符集SSS（大小为nnn）中选出的mmm个互不相同的字符所组成的有序序列。
例如，若S={1,2,3,4,5,6,7,8,9}S=\{1,2,3,4,5,6,7,8,9\}S={1,2,3,4,5,6,7,8,9}且m=4m=4m=4，则一个可能的密钥是(3,8,1,5)(3,8,1,5)(3,8,1,5)。

除Alice\texttt{Alice}Alice和Bob\texttt{Bob}Bob外无人知晓密钥。然而间谍Steve\texttt{Steve}Steve知道集合SSS和密钥长度mmm，他试图通过提交不同的猜测来推出密钥。每次猜测都会收到一个形如(c,w)(c,w)(c,w)的答复，其中：

• ccc表示猜测中位置正确的数字个数；
• www表示猜测中存在于密钥中但位置错误的数字个数（即错位数）。

例如，对于上述密钥，有以下猜测与答复：

(1,1,1,1)→(1,0),(2,2,2,2)→(0,0),(9,8,3,1)→(1,2) (1,1,1,1)\rightarrow (1,0),\quad (2,2,2,2)\rightarrow (0,0),\quad (9,8,3,1)\rightarrow (1,2)(1,1,1,1)→(1,0),(2,2,2,2)→(0,0),(9,8,3,1)→(1,2)

注意：正确的猜测会得到答复(m,0)(m,0)(m,0)。

给定SSS、mmm以及若干条（任意长度）猜测‑答复记录，程序需要执行以下操作之一：

1. 宣称给定信息不足以唯一确定正确密钥；或
2. 给出正确的密钥，即那个能得到答复(m,0)(m,0)(m,0)的密钥。

输入格式

输入文件包含多个测试用例，每个测试用例描述如下（n≤10, m≤nn\le 10,\; m\le nn≤10,m≤n）：

• 第一行给出集合SSS，元素之间以空格分隔（不含括号）。
• 第二行给出整数mmm。
• 接下来若干行，每行为一条猜测‑答复，格式为
  ⟨g1,…,gm⟩→⟨c,w⟩\langle g_1,\ldots,g_m\rangle \rightarrow \langle c,w\rangle⟨g1​,…,gm​⟩→⟨c,w⟩，其中gi∈Sg_i\in Sgi​∈S。
• 每个测试用例以单独一行字符%结束。

输出格式

对于每个测试用例，输出一行：

• 若存在唯一满足所有记录的密钥，则按格式⟨s1,…,sm⟩\langle s_1,\ldots,s_m\rangle⟨s1​,…,sm​⟩输出该密钥；
• 否则输出大写字母N。

样例

输入

123456789 3 (1,1,1)->(0,0) (2,2,2)->(0,0) (3,3,3)->(0,0) (4,4,4)->(1,0) (5,5,5)->(0,0) (6,6,6)->(0,0) (7,7,7)->(1,0) (8,8,8)->(1,0) (4,7,8)->(1,2) (4,8,7)->(0,3) (8,7,4)->(0,3) (7,8,4)->(1,2) (8,4,7)->(1,2) % 123456789 3 (1,1,1)->(0,0) (2,2,2)->(0,0) (3,3,3)->(0,0) (4,4,4)->(1,0) (5,5,5)->(0,0) (6,6,6)->(0,0) (7,7,7)->(1,0) (8,8,8)->(1,0) (9,9,9)->(0,0) %

输出

(7,4,8) N

题目分析

本题是经典的Mastermind\texttt{Mastermind}Mastermind（猜数字）变种。密钥中的字符必须互不相同，且所有字符都属于已知集合SSS。给定若干次猜测以及对应的(c,w)(c,w)(c,w)反馈，我们需要判断能否唯一确定密钥。

最直接的思路是枚举所有可能的密钥，并逐一检查是否与所有已知反馈一致。密钥总数等于从nnn个元素中选取mmm个不同元素的排列数：

P(n,m)=n!(n−m)! P(n,m)=\frac{n!}{(n-m)!}P(n,m)=(n−m)!n!​

由于题目限制n≤10n\le 10n≤10，最大情况n=10,m=10n=10,m=10n=10,m=10时P(10,10)=10!=3 628 800P(10,10)=10! = 3\,628\,800P(10,10)=10!=3628800，在可接受范围内。即使存在多条猜测记录（每条记录长度mmm），验证一个密钥的代价为O(m⋅g)O(m\cdot g)O(m⋅g)，其中ggg为猜测条数。最坏情况下总运算量约为3.6×106×10×g3.6\times 10^6 \times 10 \times g3.6×106×10×g，若ggg也较大可能略高，但实际输入规模下完全可行。

因此，采用暴力枚举所有排列并逐条验证的方法，简单可靠且无需复杂数据结构。

解题思路

1. 枚举所有合法密钥

集合SSS中字符互不相同，密钥要求mmm个位置上的字符也互不相同，因此合法密钥就是SSS中取mmm个元素的全排列。

使用深度优先搜索（DFS\texttt{DFS}DFS）生成所有排列，同时记录当前已用字符，避免重复。

2. 验证候选密钥

对于每个生成的排列key\textit{key}key，依次与每一条猜测记录比较，计算该猜测对应的(c,w)(c,w)(c,w)，并与记录值比对。

计算规则如下：

• 正确位置数ccc：逐位比较key[i]\textit{key}[i]key[i]与猜测guess[i]\textit{guess}[i]guess[i]，相同则ccc加111。
• 错位数www：首先统计key\textit{key}key和猜测中每个字符出现的次数，取逐字符次数最小值求和，得到两个序列中共同字符的总数total\textit{total}total。由于共同字符中包含了位置正确的那些，因此错位数w=total−cw = \textit{total} - cw=total−c。

若所有记录均匹配，则该key\textit{key}key是一个可行解。

3. 判断唯一性

枚举过程中维护一个解列表。若发现第二个可行解，即可提前终止枚举（因为此时不可能唯一确定），输出N。

枚举结束后，若解列表为空，说明输入数据自相矛盾（实际不会出现，因为真实密钥一定满足所有记录），也输出N；若恰好一个解，则输出该解。

4. 输入解析

每一条猜测‑答复的格式为(g1,g2,...,gm)->(c,w)，其中可能包含多余空格。处理时先去除所有空白字符，再按箭头->分割左右部分，最后解析括号内的逗号分隔数值。

复杂度分析

• 枚举排列数：O(P(n,m))O(P(n,m))O(P(n,m))。
• 每个排列验证：O(g⋅m)O(g \cdot m)O(g⋅m)，其中ggg为猜测条数。
• 总时间复杂度：O(P(n,m)⋅g⋅m)O(P(n,m) \cdot g \cdot m)O(P(n,m)⋅g⋅m)。由于n≤10n\le 10n≤10，该上界在实际数据中足够小。
• 空间复杂度：O(g⋅m)O(g \cdot m)O(g⋅m)用于存储猜测记录，以及递归栈深度O(m)O(m)O(m)。

代码实现

// Codebreakers// UVa ID: 777// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 2.150s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 存储单条猜测及其答复structGuess{vector<char>g;// 猜测序列intc,w;// 正确位置数、错位数};// 解析一行猜测‑答复，填充 Guess 结构voidparseLine(conststring&line,intm,Guess&guess){string s;for(charch:line)if(!isspace(ch))s.push_back(ch);// 移除所有空白字符size_t arrow=s.find("->");string left=s.substr(0,arrow);string right=s.substr(arrow+2);// 去掉左右括号left=left.substr(1,left.size()-2);right=right.substr(1,right.size()-2);// 解析猜测序列（逗号分隔）stringstreamss1(left);string token;while(getline(ss1,token,',')){if(!token.empty())guess.g.push_back(token[0]);}// 解析 c 和 wstringstreamss2(right);vector<int>nums;while(getline(ss2,token,',')){nums.push_back(stoi(token));}guess.c=nums[0];guess.w=nums[1];}// 检查候选密钥是否满足所有猜测boolcheckKey(constvector<char>&key,constvector<Guess>&guesses){intm=key.size();for(constauto&guess:guesses){intc=0,w=0;// 计算正确位置数for(inti=0;i<m;++i)if(key[i]==guess.g[i])++c;// 统计密钥和猜测中各字符出现次数intcntKey[256]={0},cntGuess[256]={0};for(charch:key)cntKey[(unsignedchar)ch]++;for(charch:guess.g)cntGuess[(unsignedchar)ch]++;// 共同字符总数inttotal=0;for(inti=0;i<256;++i)total+=min(cntKey[i],cntGuess[i]);w=total-c;// 错位数 = 共同总数 - 正确位置数if(c!=guess.c||w!=guess.w)returnfalse;}returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;while(getline(cin,line)){// 跳过空行if(line.empty())continue;// 读取字符集 Svector<char>S;for(charch:line)if(!isspace(ch))S.push_back(ch);// 读取 mgetline(cin,line);while(line.empty())getline(cin,line);intm=stoi(line);// 读取所有猜测记录vector<Guess>guesses;while(true){getline(cin,line);if(line.empty())continue;// 去除行首空白size_t start=line.find_first_not_of(" \t");if(start==string::npos)continue;line=line.substr(start);if(line[0]=='%')break;Guess g;parseLine(line,m,g);guesses.push_back(g);}// 枚举所有排列（回溯）vector<vector<char>>solutions;vector<bool>used(S.size(),false);vector<char>cur;function<void()>dfs=[&](){if(cur.size()==(size_t)m){if(checkKey(cur,guesses))solutions.push_back(cur);return;}for(size_t i=0;i<S.size();++i){if(!used[i]){used[i]=true;cur.push_back(S[i]);dfs();cur.pop_back();used[i]=false;// 若已找到两个可行解，无需继续枚举if(solutions.size()>1)return;}}};dfs();if(solutions.size()==1){cout<<"(";for(inti=0;i<m;++i){if(i)cout<<",";cout<<solutions[0][i];}cout<<")\n";}else{cout<<"N\n";}}return0;}

总结

本题的核心在于利用nnn很小的特点，直接枚举所有可能的排列，并逐条验证反馈。这种暴力方法实现简单，不易出错，且在当前数据规模下完全可行。

关键点：

• 密钥中字符互不相同，因此枚举时需使用排列而非组合，并利用回溯保证不重复。
• 计算(c,w)(c,w)(c,w)时，错位数www需先求出共同字符总数再减去正确位置数，不能直接统计错位字符个数（因为存在重复字符时统计方法不同）。
• 提前终止枚举（找到第二个可行解）可显著减少无用计算。

该解法的时间复杂度虽为指数级，但受限于n≤10n\le 10n≤10，运行效率尚可，可在时限内通过，是解决此类小规模约束问题的经典策略。