The new streetcars can carry people, compared to the old streetcars, which only carried people. Given an old streetcar route with the number of passengers waiting at each stop and the percentage of riders that get off, determine the number of streetcars that could be saved by using the newer ones instead.
Your goal is to determine the number of streetcars required to pick up all the passengers, with streetcars running from the first to the last stop.
Assume that if a streetcar is full the remaining passengers will wait for the next one, that no one gets off at the stop they get on, and that passengers will always board the first streetcar that has space.
Input Specification
The first line will consist of , the number of stops.
The next lines contain two space-separated integers, and .
represents the number of passengers waiting at the stop.
represents the percentage of passengers on the streetcar that get off at that stop.
When calculating the number of passengers that get off, round to the lowest integer.
Output Specification
The output should consist of the number of streetcars saved by using the new ones instead of the old ones.
Sample Input
3
30 0
50 10
70 5
Sample Output
1
Explanation of Output for Sample Input
Upon reaching the second stop the streetcar has passengers. get off and then board, leaving it with passengers. At the third stop, only get off, leaving space for only more passengers. This means that passengers will have to wait for the next streetcar, but with the new streetcar, there would have been room for more passengers, meaning that only one would have been required.
Comments
Say there are 2 streetcars being used. One is full and another one has seats available. For the percentage that gets off (say 10%), does that mean 10% of the people on the full streetcar get off and 10% of the people on the streetcar with seats available get off, freeing up seats on both streetcars? Or does the percentage just affect the non-full streetcars?
bump
I believe that all streetcars lose percent upon reaching the station.
Given the edited constraints (given the comments, I believe they have been edited as won't pass under the time limit now), should the editorial not also be edited?
_(^u^ )/
There is currently no better known solution than , which passes on the (extremely weak) data.
What is "" in your ? I presume you mean , in the context of the problem.
I'm not a good analyst, but I think my solution is with a large constant. My outer loop iterates over the stops, and its body is a bunch of operations with complexity , being the size of the large streetcar (a constant in the context of the problem).
Maybe I'm misinterpreting you. Or maybe my code is actually wrong. But I do think you can do better than .
EDIT for a little background
My code is probably unreadable so here's a similar problem for background: Panda and Xor. The editorial for it specifies a similar algorithm to mine.
I was going to reply sooner but the brute force solution still hasn't figured out the worst case solution yet so I'll just assume your solution is correct.
Yeah, I did mean instead of .
You can probably say you have a linear solution due to assuming maximum constraints, but I think saying say your algorithm is with a small constant (about ) is more accurate.
Anyway this solution wasn't known to author before or during contest and most participants already submitted that passed with time to spare so we felt it wasn't fair to change test cases or statement in the middle of the contest. Sorry for making you solve a harder problem. Is there any particular course of action you would like to see taken?
Nah, I'm definitely not looking for any sort of action. This is 100% didactic :)
What happens when there is an overflow of passengers? Lets say there was 280 people waiting at the stop. 29 would wait for next car. Does the percentage affect the full cart and the extra passengers or?...
The number of passengers that get off is a percentage of the number of people on the streetcar.
Title
"the number of streetcars saved by using the new ones instead of the old ones" Find the reduction is streetcars if you use the ones that can hold 251 people vs. 132 people.
When calculating the number of passengers getting off, do we round to the nearest integer for each street car?
"When calculating the number of passengers that get off, round to the lowest integer." For example, if 20% of 99 people get off, 19 people get off.
What? 99 * 0.05 is nowhere near 19...
I was thinking 1/5 - I meant 20%, sorry for the confusion