A. Equator

Codeforces

IDCF962A

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Polycarp has created his own training plan to prepare for the programming contests. He will train for $n$ days, all days are numbered from $1$ to $n$, beginning from the first. On the $i$\-th day Polycarp will necessarily solve $a_i$ problems. One evening Polycarp plans to celebrate the _equator_. He will celebrate it on the first evening of such a day that from the beginning of the training and to this day inclusive he will solve half or more of all the problems. Determine the index of day when Polycarp will celebrate the equator. ## Input The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of days to prepare for the programming contests. The second line contains a sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10\,000$), where $a_i$ equals to the number of problems, which Polycarp will solve on the $i$\-th day. ## Output Print the index of the day when Polycarp will celebrate the equator. [samples] ## Note In the first example Polycarp will celebrate the equator on the evening of the second day, because up to this day (inclusive) he will solve $4$ out of $7$ scheduled problems on four days of the training. In the second example Polycarp will celebrate the equator on the evening of the third day, because up to this day (inclusive) he will solve $6$ out of $12$ scheduled problems on six days of the training.

Polycarp 制定了自己的训练计划以准备编程竞赛。他将训练 $n$ 天，所有天数从 $1$ 到 $n$ 编号，从第一天开始。在第 $i$ 天，Polycarp 必须解决 $a_i$ 道题。某天晚上，他计划庆祝“昼夜平分点”。他将在第一个满足如下条件的晚上庆祝：从训练开始到该天（含）为止，他解决的题目数量达到或超过总题目数的一半。请确定 Polycarp 庆祝昼夜平分点的那一天的编号。第一行包含一个整数 $n$（$1 lt.eq n lt.eq 200 thin 000$）——准备编程竞赛的天数。第二行包含一个序列 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10 thin 000$），其中 $a_i$ 表示 Polycarp 在第 $i$ 天解决的题目数量。请输出 Polycarp 庆祝昼夜平分点的那一天的编号。在第一个例子中，Polycarp 将在第二天晚上庆祝昼夜平分点，因为到该天（含）为止，他在四天训练中总共解决了 $4$ 道题，而总题数为 $7$。在第二个例子中，Polycarp 将在第三天晚上庆祝昼夜平分点，因为到该天（含）为止，他在六天训练中总共解决了 $6$ 道题，而总题数为 $12$。 ## Input 第一行包含一个整数 $n$（$1 lt.eq n lt.eq 200 thin 000$）——准备编程竞赛的天数。第二行包含一个序列 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10 thin 000$），其中 $a_i$ 表示 Polycarp 在第 $i$ 天解决的题目数量。 ## Output 请输出 Polycarp 庆祝昼夜平分点的那一天的编号。 [samples] ## Note 在第一个例子中，Polycarp 将在第二天晚上庆祝昼夜平分点，因为到该天（含）为止，他在四天训练中总共解决了 $4$ 道题，而总题数为 $7$。在第二个例子中，Polycarp 将在第三天晚上庆祝昼夜平分点，因为到该天（含）为止，他在六天训练中总共解决了 $6$ 道题，而总题数为 $12$。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of days. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of problems solved on day $ i $. Let $ S = \sum_{i=1}^n a_i $ be the total number of problems to be solved over all days. **Constraints** 1. $ 1 \leq n \leq 200{,}000 $ 2. $ 1 \leq a_i \leq 10{,}000 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the smallest index $ k \in \{1, \dots, n\} $ such that: $$ \sum_{i=1}^k a_i \geq \left\lceil \frac{S}{2} \right\rceil $$

Samples

Input #1

4
1 3 2 1

Output #1

Input #2

6
2 2 2 2 2 2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Equator",
    "description": {
      "content": "Polycarp has created his own training plan to prepare for the programming contests. He will train for $n$ days, all days are numbered from $1$ to $n$, beginning from the first. On the $i$\\-th day Pol",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF962A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has created his own training plan to prepare for the programming contests. He will train for $n$ days, all days are numbered from $1$ to $n$, beginning from the first.\n\nOn the $i$\\-th day Pol...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 制定了自己的训练计划以准备编程竞赛。他将训练 $n$ 天，所有天数从 $1$ 到 $n$ 编号，从第一天开始。\n\n在第 $i$ 天，Polycarp 必须解决 $a_i$ 道题。某天晚上，他计划庆祝“昼夜平分点”。他将在第一个满足如下条件的晚上庆祝：从训练开始到该天（含）为止，他解决的题目数量达到或超过总题目数的一半。\n\n请确定 Polycarp 庆祝昼夜平分点的那一天的编号。\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of days.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of problems solved on day $ i $. ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments