DMOPC '14 Contest 6 P3 - Streetcars

View as PDF

Submit solution


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

Author:
Problem types

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

3
30 0
50 10
70 5

Sample Output

1

Explanation of Output for Sample Input

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

streetcars.jpg


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 percent upon reaching the i^{th} station.

      Given the edited constraints (given the comments, I believe they have been edited as 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), which passes on the (extremely weak) data.


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

      What is "N" in your \mathcal{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 \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), 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.


      • 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 instead of 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) with a small constant (about \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) 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