{"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_ (0 ≤ _i_ ≤ _m_).\n\nYou 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_.\n\n## Input\n\nThe first line contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 200000, 1 ≤ _k_ ≤ 1018). _n_ is the size of array _A_0.\n\nThe 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.\n\n## Output\n\nPrint the minimum _i_ such that _A__i_ contains a number which is larger or equal than _k_.\n\n[samples]","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_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] 的数。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200000]，#cf_span[1 ≤ k ≤ 1018]），其中 #cf_span[n] 是数组 #cf_span[A0] 的大小。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[A00, A01... A0n - 1] —— 数组 #cf_span[A0] 的元素（#cf_span[0 ≤ A0i ≤ 109]）。数组 #cf_span[A0] 中至少有两个正元素。\n\n请输出最小的 #cf_span[i]，使得 #cf_span[Ai] 中包含一个大于或等于 #cf_span[k] 的数。\n\n## Input\n\n第一行包含两个整数 #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] 中至少有两个正元素。\n\n## Output\n\n请输出最小的 #cf_span[i]，使得 #cf_span[Ai] 中包含一个大于或等于 #cf_span[k] 的数。\n\n[samples]","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 a_i \\leq 10^9 $ and at least two $ a_i > 0 $.  \n\nDefine 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}) $,  \n$$\np(x) = y, \\quad \\text{where} \\quad y_i = \\sum_{j=0}^{i-1} x_j \\quad \\text{for} \\quad 0 \\leq i \\leq m.\n$$  \nThat is, $ y $ is the prefix sum array of $ x $, of length $ m+1 $, with $ y_0 = 0 $.  \n\nDefine the sequence of arrays $ A_0, A_1, A_2, \\dots $ recursively by:  \n$$\nA_i = p(A_{i-1}) \\quad \\text{for all} \\quad i \\geq 1.\n$$  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 200000 $  \n2. $ 1 \\leq k \\leq 10^{18} $  \n3. $ A_0 \\in \\mathbb{Z}^n $, with $ \\sum_{i=0}^{n-1} a_i > 0 $ (since at least two elements are positive)  \n\n**Objective**  \nFind the minimum integer $ i \\geq 0 $ such that $ \\max(A_i) \\geq k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF837F","tags":["binary search","brute force","combinatorics","math","matrices"],"sample_group":[["2 2\n1 1","1"],["3 6\n1 1 1","2"],["3 1\n1 0 1","0"]],"created_at":"2026-03-03 11:00:39"}}