665 - False coin

[xm_dune]

#include<iostream.h>
#include<math.h>

struct{
int present;
int weight;
int exclude;
}a[1005];

int b[1005];

void process(int num){
char op;
for(int i=0;i<num*2;i++){
cin>>b;
a[b].present=1;
}
cin>>op;
switch(op){
case '>':
for(i=0;i<num;i++)
if(!a[b].exclude)
a[b].weight+=1;
for(;i<num*2;i++)
if(!a[b].exclude)
a[b].weight-=1;
break;
case '<':
for(i=0;i<num;i++)
if(!a[b].exclude)
a[b].weight-=1;
for(;i<num*2;i++)
if(!a[b].exclude)
a[b].weight+=1;
break;
case '=':
for(i=0;i<num*2;i++)
a[b[i]].exclude=1;
}
}

void judge(int n){
int time=0,max=0,t;
for(int i=1;i<n+1;i++)
if(a[i].present&&!a[i].exclude){
if(abs(a[i].weight)>max){
max=abs(a[i].weight);
t=i;
time=0;
}
else if(abs(a[i].weight)==max)
time++;
}
if(max!=0&&!time)
cout<<t;
else
cout<<0;
}

int main(){
int n,k,num;
cin>>n>>k;
for(int j=1;j<=n;j++)
a[j].present=a[j].exclude=a[j].weight=0;
for(int i=0;i<k;i++){
cin>>num;
process(num);
}
judge(n);
return 0;
}

[UFP2161]

Multiple Input.

[Jan]

Anyone can tell me whether the following input set is correct or not.

Input:

Code: Select all

1

5 3
1 1 3
<
1 1 4
=
1 3 4
=

Thanks in advance.

[Jan]

However, I got Accepted. And I m still not sure that the input set is right or wrong. But my code returns 0 for the input. Thanks...

[Yu Fan]

in this input, what is the answer should be?

1

5 2
1 1 2
=
1 1 3
<

[daveon]

Your output is correct. For a set of weights to be correct, it has to satisfy all measurements.

[viniciusweb]

I keep getting Presentation Error and I have no idea why. For the input:

Code: Select all

3

5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=

5 2
1 1 2
=
1 1 3
<

5 3
1 1 3
<
1 1 4
=
1 3 4
=

My output is:

Code: Select all

3

3

0

Can someone confirm that it's right? Thanks.

[Jan]

My accepted code returns...

Output:

Code: Select all

3

0

0

Hope it helps.

[viniciusweb]

thanks, Jan

i don't get why the second is 0

if 1 = 2, then both are not false
if 1 < 3 and 1 is not false, than 3 is false

and it's kinda weird that i'm getting presentation error if the output is in the same format as yours

[lena]

I also get a WA...

Who can give us some input/output.

i really do not konw why the second is 0.

[Kallol]

I am confused here .. I used some straight forward method for getting the solution ..but it turned out to be a WA in judge's verdict
can anyone provide me with some tricky I/O where my code fails ??
here is my code:

Code: Select all

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

#define SIZE 200

int N,M;

int main(void)
{
	int ks,i,j,p;
	int left[SIZE],right[SIZE];
	int status[SIZE];
	bool seen[SIZE];
	char s[10];

	//0 - normal
	//-1 -uninitialized
	//1 - less
	//2-more
	bool start=false;
	scanf("%d",&ks);
	while(ks--)
	{
		if(!start)
		{
			start=true;
		}
		else
		{
			printf("\n");
		}

		scanf("%d%d",&N,&M);
		for(i=1;i<=N;i++)
			status[i]=-1;

		for(i=0;i<M;i++)
		{
			memset(seen,false,sizeof(seen));

			//weightings
			scanf("%d",&p);
			for(j=0;j<p;j++)
			{
				scanf("%d",&left[j]);
				seen[left[j]]=true;
			}
			for(j=0;j<p;j++)
			{
				scanf("%d",&right[j]);
				seen[right[j]]=true;
			}
			scanf("%s",&s);

			if(strcmp(s,"=")==0)
			{
				for(j=1;j<=N;j++)if(seen[j])
					status[j]=0;//normal
			}
			else if(strcmp(s,"<")==0)
			{
				for(j=1;j<=N;j++)if(!seen[j])
					status[j]=0;//normal
				for(j=0;j<p;j++)
					if(status[left[j]]==-1)
						status[left[j]]=1;
				for(j=0;j<p;j++)
					if(status[right[j]]==-1)
						status[right[j]]=2;
			}
			else if(strcmp(s,">")==0)
			{
				for(j=1;j<=N;j++)if(!seen[j])
					status[j]=0;//normal
				for(j=0;j<p;j++)
					if(status[left[j]]==-1)
						status[left[j]]=2;
				for(j=0;j<p;j++)
					if(status[right[j]]==-1)
						status[right[j]]=1;
			}
		}

		//output
		int less=0;
		int more=0;
		for(i=1;i<N;i++)
			if(status[i]==1)
				less++;
			else if(status[i]==2)
				more++;
		if(less==1 && more==0 )
		{
			for(i=1;i<=N;i++)
				if(status[i]==1)
				{
					printf("%d\n",i);
					break;
				}
		}
		else if(less==0 && more==1)
		{
			for(i=1;i<=N;i++)
				if(status[i]==2)
				{
					printf("%d\n",i);
					break;
				}
		}
		else
		{
			printf("0\n");
		}
	}
	return 0;
}

thanks in advance

[Erkil1452]

My accepted code returns...

Output:

Code: Select all

3

0

0

Hope it helps.

My AC code returns 3,3,0 and it's kinda logical:-)

[@li_kuet]

Test Case for the guys getting WA :

Code: Select all

1

4 2
1 1 2
=
1 2 4
=

Answer should be 3

[predicate]

I am getting wrong answer for this problem. Can someone please tell me what will be the result for the following test case. On http://www.udebug.com/UVa/665 I get result as 0 but I think the result should be 1 as we can use each of 4 given weightings to eliminate coins 2 to 4 from being false, so only 1 remains.

Code: Select all

1

5 4
1 1 2
<
1 1 3
<
1 1 4
<
1 1 5
<

[lighted]

Yes, answer should be 1. Here is original sources of this problem, check your code for sample tests. http://neerc.ifmo.ru/past/1998.html