## 173 - Network Wars

**Moderator:** Board moderators

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

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

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.

### 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.

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

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

Code: Select all

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

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
```

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

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

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");
}
}
```

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
```

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.

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

Changed it to:
Still WA...hmmm

Code: Select all

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