10099 - The Tourist Guide

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

Moderator: Board moderators

kcph007
New poster
Posts: 7
Joined: Tue Nov 26, 2002 12:13 pm

10099 , something wrong???

In the sample input, each trip can take upto 25 passengers, to it needs only 4 trips to take 99 to the destination, but the sample answer is 5, am I misunderstanding?
Thanks

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
It is ok, the guide can always take only 24 passangers with him.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
In other words, the bus can take 25, and 1 of them has to be the guide. I was pondering this myself for quite awhile..

kcph007
New poster
Posts: 7
Joined: Tue Nov 26, 2002 12:13 pm
Thanks, I'm a newbie to problems here, so never thought it would be that tricky Thanks alot

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:

10099?What's wrong??

can anyone help me with this WA...
i thot it would b easy..coz guide is one of the passengers...
so i subtracted 1 from the passenger number each time...

am i wrong???
pls someone give me suggestions...

Code: Select all

#include <stdio.h>
#include <math.h>
#define MAXSZ 150
long max(long a,long b);
long min(long a,long b);

void make_2d_array(long k,long n);

long source[MAXSZ],dest[MAXSZ],node[MAXSZ],cost[MAXSZ];
long case_num,route[MAXSZ][MAXSZ];
void main()
{

long st_point,i,j,x,a,n,k,final_point,tourist,start,end;
double trip,temp;
for(case_num=1;;case_num++)
{
scanf("%ld %ld",&n,&k);
if(n==0 && k==0)  break;

for(a=0;a<k;a++)
scanf("%ld %ld %ld",&source[a],&dest[a],&cost[a]);

scanf("%ld %ld %ld",&st_point,&final_point,&tourist);

make_2d_array(k,n);

for(x=0;x<n;x++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(route[i][x]==-1 || route[x][j]==-1)
continue;
if(route[i][j]==-1)
route[i][j]=min(route[i][x],route[x][j]);

else if(route[i][j]!=-1)
route[i][j]=max(route[i][j],min(route[i][x],route[x][j]));

}

for(a=0;a<n;a++)
if(node[a]==st_point)
{
start=a;
break;
}
for(a=0;a<n;a++)
if(node[a]==final_point)
{
end=a;
break;
}

temp=(double)tourist;
trip=temp/route[start][end];
trip=ceil(trip);

printf("Scenario #%ld\n",case_num);
printf("Minimum Number of Trips = %.0lf\n\n",trip);
}
}
void make_2d_array(long k,long n)
{
long a,b,flag,stop,row,col;
node=source;
if(source!=dest)
{
node=dest;
stop=1;
}
else if(source==dest)
stop=0;

for(a=1;a<k;a++)
{
flag=1;
for(b=0;b<=stop;b++)
if(source[a]==node[b])
{
flag=0;
break;
}
if(flag)
node[++stop]=source[a];

flag=1;
for(b=0;b<=stop;b++)
if(dest[a]==node[b])
{
flag=0;
break;
}
if(flag)
node[++stop]=dest[a];
}

for(a=0;a<n;a++)
for(b=0;b<n;b++)
{
route[a][b]=-1;
}

for(a=0;a<k;a++)
{
flag=0;
for(b=0;b<n;b++)
if(source[a]==node[b])
{
flag=1;
break;
}
if(flag)
row=b;

flag=0;
for(b=0;b<n;b++)
if(dest[a]==node[b])
{
flag=1;
break;
}
if(flag)
col=b;

route[row][col]=cost[a]-1;
route[col][row]=cost[a]-1;
}
}

long max(long a,long b)
{
if(a>=b)
return a;
else return b;
}

long min(long a,long b)
{
if(a<=b)
return a;
else return b;
}
I may be wrong, but I doubt it.
Last edited by razibcse on Sun Jan 26, 2003 8:12 pm, edited 1 time in total.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Each trip requires a guide.

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:

10099

I subtracted the guide from passenger list..but it's still not etting AC...
what's the problem?pls someone help me

Code: Select all

#include <stdio.h>
#include <math.h>
#define MAXSZ 1000
long max(long a,long b);
long min(long a,long b);

void make_2d_array(long k,long n);

long source[MAXSZ],dest[MAXSZ],node[MAXSZ],cost[MAXSZ];
long case_num,route[MAXSZ][MAXSZ],trip1;
void main()
{

long st_point,i,j,x,a,n,k,final_point,tourist,start,end,trip_num;
float trip,temp;
for(case_num=1;;case_num++)
{
scanf("%ld %ld",&n,&k);
if(n==0 && k==0)  break;

for(a=0;a<k;a++)
scanf("%ld %ld %ld",&source[a],&dest[a],&cost[a]);

scanf("%ld %ld %ld",&st_point,&final_point,&tourist);

make_2d_array(k,n);

for(x=0;x<n;x++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(route[i][x]==-1 || route[x][j]==-1)
continue;
if(route[i][j]==-1)
route[i][j]=min(route[i][x],route[x][j]);

else if(route[i][j]!=-1)
route[i][j]=max(route[i][j],min(route[i][x],route[x][j]));

}

for(a=0;a<n;a++)
if(node[a]==st_point)
{
start=a;
break;
}
for(a=0;a<n;a++)
if(node[a]==final_point)
{
end=a;
break;
}

temp=(float)tourist;

trip=temp/route[start][end];
trip1=(long)trip;

if((trip-trip1)>0.00)
trip_num=trip1+1;
else if((trip-trip1)==0.00)
trip_num=trip1;
printf("Scenario #%ld\n",case_num);
printf("Minimum Number of Trips = %ld\n",trip_num);
printf("\n");
}

}
void make_2d_array(long k,long n)
{
long a,b,flag,stop,row,col;
node=source;
if(source!=dest)
{
node=dest;
stop=1;
}
else if(source==dest)
stop=0;

for(a=1;a<k;a++)
{
flag=1;
for(b=0;b<=stop;b++)
if(source[a]==node[b])
{
flag=0;
break;
}
if(flag)
node[++stop]=source[a];

flag=1;
for(b=0;b<=stop;b++)
if(dest[a]==node[b])
{
flag=0;
break;
}
if(flag)
node[++stop]=dest[a];
}

for(a=0;a<n;a++)
for(b=0;b<n;b++)
{
route[a][b]=-1;
}

for(a=0;a<k;a++)
{
flag=0;
for(b=0;b<n;b++)
if(source[a]==node[b])
{
flag=1;
break;
}
if(flag)
row=b;

flag=0;
for(b=0;b<n;b++)
if(dest[a]==node[b])
{
flag=1;
break;
}
if(flag)
col=b;

route[row][col]=cost[a]-1;
route[col][row]=cost[a]-1;
}
}

long max(long a,long b)
{
if(a>=b)
return a;
else return b;
}

long min(long a,long b)
{
if(a<=b)
return a;
else return b;
}

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Hello, ... I saw you use some floating-point arithmetic to determine how many trips needed ...

Can you try avoiding real-numbers operation there ... my AC solution doesn't use float/double at all ... I don't see anything suspicious other than that ...

min-trips is just an integer function that can be determined quickly by observing number of total tourists (given in input) and max-tourists-per-trip that you already computed.

I'd be happy to avoid floating-point arithmetic unless it's really needed.

I don't see any kind of constraints in this problem for passenger-limit and total-tourists ... try to have total tourists = 654254568 (I just picked a big number) and your maximum route = 9999 ... FYI => 654254568 / 9999 = 65432 even. For those numbers, your code below would print out 65433 instead of 65432. Of course the input-cases might not contain those big numbers ... but who knows ...

[c]temp=(float)tourist;

trip=temp/route[start][end];
trip1=(long)trip;

if((trip-trip1)>0.00)
trip_num=trip1+1;
else if((trip-trip1)==0.00)
trip_num=trip1;
printf("Scenario #%ld\n",case_num);
printf("Minimum Number of Trips = %ld\n",trip_num);
printf("\n"); [/c]

-turuthok-

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Re: Why WA:10099

Oh yes, one more thing that could trip you on this problem ... the roads are supposed to be bidirectional ... make sure you handle this.

-turuthok-

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Code: Select all

The code has been deleted because after some change it has benn accepted.thanks.
what may be the error here???
may be floating pt arithmatic error.. or anything else...
it's a simple algorithmic prob..
but why wa....
:[/b]
Last edited by yahoo on Sun Mar 23, 2003 7:28 am, edited 1 time in total.

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
silly mistake!!!
what does this following line mean? Code: Select all

printf("Scenario #1\n",cases++);
good luck
-sohel

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Oh i was so silly. I have fixed it but still wrong answer.   saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
u need to modify your code a little to get AC.

code to change:

Code: Select all

d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
code to replace with:

Code: Select all

d[i][j] = d[j][i] = max(d[i][j], min(d[i][k], d[k][j]));
hope u can understand why the change was needed. good luck
-sohel

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Thank you very much for your help saiiqbal. I got accepted. I think i have to think a lot next solving any prolem like this. junior
New poster
Posts: 5
Joined: Fri Jun 06, 2003 8:53 am
Location: jakarta
Contact:

10099

[c]
Excuse me Mr. and Mrs.(and all the gurus there)
have you ever read problem 10099?

I just don't get the point of the sample case written there

it was said that Mr G had to take the route 1-2-4-7 and
it took 5 trips(shouldn't it be 4)
and if it is true (1-2-4-7) ,the number of tourists is only
30+25+35 == 90 ---> 90<99
so the asnwer is wrong ,he couldn't have taken that route