QOJ.ac

QOJ

Limite de temps : 1.0 s Limite de mémoire : 256 MB Points totaux : 100

#11612. DotA 预选赛

Statistiques

今天,一位昵称为 “Idned” 的学生决定不复习即将到来的考试,而是参加一场大型 DotA(算法开发)锦标赛的公开预选赛。预选赛将采用单败淘汰制,共有 $2^n$ 名参赛者,Idned 是其中之一。比赛总共进行 $n$ 轮。在每一轮中,所有剩余的参赛者将被随机分成若干对,每种可能的配对方式概率均等。在每一对中,参赛者进行对决,负者将被淘汰(不再参加后续轮次)。

每位参赛者都有一个唯一的等级分,Idned 的等级分排名第 $k$ 高。Idned 确信每场比赛的结果完全由两名参赛者的等级分决定,等级分较高者获胜。基于这一假设,你能计算出 Idned 参加比赛轮数的期望值吗?

输入格式

输入包含两个整数 $n$ 和 $k$:总轮数和 Idned 在总排名中的位置($1 \le n \le 10$;$1 \le k \le 2^n$)。

输出格式

输出期望的轮数。

你的答案必须精确到绝对误差或相对误差不超过 $10^{-9}$。形式化地说,设你的答案为 $a$,裁判的答案为 $b$,如果满足 $\frac{|a-b|}{\max(1, |b|)} \le 10^{-9}$,则你的答案被视为正确。

样例

输入 1

2 2

输出 1

1.666666666667

输入 2

3 5

输出 2

1.457142857143

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.