DMOPC '14 Contest 6 P3 - Streetcars - Olympiads Online Judge

DMOPC '14 Contest 6 P3 - Streetcars

Points: 7 (partial)

Time limit: 1.4s

Memory limit: 129M

Author:

Problem types

The new streetcars can carry $251$ ~251~ people, compared to the old streetcars, which only carried $132$ ~132~ 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 $S$ ~S~ $(1 \le S \le 100\,000)$ ~(1 \le S \le 100\,000)~, the number of stops.
The next $S$ ~S~ lines contain two space-separated integers, $N$ ~N~ and $P$ ~P~.
$N$ ~N~ $(0 \le N \le 5\,000)$ ~(0 \le N \le 5\,000)~ represents the number of passengers waiting at the stop.
$P$ ~P~ $(0 \le P \le 100)$ ~(0 \le P \le 100)~ 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

Sample Output

Explanation of Output for Sample Input

Upon reaching the second stop the streetcar has $30$ ~30~ passengers. $10\%$ ~10\%~ get off and then $50$ ~50~ board, leaving it with $77$ ~77~ passengers. At the third stop, only $5\%$ ~5\%~ get off, leaving space for only $132-74 = 58$ ~132-74 = 58~ more passengers. This means that $12$ ~12~ passengers will have to wait for the next streetcar, but with the new streetcar, there would have been room for $251-74 = 177$ ~251-74 = 177~ more passengers, meaning that only one would have been required.

Comments

1

minecraftyugi commented on Nov. 19, 2015, 10: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?

0

bobhob314 commented on Dec. 5, 2015, 11:19 p.m. ← edit 2 →

bump

I believe that all streetcars lose $P_i$ ~P_i~ percent upon reaching the $i^{th}$ ~i^{th}~ station.

Given the edited constraints (given the comments, I believe they have been edited as $S^2$ ~S^2~ won't pass under the time limit now), should the editorial not also be edited?

_(^u^ )/

0

FatalEagle commented on April 8, 2015, 12:34 a.m.

There is currently no better known solution than $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~, which passes on the (extremely weak) data.

2

sigkill commented on April 8, 2015, 1:40 a.m. ← edit 2 →

What is " $N$ ~N~" in your $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~? I presume you mean $S$ ~S~, in the context of the problem.

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

0

FatalEagle commented on April 8, 2015, 2:22 a.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 $S$ ~S~ instead of $N$ ~N~.

You can probably say you have a linear solution due to assuming maximum constraints, but I think saying say your algorithm is $\mathcal{O}(SN)$ ~\mathcal{O}(SN)~ with a small constant (about $\dfrac{1}{132}$ ~\dfrac{1}{132}~) is more accurate.

Anyway this solution wasn't known to author before or during contest and most participants already submitted $\mathcal{O}(S^2)$ ~\mathcal{O}(S^2)~ 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?

2

sigkill commented on April 8, 2015, 3:23 a.m.

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

0

IDontKnowHowToCode commented on April 7, 2015, 8: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?...

0

Sentient commented on April 7, 2015, 8:50 p.m.

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

0

LOLWHATOMGBBQ commented on April 7, 2015, 8:01 p.m.

Title

0

Sentient commented on April 7, 2015, 8: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.

0

LOLWHATOMGBBQ commented on April 7, 2015, 8:15 p.m.

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

0

Sentient commented on April 7, 2015, 8: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.

2

lolzballs commented on April 7, 2015, 8:39 p.m.

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

1

Sentient commented on April 7, 2015, 8:43 p.m.

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