Codeforces Round 456 (Div. 2) |
---|
Закончено |
Поскольку Гриша весь год вел себя хорошо, в новогоднюю ночь его посетил Дед Мороз с мешком подарков! В мешке Деда Мороза содержатся n сладких конфет из той самой кондитерской, по одной конфете каждой возможной вкусности от 1 до n.
Счастье Гриши напрямую зависит от того, какие именно конфеты он возьмет. Несмотря на то, что разумно предположить, что брать нужно наиболее вкусные конфеты, новогодняя магия переворачивает все с ног на голову: оказывается, важна не просто сумма вкусностей конфет, а их XOR-сумма!
XOR-сумма последовательности целых чисел a1, a2, ..., am считается как побитовый XOR всех элементов последовательности: , здесь обозначает операцию побитового XOR; подробнее про побитовый XOR (операцию, также известную как побитовое исключающее ИЛИ) можно прочитать здесь.
Дед Мороз заранее предупредил Гришу, что ему требуется посетить еще несколько мест, а потому Гриша волен выбрать не более k конфет из мешка Деда Мороза. Помогите Грише узнать, чему равна максимальная XOR-сумма, а вместе с ней и максимальное счастье, которое он может обрести при оптимальном выборе конфет.
В единственной строке заданы два числа n и k (1 ≤ k ≤ n ≤ 1018).
Выведите одно число — максимальную возможную XOR-сумму.
4 3
7
6 6
7
В первом примере можно взять конфеты со вкусностями 1, 2 и 4. Их XOR-сумма равняется 7.
Во втором примере можно взять все шесть конфет и получить XOR-сумму 7.
Название |
---|