TLE '17 Contest 7 P6 - Base Bombing

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Fax and his squadrons attacking the base.

Fax McClad, Croneria's smartest bounty hunter, has found one of the Dankey Kang Gang's bases!

The Dankey Kang Gang base is made of a straight segment of N compartments numbered from 1 to N from left to right. The i^{th} compartment has a strength of s_i. Let compartment -1 and 0 be the space to the left of all other compartments.

Fax will attack the base using squadrons of Kyuwing bombers. Suppose Fax is over compartment i. Then, Fax can issue the following commands:

  • L - move to compartment i-1. This command cannot be issued if Fax is over compartment -1.
  • A - if there is no squadron over compartment i+1, order a new squadron to move to compartment i+1. If there is already squadron over compartment i+1, then that squadron retreats, which signals all other squadrons to the right (over compartments \ge i+2) to drop their bombs on the compartments they are over and retreat.
  • R - move to compartment i+1. This command can only be issued if there is a squadron over compartment i+1.

A compartment can only take s_i hits from bombs until it is destroyed.

Fax is initially to the left of all compartments (over compartment -1).

What is the minimum number of commands that Fax must issue to destroy the base and what should they be?


1 \le N \le 2\,000

0 \le s_i \le 100

At least one compartment will have s_i > 0.

For 20\% of the points, N \le 10.

Input Specification

The first line of input will contain N.

The next line will contain N integers. The i^{th} integer is s_i.

Output Specification

On a single line, output a string consisting of L, A, and R, denoting the commands that he should issue, in order. You may output any answer of minimum length.

Sample Input

0 0 1

Sample Output


Sample Explanation

The state when following the instructions will look like this:

- - 0 0 1    - - 0 0 1    - - 0 0 1    - - 0 0 1    - - 0 0 1    - - 0 0 1    - - 0 0 1    - - 0 0 1    - - 0 0 1    - - 0 0 0
               s            s            s s          s s          s s s        s s s        s s s s      s s s s      s s
^            ^              ^            ^              ^            ^              ^            ^          ^            ^

Note that compartment 2 was not hit by bombs.

Note: If the formatting appears incorrectly, please copy and paste the characters into a text editor.


There are no comments at the moment.