Under construction

Still being built. Things may change

Frogger's For Dinner

Time limit1sMemory limit128 MB

Summary
Simulate a frog walking down a 10 by 10 road while cars wrap around their lanes and decide if any starting column reaches the far side alive.
Level

Easy3 of 10

Topics
Simulation, Brute force, Matrix
Solved
No attempts yet

Problem

"Uncle Jacques," you ask, "what's for dinner?"

"Ask me again in ten minutes," he says, watching a tired-looking frog on the shoulder of the interstate in front of your run-down shack.

The frog starts across the busy road. You want to know whether to put a pot of water on for frog legs or reheat last night's possum, so you fire up the Swamp 'Puter XL2 and write a program that decides whether the frog reaches the far shoulder or ends up as roadkill.

The stretch of road in front of the shack is a 10 by 10 grid of squares. Rows 0 and 9 are the shoulders, rows 1 to 8 are the lanes, and the columns are numbered 0 to 9.

 row   0 1 2 3 4 5 6 7 8 9   <- column
  0    . . . . . . . . . .   starting shoulder
  1    . . . . . . . . . .   lane, traffic moves left
  2    . . . . . . . . . .   lane, traffic moves left
  3    . . . . . . . . . .   lane, traffic moves left
  4    . . . . . . . . . .   lane, traffic moves left
  5    . . . . . . . . . .   lane, traffic moves right
  6    . . . . . . . . . .   lane, traffic moves right
  7    . . . . . . . . . .   lane, traffic moves right
  8    . . . . . . . . . .   lane, traffic moves right
  9    . . . . . . . . . .   destination shoulder

The frog and the traffic move in turns.

  1. Before a run starts, the frog picks a square on row 0.
  2. Before a run starts, every vehicle sits in some column of rows 1 to 8.
  3. A turn has two steps. First the frog moves one row down toward row 9 and keeps its column, because this is not the smartest frog alive. Then every vehicle moves at the same instant, n squares left in rows 1 to 4 or n squares right in rows 5 to 8, where n is that vehicle's speed. A vehicle that leaves the grid wraps around and comes back from the other side: a vehicle bound for column -1 lands on column 9, column -2 lands on column 8, column 10 lands on column 0, column 11 lands on column 1, and so on.
  4. The frog crosses the interstate when at least one starting column on row 0 gets it to row 9 alive. It is not the dumbest frog alive either, so it takes such a column whenever one exists.
  5. The frog becomes roadkill the moment it shares a square with a vehicle. That happens in two ways: the frog moves down into a square a vehicle already occupies, or a vehicle runs the frog over by passing through or stopping on the frog's square.

Input

The input is not empty and holds at most 100 data sets. No blank line separates the data sets.

Each data set gives the starting state of one run in three parts.

  1. A single line reading START.
  2. Eight lines describing rows 1 to 8 in that order. Each line holds 10 integers separated by single spaces, one per column. A 0 means the square is empty. A value N with 1≤N≤91 \le N \le 9 means a vehicle occupies that square and moves at speed N. Every vehicle in a row has the same speed and all vehicles move at the same instant, so no vehicle ever passes over or lands on another vehicle.
  3. A single line reading END.

Output

Print exactly one line per data set. The line is either LEFTOVER POSSUM or FROGGER, in capitals, with no leading or trailing whitespace.

Print LEFTOVER POSSUM when at least one starting column on row 0 lets the frog reach row 9 alive. Print FROGGER otherwise.

Examples1

  1. Example 1

    Input
    START
    3 0 0 0 0 3 0 0 0 3
    1 0 0 0 1 0 0 0 0 0
    4 0 0 0 0 0 0 4 0 0
    0 0 2 0 0 0 0 0 0 2
    5 0 0 0 0 0 0 0 0 0
    0 2 0 0 0 0 0 2 0 2
    0 0 0 4 0 0 0 0 0 0
    0 2 0 0 0 0 0 0 0 0
    END
    START
    9 9 9 9 9 9 9 9 9 9
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    END
    START
    1 0 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 0 0 1 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    END
    
    Expected output
    FROGGER
    FROGGER
    LEFTOVER POSSUM