10099 - The Tourist Guide
Moderator: Board moderators
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?
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?
-
- New poster
- Posts: 5
- Joined: Thu Sep 23, 2004 12:10 am
- Location: Bangladesh
- Contact:
clarified
thanx
10099
/*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);
}
}
#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);
}
}
-
- 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
Sample Output
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
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/
http://groups.yahoo.com/group/acm_solver/
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..
Is a better way to do it??
Thanks.
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;
}
Thanks.
Neo
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
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...
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:](./images/smilies/icon_rolleyes.gif)
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
----------------
the world is nothing but a good program, and we are all some instances of the program
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 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;
}
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;
}
hello, my code was WA, whats wrong???
thanks
Code: Select all
I've solved that!
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