10099

kcph007 · 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 · 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 · 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 · 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

Thanks alot

razibcse · 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.

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

Each trip requires a guide.

razibcse · 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 · 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 · 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-

yahoo · 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]

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

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

Code: Select all

printf("Scenario #1\n",cases++);

good luck
-sohel

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

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

saiqbal · 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

yahoo · 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.

junior · 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]

OJ Board

10099 - The Tourist Guide

10099 , something wrong???

10099?What's wrong??

Re: Why WA:10099

please help

10099