608 - Counterfeit Dollar

[Subeen]

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

[LTH]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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.

[algoJo]

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]

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.