蓝桥杯练习题库-3算法训练之VIP题.docVIP

算法训练黑白无常?

时间限制：1.0s?内存限制：256.0MB

???????查看参考代码

问题描述

某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，那么把每个答案中贴白条的人的编号按照大小排列后组成一个数〔比方第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678〕输出最小的那个数〔如果全部都是黑纸条也满足情况的话，那么输出0〕

输入格式

第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y张黑色的纸条”。

输出格式

一行。如果无解输出“NoSolution.”。否那么输出答案中数值〔具体见问题描述〕最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0

样例输入

2

10

10

样例输出

0

样例输入

5

31

04

13

40

13

样例输出

35

数据规模和约定

n=8

#includestdio.h

#includemath.h

intn;

intx[8],y[8];

intisok(inta[],intnum,intvalue)//第i个人的话是否成立num为人下标value为0白或者1黑

{

intblack=0,white=0,i;

for(i=0;in;i++)

{

if(i!=num)

{

if(a[i])black++;//黑色

elsewhite++;//白色

}

}

if(value)//黑

{

if(x[num]==whitey[num]==black)return0;

elsereturn1;

}

else//白

{

if(x[num]==whitey[num]==black)return1;

elsereturn0;

}

}

intmain()

{

inti,j,k,sign,minnum;

inta[8],b[8];

scanf(%d,n);

for(i=0;in;i++)

scanf(%d%d,x+i,y+i);

for(i=0;ipow(2,n);i++)

{

k=i;

for(j=0;jn;j++)

{

a[j]=k%2;

k/=2;

}

sign=1;

for(j=0;jn;j++)

{

if(isok(a,j,a[j])==0)

{

sign=0;

break;

}

}

if(sign)

{

k=1;

num=0;

for(j=n-1;j=0;j--)

{

if(a[j]==0)

{

num+=k*(j+1);

k*=10;

}

}

if(nummin)min=num;

}

}

if(min=printf(NoSolution.);

else

{

for(i=0;in;i++)

b[i]=1;

for(i=0;in;i++)

{

if(isok(b,i,b[i])==0)

{

sign=0;

break;

}

}

if(sign==0)printf(%d,min);

elseprintf(0);

}

return0;

}

#includestdio.h

#includestring.h

#includemath.h

intmt[9][2],n;

intmax[9]={9};

intxl[9]={9};

boolifc();

intmain()

{

inti,j,m,fi,k,flag;

scanf(%d,n);

for(i=1;i=n;i++)scanf(%d%d,mt[i][0],mt[i][1]);

m=pow(2,n);

for(i=0;im;i++)

{

for(fi=i,j=1,xl[0]=0;j=n;j++)

{

xl[j]=fi1;

fi=1;

if(xl[j])xl[0]++;//真话数量

}

if(xl[0]max[0])continue