A. Lesha and array splitting

Codeforces

IDCF754A

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsgreedyimplementation

English · Original

Chinese · Translation

Formal · Original

One spring day on his way to university Lesha found an array _A_. Lesha likes to split arrays into several parts. This time Lesha decided to split the array _A_ into several, possibly one, new arrays so that the sum of elements in each of the new arrays is not zero. One more condition is that if we place the new arrays one after another they will form the old array _A_. Lesha is tired now so he asked you to split the array. Help Lesha! ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 100) — the number of elements in the array _A_. The next line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 103 ≤ _a__i_ ≤ 103) — the elements of the array _A_. ## Output If it is not possible to split the array _A_ and satisfy all the constraints, print single line containing "_NO_" (without quotes). Otherwise in the first line print "_YES_" (without quotes). In the next line print single integer _k_ — the number of new arrays. In each of the next _k_ lines print two integers _l__i_ and _r__i_ which denote the subarray _A_\[_l__i_... _r__i_\] of the initial array _A_ being the _i_\-th new array. Integers _l__i_, _r__i_ should satisfy the following conditions: * _l_1 = 1 * _r__k_ = _n_ * _r__i_ + 1 = _l__i_ + 1 for each 1 ≤ _i_ < _k_. If there are multiple answers, print any of them. [samples]

一个春天的早晨，Lesha 在去大学的路上发现了一个数组 $A$。Lesha 喜欢将数组拆分成若干部分。这一次，Lesha 决定将数组 $A$ 拆分成若干个（可能只有一个）新数组，使得每个新数组的元素之和不为零。另一个条件是，如果我们按顺序将这些新数组拼接起来，它们将重新组成原始数组 $A$。 Lesha 现在很累，所以他请你帮他拆分数组。请帮助 Lesha！第一行包含一个整数 $n$（$1 ≤ n ≤ 100$）— 数组 $A$ 中的元素个数。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$ - 10^3 ≤ a_i ≤ 10^3$）— 数组 $A$ 的元素。如果无法将数组 $A$ 拆分并满足所有约束，请输出一行 "_NO_"（不含引号）。否则，第一行输出 "_YES_"（不含引号）。第二行输出一个整数 $k$ —— 新数组的个数。接下来的 $k$ 行中，每行输出两个整数 $l_i$ 和 $r_i$，表示初始数组 $A$ 的子数组 $A[l_i... r_i]$ 作为第 $i$ 个新数组。整数 $l_i$, $r_i$ 应满足以下条件：如果有多个答案，输出任意一个即可。 ## Input 第一行包含一个整数 $n$（$1 ≤ n ≤ 100$）— 数组 $A$ 中的元素个数。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$ - 10^3 ≤ a_i ≤ 10^3$）— 数组 $A$ 的元素。 ## Output 如果无法将数组 $A$ 拆分并满足所有约束，请输出一行 "_NO_"（不含引号）。否则，第一行输出 "_YES_"（不含引号）。第二行输出一个整数 $k$ —— 新数组的个数。接下来的 $k$ 行中，每行输出两个整数 $l_i$ 和 $r_i$，表示初始数组 $A$ 的子数组 $A[l_i... r_i]$ 作为第 $i$ 个新数组。整数 $l_i$, $r_i$ 应满足以下条件： $l_1 = 1$，$r_k = n$，且对每个 $1 ≤ i < k$，有 $r_i + 1 = l_{i+1}$。如果有多个答案，输出任意一个即可。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the array. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \mathbb{Z} $ and $ -10^3 \leq a_i \leq 10^3 $. **Constraints** 1. $ 1 \leq n \leq 100 $ 2. The goal is to partition $ A $ into $ k \geq 1 $ contiguous non-empty subarrays $ A[1..r_1], A[r_1+1..r_2], \dots, A[r_{k-1}+1..n] $ such that: - Each subarray has a non-zero sum: $ \sum_{j=l_i}^{r_i} a_j \neq 0 $ for all $ i \in \{1, \dots, k\} $. - The subarrays are contiguous and cover $ A $ exactly: $ 1 = l_1 \leq r_1 < l_2 \leq r_2 < \dots < l_k \leq r_k = n $. **Objective** Determine if such a partition exists. If yes, output any valid partition as a sequence of intervals $ (l_i, r_i) $. If no such partition exists, output "_NO_".

Samples

Input #1

3
1 2 -3

Output #1

YES
2
1 2
3 3

Input #2

8
9 -12 3 4 -4 -10 7 3

Output #2

YES
2
1 2
3 8

Input #3

1
0

Output #3

NO

Input #4

4
1 2 3 -5

Output #4

API Response (JSON)

{
  "problem": {
    "name": "A. Lesha and array splitting",
    "description": {
      "content": "One spring day on his way to university Lesha found an array _A_. Lesha likes to split arrays into several parts. This time Lesha decided to split the array _A_ into several, possibly one, new arrays ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF754A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One spring day on his way to university Lesha found an array _A_. Lesha likes to split arrays into several parts. This time Lesha decided to split the array _A_ into several, possibly one, new arrays ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一个春天的早晨，Lesha 在去大学的路上发现了一个数组 $A$。Lesha 喜欢将数组拆分成若干部分。这一次，Lesha 决定将数组 $A$ 拆分成若干个（可能只有一个）新数组，使得每个新数组的元素之和不为零。另一个条件是，如果我们按顺序将这些新数组拼接起来，它们将重新组成原始数组 $A$。\n\nLesha 现在很累，所以他请你帮他拆分数组。请帮助 Lesha！\n\n第一行包含一个整数 $n$（$1...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z} $ and $ -10^3 \\leq a_i \\leq 10^3 $.\n\n*...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments