173 - Network Wars

wyvmak · Post by **wyvmak** » Sat Feb 09, 2002 5:29 am

i keep getting WA. beside asking for tricky input, i suspect the output.

i think all possible outputs are:
P trapped Both annihilated.
P trapped L destroyed
P trapped L trapped
P trapped
L trapped
L destroyed
Both annihilated

have i missed something?

ntrhieu · Post by **ntrhieu** » Fri Apr 12, 2002 10:09 am

I am not answering your question since I also have WA for this prob.
However, i think we can't have:

P trapped Both annihilated.

for P trapped L destroyed , I am not sure whether it is correct. As P is trapped, both will halt instantly, so how can L go to the next node and be destroyed ?
If you already got an accepted submission, please let me know the trick of this prob.

Thanks

wyvmak · Post by **wyvmak** » Fri Apr 12, 2002 5:49 pm

I got AC finally, after a long struggle.

the main trick i dealt with is: they may already in the same node in the input, so they'll be 'annihilated' , but also they may get Trapped. In this case, i guess "P trapped Both annihilated" is possible.

"P trapped L destroyed" is possible too. like after some moves, P gets to dead end, while L is moving into a place where P moved in.

ntrhieu · Post by **ntrhieu** » Fri Apr 12, 2002 11:12 pm

Thanks, you pointed out for me what I misunderstood on this problem. Since it is not clear when it is saying that both halt when one can't move.
In fact, if one can't move, and the other can, the latter one can still go one more step before it halts. As you mentioned,
P trapped Both annihilated
P trapped L destroyed
is possible

The problem should have given at least one example to clarify this situtation so people don't waste their time debugging their code.

C8H10N4O2 · Post by **C8H10N4O2** » Sat Apr 13, 2002 11:22 pm

::OLD CODE DELETED TO SAVE SPACE::

ntrhieu · Post by **ntrhieu** » Sun Apr 14, 2002 2:47 am

It seems to me that you probably didn't read the input properly.
The input can be somehow like this:
A:B.AB with no space,
or A:B.A B with no space between . and A

Try to correct it and see if you get it right.

wyvmak · Post by **wyvmak** » Sun Apr 14, 2002 4:56 am

you know, viewing code to find bug is difficult.
but, after a problem got AC, i would delete the test input

but i would suspect:

1.

void lmove(int &X)
{
...
else
{
for(j=0;j<26;j++)
{
W[j][X]=0;
}
X=(X+26-i)%26;
}
}

i didn't change W, though i may not understand why you need it.

2.

i think you've to be careful about
either "L destroyed" or "Both annihilated" will be output
but seems you would output both.
just there is such a possibility

3.
if the above still not help, try:

while(1)
{
if(P!=-1&&L!=-1&&P==L)
{
printf("Both annihilated in node %c",P+'A');
break;
}
you cannot handle Trapped statements.

consider this input:
A:B. C C

C8H10N4O2 · Post by **C8H10N4O2** » Sun Apr 14, 2002 3:36 pm

I got rid of the disconnecting W. The following has been deleted.

Code: Select all

for(j=0;j<26;j++) 
{ 
W[j][X]=0; 
}

I think the IF statements for "destroyed" and "annihilated" are mutually exclusive, both can never be displayed. Also, it works for when they are trapped.

Code: Select all

A:A. A A
Both annihilated in node A
A:B. A B
Paskill trapped in node A Both annihilated in node A
A:B. B A
Paskill trapped in node B Both annihilated in node B
A:B. C C
Both annihilated in node C
A:B. C D
Paskill trapped in node C Lisper trapped in node D

wyvmak · Post by **wyvmak** » Sun Apr 14, 2002 5:10 pm

so were you accepted?

but my program output for the input:

A:B. C C

should be

Paskill trapped in node C Lisper trapped in node C Both annihilated in node C

C8H10N4O2 · Post by **C8H10N4O2** » Sun Apr 14, 2002 5:52 pm

No, I see your point now. Let me go give it another try. I thought the both annihilated message overwrote the others.

C8H10N4O2 · Post by **C8H10N4O2** » Sun Apr 14, 2002 6:23 pm

::OLD CODE ERASED::

ntrhieu · Post by **ntrhieu** » Sun Apr 14, 2002 7:23 pm

Here is the output for your input of my AC program:

Paskill trapped in node D Lisper trapped in node F
Both annihilated in node E
Lisper trapped in node E
Both annihilated in node A
Paskill trapped in node A Both annihilated in node
Paskill trapped in node B Both annihilated in node
Both annihilated in node C
Paskill trapped in node C Lisper trapped in node D

I don't think L trapped and both annihilated is possible, refer the the 2nd sample input in the problem:
E:AB. A B, they both end up in the same place, and all trapped at node E. But still, the output is both annihilated.

OK, to make sure you do it correctly, try this input:
A:B;C:BDE;F:EG;G:H. A H
A:B;C:BDE;F:EG;G:H. A G
A:B;C:BE;F:EG;G:H. A G
A:B;C:BDE;F:EG;G:H. H C
A:B;C:BDE;F:EG;G:H. B H
A:B;C:BDE;F:EG;G:H. B E
A:B;C:BDE;F:EG;G:H. C B
A:BD;C:BD;F:E;G:DEH;H:EG. A H
E:AB. A B
B:ACD.B D
A:B;B:C;D:E. A D
#

The output should be:

Paskill trapped in node D Lisper destroyed in node C
Lisper destroyed in node C
Paskill trapped in node C Both annihilated in node C
Lisper trapped in node A
Paskill trapped in node D
Both annihilated in node C
Paskill trapped in node D Lisper trapped in node A
Paskill trapped in node D Lisper trapped in node F
Both annihilated in node E
Lisper destroyed in node B
Lisper trapped in node E

C8H10N4O2 · Post by **C8H10N4O2** » Sun Apr 14, 2002 7:46 pm

This is starting to really bug me now. I just fixed my code so that it works for all the cases on this thread and still WA:(

Code: Select all

#include <cstdio>
#include <vector>
#include <cstring>
#include <cctype>

using namespace std;

vector<vector<int> > W;
vector<int> PV,LV;
int P,L;

void pmove()
{
	int i,j,k,X;
	X=P;
	PV[P]=1;
	for(i=1;i<26;i++)
	{
		if(W[X][(X+i)%26]&&!PV[(X+i)%26]&&!LV[(X+i)%26])
		{
			break;
		}
	}
	if(i==26)
		X=-1;
	else
	{
		X=(X+i)%26;
	}
	P=X;
}

void lmove()
{
	int i,j,k,X;
	X=L;
	LV[L]=1;
	for(i=1;i<26;i++)
	{
		if(W[X][(X+26-i)%26]&&!LV[(X+26-i)%26])
		{
			break;
		}
	}
	if(i==26)
		X=-1;
	else
	{
		X=(X+26-i)%26;
	}
	L=X;
}

bool cpmove()
{
	int i,X;
	X=P;
	for(i=1;i<26;i++)
	{
		if(W[X][(X+i)%26]&&!PV[(X+i)%26]&&!LV[(X+i)%26])
		{
			return true;
		}
	}
	return false;
}

bool clmove()
{
	int i,X;
	X=L;
	for(i=1;i<26;i++)
	{
		if(W[X][(X+26-i)%26]&&!LV[(X+26-i)%26])
		{
			return true;
		}
	}
	return false;
}

void main()
{
	char B[500],S[500],SP,SL,*CP,CA,CB[100];
	int i,j,k,p,l,MSG;

	while(fgets(B,500,stdin)!=NULL)
	{
		if(B[0]=='#')
			break;
		
		sscanf(B,"%s %c %c",S,&SP,&SL);

		W=vector<vector<int> > (26,vector<int>(26,0));
		PV=vector<int> (26,0);
		LV=vector<int> (26,0);

		CP=strtok(B,";");
		while(CP)
		{
			sscanf(CP,"%c:%s",&CA,CB);
			for(i=0;i<strlen(CB);i++)
			{
				if(isalpha(CB[i]))
				{
					W[CA-'A'][CB[i]-'A']=1;
					W[CB[i]-'A'][CA-'A']=1;
				}
			}
			CP=strtok(NULL,";");
		}

		P=SP-'A';
		L=SL-'A';

		MSG=0;
		while(1)
		{
			PV[P]=1;
			LV[L]=1;
			//printf("[%c|%c]",P+'A',L+'A');
			if(P==-1)
			{
				if(MSG)
					printf(" ");
				P=p;
				printf("Paskill trapped in node %c",P+'A');
				MSG++;
			}
			if(L==-1)
			{
				if(MSG)
					printf(" ");
				L=l;
				printf("Lisper trapped in node %c",L+'A');
				MSG++;
			}
			if(PV[L]&&P!=L)
			{
				if(MSG)
					printf(" ");
				printf("Lisper destroyed in node %c",L+'A');
				MSG+=2;
			}
			if(P==L)
			{
				if(MSG)
					printf(" ");
				printf("Both annihilated in node %c",P+'A');
				MSG+=2;
			}
			if(MSG)
				break;
			p=P;
			l=L;
			pmove();
			lmove();
		}
		printf("\n");
	}
}

The output:

Code: Select all

A:BD;C:BD;F:E;G:DEH;H:EG. A H
E:AB. A B
B:ACD. B D
A:B;B:C;D:E. A D
A:A. A A 
A:B. A B 
A:B. B A 
A:B. C C 
A:B. C D 
A:B;C:BDE;F:EG;G:H. A H 
A:B;C:BDE;F:EG;G:H. A G 
A:B;C:BE;F:EG;G:H. A G 
A:B;C:BDE;F:EG;G:H. H C 
A:B;C:BDE;F:EG;G:H. B H 
A:B;C:BDE;F:EG;G:H. B E 
A:B;C:BDE;F:EG;G:H. C B 
A:BD;C:BD;F:E;G:DEH;H:EG. A H 
E:AB. A B 
B:ACD. B D 
A:B;B:C;D:E. A D

A:BD;C:BD;F:E;G:DEH;H:EG. A H
Paskill trapped in node D Lisper trapped in node F
E:AB. A B
Both annihilated in node E
B:ACD. B D
Lisper destroyed in node B
A:B;B:C;D:E. A D
Lisper trapped in node E
A:A. A A
Both annihilated in node A
A:B. A B
Paskill trapped in node A Both annihilated in node A
A:B. B A
Paskill trapped in node B Both annihilated in node B
A:B. C C
Both annihilated in node C
A:B. C D
Paskill trapped in node C Lisper trapped in node D
A:B;C:BDE;F:EG;G:H. A H
Paskill trapped in node D Lisper destroyed in node C
A:B;C:BDE;F:EG;G:H. A G
Lisper destroyed in node C
A:B;C:BE;F:EG;G:H. A G
Paskill trapped in node C Both annihilated in node C
A:B;C:BDE;F:EG;G:H. H C
Lisper trapped in node A
A:B;C:BDE;F:EG;G:H. B H
Paskill trapped in node D
A:B;C:BDE;F:EG;G:H. B E
Both annihilated in node C
A:B;C:BDE;F:EG;G:H. C B
Paskill trapped in node D Lisper trapped in node A
A:BD;C:BD;F:E;G:DEH;H:EG. A H
Paskill trapped in node D Lisper trapped in node F
E:AB. A B
Both annihilated in node E
B:ACD. B D
Lisper destroyed in node B
A:B;B:C;D:E. A D
Lisper trapped in node E

ntrhieu · Post by **ntrhieu** » Sun Apr 14, 2002 8:13 pm

Oops, I missent the msg to some place, it didn't show up in the forum.

The second input I gave you was
B:ACD.B D (with no space after .)
not B:ACD. B D
The problem is when you read scanf("%s %c %c, &, &, &) it wil read everything into your first string, and then D to the first %c, and the second %c is unexpected.

What I did in my program is:

char in[1000], dot[10], s1[10], s2[10];
scanf("%[^.]%1s %1s %1s", in, dot, s1, s2);
// read a string excluding the ., read the dot, read s1, s2 as positions of P and L.
p = s1[0] - 'A'; l = s2[0] - 'A';

Hope that help.

C8H10N4O2 · Post by **C8H10N4O2** » Sun Apr 14, 2002 8:16 pm

Changed it to:

Code: Select all

		sscanf(B,"%[^.]%*[.] %c %c",S,&SP,&SL);

Still WA...hmmm

OJ Board

173 - Network Wars

it's ambiguous