Back to School '16: Screensaver

View as PDF

Submit solution

Time limit:1.0s
Memory limit:64M

Problem type

On the first day of school, the computer science teacher shows a couple of impressive screensavers on the computer. The screensaver called :tim: stands out to you, mainly due to the simple rules that govern :tim:.

:tim: is a beautifully rendered three-dimensional arena with a couple of walls and the observer gets to bounce off these walls. The observer occasionally bounces out of the arena, which causes the animation to start again with a new set of walls.

The arena can be represented as a grid with N columns and M rows. Empty spaces are denoted with . and walls are denoted with the character -, |, / or \. The walls are similar to mirrors; the observer hits the surface of the wall and changes to the corresponding direction. The only exception to this rule is with - and | walls. The observer bounces off - when going vertically, and passes through when going horizontally. The same exception applies when going vertically through the | wall.

One notable feature of :tim: is that whenever the user bounces on a wall, that wall rotates 90 degrees. For example, when the user bounces off the wall with direction |, the wall now has direction -.

Every tick, the observer moves into an adjacent cell in the grid. The player can travel horizontally or vertically, but never diagonally. The observer begins at the cell containing O (not occupied by a wall) and initially moves horizontally to the right. The animation is reset once the observer leaves the grid.

Of course, you want to implement this screensaver yourself! You have the renderer up and running, but you want the screensaver to last more than T ticks. Given the grid, can you determine whether the requirement is satisfied?

Input Specification

The first line contains the integers N, M (1 \le N,M \le 100), and T (1 \le T \le 10\ 000).

On each of the next M lines, there are N characters. It is guaranteed that the character O appears exactly once.

Output Specification

If the observer stays within the grid for more than T ticks, output The observer stays within the grid.

Otherwise, output The observer leaves the grid after X tick(s).

Sample Input 1

4 4 100

Sample Output 1

The observer leaves the grid after 10 tick(s).

Sample Input 2

2 1 3

Sample Output 2

The observer leaves the grid after 3 tick(s).

Sample Input 3

2 1 2

Sample Output 3

The observer stays within the grid.


  • 4
     commented on Sept. 17, 2016, 8:22 p.m.
    Errors Fixed

    The sample test cases were correct, the problem statement has been fixed.

  • 1
     commented on Sept. 17, 2016, 4:01 p.m.

    same with sample input 2

  • 1
     commented on Sept. 17, 2016, 4:01 p.m.

    sample input 3 2 1 3 O| there are two columsn not ros

    • 0
       commented on Sept. 17, 2016, 4:19 p.m.

      yeah it's given as: width, height

      • 1
         commented on Sept. 17, 2016, 4:29 p.m.

        naw the setters goofed.

        The arena can be represented as a grid with NN rows and MM columns

  • 0
     commented on Sept. 17, 2016, 3:48 p.m.
    oh god