## 10099 - The Tourist Guide

Moderator: Board moderators

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 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
Contact:

### clarified

thanx

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

### 10099

#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
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:
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/

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

### 10099 TLE

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;

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));
}
}


Is a better way to do it??

Thanks.
Neo

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

### No problem

No problem..

I already do it using MAXMIN floyds.
Neo

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm

### 10099

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 ? 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:
Mr.G. counts as a passenger in each trip.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
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

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 i, j, k, scinario = 0;
long source, des, totalPassengers;
{
for( i = 0; i < roads; ++i ){
}
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 )));

}
return 0;
}

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
Salamo Aleko
Just in the intialization function

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
At last i got accepted.

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
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
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