## 10099 - The Tourist Guide

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[0]=source[0];
if(source[0]!=dest[0])
{
node[1]=dest[0];
stop=1;
}
else if(source[0]==dest[0])
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[0]=source[0];
if(source[0]!=dest[0])
{
node[1]=dest[0];
stop=1;
}
else if(source[0]==dest[0])
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