루미 알고리즘

#1407골드Robotoptimering

PO 2016 온라인 예선코딩출제 Johan Sannemo och Anton Grensjö영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

There's a robot in an R × C grid, where some unit squares are blocked so that the robot cannot walk on the square. Now she wants to move to another square, and has asked her owner to program her to do this. This owner happens to be you.

To transfer the code to a robot from your computer requires a lot of energy, so you want to make the program as short as possible - this means using as few commands as possible. As everyone knows, the robot programming language looks as follows:

  • forward Move the robot forward a single step in its current direction.
  • right Rotate 90 degrees clockwise.
  • left Rotate 90 degrees counterclockwise.
  • for X { A1 A2 ... An } Repeat the commands A1, A2, ..., An X times.
  • call X Add your current position in the program to the top of the call stack, then jump to the instruction with label X.
  • return Remove the last added position from the call stack, and continue execution at the instruction directly after it. In other words, a return resumes at the line following the call that put the position on the stack.
  • gotoblocked X Jump to the instruction with label X, if the robot cannot move forward, i.e. if the square in front of the robot is blocked or lies outside the grid.

A label has the syntax labelname:, and may not contain any whitespaces. A label cannot be inside a loop. The execution starts at the label called main.

Example program

walkandreturn:
  for 100 {
    forward
  }
  gotoblocked done
  right
  right
  for 100 {
    forward
  }
done:
  return

main:
  for 100 {
    call walkandreturn
    right
  }

Note that there is no concept of a function; if the return was not present in walkandreturn, the execution would continue down, running main.

When the robot tries to move towards the edge of the grid, or a blocked square, it doesn't move. When the robot reaches her target square, she wins, even if she doesn't stop on the square.

Input

Input consists of 10 different grids, which you can download from attachments at the bottom of the page. In the results page, the testcases are ordered lexicographically. This means that group 1 is robot_concentric.in, group 2 is robot_cross.in, etc.

Each grid is formatted as follows:

The first line contains the testcase name.

The next line contains two integers R and C (1 ≤ R,C ≤ 1000), the number of rows and columns in the grid.

The following R lines each describe a row of the grid. Each row consists of exactly C squares, each described by one of the following characters:

  • . free square
  • # blocked square
  • M goal square
  • <>^v start square, indicating the direction of the robot (in the order left, right, up, down).

There is exactly one goal and one start square.

Output

For the given maze, output a valid program on the form described above, that moves the robot from its starting position to the end position.

Additional details

As soon as the robot moves on top of the goal square, the execution is stopped, and you receive an Accepted verdict for said testcase. If you do not reach the goal in 10^8 instructions, you instead get Wrong Answer. Every executed command counts as one instruction, and each iteration of a loop counts as one additional instruction. Labels are free. If execution runs past the last instruction, you get Wrong Answer.

The program is a sequence of tokens separated by whitespace. Any mix of spaces, tabs and line breaks works, and the { and } of a loop are themselves tokens. In a loop for X { ... }, the number of repetitions X must satisfy 1 ≤ X ≤ 10^8.

The call stack may never contain more than 2 · 10^6 positions at the same time. If a call would exceed this, you get Wrong Answer.

If a jump is initiated because of a gotoblocked instruction, the state of every loop is reset. If a jump is initiated because of a call instruction, the state of every loop is saved on the call stack, and they are then reset. If a return statement is executed, the state of all loops will be set to the saved state on the top of the call stack.

The judges guarantee that there exists a program that attains full score under these constraints.

Submission

To make it easier to submit your solution, a sample submission is provided, which you can download from attachments at the bottom of the page. This submission will get 0 points, but contains valid programs.

Scoring

The scoring is based on the length of your program. The length is the number of times you use one of the listed commands in your program. Our example program has length 11. In particular, labels do not contribute to the length.

If your length on a particular test case is L and the shortest length on this case found by the judges is B, then your score on the testcase is

10 (1 - ((L - B)/L)^2)

Finally, the score per testcase is clamped to the range [0,10].

출처 표기

출처: Programmeringsolympiaden 2016년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.