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

#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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Multiple Input.

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

### 665 - False coin

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

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

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

### 665

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
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

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
Contact:
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
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
I also get a WA...

Who can give us some input/output.

i really do not konw why the second is 0.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 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
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;
}
``````
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Erkil1452
New poster
Posts: 2
Joined: Fri Nov 02, 2007 6:01 pm
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

### Re: 665 - False coin

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

### 665 - False coin (Wrong Answer)

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

### Re: 665 - False coin

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