CCC '11 J4 - Boring Business

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem type
Canadian Computing Competition: 2011 Stage 1, Junior #4

Boring is a type of drilling, specifically, the drilling of a tunnel, well, or hole in the earth. With some recent events, such as the Deepwater Horizon oil spill and the rescue of Chilean miners, the public became aware of the sophistication of the current boring technology. Using the technique known as geosteering, drill operators can drill wells vertically, horizontally, or even on a slant angle.

A well plan is prepared before drilling, which specifies a sequence of lines, representing a geometrical shape of the future well. However, as new information becomes available during drilling, the model can be updated and the well plan modified.

Your task is to write a program that verifies the validity of a well plan by verifying that the borehole will not intersect itself. A two-dimensional well plan is used to represent a vertical cross-section of the borehole, and this well plan includes some drilling that has occurred starting at (0, -1) and moving to (-1, -5). You will encode in your program the current well plan shown in the figure below:

-3-2-1012345678910
-1
-2
-3
-4
-5
-6
-7
-8

Input Specification

The input consists of a sequence of drilling command pairs. A drilling command pair begins with one of four direction indicators (d for down, u for up, l for left, and r for right) followed by a positive length. There is an additional drilling command indicated by q (quit) followed by any integer, which indicates the program should stop execution. You can assume that the input is such that the drill point will not:

  • rise above the ground, nor
  • be more than 200 units below ground, nor
  • be more than 200 units to the left of the original starting point, nor
  • be more than 200 units to the right of the original starting point

Output Specification

The program should continue to monitor drilling assuming that the well shown in the figure has already been made. As we can see (-1, -5) is the starting position for your program. After each command, the program must output one line with the coordinates of the new position of the drill, and one of the two comments safe, if there has been no intersection with a previous position or DANGER if there has been an intersection with a previous borehole location. After detecting and reporting a self-intersection, your program must stop.

Sample Input 1

l 2
d 2
r 1
q 0

Output for Sample Input 1

-3 -5 safe
-3 -7 safe
-2 -7 safe

Sample Input 2

r 2
d 10
r 4
q 0

Output for Sample Input 2

1 -5 safe
1 -15 DANGER

Comments


  • 0
    petlop222  commented on July 23, 2024, 3:24 a.m.

    why am I failing the last test case? https://dmoj.ca/submission/6508342


  • -2
    NonNonCroissant  commented on April 23, 2024, 5:15 a.m.

  • -1
    wome  commented on Feb. 9, 2021, 11:05 a.m.

    which point is the original starting point,0 -1 or -1 -5.


    • 7
      Badmode  commented on Feb. 9, 2021, 5:43 p.m. edited

      As we can see (-1, -5) is the starting position for your program.


  • 71
    faraz123  commented on Sept. 4, 2020, 12:11 a.m.

    Never mine straight down


  • 0
    Neon  commented on Nov. 28, 2019, 2:22 a.m.

    For test case #3, the input given doesn't seem to seem to intersect, but yet there is DANGER on the last step.


    • 7
      Badmode  commented on Dec. 31, 2020, 4:06 a.m.

      You intersect at 1 -5 for the third test case.

      The first command of the test case was to dig right from -1 -5 → 2 -5, digging up the blocks:

      0 -5, 1 -5, 2 -5

      The last command of the test case was to dig down from 1 -4 → 1 -6, digging up the blocks:

      1 -5, 1 -6

      Hopefully this answers your question.


  • 0
    pro  commented on Sept. 13, 2017, 6:26 p.m. edited

    How does the second sample input output Danger? They don't seem to intersect?


    • 4
      injust  commented on Sept. 13, 2017, 8:03 p.m.

      You will encode in your program the current well plan shown in the figure


      • 0
        pro  commented on Sept. 13, 2017, 10:24 p.m.

        OH YES TY


  • 1
    bobhob314  commented on Jan. 17, 2015, 1:07 a.m.

    There is no "q 0". Does there not need to be one if the program terminates due with "DANGER"?


    • 11
      Xyene  commented on Feb. 3, 2015, 2:19 a.m.

      Your program must stop when it's in DANGER, so it's implied you are not to read input past that point. So yes, there need not be a q directive if the drill is in DANGER.