## 173 - Network Wars

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 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
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 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
Hieu Nguyen

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
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
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am

### it's ambiguous

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.
Hieu Nguyen

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
::OLD CODE DELETED TO SAVE SPACE::
Last edited by C8H10N4O2 on Sun Apr 14, 2002 6:21 pm, edited 1 time in total.

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 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.
Hieu Nguyen

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 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
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
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
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
No, I see your point now. Let me go give it another try. I thought the both annihilated message overwrote the others.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
::OLD CODE ERASED::
Last edited by C8H10N4O2 on Sun Apr 14, 2002 7:42 pm, edited 1 time in total.

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am
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
Hieu Nguyen

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
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
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am
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.
Hieu Nguyen

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA
Changed it to:

Code: Select all

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