F. Prefix Sums

Codeforces

IDCF837F

Time1000ms

Memory256MB

Difficulty—

binary searchbrute forcecombinatoricsmathmatrices

English · Original

Chinese · Translation

Formal · Original

Consider the function _p_(_x_), where _x_ is an array of _m_ integers, which returns an array _y_ consisting of _m_ + 1 integers such that _y__i_ is equal to the sum of first _i_ elements of array _x_ (0 ≤ _i_ ≤ _m_). You have an infinite sequence of arrays _A_0, _A_1, _A_2..., where _A_0 is given in the input, and for each _i_ ≥ 1 _A__i_ = _p_(_A__i_ - 1). Also you have a positive integer _k_. You have to find minimum possible _i_ such that _A__i_ contains a number which is larger or equal than _k_. ## Input The first line contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 200000, 1 ≤ _k_ ≤ 1018). _n_ is the size of array _A_0. The second line contains _n_ integers _A_00, _A_01... _A_0_n_ - 1 — the elements of _A_0 (0 ≤ _A_0_i_ ≤ 109). At least two elements of _A_0 are positive. ## Output Print the minimum _i_ such that _A__i_ contains a number which is larger or equal than _k_. [samples]

考虑函数 #cf_span[p(x)]，其中 #cf_span[x] 是一个包含 #cf_span[m] 个整数的数组，该函数返回一个包含 #cf_span[m + 1] 个整数的数组 #cf_span[y]，使得 #cf_span[yi] 等于数组 #cf_span[x] 的前 #cf_span[i] 个元素之和（#cf_span[0 ≤ i ≤ m]）。你有一个无限序列的数组 #cf_span[A0, A1, A2...]，其中 #cf_span[A0] 在输入中给出，且对于每个 #cf_span[i ≥ 1]，有 #cf_span[Ai = p(Ai - 1)]。同时给你一个正整数 #cf_span[k]。你需要找到最小的 #cf_span[i]，使得 #cf_span[Ai] 中包含一个大于或等于 #cf_span[k] 的数。第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200000]，#cf_span[1 ≤ k ≤ 1018]），其中 #cf_span[n] 是数组 #cf_span[A0] 的大小。第二行包含 #cf_span[n] 个整数 #cf_span[A00, A01... A0n - 1] —— 数组 #cf_span[A0] 的元素（#cf_span[0 ≤ A0i ≤ 109]）。数组 #cf_span[A0] 中至少有两个正元素。请输出最小的 #cf_span[i]，使得 #cf_span[Ai] 中包含一个大于或等于 #cf_span[k] 的数。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200000]，#cf_span[1 ≤ k ≤ 1018]），其中 #cf_span[n] 是数组 #cf_span[A0] 的大小。第二行包含 #cf_span[n] 个整数 #cf_span[A00, A01... A0n - 1] —— 数组 #cf_span[A0] 的元素（#cf_span[0 ≤ A0i ≤ 109]）。数组 #cf_span[A0] 中至少有两个正元素。 ## Output 请输出最小的 #cf_span[i]，使得 #cf_span[Ai] 中包含一个大于或等于 #cf_span[k] 的数。 [samples]

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 2 \leq n \leq 200000 $, $ 1 \leq k \leq 10^{18} $. Let $ A_0 = (a_0, a_1, \dots, a_{n-1}) \in \mathbb{Z}^n $ be the initial array, with $ 0 \leq a_i \leq 10^9 $ and at least two $ a_i > 0 $. Define the operator $ p: \mathbb{Z}^m \to \mathbb{Z}^{m+1} $ such that for any array $ x = (x_0, x_1, \dots, x_{m-1}) $, $$ p(x) = y, \quad \text{where} \quad y_i = \sum_{j=0}^{i-1} x_j \quad \text{for} \quad 0 \leq i \leq m. $$ That is, $ y $ is the prefix sum array of $ x $, of length $ m+1 $, with $ y_0 = 0 $. Define the sequence of arrays $ A_0, A_1, A_2, \dots $ recursively by: $$ A_i = p(A_{i-1}) \quad \text{for all} \quad i \geq 1. $$ **Constraints** 1. $ 2 \leq n \leq 200000 $ 2. $ 1 \leq k \leq 10^{18} $ 3. $ A_0 \in \mathbb{Z}^n $, with $ \sum_{i=0}^{n-1} a_i > 0 $ (since at least two elements are positive) **Objective** Find the minimum integer $ i \geq 0 $ such that $ \max(A_i) \geq k $.

Samples

Input #1

2 2
1 1

Output #1

Input #2

3 6
1 1 1

Output #2

Input #3

3 1
1 0 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "F. Prefix Sums",
    "description": {
      "content": "Consider the function _p_(_x_), where _x_ is an array of _m_ integers, which returns an array _y_ consisting of _m_ + 1 integers such that _y__i_ is equal to the sum of first _i_ elements of array _x_",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF837F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider the function _p_(_x_), where _x_ is an array of _m_ integers, which returns an array _y_ consisting of _m_ + 1 integers such that _y__i_ is equal to the sum of first _i_ elements of array _x_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "考虑函数 #cf_span[p(x)]，其中 #cf_span[x] 是一个包含 #cf_span[m] 个整数的数组，该函数返回一个包含 #cf_span[m + 1] 个整数的数组 #cf_span[y]，使得 #cf_span[yi] 等于数组 #cf_span[x] 的前 #cf_span[i] 个元素之和（#cf_span[0 ≤ i ≤ m]）。\n\n你有一个无限序列的数组 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 200000 $, $ 1 \\leq k \\leq 10^{18} $.  \nLet $ A_0 = (a_0, a_1, \\dots, a_{n-1}) \\in \\mathbb{Z}^n $ be the initial array, with $ 0 \\leq ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments