A. Pizza Separation

Codeforces

IDCF895A

Time1000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

Students Vasya and Petya are studying at the BSU (Byteland State University). At one of the breaks they decided to order a pizza. In this problem pizza is a circle of some radius. The pizza was delivered already cut into _n_ pieces. The _i_\-th piece is a sector of angle equal to _a__i_. Vasya and Petya want to divide all pieces of pizza into two _continuous_ sectors in such way that the difference between angles of these sectors is minimal. Sector angle is sum of angles of all pieces in it. Pay attention, that one of sectors can be empty. ## Input The first line contains one integer _n_ (1 ≤ _n_ ≤ 360) — the number of pieces into which the delivered pizza was cut. The second line contains _n_ integers _a__i_ (1 ≤ _a__i_ ≤ 360) — the angles of the sectors into which the pizza was cut. The sum of all _a__i_ is 360. ## Output Print one integer — the minimal difference between angles of sectors that will go to Vasya and Petya. [samples] ## Note In first sample Vasya can take 1 and 2 pieces, Petya can take 3 and 4 pieces. Then the answer is |(90 + 90) - (90 + 90)| = 0. In third sample there is only one piece of pizza that can be taken by only one from Vasya and Petya. So the answer is |360 - 0| = 360. In fourth sample Vasya can take 1 and 4 pieces, then Petya will take 2 and 3 pieces. So the answer is |(170 + 10) - (30 + 150)| = 0. Picture explaning fourth sample: ![image](https://espresso.codeforces.com/7aeb1713868b7fb0ae534eafef943af97abd11ae.png) Both red and green sectors consist of two adjacent pieces of pizza. So Vasya can take green sector, then Petya will take red sector.

学生 Vasya 和 Petya 在 BSU（Byteland 国立大学）学习。在一次休息时，他们决定点一份披萨。在本题中，披萨是一个半径为某值的圆。披萨被切成 #cf_span[n] 块，第 #cf_span[i] 块是一个角度为 #cf_span[ai] 的扇形。Vasya 和 Petya 希望将所有披萨块划分为两个 _连续_ 的扇形，使得这两个扇形的角度差最小。扇形的角度等于其中所有块的角度之和。请注意，其中一个扇形可以为空。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 360]) —— 披萨被切成的块数。第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 360]) —— 披萨被切成的各扇形的角度。所有 #cf_span[ai] 的和为 360。请输出一个整数 —— Vasya 和 Petya 所得扇形角度的最小差值。在第一个样例中，Vasya 可以取第 #cf_span[1] 和 #cf_span[2] 块，Petya 可以取第 #cf_span[3] 和 #cf_span[4] 块。此时答案为 #cf_span[|(90 + 90) - (90 + 90)| = 0]。在第三个样例中，只有一块披萨，只能由 Vasya 或 Petya 之一取走。因此答案为 #cf_span[|360 - 0| = 360]。在第四个样例中，Vasya 可以取第 #cf_span[1] 和 #cf_span[4] 块，Petya 则取第 #cf_span[2] 和 #cf_span[3] 块。因此答案为 #cf_span[|(170 + 10) - (30 + 150)| = 0]。第四个样例的图示：红色和绿色扇形均由两个相邻的披萨块组成。因此 Vasya 可以取绿色扇形，Petya 则取红色扇形。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 360]) —— 披萨被切成的块数。第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 360]) —— 披萨被切成的各扇形的角度。所有 #cf_span[ai] 的和为 360。 ## Output 请输出一个整数 —— Vasya 和 Petya 所得扇形角度的最小差值。 [samples] ## Note 在第一个样例中，Vasya 可以取第 #cf_span[1] 和 #cf_span[2] 块，Petya 可以取第 #cf_span[3] 和 #cf_span[4] 块。此时答案为 #cf_span[|(90 + 90) - (90 + 90)| = 0]。在第三个样例中，只有一块披萨，只能由 Vasya 或 Petya 之一取走。因此答案为 #cf_span[|360 - 0| = 360]。在第四个样例中，Vasya 可以取第 #cf_span[1] 和 #cf_span[4] 块，Petya 则取第 #cf_span[2] 和 #cf_span[3] 块。因此答案为 #cf_span[|(170 + 10) - (30 + 150)| = 0]。第四个样例的图示：红色和绿色扇形均由两个相邻的披萨块组成。因此 Vasya 可以取绿色扇形，Petya 则取红色扇形。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of pizza pieces. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers such that $ \sum_{i=1}^n a_i = 360 $. **Constraints** 1. $ 1 \leq n \leq 360 $ 2. $ 1 \leq a_i \leq 360 $ for all $ i \in \{1, \dots, n\} $ 3. The pizza pieces are arranged in a circular order; a continuous sector is a contiguous subsequence of pieces in this circular arrangement. **Objective** Find the minimum absolute difference between the sums of two complementary continuous sectors: $$ \min_{\substack{0 \leq i < j \leq n \\ \text{sector from } i \text{ to } j-1 \text{ (circular)}}} \left| \sum_{k=i}^{j-1} a_k - \left(360 - \sum_{k=i}^{j-1} a_k\right) \right| = \min \left| 2 \cdot S - 360 \right| $$ where $ S $ is the sum of angles in some continuous sector (possibly empty, i.e., $ S = 0 $).

Samples

Input #1

4
90 90 90 90

Output #1

Input #2

3
100 100 160

Output #2

Input #3

1
360

Output #3

Input #4

4
170 30 150 10

Output #4

API Response (JSON)

{
  "problem": {
    "name": "A. Pizza Separation",
    "description": {
      "content": "Students Vasya and Petya are studying at the BSU (Byteland State University). At one of the breaks they decided to order a pizza. In this problem pizza is a circle of some radius. The pizza was delive",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF895A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Students Vasya and Petya are studying at the BSU (Byteland State University). At one of the breaks they decided to order a pizza. In this problem pizza is a circle of some radius. The pizza was delive...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "学生 Vasya 和 Petya 在 BSU（Byteland 国立大学）学习。在一次休息时，他们决定点一份披萨。在本题中，披萨是一个半径为某值的圆。披萨被切成 #cf_span[n] 块，第 #cf_span[i] 块是一个角度为 #cf_span[ai] 的扇形。Vasya 和 Petya 希望将所有披萨块划分为两个 _连续_ 的扇形，使得这两个扇形的角度差最小。扇形的角度等于其中所有块的角度...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of pizza pieces.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers such that $ \\sum_{i=1}^n a_i = 360 $.  \n\n**Constraints...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments