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
Location: Bangladesh
Contact:

608 - Counterfeit Dollar

Post by Subeen » Thu Nov 29, 2001 11:50 am

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:

Post by LTH » Sun Feb 10, 2002 10:10 am

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[4];
long rightp[4];
long stable;
};
void main()
{
long i,j,k,t,tmp,tmpx,num,cnt,sum,n[12],a,b,p;
char left[10],right[10],sta[10];
stat c[3];
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[0]=='e')
{
c.stable=0;
}
else if(sta[0]=='u')
{
c.stable=1;
}
else if(sta[0]=='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[0]]+n[c[j].leftp[1]]+n[c[j].leftp[2]]+n[c[j].leftp[3]];
b=n[c[j].rightp[0]]+n[c[j].rightp[1]]+n[c[j].rightp[2]]+n[c[j].rightp[3]];
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[0]]+n[c[j].leftp[1]]+n[c[j].leftp[2]]+n[c[j].leftp[3]];
b=n[c[j].rightp[0]]+n[c[j].rightp[1]]+n[c[j].rightp[2]]+n[c[j].rightp[3]];
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

Post by Revenger » Sat Aug 10, 2002 10:51 am

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
Readln(T);
for tt:=1 to T do begin
for k:=1 to 3 do begin
for i:=1 to length(S) do S:=UpCase(S);
Readln(S);
While S[1]=' ' do Delete(S,1,1);
Inf[k].L:=Copy(S,1,Pos(' ',S)-1);
Delete(S,1,Pos(' ',S));
While S[1]=' ' 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:

Post by sergio » Thu Aug 21, 2003 3:35 pm

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:

Post by Larry » Thu Aug 21, 2003 8:59 pm

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:

Post by Larry » Thu Aug 21, 2003 9:00 pm

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:

Post by sergio » Fri Aug 22, 2003 5:45 am

Hi!

I think my solution is correct :D

But, I can be wrong :P

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

Post by Larry » Fri Aug 22, 2003 8:33 am

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:

Post by sergio » Fri Aug 22, 2003 3:18 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Jan 26, 2005 6:20 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Jan 26, 2005 6:22 pm

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

Post by andrei_vish » Mon Nov 14, 2005 4:18 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 23, 2005 10:47 pm

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

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

what's wrong???

Post by algoJo » Sun Dec 17, 2006 9:12 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Dec 17, 2006 11:34 am

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
EIL ADJ down
K J even
Output:

Code: Select all

F 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 light.
Hope these help.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 6 (600-699)”