665 - False coin

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

xm_dune
New poster
Posts: 1
Joined: Sat Jul 19, 2003 8:33 am

665 - False coin

Post by xm_dune » Sat Jul 19, 2003 8:38 am

#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;
}

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sat May 22, 2004 8:47 pm

Multiple Input.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

665 - False coin

Post by Jan » Fri Dec 23, 2005 8:31 pm

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.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 23, 2005 8:44 pm

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...
Ami ekhono shopno dekhi...
HomePage

User avatar
Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

665

Post by Yu Fan » Wed Jan 25, 2006 8:23 am

in this input, what is the answer should be?

1

5 2
1 1 2
=
1 1 3
<

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Tue Aug 01, 2006 4:30 pm

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

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Presentation error

Post by viniciusweb » Mon Apr 23, 2007 9:05 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Apr 24, 2007 2:31 pm

My accepted code returns...

Output:

Code: Select all

3

0

0
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Post by viniciusweb » Tue Apr 24, 2007 6:45 pm

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
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

Post by lena » Thu Aug 09, 2007 10:59 am

I also get a WA...

Who can give us some input/output.

i really do not konw why the second is 0.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Fri Dec 21, 2007 5:17 am

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 :cry:
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
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Erkil1452
New poster
Posts: 2
Joined: Fri Nov 02, 2007 6:01 pm

Post by Erkil1452 » Sun Mar 02, 2008 10:11 am

Jan wrote: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
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 665 - False coin

Post by @li_kuet » Fri Jul 12, 2013 11:05 pm

Test Case for the guys getting WA :

Code: Select all

1

4 2
1 1 2
=
1 2 4
=
Answer should be 3

predicate
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

665 - False coin (Wrong Answer)

Post by predicate » Mon Oct 06, 2014 8:32 am

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 665 - False coin

Post by lighted » Mon Oct 06, 2014 12:44 pm

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 6 (600-699)”