#8962. 「洛谷 P12056」[THUPC 2025 决赛] 石墨烯 暂未评定

Ecrade_ 看着食堂里来回游走等位的人们陷入了沉思，于是他想到了这样一个问题。

食堂中共有 个区域，在食堂即将开门时，第 个区域中有 名正在等位的学生和 个空位。保证 。

食堂开门后的每个时刻，都会依次发生如下两个事件：

1. 每个区域中当前正在等位的学生都会尽可能地坐到该区域的空位上。具体而言，假设第 个区域中当前有 名正在等位的学生和 个空位。

   • 若 ，那么所有正在等位的学生都会坐到空位上，此时第 个区域中没有正在等位的学生，且会剩下 个空位；
   • 若 ，那么会有恰好 名正在等位的学生坐到所有空位上，此时第 个区域中剩下 名正在等位的学生，且没有剩余的空位。

2. 每个区域中当前正在等位的所有学生都会同时移动到下一个区域中。具体而言，第 个区域中所有正在等位的学生都会移动到第 个区域中。

在这群学生中，有恰好 名学生因为赶时间上课，在食堂开门的瞬间就打包离开了。而 Ecrade_ 并不清楚这 名学生都在哪些区域，所以他想知道，在这 名学生所有可能的分布情况中，在食堂开门后，最少经过多少个时刻，就能够使得每个区域中都没有正在等位的学生。

第一行一个整数 ，表示测试数据组数。

对于每组测试数据：

• 第一行两个整数 。
• 第二行 个整数 。
• 第三行 个整数 。

保证 ，所有测试数据的 的和不超过 。

对于每组测试数据，输出一行一个整数表示答案。

样例输入 1

复制4
3 0
1 1 4
5 1 4
4 0
1 2 3 4
4 3 2 1
3 6
1 1 4
5 1 4
4 1
1 2 3 4
4 3 2 1

样例输出 1

复制1
4
0
2

样例 #1 解释

为方便表述，下直接用数组 表示每个时刻后每个区域中正在等位的学生数以及剩余空位数。

对于第一组测试数据，没有学生会离开食堂：

• 第一个时刻后，。

对于第二组测试数据，没有学生会离开食堂：

• 第一个时刻后，；
• 第二个时刻后，；
• 第三个时刻后，；
• 第四个时刻后，。

对于第三组测试数据，所有学生都会离开食堂。

对于第四组测试数据，仅有一名学生会离开食堂：

• 若这名学生在第 个区域，则 会变为 ：
  • 第一个时刻后，；
  • 第二个时刻后，；
  • 第三个时刻后，。
• 若这名学生在第 个区域，则 会变为 ：
  • 第一个时刻后，；
  • 第二个时刻后，；
  • 第三个时刻后，；
  • 第四个时刻后，。
• 若这名学生在第 个区域，则 会变为 ：
  • 第一个时刻后，；
  • 第二个时刻后，。
• 若这名学生在第 个区域，则 会变为 ：
  • 第一个时刻后，；
  • 第二个时刻后，；
  • 第三个时刻后，。
• 因此，当这名学生在第 个区域时，最少经过 个时刻，就能够使得每个区域中都没有正在等位的学生。

来源与致谢

来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public。