#P3492. PA2012 Binary Dodgeball

    ID: 2704 传统题 1000ms 128MiB 尝试: 36 已通过: 18 难度: 8 上传者: 标签>CF2500提高+/省选-SG 函数异或抵消数位 DP上界限制状态二分第 k 小滚动数组

PA2012 Binary Dodgeball

[PA 2012 Finals] Binary Dodgeball

题目描述

有 nn 个盒子,开始时每个盒子中有一个棋子。

两位选手轮流操作,每次可以选择一个 ii 号盒子中的棋子和一个正整数 pp,将棋子移到编号为 2p×i2^p\times i 的盒子中。若编号为 2p×i2^p\times i 的盒子中已有棋子了,则这两个棋子都会被移出盒子。不能移动者输。

求第 kk 小的 nn,使得后手能赢得游戏。

输入格式

仅一行,包含一个正整数 kk。

输出格式

仅一行,包含一个正整数 nn。

样例 #1

样例输入 #1

2

样例输出 #1

10

提示

对于 100%100\% 的数据,1≤k<1091\le k<10^9。