## DMOPC '14 Contest 7 P3 - Streetcars

View as PDF

Points: 7 (partial)
Time limit: 1.4s
Memory limit: 129M

Author:
Problem types

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.

• commented on Nov. 19, 2015, 5:52 p.m.

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?

• commented on Dec. 5, 2015, 6:19 p.m. edit 2

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^ )/

• commented on April 7, 2015, 8:34 p.m.

There is currently no better known solution than , which passes on the (extremely weak) data.

• commented on April 7, 2015, 9:40 p.m. edited

What is "N" in your O(N^2)? I presume you mean S, in the context of the problem.

I'm not a good analyst, but I think my solution is O(S) with a large constant. My outer loop iterates over the stops, and its body is a bunch of operations with complexity O(B), B 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 S^2.

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.

• commented on April 7, 2015, 10:22 p.m.

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?

• commented on April 7, 2015, 11:23 p.m.

Nah, I'm definitely not looking for any sort of action. This is 100% didactic :)

• commented on April 7, 2015, 4:46 p.m.

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?...

• commented on April 7, 2015, 4:50 p.m.

The number of passengers that get off is a percentage of the number of people on the streetcar.

• commented on April 7, 2015, 4:01 p.m.

Title

• commented on April 7, 2015, 4:08 p.m. edited

"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.

• commented on April 7, 2015, 4:15 p.m.

When calculating the number of passengers getting off, do we round to the nearest integer for each street car?

• commented on April 7, 2015, 4:17 p.m. edited

"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.

• commented on April 7, 2015, 4:39 p.m.

What? 99 * 0.05 is nowhere near 19...

• commented on April 7, 2015, 4:43 p.m.

I was thinking 1/5 - I meant 20%, sorry for the confusion