#P17761. 「奶龙OI」Round 3 - 红石大佬
「奶龙OI」Round 3 - 红石大佬
背景
红石大佬小 G 在改造他的西瓜机。
题目描述
小 G 的西瓜机中包含一块 的矩形田地,共有 个格子。初始时,所有格子均为空。
小 G 要选择其中恰好 个格子种下西瓜种子,每个格子至多种下一颗种子。
当西瓜藤成熟后,一个没有种子的格子能够长出西瓜,当且仅当它与至少一个种有西瓜种子的格子共用一条边。一个格子即使与多个种有西瓜种子的格子相邻,也只计算一次。
特别注意:存在种子的格子不能长出西瓜!
请你求出,小 G 合理安排种子的位置后,最多有多少个格子能够长出西瓜。
输入格式
第一行包含一个正整数 ,表示测试数据的组数。
接下来 行,每行包含两个整数 ,分别表示田地的列数和种子的数量。
输出格式
对于每组测试数据,输出一行一个整数,表示最多能够长出西瓜的格子数量。
5
1 1
5 2
5 3
2026 1013
10 9
1
6
7
3038
11
提示
【数据范围与约定】
本题采用捆绑测试。
对于所有测试数据,保证:
- ;
- ;
- ;
- 输入的所有数均为整数。
| Subtask | 数据范围 | 分值 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | 无特殊限制 |