B. New Year's Eve

Codeforces

IDCF912B

Time1000ms

Memory256MB

Difficulty—

bitmasksconstructive algorithmsnumber theory

English · Original

Chinese · Translation

Formal · Original

Since Grisha behaved well last year, at New Year's Eve he was visited by Ded Moroz who brought an enormous bag of gifts with him! The bag contains _n_ sweet candies from _the good ol' bakery_, each labeled from 1 to _n_ corresponding to its tastiness. No two candies have the same tastiness. The choice of candies has a direct effect on Grisha's happiness. One can assume that he should take the tastiest ones — but no, the holiday magic turns things upside down. It is the xor-sum of tastinesses that matters, not the ordinary sum! A xor-sum of a sequence of integers _a_1, _a_2, ..., _a__m_ is defined as the bitwise XOR of all its elements: , here denotes the bitwise XOR operation; more about bitwise XOR can be found [here.](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) Ded Moroz warned Grisha he has more houses to visit, so Grisha can take **no more than _k_** candies from the bag. Help Grisha determine the largest xor-sum (largest xor-sum means maximum happiness!) he can obtain. ## Input The sole string contains two integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 1018). ## Output Output one number — the largest possible xor-sum. [samples] ## Note In the first sample case, one optimal answer is 1, 2 and 4, giving the xor-sum of 7. In the second sample case, one can, for example, take all six candies and obtain the xor-sum of 7.

由于 Grisha 去年表现良好，除夕夜他被圣诞老人拜访，后者带来了一个装满礼物的巨大袋子！袋子里有 #cf_span[n] 颗来自 _传统烘焙店_ 的糖果，每颗糖果的美味度从 #cf_span[1] 到 #cf_span[n] 标记，且每颗糖果的美味度互不相同。糖果的选择直接影响 Grisha 的幸福感。人们可能会认为他应该拿最美味的糖果——但不对，节日的魔法让事情颠倒了！决定幸福感的是美味度的交错和，而不是普通的和！一个整数序列 #cf_span[a1, a2, ..., am] 的交错和定义为其中所有元素的按位异或：，这里表示按位异或操作；有关按位异或的更多信息请参见此处。圣诞老人提醒 Grisha 他还要去其他房子，因此 Grisha 最多只能从袋子里拿 *不超过 #cf_span[k]* 颗糖果。请帮助 Grisha 确定他能获得的最大交错和（最大的交错和意味着最大的幸福感！）。输入仅包含一行，包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ k ≤ n ≤ 1018])。请输出一个数字——可能的最大交错和。在第一个样例中，一个最优解是拿 #cf_span[1]、#cf_span[2] 和 #cf_span[4]，得到交错和 #cf_span[7]。在第二个样例中，例如可以拿全部六颗糖果，得到交错和 #cf_span[7]。 ## Input 输入仅包含一行，包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ k ≤ n ≤ 1018])。 ## Output 请输出一个数字——可能的最大交错和。 [samples] ## Note 在第一个样例中，一个最优解是拿 #cf_span[1]、#cf_span[2] 和 #cf_span[4]，得到交错和 #cf_span[7]。在第二个样例中，例如可以拿全部六颗糖果，得到交错和 #cf_span[7]。

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 1 \leq k \leq n \leq 10^{18} $. Let $ S = \{1, 2, \dots, n\} $ be the set of candy tastiness values. **Objective** Find the maximum possible XOR-sum over all subsets $ T \subseteq S $ such that $ |T| \leq k $. **Constraint** $ |T| \leq k $, where $ T \subseteq \{1, 2, \dots, n\} $ **Goal** Maximize $ \bigoplus_{x \in T} x $ over all such $ T $.

Samples

Input #1

4 3

Output #1

Input #2

6 6

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. New Year's Eve",
    "description": {
      "content": "Since Grisha behaved well last year, at New Year's Eve he was visited by Ded Moroz who brought an enormous bag of gifts with him! The bag contains _n_ sweet candies from _the good ol' bakery_, each la",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF912B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Since Grisha behaved well last year, at New Year's Eve he was visited by Ded Moroz who brought an enormous bag of gifts with him! The bag contains _n_ sweet candies from _the good ol' bakery_, each la...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "由于 Grisha 去年表现良好，除夕夜他被圣诞老人拜访，后者带来了一个装满礼物的巨大袋子！袋子里有 #cf_span[n] 颗来自 _传统烘焙店_ 的糖果，每颗糖果的美味度从 #cf_span[1] 到 #cf_span[n] 标记，且每颗糖果的美味度互不相同。\n\n糖果的选择直接影响 Grisha 的幸福感。人们可能会认为他应该拿最美味的糖果——但不对，节日的魔法让事情颠倒了！决定幸福感的是美味...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n \\leq 10^{18} $.  \nLet $ S = \\{1, 2, \\dots, n\\} $ be the set of candy tastiness values.\n\n**Objective**  \nFind the maximum possible X...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments