CCC '00 S2 - Babbling Brooks

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 16M
Problem type
Canadian Computing Competition: 2000 Stage 1, Junior #4, Senior #2

A series of streams run down the side of a mountain. The mountainside is very rocky so the streams split and rejoin many times. At the foot of the mountain, several streams emerge as rivers. Your job is to compute how much water flows in each river.

At any given elevation there are m streams, labelled 1 to m from left-to-right. As we proceed down the mountainside, one of the streams may split into a left fork and a right fork, increasing the total number of streams by 1, or two streams may rejoin, reducing the total number of streams by 1. After a split or a rejoining occurs, the streams are renumbered consecutively from left-to-right. There is always at least one stream and there are never more than 100 streams.

Input Specification

The first line of input contains n, the initial number of streams at some high altitude. The next n lines give the flow in each of the streams from left-to-right. Proceeding down the mountainside, several split or rejoin locations are encountered. For each split location, there will be three lines of input.

  • a line containing 99 (to indicate a split)
  • a line containing an integer, the number of the stream that is split
  • a line containing an integer between 0 and 100, the percentage of flow from the split stream that flows to the left fork. (The rest flows to the right fork)

For each join location, there will be two lines of input:

  • a line containing 88 (to indicate a join)
  • a line containing an integer, the number of the stream that is rejoined with the stream to its right

The flow from both joined streams is combined. After the last split or join location will be:

  • a single line containing 77 (to indicate end of input)

Output Specification

Your job is to determine how many streams emerge at the foot of the mountain and what the flow is in each. Your output is a sequence of real numbers, rounded to the nearest integer, giving the flow in rivers 1 through m.

Sample Input

3
10
20
30
99
1
50
88
3
88
2
77

Sample Output

5 55

Comments


  • -3
    olli67  commented on Sept. 18, 2021, 6:46 p.m.

    well, we start with three streams. the first, which means the leftmost is split into two streams. renumbering the streams we get stream 1, transporting 50% of the initial 10 whatsoevers, let#s say liters, which are 5 liters, and, according to the precise specification of the problem, " (The rest flows to the right fork)", stream 2, transporting "The rest", which is roundabout 50%, lets say 5 liters. here we are.

    s1 = 5

    s2 = 5

    s3 = 20

    s4 = 30

    total = 60

    Then "88". rejoin s3 with s4.

    we get

    s1 = 5

    s2 = 5

    s3(rejoined with s4) = 50

    total = 60

    Then again "88". rejoin s2 with s3

    we get

    s1 = 5

    s2(rejoined with s3) = 55

    total = 60

    number of streams: 2

    name of the mountain:

    mountain sinai

    name of the author:

    Moses

    Year:

    1200 b.c.

    language:

    machine-code

    (sorry, some bits or bytes got probably lost in transmission ..)


  • 0
    Sdr70  commented on Sept. 15, 2021, 12:03 p.m.

    Can anyone explain to me why the output stream is 5? after 1 split and 2 rejoin? thz


  • 0
    Daniel_Ye  commented on April 17, 2021, 7:23 p.m. ← edited

    Not getting last test case right. Can someone help https://dmoj.ca/src/3567802


  • 1
    Mad_Milk  commented on Jan. 1, 2021, 10:29 p.m.

    Getting all test cases right except for the last one. Can't find any issues in my code. Does anyone have any ideas?


    • 3
      Ehsian  commented on Jan. 13, 2021, 11:43 p.m.

      When you multiply with the "percent" variable, it casted the value to an integer, which messes with your rounding in the end.


  • 3
    Tony1234  commented on Nov. 20, 2020, 10:17 a.m. ← edited

    Nvm


  • 2
    maxcruickshanks  commented on July 13, 2020, 4:48 p.m.

    When splitting or merging, left and right is based on your view of the mountain (i.e., the direction is not relative to the split).


  • 0
    ria32  commented on Feb. 10, 2020, 5:33 p.m. ← edited

    I'm getting all of the cases right except for the index out of bounds error on the last one but I can't find anything wrong. Any ideas??


  • 0
    koumakpet  commented on Feb. 8, 2020, 4:25 p.m. ← edited

    The first 3 cases got accepted, but I can't quite figure out what's wrong with the last one. Could someone help? (I use Python)

    My submission


    • 0
      Ehsian  commented on Jan. 13, 2021, 11:53 p.m.

      Line 29 - Integer divided by an integer returns integer, flooring the value before you intend to round it.


  • -1
    Ironboy4000  commented on July 10, 2019, 5:20 p.m. ← edit 3

    Getting all test cases right except for the last one. Can't find any issues in my code. Anyone have any ideas?

    Edit: Found my issue


    • 8
      Evang  commented on Jan. 18, 2020, 6:09 p.m. ← edit 2

      I have the same issue. How did you fix yours?

      Edit: The problem was that, when a stream splits, the amount of water in it could be a decimal.


    • -19
      MisakaMikoto  commented on Dec. 31, 2019, 7:19 p.m. ← edited

      This comment is hidden due to too much negative feedback. Click here to view it.


  • 2
    sobko  commented on April 5, 2019, 6:09 p.m. ← edit 2

    Getting first 3 cases right, however last 2 cases wrong and I can't seem to figure it out :/ Any ideas?

    Edit: When adding (88), I messed up and made any number after the one joining take from one before instead of one after. My bad.