B. Help King

Codeforces

IDCF98B

Time2000ms

Memory256MB

Difficulty—

implementationprobabilitiestrees

English · Original

Chinese · Translation

Formal · Original

_This is the modification of the problem used during the official round. Unfortunately, author's solution of the original problem appeared wrong, so the problem was changed specially for the archive._ Once upon a time in a far away kingdom lived the King. The King had a beautiful daughter, Victoria. They lived happily, but not happily ever after: one day a vicious dragon attacked the kingdom and stole Victoria. The King was full of grief, yet he gathered his noble knights and promised half of his kingdom and Victoria's hand in marriage to the one who will save the girl from the infernal beast. Having travelled for some time, the knights found the dragon's lair and all of them rushed there to save Victoria. Each knight spat on the dragon once and, as the dragon had quite a fragile and frail heart, his heart broke and poor beast died. As for the noble knights, they got Victoria right to the King and started brawling as each one wanted the girl's hand in marriage. The problem was that all the noble knights were equally noble and equally handsome, and Victoria didn't want to marry any of them anyway. Then the King (and he was a very wise man and didn't want to hurt anybody's feelings) decided to find out who will get his daughter randomly, i.e. tossing a coin. However, there turned out to be _n_ noble knights and the coin only has two sides. The good thing is that when a coin is tossed, the coin falls on each side with equal probability. The King got interested how to pick one noble knight using this coin so that all knights had equal probability of being chosen (the probability in that case should always be equal to 1 / _n_). First the King wants to know the expected number of times he will need to toss a coin to determine the winner. Besides, while tossing the coin, the King should follow the optimal tossing strategy (i.e. the strategy that minimizes the expected number of tosses). Help the King in this challenging task. ## Input The first line contains a single integer _n_ from the problem's statement (1 ≤ _n_ ≤ 10000). ## Output Print the sought expected number of tosses as an irreducible fraction in the following form: "_a__/__b_" (without the quotes) without leading zeroes. [samples]

_这是官方比赛中使用的问题的修改版本。不幸的是，原问题的作者解法有误，因此该问题专门为归档而修改。_ 从前，在一个遥远的王国里住着一位国王。国王有一个美丽的女儿，维多利亚。他们生活幸福，但并未从此永远幸福下去：有一天，一条邪恶的龙袭击了王国并掳走了维多利亚。国王悲痛欲绝，但仍召集了他的贵族骑士们，许诺将王国的一半和维多利亚的手作为奖赏，赐予能从恶龙手中救出女孩的人。骑士们经过一段时间的旅行后，找到了龙的巢穴，所有人都冲了过去拯救维多利亚。每位骑士向龙吐了一口唾沫，而由于龙的心脏极其脆弱，龙的心脏破裂，可怜的生物就此死去。至于这些高贵的骑士们，他们将维多利亚安全送回国王面前，却开始争斗起来，因为每个人都想迎娶这位姑娘。问题在于，所有贵族骑士都同样高贵、同样英俊，而维多利亚无论如何也不想嫁给其中任何一人。于是国王（他是一位非常睿智的人，不愿伤害任何人的感情）决定通过随机方式选出获胜者，即抛硬币。然而，此时出现了 #cf_span[n] 位贵族骑士，而硬币只有两面。幸运的是，抛硬币时，硬币落在每一面的概率相等。国王开始思考：如何用这枚硬币选出一位骑士，使得每位骑士被选中的概率相等（此时概率必须恒为 #cf_span[1 / n]）？首先，国王想知道为了确定胜者，他需要抛硬币的期望次数是多少。此外，在抛硬币的过程中，国王应遵循最优策略（即最小化期望抛掷次数的策略）。请帮助国王完成这一艰巨任务。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10000]）。请以最简分数形式输出所求的期望抛掷次数，格式为："#cf_span[a]_/_#cf_span[b]"（不含引号），且不带前导零。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10000]）。 ## Output 请以最简分数形式输出所求的期望抛掷次数，格式为："#cf_span[a]_/_#cf_span[b]"（不含引号），且不带前导零。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 10000 $, be the number of knights. Let $ X $ be the random variable denoting the number of fair coin tosses required to select one knight uniformly at random using an optimal strategy. **Constraints** The selection must yield each knight with probability $ \frac{1}{n} $. Each coin toss is independent and yields heads or tails with probability $ \frac{1}{2} $. **Objective** Compute the minimal expected number of coin tosses $ \mathbb{E}[X] $, expressed as an irreducible fraction $ \frac{a}{b} $.

Samples

Input #1

Output #1

1/1

Input #2

Output #2

8/3

Input #3

Output #3

2/1

API Response (JSON)

{
  "problem": {
    "name": "B. Help King",
    "description": {
      "content": "_This is the modification of the problem used during the official round. Unfortunately, author's solution of the original problem appeared wrong, so the problem was changed specially for the archive._",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF98B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_This is the modification of the problem used during the official round. Unfortunately, author's solution of the original problem appeared wrong, so the problem was changed specially for the archive._...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_这是官方比赛中使用的问题的修改版本。不幸的是，原问题的作者解法有误，因此该问题专门为归档而修改。_\n\n从前，在一个遥远的王国里住着一位国王。国王有一个美丽的女儿，维多利亚。他们生活幸福，但并未从此永远幸福下去：有一天，一条邪恶的龙袭击了王国并掳走了维多利亚。国王悲痛欲绝，但仍召集了他的贵族骑士们，许诺将王国的一半和维多利亚的手作为奖赏，赐予能从恶龙手中救出女孩的人。\n\n骑士们经过一段时间的旅行后...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10000 $, be the number of knights.  \nLet $ X $ be the random variable denoting the number of fair coin tosses required to select one knight ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments