#P7224. [2023省队模拟]书

    ID: 7058 传统题 1000ms 512MiB 尝试: 5 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-期望 DP概率 DP首次步分析期望方程添加哨兵

[2023省队模拟]书

题目描述

有 nn 本书。第 ii 本书的大小为 aia_i,厚度为 bib_i。你使用一个初始为空的栈来整理这些书。

每次找到所有大小严格小于栈顶那本书的书。如果栈为空,则所有书都符合条件。将符合条件的书从 11 开始编号,设它们共有 cc 本。从 [0,c][0,c] 中等概率随机选取一个整数 xx。若 x≠0x\ne 0,把编号为 xx 的书放在栈顶。若 x=0x=0,尝试从栈顶取出一本书。

重复操作,直到选到 x=0x=0 时栈为空,或者栈中所有书的厚度和大于 ww。求停止前的期望操作次数。导致停止的那一次操作也计入次数。

输入格式

第一行一个整数 TT,表示数据组数。

每组数据的第一行包含两个整数 n,wn,w,表示书的数量和允许的最大厚度和。接下来 nn 行,每行两个整数 ai,bia_i,b_i,表示一本书。

输出格式

每组数据输出一行,表示答案,保留小数点后三位。若答案严格大于 1800018000,输出 INF。

样例输入

2
2 2
1 1
2 2
1 1
1 2

样例输出

3.333
1.000

数据范围与约定

对于所有数据,1≤n,w,ai,bi≤1001\le n,w,a_i,b_i\le 100,1≤T≤601\le T\le 60。

对于 10%10\% 的数据,n≤5n\le 5。对于 30%30\% 的数据,n≤20n\le 20。对于另外 20%20\% 的数据,⌊w/2⌋<bi\lfloor w/2\rfloor < b_i。