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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Jun 06, 2003 9:26 am

No... You've misinterpreted the qq......

In the sample input,
the tourist guide "wants to take 99 tourists from city 1 to city 7"

If he takes the route 1-2-4-7, Max. no. of people per trip
= Min(30, 25, 35) = 25

Thus max. no. of tourists per trip = 25 - 1 = 24 (Why? :P )

In 5 trips, max no. of tourists taken from 1 to 7
= 24 * 5 = 120 >= 99

So the sample input/output is correct!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by junior » Sun Jun 08, 2003 3:48 pm

Thanks a lot Mr.

I do appreciate that
codes are just codes

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

Post by junior » Tue Jun 10, 2003 4:30 pm

I've done the algorithm but why did I get Compile Error for 12 times???

I've followed the ANSI procedure like

int main(){
...
..
...
return 0;
}
etc.

and I've compiled it in my home with both Borland C and gcc
(in GNU/LINUX) and it was succesfull

but why I still got CE???

any comments or suggestions???
codes are just codes

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Jun 11, 2003 8:01 am

please post error messages or code - it'll be easier to tell you what's wrong :)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

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

Post by junior » Tue Jun 17, 2003 7:01 am

Never Mind ,
I just forgot , I used the //comment

Thanks anyway
codes are just codes

raymond85
New poster
Posts: 21
Joined: Tue Jul 01, 2003 9:26 am
Location: Hong Kong
Contact:

10099 - Why WA?!

Post by raymond85 » Mon Jul 14, 2003 5:39 pm

I have no idae why i am getting WA. I have test the program with many different test cases. Please Help! Here's my code:

Code: Select all

Just figured out I misunderstand the input format......

de
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

10099 WA

Post by de » Sat Aug 16, 2003 3:43 pm

I don't know why got WA.

Thanks for you help..><

[cpp]#include <iostream.h>

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

int main()
{
int n,r;
long graph[120][120];
int k,t,t2;
int x,y,l;
int s,d,p;
long temp;
long sum;
int count;

count=0;

while (cin >> n >> r)
{
if (n==0 && r==0)
break;

count++;

for (t=0 ;t<=n ;t++)
{
for (t2=0 ;t2<=n ;t2++)
graph[t][t2]=0;
}

for (t=0 ;t<r ;t++)
{
cin >> x >> y >> l;
graph[x][y]=graph[y][x]=l;
}

cin >> s >> d >> p;

for (k=1 ;k<=n ;k++)
{
for (t=1 ;t<=n ;t++)
{
for (t2=1 ;t2<=n ;t2++)
{
if (graph[t][k]==0 || graph[k][t2]==0)
continue;

temp=min(graph[t][k],graph[k][t2]);

graph[t][t2]=max(graph[t][t2],temp);
}
}
}

temp=graph[s][d];

temp--;

sum=p/temp;

if (temp%p!=0)
sum++;

cout << "Scenario #" << count << endl;
cout << "Minimum Number of Trips = " << sum << endl << endl;
}
return 0;
}[/cpp]

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Tue Aug 19, 2003 5:56 pm

there are some errors in ur code


[cpp]
graph[x][y]=graph[y][x]=l;
[/cpp]
should be
[cpp]
graph[x][y]=graph[y][x]=l-1; //because the tourist will also go
[/cpp]

and u r doing

[cpp]
temp--
[/cpp]

this is wrong. u should not do this

u checked
[cpp]
if (temp%p!=0)
sum++;
[/cpp]

i think it should be

[cpp]
if (p%temp!=0)
sum++;
[/cpp]

hope this can help
Rakeb

de
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

thanks!

Post by de » Wed Aug 20, 2003 4:26 pm

special thanks for your help!!..^^

dserrano
New poster
Posts: 7
Joined: Tue Sep 17, 2002 2:39 am

10099 - Disjkstra

Post by dserrano » Wed Nov 05, 2003 2:49 am

Can I solve the problem 10099 using a variation of Dijkstra algorithm?
In each step, instead of looking for the lowest cost, I look for the highest minimum cost of the whole path.
I'm in the right way, or not :( ?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Nov 05, 2003 4:24 am

Probably, but I solved this using min-max Floyd's.

maxagaze
New poster
Posts: 2
Joined: Tue Sep 23, 2003 12:02 am

yep

Post by maxagaze » Tue Nov 25, 2003 9:23 pm

Dijkstra worked for me.

watershed
New poster
Posts: 13
Joined: Thu Aug 05, 2004 9:14 am

10099 WRONG

Post by watershed » Thu Aug 05, 2004 9:34 am

This problem is Floyd algorithm.
Why did I get WA?
Thanks for your help....

[cpp]nothing[/cpp]
Last edited by watershed on Mon Aug 09, 2004 8:43 am, edited 1 time in total.

Eric3k
New poster
Posts: 29
Joined: Mon Apr 29, 2002 5:22 pm
Contact:

Post by Eric3k » Sun Aug 08, 2004 8:18 pm

You should set all the values of map to 0 for every test case and then read the input.

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

10099 (clarification needed)

Post by backbencher » Sat Oct 02, 2004 1:31 am

can anyone clarify the sample i/o to me?

how the output is : 5 trips ???

Post Reply

Return to “Volume 100 (10000-10099)”