COCI '07 Regional #1 Platforme

View as PDF

Submit solution


Points: 7
Time limit: 0.6s
Memory limit: 32M

Problem type

A level is being designed for a new platform game. The locations of the platforms have been chosen. Contrary to popular opinion, platforms can't float in the air, but need pillars for support. More precisely, each of the two ends of the platform needs to be supported by a pillar standing on the floor or on a different platform.

You will be given the locations of the platforms in a coordinate system as in the left image below. Each platform's location is determined by its altitude (vertical distance from the ground) and the start and end coordinates in the horizontal direction. Each support pillar is placed half a unit from the end of a platform, as in the right image.

Determine the total length of pillars needed to support all the platforms.

Example level with three platforms. The lowest platform is at altitude 1,
the second lowest at altitude 3 and the third at altitude 5.


The total length of pillars needed to support all platforms is 14.

Input Specification

The first line contains the integer N, 1 \le N \le 100, the number of platforms. Each of the following N lines contains the position of one platform, three coordinates Y, X_1 and X_2.

The first number is the altitude, the other two the horizontal coordinates. All coordinates will be positive integers less than 10\,000 satisfying X_2 > X_1+1 (i.e. the length of each platform will be at least 2).

The input will be such that no two platforms overlap.

Output Specification

Output the total length of pillars needed to support all the platforms.

Sample Input 1

3
1 5 10
3 1 5
5 3 7

Sample Output 1

14

Sample Input 2

5
50 50 90
40 40 80
30 30 70
20 20 60
10 10 50

Sample Output 2

200

Comments


  • 0
    0815  commented on Jan. 24, 2023, 10:38 p.m.

    I keep getting some WA results. My test cases work fine though. I assume there may be something in the problem that I am misunderstanding.

    Why is the result for this sample problem 14? 3 1 5 10 this is the lowest platform with height 1, so both pillars have length 1 (total 2) 3 1 5 middle platform with height 3. left pillar is 3, right pillar rests on lower platform so 2 (total 5). 5 3 7 highest platform with height 5. left pillar rests on middle platform so is 2, right pillar rests on lowest platform so 4 (total 6)

    This adds up to a total pillar length of 13. Am I missing something?

    Any help is appreciated.


    • 1
      dnialh_  commented on Jan. 25, 2023, 2:15 a.m.

      Look at the image in the problem statement.

      In particular, the second platform is not directly over the first.


      • 0
        0815  commented on Jan. 25, 2023, 12:17 p.m. edited

        Thanks. I think I figured it out. I was counting squares instead of lines. That makes the difference!


  • 0
    dinglequandale  commented on Oct. 31, 2022, 12:01 a.m.

    I have no clue why my code is not working; I have manually tried a bunch of test cases which passed.


  • -1
    pyhead42  commented on Oct. 24, 2022, 8:24 p.m.

    Drawing a picture can help you a lot in this problem with thinking through it and debugging. Start simple and then add on more when you need more test cases. I used seven different platforms to test before I got my code working properly for the judge even though it worked for the example tests hours before I got it correct. Hope this helps, good luck!


  • 1
    mikoSingle  commented on June 6, 2022, 9:20 p.m.

    wow i spent several days writing a program that draws the platforms and pillars and trying to calculate the lengths that way but it's just a math problem.................


  • 0
    neo_coder  commented on Jan. 20, 2022, 9:41 a.m.

    What am I missing in my code? Any help is appreciated!


    • 3
      Spitfire720  commented on Jan. 21, 2022, 11:57 a.m.

      Consider a test case where a platform is completely above another. For example:

      2
      2 1 3
      1 1 3

      The correct output should be 4.


      • 0
        darek  commented on Jan. 25, 2022, 12:10 p.m.

        "The input will be such that no two platforms overlap."?


        • 2
          bglamb  commented on March 5, 2022, 6:18 a.m.

          I think this is supposed to mean that no part of any two platforms will be occupying the same space, not that no platform will be above another platform. The platforms partially 'overlapping' above each other is the whole point of the exercise.

          The example above seems valid to me.


          • 0
            Spitfire720  commented on March 5, 2022, 9:24 a.m.

            It's not, because the platforms entirely overlap each other. The x1 and x2 values for the two platforms are the same.


        • 1
          Spitfire720  commented on Jan. 25, 2022, 12:18 p.m.

          Oops, I forgot that existed. neo_coder still passed lol


      • 1
        neo_coder  commented on Jan. 23, 2022, 9:32 a.m.

        Thanks for the help!