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

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

10099 , something wrong???

Post by kcph007 » Tue Nov 26, 2002 12:15 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Nov 26, 2002 1:11 pm

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:

Post by Larry » Tue Nov 26, 2002 5:27 pm

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

Post by kcph007 » Tue Dec 03, 2002 4:45 am

Thanks, I'm a newbie to problems here, so never thought it would be that tricky :lol:
Thanks alot

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

10099?What's wrong??

Post by razibcse » Thu Jan 23, 2003 8:29 pm

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:

Post by Larry » Fri Jan 24, 2003 1:26 pm

Each trip requires a guide.

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

10099

Post by razibcse » Fri Jan 31, 2003 8:23 pm

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:

Post by turuthok » Tue Feb 04, 2003 1:38 pm

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

Post by turuthok » Tue Feb 04, 2003 1:52 pm

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-

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

please help

Post by yahoo » Sat Mar 22, 2003 9:14 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...
please help....
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.

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Sat Mar 22, 2003 10:51 am

silly mistake!!!
what does this following line mean? :wink:

Code: Select all

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

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

Post by yahoo » Sat Mar 22, 2003 4:30 pm

Oh i was so silly. I have fixed it but still wrong answer. :oops: :oops: :oops:

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Sat Mar 22, 2003 5:15 pm

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

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

Post by yahoo » Sun Mar 23, 2003 7:22 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.
8)

junior
New poster
Posts: 5
Joined: Fri Jun 06, 2003 8:53 am
Location: jakarta
Contact:

10099

Post by junior » Fri Jun 06, 2003 9:06 am

[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

what about
1-2-5-7 ----> 4 trips with 110 passengers
I think it's the best answers

anybody can help me?
Maybe I just don't get the problem and the sample case
Thanks .....[/c]
codes are just codes

Post Reply

Return to “Volume 100 (10000-10099)”