I. Derivative of Array

Codeforces

IDCF10018I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Let us define the derivatives of array in the following way: You are given n numbers b0, ..., bn - 1, each equals either to zero or to one. You are to build an array of length n so that its k-th derivative is strictly increasing if bk = 1 and strictly decreasing if bk = 0. Each element of array should be an integer from - 109 to 109, inclusively. If it is impossible, output _«IMPOSSIBLE»_. The first line contains the only integer n (1 ≤ n ≤ 2000) — the length of the array you are to build. The second line contains n integers b0, ..., bn - 1 (0 ≤ bi ≤ 1) separated by spaces. If bk = 1, k-th derivative of array should be strictly increasing, and if bk = 0 — strictly decreasing. Output n integers a1, ..., an — the array which derivatives satisfy all the conditions specified by numbers b0, ..., bn - 1. The elements of the array should not exceed 109 by absolute value. If there are several such arrays, you can output any of them. If there is no such array or some of its elements are greater than 109 by absolute value, output «_IMPOSSIBLE_». ## Input The first line contains the only integer n (1 ≤ n ≤ 2000) — the length of the array you are to build.The second line contains n integers b0, ..., bn - 1 (0 ≤ bi ≤ 1) separated by spaces. If bk = 1, k-th derivative of array should be strictly increasing, and if bk = 0 — strictly decreasing. ## Output Output n integers a1, ..., an — the array which derivatives satisfy all the conditions specified by numbers b0, ..., bn - 1. The elements of the array should not exceed 109 by absolute value.If there are several such arrays, you can output any of them.If there is no such array or some of its elements are greater than 109 by absolute value, output «_IMPOSSIBLE_». [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 2000 $. Let $ \mathbf{b} = (b_0, b_1, \dots, b_{n-1}) \in \{0,1\}^n $ be a binary sequence. Let $ \mathbf{a} = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the target array. For $ k \in \{0, 1, \dots, n-1\} $, define the $ k $-th derivative $ \mathbf{a}^{(k)} $ recursively: - $ \mathbf{a}^{(0)} = \mathbf{a} $, - $ \mathbf{a}^{(k)} = \left( a_{i+1}^{(k-1)} - a_i^{(k-1)} \right)_{i=1}^{n-k} $ for $ k \geq 1 $. **Constraints** 1. For each $ k \in \{0, 1, \dots, n-1\} $: - If $ b_k = 1 $, then $ \mathbf{a}^{(k)} $ is strictly increasing: $$ a_{i+1}^{(k)} > a_i^{(k)} \quad \forall i \in \{1, \dots, n-k-1\} $$ - If $ b_k = 0 $, then $ \mathbf{a}^{(k)} $ is strictly decreasing: $$ a_{i+1}^{(k)} < a_i^{(k)} \quad \forall i \in \{1, \dots, n-k-1\} $$ 2. $ |a_i| \leq 10^9 $ for all $ i \in \{1, \dots, n\} $. **Objective** Find any $ \mathbf{a} \in \mathbb{Z}^n $ satisfying the above constraints, or output "IMPOSSIBLE" if none exists.

API Response (JSON)

{
  "problem": {
    "name": "I. Derivative of Array",
    "description": {
      "content": "Let us define the derivatives of array in the following way: You are given n numbers b0, ..., bn - 1, each equals either to zero or to one. You are to build an array of length n so that its k-th deri",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10018I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let us define the derivatives of array in the following way:\n\nYou are given n numbers b0, ..., bn - 1, each equals either to zero or to one. You are to build an array of length n so that its k-th deri...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 2000 $.  \nLet $ \\mathbf{b} = (b_0, b_1, \\dots, b_{n-1}) \\in \\{0,1\\}^n $ be a binary sequence.  \nLet $ \\mathbf{a} = (a_1, a_2, \\dots, a...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments