608 - Counterfeit Dollar

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

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:

608 - Counterfeit Dollar

i got W.A. with this problem. can anyone gimme some test data for this problem???

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:
i have no idea about why i get wrong answer..
i just test all possibilities,and print the anwer...
Does it may have more than one conterfeit dollar?

#include <stdio.h>
#include <string.h>
class stat
{
public:
long leftp;
long rightp;
long stable;
};
void main()
{
long i,j,k,t,tmp,tmpx,num,cnt,sum,n,a,b,p;
char left,right,sta;
stat c;
scanf("%ld",&num);
for(p=0;p<num;p++)
{
for(i=0;i<3;i++)
{
scanf("%s %s %s",&left,&right,&sta);
for(j=0;j<4;j++)
{
c.leftp[j]=left[j]-65;
}
for(j=0;j<4;j++)
{
c.rightp[j]=right[j]-65;
}
if(sta=='e')
{
c.stable=0;
}
else if(sta=='u')
{
c.stable=1;
}
else if(sta=='d')
{
c.stable=-1;
}
}
for(j=0;j<12;j++)
{
n[j]=0;
}
for(i=0;i<12;i++)
{
n=1;
t=0;
for(j=0;j<3;j++)
{
a=n[c[j].leftp]+n[c[j].leftp]+n[c[j].leftp]+n[c[j].leftp];
b=n[c[j].rightp]+n[c[j].rightp]+n[c[j].rightp]+n[c[j].rightp];
k=a-b;
if(k!=c[j].stable)
{
t=1;
}
}
if(t==0)
{
tmpx=i;
break;
}
n=-1;
t=0;
for(j=0;j<3;j++)
{
a=n[c[j].leftp]+n[c[j].leftp]+n[c[j].leftp]+n[c[j].leftp];
b=n[c[j].rightp]+n[c[j].rightp]+n[c[j].rightp]+n[c[j].rightp];
k=a-b;
if(k!=c[j].stable)
{
t=1;
}
}
if(t==0)
{
tmpx=i;
break;
}
n=0;
}
if(n[tmpx]==1)
{
printf("%c is the counterfeit coin and it is heavy.n",tmpx+65);
}
else if(n[tmpx]==-1)
{
printf("%c is the counterfeit coin and it is light.n",tmpx+65);
}
}
}

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

608 (Counterfeit Dollar) WA

I just wonder why I get WA? For each coin I consider that it is false and then check 3 weighings. If these weighings are correct (I consider that all other coins is not false) then I write these coin as answer. Am I wrong?

[pascal]Program p608;

Var T,tt : Integer;
i,j,k : Integer;
Ch : Char;
Inf : Array[1..3]of Record L,R,S : String End;
S : String;

Function CheckChar(Ch : Char) : Boolean;
Var S,i,j : Integer;
begin
CheckChar:=False;
k:=0;
for i:=1 to 3 do begin
S:=0;
for j:=1 to length(Inf.L) do if Inf.L[j]=Ch then S:=S+1;
for j:=1 to length(Inf.R) do if Inf.R[j]=Ch then S:=S-1;
if (S=0) And (Inf.S<>'even') then Exit;
if (S<>0) And (Inf.S<>'up') then Exit;
if Inf.S='up' then if S<0 then k:=1;
end;
CheckChar:=True;
end;

begin
for tt:=1 to T do begin
for k:=1 to 3 do begin
for i:=1 to length(S) do S:=UpCase(S);
While S=' ' do Delete(S,1,1);
Inf[k].L:=Copy(S,1,Pos(' ',S)-1);
Delete(S,1,Pos(' ',S));
While S=' ' do Delete(S,1,1);
Inf[k].R:=Copy(S,1,Pos(' ',S)-1);
Delete(S,1,Pos(' ',S));
While Pos(' ',S)>0 do Delete(S,Pos(' ',S),1);
if S='EVEN' then Inf[k].S:='even' else
if S='UP' then Inf[k].S:='up' else begin
S:=Inf[k].L;
Inf[k].L:=Inf[k].R;
Inf[k].R:=S;
Inf[k].S:='up';
end;
end;
for Ch:='A' to 'L' do
if CheckChar(Ch) then begin
Write(Ch,' is the counterfeit coin and it is ');
if k=0 then Writeln('heavy.') else Writeln('light.');
Break;
end;
end;
end.[/pascal]

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:
I made some test cases for you:

INPUT

ABCD EFGH even
I J even
K A even

A B even
DE FG up
KG LI down

F G up
G K even
A I even

ABCDE FGHIJ even
K A even
B D even

BEF AGI down
AEF BGI up
B C down

OUTPUT

L is the counterfeit coin and it is heavy.
G is the counterfeit coin and it is light.
F is the counterfeit coin and it is heavy.
L is the counterfeit coin and it is heavy.
B is the counterfeit coin and it is light.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can someone post some outputs? I dno't think sergio's are correct because the solutions are not uniquely determined for some of them...

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can someone post some outputs? I dno't think sergio's are correct because the solutions are not uniquely determined for some of them...

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:
Hi!

I think my solution is correct But, I can be wrong In my first input
ABCD EFGH even
I J even
K A even

All the coins appear on weighing, least L, and all is fine. So, L is the answer, ok??

In the second input
A B even
DE FG up
KG LI down

A e B are good coins, obviously So, we know the bad coin is D, E, F or G, ok??
Thus, only G appears again in third line.
But it appears on the other side, i think it

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Ya, but
For each case, the output will identify the counterfeit coin by its letter and tell whether it is heavy or light. The solution will always be uniquely determined.
And since L never appeared, you don't know if it's heavy or light..

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:
Well, I think you are right again I made another test cases, I hope that it's ok. Tell me if you find some error.

INPUT
ABC DEF up
GHI JKL even
EF DA up

AFG JKL down
A J down
A D even

ED FG even
AB CI up
A D up

IL JK even
A B even
E L down

BEF JIL down
J A even
CEF BJI even

OUTPUT
D is the counterfeit coin and it is light.
J is the counterfeit coin and it is heavy.
A is the counterfeit coin and it is heavy.
E is the counterfeit coin and it is light.
L is the counterfeit coin and it is heavy.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Well, my JAVA program covers these test cases.

But still I get Wrong Answer after the program runs for
3.951 secs.

Are sure for example that there're empty lines between
the different test cases.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
No, there're no empty lines in the tests used by Online Judge.
I've commented out the code which expects an empty
line between the different test cases and now the Online
Judge says "Accepted".

andrei_vish
New poster
Posts: 4
Joined: Mon Nov 14, 2005 4:03 pm
I don't know what's wrong ?
This is my source:

Code: Select all

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct SetWeight
{
enum { Len = 12};
bool	st[Len];
int		weight;
string	swstr;

explicit SetWeight(bool setted = false)
{
for (unsigned i = 0; i < Len; ++i)
st[i] = setted;
};

void SetStr(const string & str)
{
swstr = str;
for (unsigned i = 0; i < str.size(); ++i)
{
if (str[i] >= 'A' && str[i] <= 'L')
st[str[i]-'A'] = true;
else if (str[i] == 'e')
{
weight = 0;
break;
}
else if (str[i] == 'u')
{
weight = 1;
break;
}
else if (str[i] == 'd')
{
weight = -1;
break;
}
}
};

void Substraction(const SetWeight & sw)
{
for (unsigned i = 0; i < Len; ++i)
if (sw.st[i])
st[i] = false;
};

void Intersection(const SetWeight & sw)
{
for (unsigned i = 0; i < Len; ++i)
if (sw.st[i] && st[i])
st[i] = true;
else
st[i] = false;
};

int Size()
{
int retVal = 0;
for (unsigned i = 0; i < Len; ++i)
retVal += st[i] ? 1 : 0;
return retVal;
};

char Get()
{
for (unsigned i = 0; i < Len; ++i)
if (st[i])
return 'A' + i;
};

int GetSide(char ch)
{
bool left = true;
for (unsigned i = 0; i < swstr.size(); ++i)
{
if (swstr[i] >= 'A' && swstr[i] <= 'L')
{
if (swstr[i] == ch)
if (left)
return -1;
else
return 1;
}
else if (swstr[i] == 'e' || swstr[i] == 'u' || swstr[i] == 'd')
return 0;
else if (swstr[i] == ' ')
left = false;
}
};
};

int main(int argc, char* argv[])
{
int n;
cin >> n;

while ( n-- > 0)
{
unsigned i;
vector<SetWeight> inputSet(3);
SetWeight	all(true);
SetWeight	allInter;
bool		allInterEmpty = true;

for (i = 0; i < 3; ++i)
{
string inp1, inp2, inp3;
cin >> inp1 >> inp2 >> inp3;
inputSet[i].SetStr(inp1 + " " + inp2 + " " + inp3);
}

for (i = 0; i < inputSet.size(); ++i)
if (inputSet[i].weight == 0)
all.Substraction(inputSet[i]);
else
if (allInterEmpty)
{
allInter = 	inputSet[i];
allInterEmpty = false;
}
else
allInter.Intersection(inputSet[i]);

if (allInter.Size() > 0)
all.Intersection(allInter);

char cntr = all.Get();
cout << cntr << " is the counterfeit coin and it is " ;

for (i = 0; i < inputSet.size(); ++i)
if (inputSet[i].weight != 0)
{
int side = inputSet[i].GetSide(cntr);
if (side != 0)
{
if (side == -1)
{
if (inputSet[i].weight == 1)
cout << "heavy";
else
cout << "light";
}
else
{
if (inputSet[i].weight == 1)
cout << "light";
else
cout << "heavy";
}
break;
}
}

cout << ".\n";
}

return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Just try the input/output. (I dont have any pascal compiler, so I dont know whether the set helps you or not...)

Input:

Code: Select all

1
AC BD down
AC EF down
A F even

Output:

Code: Select all

C is the counterfeit coin and it is light.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

what's wrong???

can anybody give me some critical I/O?
I've checked my program with the input in this board and it gives the same result ...
here's the sample of my input:

Code: Select all

input:
7
ABC DEF even
GHI JEF even
K EF up
ED FG even
AB CI down
A D down
ED FG even
AB CI down
D A up
ED FG even
CI AB up
A D down
ED FG even
AB CI up
D A down
ED FG even
CI AB down
A D up
AC BD down
AC EF down
A F even

Code: Select all

output:
K is the counterfeit coin and it is heavy.
A is the counterfeit coin and it is light.
A is the counterfeit coin and it is light.
A is the counterfeit coin and it is light.
A is the counterfeit coin and it is heavy.
A is the counterfeit coin and it is heavy.
C is the counterfeit coin and it is light.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your outputs are correct. Check the samples...

Input:

Code: Select all

3
IJK ABC even
C L even
L F up
IJK ABC even
C L even
L F down
ABCDE FGHIJ even