#P3279. 小Z的麻烦

    ID: 2466 传统题 1000ms 512MiB 尝试: 258 已通过: 52 难度: 6 上传者: 标签>难度分类提高组合数学贡献法构造与建模交换求和顺序数论向下取整与向上取整模拟与实现技巧高精度除法高精度加法CF2000

小Z的麻烦

小 Z 的麻烦

题目描述

有 nn 个标号为 11 至 nn 的球,以及编号为 11 至 mm 的盒子。可以选出若干个球放入盒子,每个被选的球只放入一个盒子。放入盒子的球必须满足下列规则。

  1. 若球 ii 放在第 jj 个盒子,且 j<mj<m,则球 2i2i 必须存在,并放在第 j+1j+1 个盒子。
  2. 若球 ii 放在第 jj 个盒子,且 j>1j>1、i=2ki=2k,则球 kk 必须放在第 j−1j-1 个盒子。

给定 n,mn,m,求第一个盒子最多能放多少个球。

输入格式

第一行一个整数 TT,表示数据组数。接下来 TT 行,每行两个整数 n,mn,m。

输出格式

每组数据输出一行一个整数,表示第一个盒子最多能放的球数。

样例

2
10 2
10 3
4
1

第一组的一种最优放法是将 {1,3,4,5}\{1,3,4,5\} 放进第一盒,将 {2,6,8,10}\{2,6,8,10\} 放进第二盒。第二组可依次将 {1},{2},{4}\{1\},\{2\},\{4\} 放进三个盒子。

数据规模与约定

T≤20T\le20,n≤1010000n\le10^{10000},2≤m≤252\le m\le25。

BZOJ 归档题面