E. Santa Claus and Tangerines

Codeforces

IDCF748E

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresgreedytwo pointers

English · Original

Chinese · Translation

Formal · Original

Santa Claus has _n_ tangerines, and the _i_\-th of them consists of exactly _a__i_ slices. Santa Claus came to a school which has _k_ pupils. Santa decided to treat them with tangerines. However, there can be too few tangerines to present at least one tangerine to each pupil. So Santa decided to divide tangerines into parts so that no one will be offended. In order to do this, he can divide a tangerine or any existing part into two smaller equal parts. If the number of slices in the part he wants to split is odd, then one of the resulting parts will have one slice more than the other. It's forbidden to divide a part consisting of only one slice. **Santa Claus wants to present to everyone either a whole tangerine or exactly one part of it** (that also means that everyone must get a positive number of slices). One or several tangerines or their parts may stay with Santa. Let _b__i_ be the number of slices the _i_\-th pupil has in the end. Let Santa's _joy_ be the minimum among all _b__i_'s. Your task is to find the maximum possible _joy_ Santa can have after he treats everyone with tangerines (or their parts). ## Input The first line contains two positive integers _n_ and _k_ (1 ≤ _n_ ≤ 106, 1 ≤ _k_ ≤ 2·109) denoting the number of tangerines and the number of pupils, respectively. The second line consists of _n_ positive integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 107), where _a__i_ stands for the number of slices the _i_\-th tangerine consists of. ## Output If there's no way to present a tangerine or a part of tangerine to everyone, print _\-1_. Otherwise, print the maximum possible _joy_ that Santa can have. [samples] ## Note In the first example Santa should divide the second tangerine into two parts with 5 and 4 slices. After that he can present the part with 5 slices to the first pupil and the whole first tangerine (with 5 slices, too) to the second pupil. In the second example Santa should divide both tangerines, so that he'll be able to present two parts with 6 slices and two parts with 7 slices. In the third example Santa Claus can't present 2 slices to 3 pupils in such a way that everyone will have anything.

圣诞老人有 #cf_span[n] 个橘子，第 #cf_span[i] 个橘子恰好由 #cf_span[ai] 片组成。圣诞老人来到一所有 #cf_span[k] 名学生的学校，决定用橘子招待他们。然而，橘子的数量可能不足以给每个学生至少一个橘子。因此，圣诞老人决定将橘子分割成更小的部分，以确保每个人都不会被冒犯。为此，他可以将一个橘子或任何已有的部分分割成两个更小的相等部分。如果他要分割的部分包含奇数片，则其中一个结果部分将比另一个多一片。禁止分割仅由一片组成的部分。 *圣诞老人希望每位学生要么得到一个完整的橘子，要么恰好得到它的一个部分*（这意味着每个人必须获得正数的片数）。一个或多个橘子或其部分可以留给圣诞老人。令 #cf_span[bi] 表示第 #cf_span[i] 个学生最终获得的片数。定义圣诞老人的 _喜悦值_ 为所有 #cf_span[bi] 中的最小值。你的任务是找出在圣诞老人招待完所有学生（或其部分）后，可能达到的最大 _喜悦值_。第一行包含两个正整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 106]，#cf_span[1 ≤ k ≤ 2·109]），分别表示橘子的数量和学生的数量。第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 107]），其中 #cf_span[ai] 表示第 #cf_span[i] 个橘子的片数。如果无法给每个学生分到一个橘子或其一部分，请输出 _-1_。否则，输出圣诞老人可能获得的最大 _喜悦值_。在第一个例子中，圣诞老人应将第二个橘子分割成包含 #cf_span[5] 片和 #cf_span[4] 片的两部分。之后，他可以将包含 #cf_span[5] 片的部分给第一个学生，将第一个完整的橘子（也包含 #cf_span[5] 片）给第二个学生。在第二个例子中，圣诞老人应分割两个橘子，以便能够提供两个包含 #cf_span[6] 片的部分和两个包含 #cf_span[7] 片的部分。在第三个例子中，圣诞老人无法将 #cf_span[2] 片分给 #cf_span[3] 个学生，使得每个人都能获得一些片数。 ## Input 第一行包含两个正整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 106]，#cf_span[1 ≤ k ≤ 2·109]），分别表示橘子的数量和学生的数量。第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 107]），其中 #cf_span[ai] 表示第 #cf_span[i] 个橘子的片数。 ## Output 如果无法给每个学生分到一个橘子或其一部分，请输出 _-1_。否则，输出圣诞老人可能获得的最大 _喜悦值_。 [samples] ## Note 在第一个例子中，圣诞老人应将第二个橘子分割成包含 #cf_span[5] 片和 #cf_span[4] 片的两部分。之后，他可以将包含 #cf_span[5] 片的部分给第一个学生，将第一个完整的橘子（也包含 #cf_span[5] 片）给第二个学生。在第二个例子中，圣诞老人应分割两个橘子，以便能够提供两个包含 #cf_span[6] 片的部分和两个包含 #cf_span[7] 片的部分。在第三个例子中，圣诞老人无法将 #cf_span[2] 片分给 #cf_span[3] 个学生，使得每个人都能获得一些片数。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of tangerines, $ k \in \mathbb{Z}^+ $ the number of pupils. Let $ A = (a_1, a_2, \dots, a_n) $ with $ a_i \in \mathbb{Z}^+ $ be the slice counts of the tangerines. A *part* is a positive integer number of slices obtainable by recursively splitting tangerines: - A tangerine of $ s $ slices can be split into $ \left\lfloor \frac{s}{2} \right\rfloor $ and $ \left\lceil \frac{s}{2} \right\rceil $ if $ s > 1 $. - Splitting is repeated arbitrarily, but parts of size 1 cannot be split further. Let $ P \subseteq \mathbb{Z}^+ $ be the multiset of all possible parts obtainable from $ A $ via splitting. **Constraints** 1. $ 1 \leq n \leq 10^6 $ 2. $ 1 \leq k \leq 2 \cdot 10^9 $ 3. $ 1 \leq a_i \leq 10^7 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the maximum integer $ j \in \mathbb{Z}^+ $ such that at least $ k $ parts of size $ \geq j $ can be obtained from $ A $ via splitting. If no such $ j $ exists (i.e., total number of obtainable parts $ < k $), output $ -1 $. Equivalently: Let $ f(j) = $ total number of parts of size $ \geq j $ obtainable from $ A $. Maximize $ j $ such that $ f(j) \geq k $.

Samples

Input #1

3 2
5 9 3

Output #1

Input #2

2 4
12 14

Output #2

Input #3

2 3
1 1

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "E. Santa Claus and Tangerines",
    "description": {
      "content": "Santa Claus has _n_ tangerines, and the _i_\\-th of them consists of exactly _a__i_ slices. Santa Claus came to a school which has _k_ pupils. Santa decided to treat them with tangerines. However, the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF748E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Santa Claus has _n_ tangerines, and the _i_\\-th of them consists of exactly _a__i_ slices. Santa Claus came to a school which has _k_ pupils. Santa decided to treat them with tangerines.\n\nHowever, the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "圣诞老人有 #cf_span[n] 个橘子，第 #cf_span[i] 个橘子恰好由 #cf_span[ai] 片组成。圣诞老人来到一所有 #cf_span[k] 名学生的学校，决定用橘子招待他们。\n\n然而，橘子的数量可能不足以给每个学生至少一个橘子。因此，圣诞老人决定将橘子分割成更小的部分，以确保每个人都不会被冒犯。为此，他可以将一个橘子或任何已有的部分分割成两个更小的相等部分。如果他要分割的部...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of tangerines, $ k \\in \\mathbb{Z}^+ $ the number of pupils.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ with $ a_i \\in \\mathbb{Z}^+ $ be the slice c...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments