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

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am

Post by jambon_vn » Sat Oct 02, 2004 5:51 am

Hi,

According to this problem, you will use the route 1 - 2 - 4 - 7. And the maximum number of passengers is 25. But only 24 tourists can go each time because the tourist guide has to ride the bus with each group. The input sample has 99 tourists. With 4 trips only 96 tourists can go to the destination. So the output is 5 trips.

Is it clear enough for you?

backbencher
New poster
Posts: 5
Joined: Thu Sep 23, 2004 12:10 am
Location: Bangladesh
Contact:

clarified

Post by backbencher » Fri Oct 08, 2004 10:42 pm

thanx

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

10099

Post by efr_shovo » Thu Oct 14, 2004 4:59 pm

/*Here Is My Code. Please Help*/

#include<stdio.h>


long n,R,C1,C2,P,W[100][100],s,d,t;

long min(long x,long y)
{
long mi;
if(x<y)
mi=x;
else
mi=y;
return mi;
}

long max(long x,long y)
{
long mx;
if(x>y)
mx=x;
else
mx=y;
return mx;
}


void F_W()
{
long k,i,j;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
W[j]=max(W[j],min(W[k],W[k][j]));
}

void main()
{
long i,j,mod,count=0,div=0,mutex=0;
freopen("c:\\in.txt","r",stdin);
while(1)
{
scanf("%ld %ld",&n,&R);
if(n<=0&&R<=0)
break;
else if(count)
printf("\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
W[j]=0;
for(i=1;i<=R;i++)
{
scanf("%ld %ld %ld",&C1,&C2,&P);
if((C1<1&&C1>n)||C2<1&&C2>n||P<1)
{
mutex=1;
break;
}
W[C1][C2]=P;
W[C2][C1]=P;
}
if(mutex)
break;
F_W();
scanf("%ld %ld %ld",&s,&d,&t);
mod=t%(W[s][d]-1);
div=t/(W[s][d]-1);
if(count!=0)
printf("\n");
printf("Scenario #%ld\n",++count);
if(mod==0)
printf("Minimum Number of Trips = %ld\n",div);
else
printf("Minimum Number of Trips = %ld\n",++div);
}
}

eg_frx
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by eg_frx » Fri Oct 29, 2004 5:28 pm

Did you print a blank line after each scenario?

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Sat Dec 18, 2004 5:17 pm

There will be a complete blank line after each scenario. I am giving here a sample input output format. Hope it will help you.

Sample Input

Code: Select all

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
0 0
Sample Output

Code: Select all

Scenario #1
Minimum Number of Trips = 5

Scenario #2
Minimum Number of Trips = 5
 <<------- [There is a new line also]
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

User avatar
neowarez
New poster
Posts: 14
Joined: Tue May 06, 2003 11:04 pm
Location: Portugal
Contact:

10099 TLE

Post by neowarez » Wed Jun 29, 2005 9:37 pm

Hi to all!!!

I am trying to solve this graph problem but it gives me TLE..

I use this metoth to find the MAX..

Code: Select all


void bfs(long a, long b, long cost) {
  long i;

  visitado[a]=1;
  if (a==b && cost>max)
    max=cost;
  else {
    for (i=0;i<=n;i++)
      if (!visitado[i] && edges[a][i]>0 && min(edges[a][i], cost)>max)
	bfs(i, b, min(edges[a][i], cost));
  }
  visitado[a]=0;
}

Is a better way to do it??

Thanks.
Neo

User avatar
neowarez
New poster
Posts: 14
Joined: Tue May 06, 2003 11:04 pm
Location: Portugal
Contact:

No problem

Post by neowarez » Thu Jun 30, 2005 1:55 am

No problem..

I already do it using MAXMIN floyds.
Neo

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

10099

Post by ayon » Sun Nov 06, 2005 11:12 am

Hi,
my problem is very simple. I cannot undersatnd the sample input !!! In the sample input i think the maximin distance is 25. so for 99 tourists it takes minimum ceil(99/25) = 4 trips. then why they says Minimum Number of Trips = 5 ? :roll: plz help...
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Nov 07, 2005 10:33 am

Mr.G. counts as a passenger in each trip.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Mon Nov 07, 2005 2:49 pm

:oops: what a fool i am !!! anyway, thanx to mf very much, i wrote my code and got accepted
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Amran
New poster
Posts: 2
Joined: Sun Feb 12, 2006 12:20 pm

10099 - The Tourist Guide

Post by Amran » Sun Feb 12, 2006 12:40 pm

i can't understand why this code is runtime error.
can any one say why?


#include <stdio.h>
#include <math.h>

#define MAX 102
#define NEGINF -10000

#define max(a, b) ( (a > b) ? (a) : (b) )
#define min(a, b) ( (a < b) ? (a) : (b) )

long passengers[MAX][MAX];

void init( long roads ) {
long i, j;
for( i = 1; i <= roads; ++i )
for( j = 1; j <= roads; ++j )
passengers[i][j] = NEGINF;
}
int main()
{
long cities, roads, road1, road2;
long i, j, k, scinario = 0;
long source, des, totalPassengers;
scanf( "%ld%ld", &cities, &roads );
while( cities && roads )
{
init( roads );
for( i = 0; i < roads; ++i ){
scanf( "%ld%ld", &road1, &road2 );
scanf( "%ld", &passengers[road1][road2] );
passengers[road2][road1] = passengers[road1][road2];
}
scanf( "%ld%ld%ld", &source, &des, &totalPassengers );
for( k = 1; k <= cities; ++k )
for( i = 1; i <= cities; ++i )
for( j = 1; j <= cities; ++j )
passengers[i][j] = max( passengers[i][j], min( passengers[i][k], passengers[k][j]));

printf( "Scenario #%ld\nMinimum Number of Trips = %.0lf\n\n", ++scinario,
ceil( double(totalPassengers) / ( passengers[source][des] - 1 )));

scanf( "%ld%ld", &cities, &roads );
}
return 0;
}

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Sun Mar 05, 2006 1:39 am

Salamo Aleko
Just in the intialization function

Mostafa Saad Wrote.... :o
void init( int roads ) {
int i, j;
for( i = 1; i < MAX; ++i )
for( j = 1; j < MAX; ++j )
passengers[j] = 0;
}

Amran
New poster
Posts: 2
Joined: Sun Feb 12, 2006 12:20 pm

Post by Amran » Sun Mar 12, 2006 3:47 pm

Thanks, Mostafa Saad
At last i got accepted.

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Fri Jun 09, 2006 3:36 pm

hello, my code was WA, whats wrong???

Code: Select all


I've solved that!		

thanks
Last edited by beloni on Fri Jun 30, 2006 11:50 pm, edited 3 times in total.
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Tue Jun 27, 2006 2:32 pm

so...
can you tell me some tip to get AC ?
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

Post Reply

Return to “Volume 100 (10000-10099)”