E. Santa Claus and Tangerines

Codeforces

IDCF752E

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresdptwo pointers

English · Original

Chinese · Translation

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] 个学生，使得每个人都能得到一些东西。

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": "CF752E"
  },
  "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"
    }
  ]
}

Full JSON Raw Segments