33OJ
登录 注册

#P17761. 「奶龙OI」Round 3 - 红石大佬

    ID: 20433 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及− 上传者: 标签>数学洛谷原创O2优化洛谷月赛分类讨论

「奶龙OI」Round 3 - 红石大佬

背景

红石大佬小 G 在改造他的西瓜机。

题目描述

小 G 的西瓜机中包含一块 2×n2\times n 的矩形田地,共有 2n2n 个格子。初始时,所有格子均为空。

小 G 要选择其中恰好 kk 个格子种下西瓜种子,每个格子至多种下一颗种子。

当西瓜藤成熟后,一个没有种子的格子能够长出西瓜,当且仅当它与至少一个种有西瓜种子的格子共用一条边。一个格子即使与多个种有西瓜种子的格子相邻,也只计算一次。

特别注意:存在种子的格子不能长出西瓜!

请你求出,小 G 合理安排种子的位置后,最多有多少个格子能够长出西瓜。

输入格式

第一行包含一个正整数 TT,表示测试数据的组数。

接下来 TT 行,每行包含两个整数 n,kn,k,分别表示田地的列数和种子的数量。

输出格式

对于每组测试数据,输出一行一个整数,表示最多能够长出西瓜的格子数量。

5
1 1
5 2
5 3
2026 1013
10 9
1
6
7
3038
11

提示

【数据范围与约定】

本题采用捆绑测试。

对于所有测试数据,保证:

  • 1≤T≤1041\le T\le 10^4;
  • 1≤n≤10151\le n\le 10^{15};
  • 1≤k≤2n1\le k\le 2n;
  • 输入的所有数均为整数。
Subtask 数据范围 分值
1 n,k≤15n,k\le 15 2525
2 n,k≤5000n,k\le 5000
3 k≥⌊n2⌋k\ge \left\lfloor\dfrac n2\right\rfloor
4 无特殊限制