CF63C 题解

ikunTLE · 2024-11-30 09:20:27 · 题解

题目传送门

思路

题目中提到一个 4 位数，不难想到枚举 0 到 9999 所有的数，并统计其中成立的个数。由于题目中的 n 很小，我们可以挨个判断。

若成立个数为 0，则输出 Incorrect data；若成立个数为 1，则输出答案；若成立个数 \ge2，则输出 Need more data。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=15,E=1e4,M=1e4+10,X=10;
int n,d[X],pos[N],num[N];
bool vis[N],flag[M];
string s[N];
int calc_num(){
    int res=0;
    for(int i=1;i<=4;++i)
        res=res*10+d[i];
    return res;
}
void solve(){
    int temp=calc_num();
    flag[temp]=true;
    for(int i=1;i<=n;++i){
        int cnt1=0,cnt2=0;
        for(int j=1;j<=4;++j)
            if(d[j]==s[i][j-1]-'0')
                ++cnt1;
            else if(vis[s[i][j-1]-'0'])
                ++cnt2;
        if(cnt1!=pos[i]||cnt2!=num[i])
            flag[temp]=false;
    }
    return;
}
void dfs(int x){
    if(x==5){
        solve();
        return;
    }
    for(int i=0;i<=9;++i)
        if(!vis[i]){
            vis[i]=true;
            d[x]=i;
            dfs(x+1);
            vis[i]=false;
        }
    return;
}
int main(){
    n=read();
    for(int i=1;i<=n;++i){
        cin>>s[i];
        pos[i]=read(),num[i]=read();
    }
    dfs(1);
    int cnt=0,ans=-1;
    for(int i=1;i<=E;++i)
        if(flag[i])
            ++cnt,ans=i;
    if(!cnt)
        printf("Incorrect data\n");
    else if(cnt>=2)
        printf("Need more data\n");
    else printf("%04d\n",ans);
    return 0;
}