时间限制 1000 ms 内存限制 65536 KB
果园大咖圣哲有12个棵树,其中有且仅有一个是有病的,有病的树比真的或轻或重,给出3次天平测量重量的结果,每次告知左侧和右侧的树各有哪几个,以及天平的平衡状态,问第几棵树是生病的,并且请准确说出这棵树是轻是重。
数据保证每次天平的左右两边树数量相等。
输入有多组数据,第一行有一个整数T(T≤15)。每组的数据有三行:每一行分别为三个字符串S1,S2,S3S1表示天平左侧放置的树,S2表示天平右侧放置的树,S3表示天平平衡后右侧的状态up,down,even。S1,S2由ABCDEFGHIJKL组成,分别以此表示12棵树。
每组数据输出独占一行,输出是三种可能中的一种:
X is light.
X is heavy.
cannot judge.
2
A B up
B A down
A C even
AB CD even
EF GH even
I J even
B is light.
cannot judge.
法一:数据小,可以直接暴力枚举病树,以及是轻是重,当只有一种情况符合三次天平结果则有答案。
法二:even时,两边的都是健康的,up时,可能右边的有轻的,或者左边的有重的,down,相反。
v[i]记录第i棵树可能重或者可能轻的次数,up时,就给天平右边的v[i]--,左边的v[i]++。最后找除了健康的树以外,v[i]绝对值最大的,如果只有一个,那就是答案。健康的数的v[i]赋一个能区分开的值,比如v[i]设为9,如果第一次是even,后面最多减两次,为7,而可能不健康的数v最大为3,这样就可以区分开。
#include<iostream>
#include<cmath>
#include<cstring>
#define l v[s1[j]-'A']
#define r v[s2[j]-'A']
using namespace std;
int t,v[15];
char ch;
string s1,s2,s3,ans;
void solve(int f)
{
for(int j=0; j<s1.size(); j++)
{
l+=f;
r-=f;
}
}
void judge()
{
ch=0;
int max=0,maxi=-1,t;
for(int i=0; i<12; i++)
if(v[i]<4)
{
t=abs(v[i]);
if(t==max) maxi=-1;
else if(t>max)
{
max=t;
maxi=i;
}
}
if(maxi>=0)
{
ch=maxi+'A';
if(v[maxi]<0) ans=" is light.\n";
else ans=" is heavy.\n";
}
}
int main()
{
cin>>t;
while(t--)
{
memset(v,0,sizeof v);
for(int i=1; i<4; i++)
{
cin>>s1>>s2>>s3;
if(s3=="up") solve(1);
else if(s3=="down") solve(-1);
else for(int j=0; j<s1.size(); j++)l=r=9;
}
judge();
if(ch) cout<<ch<<ans;
else cout<<"cannot judge.\n";
}
return 0;
}