SkyscraperElevator
SRM 853 · 2024-02-21 · by misof
Problem Statement
There is a skyscraper with floors numbered from 0 (the lobby) to N, inclusive.
The skyscraper has a single elevator. Initially, the elevator is in the lobby, i.e., its initial floor is 0.
In the lobby, the elevator has a display showing its current floor.
The elevator needs 1 second to move one floor up or down. A person needs 20 seconds to move one floor up when using stairs.
Everything else in this problem (e.g., pushing buttons, getting onto and off the elevator, etc.) happens instantly. E.g., if the elevator is on floor 7 and a new person arrives to the lobby, calls the elevator, waits for it, enters the elevator, pushes the "10" button, rides the elevator to floor 10 and then gets off the elevator, the whole process takes exactly 7 + 10 = 17 seconds.
A sequence of people will enter the lobby of the building, one person at a time.
Each person is going to a specific floor.
These floors are given in the
Whenever a person enters the lobby, they look at the elevator's display and determine the fastest way to get to their desired floor:
- If taking the stairs is strictly faster, they take the stairs.
- Otherwise (if taking the elevator is equally fast or faster than taking the stairs) they take the elevator.
(The people know both their own speed and the elevator's speed so they always correctly determine which option is better for them.)
Each person will follow the rule given above when deciding whether to take the elevator. Each person will complete their journey before the next person enters the building.
For each person, calculate the number of seconds in which they will reach their destination. Return the sum of those times.
Notes
- It can be shown that the correct return value always fits into a signed 32-bit integer.
- People in this problem do not get tired. Regardless of how many floors they go up on foot, each floor will always take them exactly 20 seconds.
Constraints
- N will be between 1 and 10,000,000, inclusive.
- people will have between 1 and 100 elements, inclusive.
- Each element of people will be between 1 and N, inclusive.
1000000
{1000000, 1000000, 1000000, 7, 500000}
Returns: 6500140
Here's what happens: The first person takes the elevator from the lobby to floor 1,000,000. (This takes 1,000,000 seconds.) The second person calls the elevator, waits for it to arrive, and then takes it back to floor 1,000,000. (This takes 2,000,000 seconds.) The third person also calls the elevator, waits for it to arrive, and then takes it back to floor 1,000,000. (Again, this takes 2,000,000 seconds.) The fourth person observes that waiting for the elevator would take too long, so they walk to floor 7 instead. (This takes 7*20 = 140 seconds. The elevator remains on floor 1,000,000.) The fifth person calls the elevator and then rides it to floor 500,000. (The elevator will need 1,000,000 seconds to come down and then the ride takes another 500,000 seconds.)
47000
{19, 1, 1000}
Returns: 1040
The first person takes the elevator to floor 19. The second person now sees that both options are equally good: walking to floor 1 will take 20 seconds, and calling the elevator + riding it to floor 1 will also take 19+1 = 20 seconds. As specified in the statement, in case of a tie the person still chooses to use the elevator. The choice matters later. As the third person enters the lobby, the elevator is now on floor 1 and thus the third person will only need 1+1000 seconds.
47000
{20, 1, 1000}
Returns: 1060
Almost the same scenario as before, but now the second person will prefer the stairs (it's 1 second faster than taking the elevator). In this scenario, when the third person arrives, the elevator is still on floor 20. The third person will need to wait much longer than in the previous example. (Thus, a tiny change in the input sequence produced a significant change in the total travel time.)
10000000
{10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000, 10000000}
Returns: 1990000000
1
{1}
Returns: 1
Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SkyscraperElevator with a public method int simulate(int N, vector<int> people) · 98 test cases · 2 s / 256 MB per case