CCC '00 S2 - Babbling Brooks

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 256M
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


  • 2
    CopeSoap  commented on Feb. 4, 2024, 5:17 p.m.

    is anyone else having trouble on the last test case?


    • 0
      ahora240  commented on April 12, 2024, 6:28 a.m.

      Experienced the same thing..could not find what is error for last input case


  • 1
    JoeP  commented on Jan. 27, 2024, 9:50 a.m.

    I also get WA on last fifth test case. It would be nice to be able to see the input for the test cases that goes wrong in order to improve our codes!


    • 0
      踏雪寻梅  commented on Feb. 1, 2024, 2:29 a.m.

      I think you may have misunderstood the question as I did, stream that splits to the left does not combine with other stream (It becomes a new stream on its own).


    • 0
      htoshiro  commented on Jan. 27, 2024, 2:58 p.m.

      http://mmhs.ca/ccc/#2000%20Problems there are test cases provided by mmhs


  • 0
    daveys  commented on Jan. 18, 2024, 3:17 p.m.

    That was interesting! I had to submit three times due to a bug, but I'll put that down to the fact that I didn't test the code properly using my own test cases before submitting.

    I think that there aren't enough test cases to really ensure that your code is correct.

    Try this input, which tests for an error in your splitting maths:

    3, 10, 20, 100, 99, 10, 77

    Output: 10 20 10 90


    • 1
      350372058  commented on Feb. 19, 2024, 3:37 p.m.

      I think there are two lines of input after "99".


      • 2
        Just_Do_It  commented on Feb. 21, 2024, 1:54 a.m.

        yeah i think the input they're referring to is actually this:

        3 10 20 100 99 3 10 77


  • 2
    zackerburg  commented on Nov. 27, 2023, 12:01 a.m.

    what is the forth and fifth test case?


  • 0
    ItzAyan  commented on Nov. 12, 2023, 3:27 p.m.

    I need help for the last test case


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

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


    • 47
      silent_air  commented on Nov. 26, 2021, 5:21 p.m. ← edit 2

      rivers at first:
      10 20 30

      after 1st split:
      5 5 20 30
      (1st river is split 50:50)

      after 1st join:
      5 5 50
      (3rd river combines with the river to the right)

      after 2nd join:
      5 55
      (2nd river...)

      so the final outcome is:
      5 55


  • 2
    maxcruickshanks  commented on July 13, 2020, 8: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).