글 읽기 - 반례 찾아주세요

johnny8337 2년 전 1

72%에서 틀리는데 무엇이 틀렸는지 모르겠습니다

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int dist[1<<16],b,e,ans,arr[101];
queue <int> q;
int cmp(int cur)
{
    int ret=0;
    for(int i=0;i<b;i++)
    {
        if((cur&(1<<i))!=(ans&(1<<i)))
            ret++;
    }
    return ret;
}
int main()
{
    scanf("%d %d",&b,&e);
    for(int j=b-1;j>=0;j--)
    {
        bool ttemp;
        scanf("%1d",&ttemp);
        ans|=(ttemp<<j);
    }
    for(int i=0;i<e;i++)
    {
        int temp=0;
        for(int j=b-1;j>=0;j--)
        {
            bool ttemp;
            scanf("%1d",&ttemp);
            temp|=(ttemp<<j);
        }
        arr[i]=temp;
        q.push(arr[i]);
    }
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        for(int i=0;i<e;i++)
        {
            if(dist[temp^arr[i]]==0)
            {
                q.push(temp^arr[i]);
                dist[temp^arr[i]]=dist[temp]+1;
            }
        }
    }
    int ret;
    int Min=100000000;
    int Min2=(1<<31)-1;
    for(int i=0;i<(1<<b);i++)
    {
        if(Min>cmp(i)&&dist[i]>0)
        {
            Min=cmp(i);
            Min2=dist[i];
            ret=i;
        }
        if(Min==cmp(i)&&dist[i]>0)
        {
            if(dist[i]<Min2)
            {
                Min=cmp(i);
                Min2=dist[i];
                ret=i;
            }
        }
    }
    printf("%d\n",dist[ret]);
    for(int j=b-1;j>=0;j--)
    {
        printf("%d",(ret>>j)&1);
    }
}

johnny8337 2년 전 0

거리 0 일때 처리가 약간 문제있었던 것 같아요.

그 부분을 바꾸니까 되네요

#include<iostream>
#include<queue>
using namespace std;
int dist[1<<16],b,e,ans,arr[101];
queue <int> q;
int cmp(int cur)
{
    int ret=0;
    for(int i=0;i<b;i++)
    {
        if((cur&(1<<i))!=(ans&(1<<i)))
            ret++;
    }
    return ret;
}
int main()
{
    scanf("%d %d",&b,&e);
    for(int j=b-1;j>=0;j--)
    {
        int ttemp;
        scanf("%1d",&ttemp);
        ans|=(ttemp<<j);
    }
    for(int i=0;i<e;i++)
    {
        int temp=0;
        for(int j=b-1;j>=0;j--)
        {
            bool ttemp;
            scanf("%1d",&ttemp);
            temp|=(ttemp<<j);
        }
        arr[i]=temp;
    }
    for(int i=0;i<e;i++)
    {
        for(int j=0;j<e;j++)
        {
            dist[arr[i]^arr[j]]=1;
            q.push(arr[i]^arr[j]);
        }
    }
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        for(int i=0;i<e;i++)
        {
            if(dist[temp^arr[i]]==0)
            {
                q.push(temp^arr[i]);
                dist[temp^arr[i]]=dist[temp]+1;
            }
        }
    }
    int ret;
    int Min=100000000;
    int Min2=(1<<31)-1;
    for(int i=0;i<(1<<b);i++)
    {
        if(Min>cmp(i)&&dist[i]>0)
        {
            Min=cmp(i);
            Min2=dist[i];
            ret=i;
        }
        if(Min==cmp(i)&&dist[i]>0)
        {
            if(dist[i]<Min2)
            {
                Min=cmp(i);
                Min2=dist[i];
                ret=i;
            }
        }
    }
    printf("%d\n",dist[ret]);
    for(int j=b-1;j>=0;j--)
    {
        printf("%d",(ret>>j)&1);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 찾아주세요

johnny8337 2년 전 1

johnny8337 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말