E. Fire and Ice

Codeforces

IDCF89E

Time2000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

The Fire Lord attacked the Frost Kingdom. He has already got to the Ice Fortress, where the Snow Queen dwells. He arranged his army on a segment _n_ in length not far from the city walls. And only the frost magician Solomon can save the Frost Kingdom. <center>![image](https://espresso.codeforces.com/4741bbfca80ae69e0f520e2d1382e89f29191685.png)</center>The _n_\-long segment is located at a distance equal exactly to 1 from the castle walls. It can be imaginarily divided into unit segments. On some of the unit segments _fire demons_ are located — no more than one demon per position. Each demon is characterised by his _strength_ - by some positive integer. We can regard the fire demons being idle. Initially Solomon is positioned on the fortress wall. He can perform the following actions several times in a row: * "_L_" — Solomon shifts one unit to the left. This movement cannot be performed on the castle wall. * "_R_" — Solomon shifts one unit to the left. This movement cannot be performed if there's no ice block to the right. * "_A_" — If there's nothing to the right of Solomon, then Solomon creates an ice block that immediately freezes to the block that Solomon is currently standing on. If there already is an ice block, then Solomon destroys it. At that the ice blocks to the right of the destroyed one can remain but they are left unsupported. Those ice blocks fall down. Solomon spends exactly a second on each of these actions. As the result of Solomon's actions, ice blocks' segments fall down. When an ice block falls on a fire demon, the block evaporates and the demon's strength is reduced by 1. When the demons' strength is equal to 0, the fire demon vanishes. The picture below shows how it happens. The ice block that falls on the position with no demon, breaks into lots of tiny pieces and vanishes without hurting anybody. <center>![image](https://espresso.codeforces.com/4095d5581a0443f05bb6fec515c0fb18deacd9d4.png)</center>Help Solomon destroy all the Fire Lord's army in minimum time. ## Input The first line contains an integer _n_ (1 ≤ _n_ ≤ 1000). The next line contains _n_ numbers, the _i_\-th of them represents the strength of the fire demon standing of the _i_\-th position, an integer from 1 to 100. If there's no demon on the _i_\-th position, then the _i_\-th number equals to 0. It is guaranteed that the input data have at least one fire demon. ## Output Print a string of minimum length, containing characters "_L_", "_R_" and "_A_" — the succession of actions leading to the required result. If there are several possible answers, print any of them. [samples]

火神袭击了霜之王国。他已抵达雪女王居住的冰堡，并在距城墙恰好距离为 #cf_span[1] 的一段长度为 #cf_span[n] 的区域上部署了他的军队。这段区域可被想象地划分为若干单位长度的段。某些单位段上分布着 _火魔_ —— 每个位置至多一个恶魔。每个恶魔具有其 _力量值_ —— 一个正整数。我们可以认为火魔处于静止状态。起初，所罗门位于城墙之上。他可以连续多次执行以下动作：所罗门执行每个动作恰好花费一秒。由于所罗门的动作，冰块会从城墙上落下。当冰块落在火魔身上时，冰块蒸发，该恶魔的力量值减少 #cf_span[1]。当恶魔的力量值降至 #cf_span[0] 时，该火魔消失。下图展示了这一过程。落在无恶魔位置的冰块会碎裂成无数微小碎片并消失，不会伤害任何人。请帮助所罗门以最少的时间摧毁火神的所有军队。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）。下一行包含 #cf_span[n] 个数字，第 #cf_span[i] 个数字表示位于第 #cf_span[i] 个位置的火魔的力量值，其为 #cf_span[1] 到 #cf_span[100] 之间的整数。若第 #cf_span[i] 个位置无恶魔，则该数字为 #cf_span[0]。保证输入数据至少包含一个火魔。请输出一个最短长度的字符串，由字符 "_L_"、"_R_" 和 "_A_" 组成，表示达成目标所需的行动序列。若存在多个可能的答案，输出任意一个即可。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）。下一行包含 #cf_span[n] 个数字，第 #cf_span[i] 个数字表示位于第 #cf_span[i] 个位置的火魔的力量值，其为 #cf_span[1] 到 #cf_span[100] 之间的整数。若第 #cf_span[i] 个位置无恶魔，则该数字为 #cf_span[0]。保证输入数据至少包含一个火魔。 ## Output 请输出一个最短长度的字符串，由字符 "_L_"、"_R_" 和 "_A_" 组成，表示达成目标所需的行动序列。若存在多个可能的答案，输出任意一个即可。 [samples]

Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 1000 $. Let $ a = (a_1, a_2, \dots, a_n) \in \{0, 1, \dots, 100\}^n $, where $ a_i $ is the strength of the fire demon at position $ i $, and $ a_i = 0 $ if no demon is present. Assume $ \sum_{i=1}^n [a_i > 0] \geq 1 $. Solomon starts at position $ 0 $ (beyond the left end of the segment). Each action takes 1 second and is one of: - **L**: move left by 1 unit (only possible if current position $ > 0 $), - **R**: move right by 1 unit (only possible if current position $ < n $), - **A**: attack (drop an ice block), reducing the demon strength at current position by 1 (if any). Goal: Reduce all $ a_i $ to 0 using a minimum-length sequence of actions, output as a string over $ \{L, R, A\} $. **Objective**: Find a shortest sequence $ s \in \{L, R, A\}^* $ such that, starting at position 0, executing $ s $ results in $ a_i = 0 $ for all $ i \in \{1, \dots, n\} $.

Samples

Input #1

3
1 0 1

Output #1

ARARARALLLA

Input #2

3
0 2 0

Output #2

ARARALAARALA

API Response (JSON)

{
  "problem": {
    "name": "E. Fire and Ice",
    "description": {
      "content": "The Fire Lord attacked the Frost Kingdom. He has already got to the Ice Fortress, where the Snow Queen dwells. He arranged his army on a segment _n_ in length not far from the city walls. And only the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF89E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Fire Lord attacked the Frost Kingdom. He has already got to the Ice Fortress, where the Snow Queen dwells. He arranged his army on a segment _n_ in length not far from the city walls. And only the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "火神袭击了霜之王国。他已抵达雪女王居住的冰堡，并在距城墙恰好距离为 #cf_span[1] 的一段长度为 #cf_span[n] 的区域上部署了他的军队。这段区域可被想象地划分为若干单位长度的段。某些单位段上分布着 _火魔_ —— 每个位置至多一个恶魔。每个恶魔具有其 _力量值_ —— 一个正整数。我们可以认为火魔处于静止状态。\n\n起初，所罗门位于城墙之上。他可以连续多次执行以下动作：\n\n所罗门执...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 1000 $.  \nLet $ a = (a_1, a_2, \\dots, a_n) \\in \\{0, 1, \\dots, 100\\}^n $, where $ a_i $ is the strength of the fire demon at position $ i $, and $ a_i = 0 $ if...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments