10793 - The Orc Attack

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

Moderator: Board moderators

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Thu Dec 16, 2004 8:56 pm

Unknown-error
I don't understand.
if there are any isolated node then output is -1
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Dec 16, 2004 10:11 pm

I believe they mean the same thing, since if there's an isolated node, then the rally point isn't connected to every point..

It simply means that the graph is not connected, thus, there's no rally point.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Thu Dec 16, 2004 10:40 pm

Got it.... thanks boys

The problem was while initializing the matrix, it affected the output when I put that dist = 0 con = true..... Why?

There is no way one of the first five points is a rally point, right?

Guilherme

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Fri Dec 17, 2004 6:25 am

consider the fact that the farthest point from the desired point can be the shortest distance from the first 5 five points.

example.

1 6 10
2 6 10
3 6 10
4 6 10
5 6 10

since the distance from the fr five(1,2,3,4,5) points to 6 are same that is 10, so 6 is a candidate.Again the farthest point(among the shortest) from 6 is 10.
so output 10;

finally you need to consider whether the graph matrix G[6][1...node] contains any infinity or not where 6 stands for the desired point.if yes print -1 else print the output.
cuii e

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sun Mar 20, 2005 8:26 am

Sorry, I have a silly problem. I got confused @@
How could check the rally point equidistant from point 1 to point 5?
Any good method?

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

10793 The Orc Attack WA

Post by boshkash1986 » Thu Jan 26, 2006 8:13 pm

Please can anyone send me some input and output samples
I tried everyting i could know can anyone help ?

i tried the case which was given in problem statment and here is the input and output

Input:

Code: Select all

1
10 34
1 7 12
1 9 20
2 7 12
2 3 7
2 8 10
3 2 7
3 8 10
4 8 10
4 6 4
5 9 31
5 9 20
5 7 12
6 4 4
6 10 35
6 9 16
7 1 12
7 5 20
7 9 35
7 2 12
7 8 2
8 4 10
8 2 10
8 3 10
8 7 2
8 9 10
9 8 10
9 10 40
9 6 16
9 5 20
9 5 31
9 1 20
9 7 35
10 9 40
10 6 35

Output

Code: Select all

Map 1: 40

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

Post by boshkash1986 » Sat Jan 28, 2006 10:30 pm

Please can anyone help me please

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Jan 28, 2006 10:36 pm

Your output for this case is ok.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

Post by boshkash1986 » Mon Jan 30, 2006 12:04 pm

i know and that what confuses i tried alot of different cases but still i get WA


Please can you providde me with some test cases ?
Thanks

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Jan 30, 2006 12:15 pm

I don't have input generator for this one, but if you create some cases on your own, I can give you answers.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Fri Oct 19, 2007 9:45 pm

This is misleading:
You should remember that a unit does not need to cover any distance if it remains static.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

Re: 10793 - The Orc Attack

Post by empo » Wed Dec 10, 2008 4:58 pm

Getting Wrong Answer
Input for the case

Code: Select all

5
7 11
1 7 2
2 7 2
3 7 2
5 7 2
6 7 1
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1
7 6 1


6 1
1 2 3
7 5
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1


10 17
1 9 20
1 7 12
2 3 7
2 8 10
2 7 12
3 8 10
4 8 10
4 6 4
5 7 12
5 9 20
5 9 31
6 9 16
6 10 35
7 8 2
7 9 35
8 9 10
9 10 40

6 5
1 6 10
2 6 10
3 6 10
4 6 10
5 6 10 
I am getting output::

Code: Select all

Map 1: 1
Map 2: -1
Map 3: -1
Map 4: 40
Map 5: 10
"Accepted" is my passion but RTE is my weakness.....

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10793 - The Orc Attack

Post by Jan » Fri May 08, 2009 5:15 am

Your cases are correct.
Ami ekhono shopno dekhi...
HomePage

ferd@u$
New poster
Posts: 4
Joined: Fri Jul 16, 2010 2:02 pm
Location: CUET
Contact:

WA: 10793 - The Orc Attack........Plz someone help me

Post by ferd@u$ » Mon Aug 16, 2010 4:06 pm

#include<stdio.h>

long A[1100][1100],B[1100][1100],check[1100];
long node;
void init(void)
{
long i,j;

for(i=0;i<node;i++)
{
check=0;
for(j=0;j<node;j++)
{
if(i==j)
{
A[j]=0;
B[j]=0;
}
else
{
A[j]=10000000;
B[j]=10000000;
}
}
}
return;
}

void warshall(void)
{
long k,i,j;

for (k=0 ;k<node ;k++)
{
for (i=0 ;i<node ;i++)
{
for (j=0 ;j<node ;j++)
{
if(A[j]<A[k]+A[k][j])
A[j]=A[j];
else
A[j]=A[i][k]+A[k][j];
}
}
}
/* for(i=0;i<node;i++)
{
for(j=0;j<node;j++)
printf("%ld ",A[i][j]);
printf("\n");
}*/
return;
}

int main()
{
long cost,flag,Flag,N,u,v,x,i,j,k,min,s,ii,testCase,dataSet,p,max,start,minCost,count,hand;

scanf("%ld",&testCase);
for(dataSet=1;dataSet<=testCase;dataSet++)
{
scanf("%ld %ld",&node,&N);

init();

count=0;
for(i=0;i<N;i++)
{
scanf("%ld %ld %ld",&u,&v,&cost);
u--;
v--;
if(cost<A[v])
{
A[v]=cost;
A[v]=cost;

if(u<node)
{
if(check==0)
{
check=1;
count++;
}
}
if(v<node)
{
if(check[v]==0)
{
check[v]=1;
count++;
}
}
}
}

if(count==node)
{
warshall();

Flag=start=0;
for(i=0;i<node;i++)
{
count=0;
p=-1000000;
if(A[i][0]<10000000)
{
p=A[i][0];
count++;
}
for(j=1;j<5;j++)
{
if(A[i][j]==p)
count++;
}
if(count==5)
{
if(start==0)
{
if(i!=node-1)
{
if(A[i][node-1]<10000000)
min=A[i][node-1];
else
{
if(A[i][0]<min)
min=A[i][0];
}
}
else
{
if(A[i][0]<min)
min=A[i][0];
}

start=1;
}
else
{
if(i!=node-1)
{
if(A[i][node-1]<min)
min=A[i][node-1];
else
{
if(A[i][0]<min)
min=A[i][0];
}
}
else
{
if(A[i][0]<min)
min=A[i][0];
}
}
Flag=1;
}
}
if(Flag==1)
printf("Map %ld: %ld\n",dataSet,min);
else
printf("Map %ld: -1\n",dataSet);
}
else
printf("Map %ld: -1\n",dataSet);
}
return 0;
}

ferd@u$
New poster
Posts: 4
Joined: Fri Jul 16, 2010 2:02 pm
Location: CUET
Contact:

WA: 10793 - The Orc Attack............Cant find the reason o

Post by ferd@u$ » Mon Aug 16, 2010 4:17 pm

If there is only one rally point in the given map and also itself a farthest point then what will be the correct result.....
suppose for
1
6 5
6 1 1
6 2 1
6 3 1
6 4 1
6 5 1

what will be the output ???and plz give me some sample input output.........

Post Reply

Return to “Volume 107 (10700-10799)”