This page is still under construction.

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

Gears on a Board

Time limit1sMemory limit128 MB

Summary
Determine each gear's rotation direction and speed from the motor, propagating through same-level ring contacts, and report overlap or conflicting rotation errors.
Level

Medium7 of 10

Topics
Graph, BFS, Geometry, Simulation
Solved
No attempts yet

Problem

An engineering firm, "Gears R Us," needs a program that evaluates how gears turn on a board. The board is a two-dimensional mounting plane. Every gear has two levels of teeth: an inner level (the ring closest to the board, of radius irir) and an outer level (the ring farther from the board, of radius oror). A gear rotates about the center of its axle, and both of its levels always share the same angular velocity.

Two gears interact only when a ring of one gear exactly touches a ring of the other at the same level -- inner touches inner, or outer touches outer. Where they touch, the two rings have equal tangential velocity, so the driven gear turns in the opposite direction to the gear driving it. Because tangential velocity v=ωrv = \omega r is shared at the contact point, a gear spinning at angular velocity ωA\omega_A through a ring of radius rAr_A drives a ring of radius rBr_B at angular velocity ωB=ωA⋅rA/rB\omega_B = \omega_A \cdot r_A / r_B.

Boards are square, with a 300×300300 \times 300 grid of mounting holes on 1 cm centers. The lower-left hole is x=1,y=1x = 1, y = 1 and the upper-right hole is x=300,y=300x = 300, y = 300. Gears mount only on holes, and each radius is an integer from 1 to 100. The motor is the only source of power on a board; it is powered from behind the board but is otherwise an ordinary gear subject to every rule above.

board diagram

Your program must also detect two error conditions. An overlap error occurs when two or more gears would overlap at their inner rings or at their outer rings (touching exactly is allowed; overlapping is not). A conflict error occurs when some gear is driven at two or more different speeds or directions -- it is perfectly valid, though, for several gears to drive one gear at the same speed and in the same direction. If both errors are present, report the overlap error.

A gear that is not connected to the motor never turns (rotation 0.000.00); report this as an idle-gear warning.

Input

The input contains an undetermined number of configurations, one after another, until end of file.

Each configuration begins with a line of six integers:

  • x yx\ y -- the motor's coordinates (1≤x,y≤3001 \le x, y \le 300);
  • ir orir\ or -- the motor's inner and outer radii (1≤ir,or≤1001 \le ir, or \le 100);
  • AVAV -- the motor's rotational speed in RPM (1≤∣AV∣≤10001 \le |AV| \le 1000; negative means counter-clockwise, positive means clockwise);
  • NGNG -- the number of gears on the board, excluding the motor (1≤NG≤201 \le NG \le 20).

Each of the next NGNG lines describes one gear, gear 1 through gear NGNG in order, with four integers: x yx\ y (its coordinates, 1≤x,y≤3001 \le x, y \le 300) and ir orir\ or (its inner and outer radii, 1≤ir,or≤1001 \le ir, or \le 100).

Output

For each configuration, print a result block.

The first line is Simulation #X, where X is the configuration number starting from 1 (the number begins in column 13, immediately after Simulation #).

If there is no error, print one line for each gear, gear 1 through gear NGNG:

  • the gear number, right-justified in columns 1-2;
  • a colon : in column 3;
  • in column 5, L if the gear turns counter-clockwise or R if it turns clockwise;
  • from column 7, the magnitude of the rotation in RPM, always printed with exactly two digits after the decimal point.

If a gear's rotation magnitude is zero, print Warning -- Idle Gear starting in column 5 instead of the direction and magnitude.

If there is an error, print only the Simulation #X line followed by exactly one error message, starting in column 1: Error -- Overlapping Gears for an overlap, or Error -- Conflicting Gear Rotation for a conflict. The overlap error takes precedence.

Print one blank line after each configuration's block.

Examples4

  1. Example 1

    Input
    20 100 5 5 -300 5
    43 100 18 10
    43 74 8 4
    71 100 10 15
    94 100 3 8
    122 100 25 6
    20 100 5 5 -300 5
    43 100 18 10
    43 74 8 4
    71 100 10 10
    89 100 3 8
    105 100 25 6
    20 100 5 5 -300 5
    43 100 18 10
    43 74 8 4
    71 100 10 10
    89 100 3 8
    125 100 25 6
    
    Expected output
    Simulation #1
     1: R 83.33
     2: L 187.50
     3: L 150.00
     4: R 281.25
     5: L 33.75
    
    Simulation #2
    Error -- Overlapping Gears
    
    Simulation #3
     1: R 83.33
     2: L 187.50
     3: L 150.00
     4: R 187.50
     5: Warning -- Idle Gear
    
  2. Example 2

    Input
    10 10 6 3 100 1
    10 20 4 3
    
    Expected output
    Simulation #1
     1: L 150.00
    
  3. Example 3

    Input
    20 100 5 5 -300 1
    43 100 18 10
    
    Expected output
    Simulation #1
     1: R 83.33
    
  4. Example 4

    Input
    10 10 5 5 -200 2
    10 20 5 5
    100 100 5 5
    
    Expected output
    Simulation #1
     1: R 200.00
     2: Warning -- Idle Gear