← 返回题目列表

Codeforces · 98/B

B. 救命王

中文机器翻译题面 查看原题

这是对正式回合中使用的问题的修改。不幸的是,作者对原问题的解决方案出现了错误,因此专门针对存档更改了该问题。

从前,在一个遥远的王国里住着国王。国王有一个美丽的女儿维多利亚。他们生活得很幸福,但从此以后并不幸福:有一天,一条恶龙袭击了王国并偷走了维多利亚。国王悲痛欲绝,但他召集了高贵的骑士,承诺将一半的王国和维多利亚之手嫁给能从地狱野兽手中拯救女孩的人。

经过一段时间的旅行,骑士们发现了龙的巢穴,所有人都赶到那里拯救维多利亚。每个骑士都向龙吐口水一次,由于龙的心脏非常脆弱,他的心碎了,可怜的野兽死了。至于贵族骑士们,他们把维多利亚带到了国王面前,并开始争吵,因为每个人都想要这个女孩结婚。

问题是,所有的贵族骑士都同样高贵,同样英俊,维多利亚无论如何也不想嫁给他们中的任何一个。然后国王(他是一个非常聪明的人,不想伤害任何人的感情)决定随机找出谁会得到他的女儿,即抛硬币。然而,原来有n位高贵的骑士,而硬币只有两个面。好的一点是,当抛掷硬币时,硬币掉落到每一面的概率是相等的。国王感兴趣的是如何使用这枚硬币挑选一位高贵的骑士,以便所有骑士都有相同的被选择概率(在这种情况下概率应始终等于 1 / n)。首先,国王想知道他需要掷硬币来确定获胜者的预期次数。此外,在抛硬币时,国王应该遵循最优抛硬币策略(即最小化预期抛硬币次数的策略)。帮助国王完成这项艰巨的任务。

输入

第一行包含问题陈述中的单个整数 n (1 ≤ n ≤ 10000)。

输出

将寻求的预期抛掷次数打印为以下形式的不可约分数:“a/b”(不带引号),不带前导零。

示例

输入 #1

2

输出 #1

1/1

输入 #2

3

输出 #2

8/3

输入 #3

4

输出 #3

2/1