猜测集合
题面描述
小 P 和小 Q 要进行一个叫“猜集合”的游戏。
在这个游戏中，两人先确定好了一个整数 ，以及 个 的子集 。在这之后，小 P 会秘密选择其中一个子集，并且不告诉小 Q。小 Q 需要通过若干次猜测来得出小 P 的集合。在一次猜测中，小 Q 会选择一个 之间的整数，并问小 P 该整数是否属于选定的那个子集。小 P 会如实回答小 Q 的问题。
问题来了，假设小 P 等概率地从这 个子集中选择一个，在最优策略下，小 Q 期望需要多少次才能猜出这个子集？
输入格式
第一行一个正整数 。
第二行一个正整数 ，表示子集的个数。
接下来 行，每行 个数。第一个数表示 ，即第 个子集的大小。后面跟着 个 之间的互不相同的整数，表示 的元素。
输出格式
如果有概率小 Q 猜不出小 P 选定的集合，输出 not possible。否则，以小数形式输出小 Q 所需的期望步数。当你输出的小数与正确答案误差 时，你就会被判对。
样例
3
3
3 0 1 2
1 1
1 2
1.666666666
10
2
1 0
1 0
not possible
说明/提示
对于第一个样例，假设小 Q 第一次问 ，则他有 的概率猜对。如果没有猜对，他再问一次就可以了。于是期望为 。可以证明没有期望更少的策略。
对于第二个样例，无论小 Q 怎么问，他都无法分辨小 P 选择的是第一个子集，还是第二个子集。
对于 的数据，有 ，。
国庆提高/省选组比赛
- Status
- Live... (Attended)
- Rule
- IOI
- Problem
- 40
- Start at
- 2025-10-15 19:32
- End at
- 2025-11-16 0:00
- Duration
- 1104 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 85