10307

Even · Post by **Even** » Fri Sep 06, 2002 10:22 am

there are 1 S and at most 100 A

I find all pairs distance( include S and A )

and use Prim to find MST, minimum cost

in my method...S and A are treat as the same.

but WA..

is there any tricky??

or I misunderstand something ??

please help ~~ thank you

Even · Post by **Even** » Fri Sep 06, 2002 10:28 am

stupid as me...

I find my mistake...

for there are 1 S and 100 A... there should be total 101 points

but my array size has only 100....so WA /.\

but... why WA not Rutime Error?

cyfra · Post by **cyfra** » Tue Sep 10, 2002 8:42 am

Hi!

This is not the first time when program should gave RE and it gives WA.

When I m writing a program in Pascal and I turn off Range checking then it sometimes happen that if I use array[1..100] and I want to write something to [101] place it writes it there !! But there can be other varaible and the whole program whill produce Wrong Answer...

I think that programs should be tested with Range checking but on the other hand it means that they will be working a little bit slower...

And I think that's all...

Good Luck

PS.
Did you write this program in C or in Pascal ??

ahanys · Post by **ahanys** » Tue Mar 25, 2003 2:07 pm

I have curently wrong answer and on the test data I get the correct output. May somebody give some INPUT/OUTPUT or look at the code what's wrong on it.

Thanks in advance ahanys.
[cpp]
/* @JUDGE_ID: 9072XC 10307 C++ */
#include <stdio.h>
#include <stdlib.h>

const int MAX=100;
char p[MAX+1][MAX+1];
int map[MAX+1][MAX+1];
int used[MAX+1][MAX+1];
int m[101][101];

int cena=0;

struct point {
int x;
int y;
int val;
};

int cmp(const void *a, const void *b) {
point c = *((point *)a);
point d = *((point *)b);
if (c.val > d.val) {
return 1;
} else if (c.val < d.val) {
return -1;
} else {
return 0;
}
}

point body[101];
point fronta[(MAX+7) * (MAX+7)];
int velikost;

int main() {
int n;
scanf("%i", &n);
for (int a=0; a<n; a++) {
int x,y;
scanf("%i %i\n", &x, &y);
for (int i=0; i<y; i++) {
gets(p);
}

int uzel = 0;
for (int c=0; c<y; c++) {
for (int d=0; d<x; d++) {
if (p[c][d] == 'A' || p[c][d] == 'S') {
if (p[c][d] == 'S') p[c][d]='A';
body[uzel].x = d;
body[uzel].y = c;
body[uzel].val = 0;
map[c][d] = uzel++;
} else {
map[c][d] = -1;
}
}
}

for (int r=0; r<uzel; r++) {// pro kazdy uzel
fronta[0] = body[r];
velikost = 1;
int akt = 0;
for (int e=0; e<y; e++)
for (int f=0; f<x; f++) used[e][f]=0;

while (velikost > akt) {
point prvni = fronta[akt++];
if (p[prvni.y][prvni.x] == 'A' && !used[prvni.y][prvni.x]) {
m[r][map[prvni.y][prvni.x]] = prvni.val;
}
used[prvni.y][prvni.x] = 1;
prvni.val++;
if (p[prvni.y][prvni.x+1] != '#') {
if (!used[prvni.y][prvni.x+1]) {
fronta[velikost++] = prvni;
fronta[velikost-1].x++;
}

}
if (p[prvni.y][prvni.x-1] != '#') {
if (!used[prvni.y][prvni.x-1]) {
fronta[velikost++] = prvni;
fronta[velikost-1].x--;
}
}
if (p[prvni.y-1][prvni.x] != '#') {
if (!used[prvni.y-1][prvni.x]) {
fronta[velikost++] = prvni;
fronta[velikost-1].y--;
}
}
if (p[prvni.y+1][prvni.x] != '#') {
if (!used[prvni.y+1][prvni.x]) {
fronta[velikost++] = prvni;
fronta[velikost-1].y++;
}
}
}
}

point seznam[(MAX+7) * (MAX+7)];
int pocet=0;
for (int t=0; t<uzel; t++) {
for (int u=0; u<uzel; u++) {
if (t != u && m[t] != 0) {
point p1;
p1.x = t;
p1.y = u;
p1.val = m[t];
seznam[pocet++] = p1;
}
}
}
qsort(seznam, pocet, sizeof(point), cmp);

int kused[MAX+1];

int zbyva=uzel-1;
int komponenta=1;
for (int g=0; g<uzel; g++) kused[g]=0;

for (int q=0; q<pocet; q++) {
int pridej = 0;
if (zbyva == 0) break;
if (!kused[seznam[q].x]) {
pridej = 1;
}
if (!kused[seznam[q].y]) {
pridej += 2;
}
if (kused[seznam[q].y] != 0 && kused[seznam[q].x] != 0) {
if (kused[seznam[q].y] != kused[seznam[q].x]) {
pridej = 4;
}
}

if (pridej == 1) {
kused[seznam[q].x] = kused[seznam[q].y];
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 2) {
kused[seznam[q].y] = kused[seznam[q].x];
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 3) {
kused[seznam[q].x] = komponenta;
kused[seznam[q].y] = komponenta++;
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 4) {
if (kused[seznam[q].y] > kused[seznam[q].x]) {
int mensi = kused[seznam[q].x];
int vetsi = kused[seznam[q].y];
for (int za=0; za<uzel; za++) {
if (kused[za]==vetsi) {
kused[za] = mensi;
}
}
} else {
int vetsi = kused[seznam[q].x];
int mensi = kused[seznam[q].y];
for (int z=0; z<uzel; z++) {
if (kused[z]==vetsi) {
kused[z] = mensi;
}
}
}
cena+=seznam[q].val;
zbyva--;
}
}

printf("%i\n", cena);
}

return 0;
}

[/cpp][/cpp]

hank · Post by **hank** » Mon Jul 21, 2003 4:05 pm

I cannot understand why the answer of the following input is "11"?

Code: Select all

#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
#####

Code: Select all

and why it said , "That is, if the original group walks five steps, then splits into two groups each walking three steps, the total distance is 11=5+3+3. " ?

please help me understand this "sample input"!
Thanks a lot!

Per · Post by **Per** » Mon Jul 21, 2003 5:42 pm

I'm not sure what they mean by the text, but I'll show why the output is 11.

Let the borgs split once in the beginning, one group going upwards, one group going downwards, so we get (where B denotes a borg group):

Code: Select all

##### 
#ABA###
#    A#
#   ###
#     #
#ABA###
#####

having walked a total of four steps (both groups take two steps). The groups then split again, each group taking one step left/right, and we get:

Code: Select all

##### 
#B B###
#    A#
#   ###
#     #
#B B###
#####

having walked a total of eight steps (each of the four groups take one step). Finally, the group in the upper right walks the three steps to the last alien, and the total is now 11 steps.

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jul 24, 2003 8:28 am

But what about this (first sample) case ? Second is easy. But hw can I get 8 in this case ? Could anyone explain me ?

Code: Select all

6 5
##### 
#A#A##
# # A#
#S  ##
#####

I always get 7!!!!!

Best regards
DM

Per · Post by **Per** » Thu Jul 24, 2003 9:07 am

The borgs can only split at aliens, not in arbitrary cells!

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jul 24, 2003 1:30 pm

Off course - I miss this

Thanks

DM

Larry · Post by **Larry** » Thu Jul 24, 2003 4:34 pm

You can also split in the beginning, of course

Dominik Michniewski · Post by **Dominik Michniewski** » Sat Jul 26, 2003 9:13 am

I try to solve this problem using MST , but I got WA. Could anyone help me and tell me some special cases ??

Best regards
DM

Faizur · Post by **Faizur** » Sat Jul 26, 2003 10:59 am

I use bfs to get the distance btw them.and then i construct kruskal mst with them.But i recieved time limit exceed. I get accepted with my kruskal implementation in other mst problems.Is there any other faster algorithm to find the shortest distance in a maze.Help me...

hank · Post by **hank** » Sat Jul 26, 2003 3:15 pm

Faizur wrote:I use bfs to get the distance btw them.and then i construct kruskal mst with them.But i recieved time limit exceed. I get accepted with my kruskal implementation in other mst problems.Is there any other faster algorithm to find the shortest distance in a maze.Help me...

I think Prim algorithm is better than kruskal in this problem.
And it it fast!
You don't have to get all the distance between them.
you just get the distance if needed.

Larry · Post by **Larry** » Mon Jul 28, 2003 4:09 pm

I use BFS to calculate the distance between all nodes, then I use Prim MST.. and my solution is ranked ~66th, so it isn't so bad...

Faizur · Post by **Faizur** » Tue Jul 29, 2003 8:59 am

Thanks for the help. But i dont know which one will be more efficient in which case. Is there any documents or resources.Pls send me some hints

OJ Board

10307 - Killing Aliens in Borg Maze

10307 - Killing Aliens in Borg Maze

Sorry

Hi!

10307 Killing Aliens in Borg Maze

faster algorithm

Re: faster algorithm