10801 - Lift Hopping
Moderator: Board moderators
10801 - Lift Hopping
I used modified floyd-warshall & managed a wrong ans.
please give me some I/O.
please give me some I/O.
-
- New poster
- Posts: 43
- Joined: Mon Oct 13, 2003 4:54 pm
- Location: Mexico
- Contact:
Re: Need I/O-10801
InputZuberul wrote:I used modified floyd-warshall & managed a wrong ans.
please give me some I/O.
Code: Select all
3 30
100 100 1
0 2 4 5 6 7 8 21 22 23 24 25 26 30
1 2 19 11 12 13 14 15 16 30
1 10 30
Code: Select all
449
What should be the output of this input?9900? or 417?
Code: Select all
2 99
100 1
0 1 98 99
1 98
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
The issue Cho was pointing to: Consider the test case he posted. The optimal solution is: take lift 1 from 0 to 1, take lift 2 from 1 to 98, take lift 1 from... oh, wait! Isn't the slow lift 1 somewhere around floor 2 now? How is it possible that suddenly it is here and I can take it again (to get to the floor 99)?
I think a way around this problem is to assume that if a lift is empty, it may move faster than if it is transporting a person. Then the assumption about waiting 60 seconds may make sense.
I think a way around this problem is to assume that if a lift is empty, it may move faster than if it is transporting a person. Then the assumption about waiting 60 seconds may make sense.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
I fully agree with cho on this matter. I think problem descriptions should withstand the reality check, otherwise they are misleading.
In cho's case:
1. take elevator 1 to floor 1, which takes 100 seconds
2. wait 60 seconds for elevator 2
3. take elevator 2 to floor 98, which takes 97 seconds
4. wait 60 seconds for elevator 1
5. tale elevator 1 to floor 99, which takes 100 seconds
The total trip takes 100+60+97+60+100 = 417 seconds.
But between step 2. and step 4. elevator 1 has 60+60+97 = 217 seconds to get from floor 1 to floor 98 at a speed of 100 seconds per floor. This is absurd. Or does it magically teleports from one floor to another if nobody is in it? Why wait 60 seconds then?
Complete rubbish...
In cho's case:
1. take elevator 1 to floor 1, which takes 100 seconds
2. wait 60 seconds for elevator 2
3. take elevator 2 to floor 98, which takes 97 seconds
4. wait 60 seconds for elevator 1
5. tale elevator 1 to floor 99, which takes 100 seconds
The total trip takes 100+60+97+60+100 = 417 seconds.
But between step 2. and step 4. elevator 1 has 60+60+97 = 217 seconds to get from floor 1 to floor 98 at a speed of 100 seconds per floor. This is absurd. Or does it magically teleports from one floor to another if nobody is in it? Why wait 60 seconds then?
Complete rubbish...
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Sure, the problem description is complete in the sense that it contains enough information to solve the problem. My point is, however, that it pretends to describe a real life situation, but misses the reality check by several orders of magnitude.
Of course, to make a problem out of a real life situation, one has to make simplifications, assumptions and idealisations, but in my opinion they should only have a minor effect on the outcome of the problem. This is simply stretching it too far and therefore misleading.
But maybe I'm being too philosophical about it.
Of course, to make a problem out of a real life situation, one has to make simplifications, assumptions and idealisations, but in my opinion they should only have a minor effect on the outcome of the problem. This is simply stretching it too far and therefore misleading.
But maybe I'm being too philosophical about it.
-
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
- Contact:
Cho and little joey, you're absolutely right. I could say that elevators use "subspace teleporting" to move between floors, but that procedure is dangerous to humans and it always takes exactly 60 seconds.
This is a poor defence though. Next time, I will do this problem the correct way. Stay tuned for "Lift Hopping 2.0"...
This is a poor defence though. Next time, I will do this problem the correct way. Stay tuned for "Lift Hopping 2.0"...
If only I had as much free time as I did in college...