A. Arya and Bran

Codeforces

IDCF839A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Bran and his older sister Arya are from the same house. Bran like candies so much, so Arya is going to give him some Candies. At first, Arya and Bran have 0 Candies. There are _n_ days, at the _i_\-th day, Arya finds _a__i_ candies in a box, that is given by the Many-Faced God. Every day she can give Bran **at most** 8 of her candies. If she don't give him the candies at the same day, they are saved for her and she can give them to him later. Your task is to find the minimum number of days Arya needs to give Bran _k_ candies **before** the end of the _n_\-th day. Formally, you need to output the minimum day index to the end of which _k_ candies will be given out (the days are indexed from 1 to _n_). Print _\-1_ if she can't give him _k_ candies during _n_ given days. ## Input The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 100, 1 ≤ _k_ ≤ 10000). The second line contains _n_ integers _a_1, _a_2, _a_3, ..., _a__n_ (1 ≤ _a__i_ ≤ 100). ## Output If it is impossible for Arya to give Bran _k_ candies within _n_ days, print _\-1_. Otherwise print a single integer — the minimum number of days Arya needs to give Bran _k_ candies before the end of the _n_\-th day. [samples] ## Note In the first sample, Arya can give Bran 3 candies in 2 days. In the second sample, Arya can give Bran 17 candies in 3 days, because she can give him at most 8 candies per day. In the third sample, Arya can't give Bran 9 candies, because she can give him at most 8 candies per day and she must give him the candies within 1 day.

Bran 和他的姐姐 Arya 来自同一个家族。Bran 非常喜欢糖果，因此 Arya 计划给他一些糖果。最初，Arya 和 Bran 都有 $0$ 颗糖果。共有 $n$ 天，在第 $i$ 天，Arya 会从 Many-Faced God 那里得到 $a_i$ 颗糖果。每天她最多可以给 Bran $8$ 颗糖果。如果当天没有给他糖果，这些糖果会被保留下来，供以后使用。你的任务是找出 Arya 在第 $n$ 天结束前给 Bran 总共 $k$ 颗糖果所需的最少天数。形式上，你需要输出最小的天数索引，使得在该索引对应的天结束时，已送出的糖果总数达到 $k$（天数从 $1$ 到 $n$ 编号）。如果在给定的 $n$ 天内 Arya 无法给 Bran $k$ 颗糖果，请输出 $-1$。第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 100$，$1 ≤ k ≤ 10000$）。第二行包含 $n$ 个整数 $a_1, a_2, a_3, ..., a_n$（$1 ≤ a_i ≤ 100$）。如果 Arya 在 $n$ 天内无法给 Bran $k$ 颗糖果，则输出 $-1$。否则，输出一个整数 —— Arya 在第 $n$ 天结束前给 Bran $k$ 颗糖果所需的最少天数。在第一个样例中，Arya 可以在 $2$ 天内给 Bran $3$ 颗糖果。在第二个样例中，Arya 可以在 $3$ 天内给 Bran $17$ 颗糖果，因为她每天最多只能给 $8$ 颗糖果。在第三个样例中，Arya 无法在 $1$ 天内给 Bran $9$ 颗糖果，因为她每天最多只能给 $8$ 颗糖果。 ## Input 第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 100$，$1 ≤ k ≤ 10000$）。第二行包含 $n$ 个整数 $a_1, a_2, a_3, ..., a_n$（$1 ≤ a_i ≤ 100$）。 ## Output 如果 Arya 在 $n$ 天内无法给 Bran $k$ 颗糖果，则输出 $-1$。否则，输出一个整数 —— Arya 在第 $n$ 天结束前给 Bran $k$ 颗糖果所需的最少天数。 [samples] ## Note 在第一个样例中，Arya 可以在 $2$ 天内给 Bran $3$ 颗糖果。在第二个样例中，Arya 可以在 $3$ 天内给 Bran $17$ 颗糖果，因为她每天最多只能给 $8$ 颗糖果。在第三个样例中，Arya 无法在 $1$ 天内给 Bran $9$ 颗糖果，因为她每天最多只能给 $8$ 颗糖果。

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ denote the number of days and the target number of candies to give Bran, respectively. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i $ is the number of candies Arya finds on day $ i $. Let $ c = 8 $ be the maximum number of candies Arya can give Bran per day. **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ 1 \leq k \leq 10000 $ 3. $ 1 \leq a_i \leq 100 $ for all $ i \in \{1, \dots, n\} $ 4. Each day $ i $, Arya may give Bran at most $ c = 8 $ candies, and may carry over unused candies from previous days. 5. Candies found on day $ i $ become available for giving on day $ i $ or later. **Objective** Find the minimum day index $ d \in \{1, \dots, n\} $ such that the total candies given to Bran by the end of day $ d $ is at least $ k $. If no such $ d $ exists, output $ -1 $. Formally, simulate day-by-day: - Let $ \text{stored} = 0 $ be the number of candies Arya has saved (not yet given). - For each day $ i = 1 $ to $ n $: - Update $ \text{stored} \leftarrow \text{stored} + a_i $ - Let $ \text{give}_i = \min(\text{stored}, 8) $ be the maximum candies Arya can give on day $ i $ - Update $ \text{stored} \leftarrow \text{stored} - \text{give}_i $ - Update cumulative given: $ \text{total\_given} \leftarrow \text{total\_given} + \text{give}_i $ - If $ \text{total\_given} \geq k $, return $ i $ - If loop completes and $ \text{total\_given} < k $, return $ -1 $ **Output** The smallest $ d \in \{1, \dots, n\} $ such that cumulative given $ \geq k $, or $ -1 $ if impossible.

Samples

Input #1

2 3
1 2

Output #1

Input #2

3 17
10 10 10

Output #2

Input #3

1 9
10

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "A. Arya and Bran",
    "description": {
      "content": "Bran and his older sister Arya are from the same house. Bran like candies so much, so Arya is going to give him some Candies. At first, Arya and Bran have 0 Candies. There are _n_ days, at the _i_\\-t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF839A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bran and his older sister Arya are from the same house. Bran like candies so much, so Arya is going to give him some Candies.\n\nAt first, Arya and Bran have 0 Candies. There are _n_ days, at the _i_\\-t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Bran 和他的姐姐 Arya 来自同一个家族。Bran 非常喜欢糖果，因此 Arya 计划给他一些糖果。\n\n最初，Arya 和 Bran 都有 $0$ 颗糖果。共有 $n$ 天，在第 $i$ 天，Arya 会从 Many-Faced God 那里得到 $a_i$ 颗糖果。每天她最多可以给 Bran $8$ 颗糖果。如果当天没有给他糖果，这些糖果会被保留下来，供以后使用。\n\n你的任务是找出 Ary...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ denote the number of days and the target number of candies to give Bran, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, w...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments