#P7224. [2023省队模拟]书
[2023省队模拟]书
题目描述
有 本书。第 本书的大小为 ,厚度为 。你使用一个初始为空的栈来整理这些书。
每次找到所有大小严格小于栈顶那本书的书。如果栈为空,则所有书都符合条件。将符合条件的书从 开始编号,设它们共有 本。从 中等概率随机选取一个整数 。若 ,把编号为 的书放在栈顶。若 ,尝试从栈顶取出一本书。
重复操作,直到选到 时栈为空,或者栈中所有书的厚度和大于 。求停止前的期望操作次数。导致停止的那一次操作也计入次数。
输入格式
第一行一个整数 ,表示数据组数。
每组数据的第一行包含两个整数 ,表示书的数量和允许的最大厚度和。接下来 行,每行两个整数 ,表示一本书。
输出格式
每组数据输出一行,表示答案,保留小数点后三位。若答案严格大于 ,输出 INF。
样例输入
2
2 2
1 1
2 2
1 1
1 2
样例输出
3.333
1.000
数据范围与约定
对于所有数据,,。
对于 的数据,。对于 的数据,。对于另外 的数据,。