This page is still under construction.

Parts of this page are still being built. What you see may change.

Get Out 'Da Way!

Time limit1sMemory limit128 MB

Summary
Simulate up to ten bullets fired at a moving flat target and mark each hit block with an asterisk.
Level

Medium6 of 10

Topics
Geometry, Simulation, Implementation
Solved
No attempts yet

Problem

Boudreaux and Thibodaux just watched The Matrix, and now they are arguing about whether a person could really dodge bullets by moving fast enough. Boudreaux hunts nutria with buckshot and says that once a load spreads out there is no way to dodge every pellet. Thibodaux is still throwing kung fu moves in his head and insists that enough speed beats any spread. Boudreaux is fed up and close to settling the question with live ammunition, so write a simulator and settle it the safe way instead.

Input

The input holds 1 to 20 data sets, one after another, with no blank line between them.

Each data set has five parts, in this order.

  1. A line START N, where NN is the number of bullets fired at the target and 1≤N≤101 \le N \le 10.
  2. One line with the velocity of the target.
  3. NN lines, one velocity per bullet.
  4. The target drawing, 1 to 30 lines of at most 30 characters each. Every non-whitespace character is a piece of the target that a bullet can hit. The drawing contains no digits, asterisks, or commas. Treat the drawing as a rectangle whose width is the length of its longest line and whose height is its number of lines, and give every block of that grid a size of 10cm by 10cm.
  5. A line END.

A velocity is three components written with no spaces, <north>,<east>,<up>, in meters per second. Any component may be negative or fractional.

Every bullet leaves at the same instant from one point, 10 meters due south of the center of the target and at a height equal to half the height of the target, which puts the muzzle level with that center. From then on the target and every bullet travel in a straight line at constant velocity.

The drawing shows the target as the shooter sees it, so east is to the right and up is toward the first line.

Output

Treat the target as a flat sheet with no thickness and each bullet as a point with no volume. A bullet hits when it crosses the plane of the target inside a block that holds a non-whitespace character. A bullet that crosses the plane outside the drawing or inside a blank block does nothing, and a bullet that never reaches the plane because the target is running away at least as fast does nothing either. No bullet in the input passes near a block boundary, so plain arithmetic carried to four decimal places or better decides every case.

Print one result per data set, with exactly one blank line between consecutive results.

If no bullet hit the target, print

Got Out Da Way!

Otherwise print the target drawing again with every block that was hit replaced by an asterisk *. Each line keeps its original length.

Examples1

  1. Example 1

    Input
    START 3
    -10,-2,1
    300,14.5,-20
    350,-80,0
    400,28.75,26
         @@@@      n
         #^^#     oU
          ##     o
      ooooooooooo
      o oooooo
      o  oooo
     o   DDDD
    oo   DDDD
         D  D
         D  D
        TT  TT
        TT  TT
      <TTT  TTT>
    END
    START 2
    -10,-2,1
    300,14.5,-20
    350,-80,0
         @@@@      n
         #^^#     oU
          ##     o
      ooooooooooo
      o oooooo
      o  oooo
     o   DDDD
    oo   DDDD
         D  D
         D  D
        TT  TT
        TT  TT
      <TTT  TTT>
    END
    
    Expected output
         @@@@      *
         #^^#     oU
          ##     o
      ooooooooooo
      o oooooo
      o  oooo
     o   DDDD
    oo   DDDD
         D  D
         D  D
        TT  TT
        TT  TT
      <TTT  TTT>
    
    Got Out Da Way!