A. Double Cola

Codeforces

IDCF82A

Time1000ms

Memory256MB

Difficulty—

implementationmath

English · Original

Chinese · Translation

Formal · Original

Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on. This process continues ad infinitum. For example, Penny drinks the third can of cola and the queue will look like this: Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny. Write a program that will print the name of a man who will drink the _n_\-th can. Note that in the very beginning the queue looks like that: Sheldon, Leonard, Penny, Rajesh, Howard. The first person is Sheldon. ## Input The input data consist of a single integer _n_ (1 ≤ _n_ ≤ 109). It is guaranteed that the pretests check the spelling of all the five names, that is, that they contain all the five possible answers. ## Output Print the single line — the name of the person who drinks the _n_\-th can of cola. The cans are numbered starting from 1. Please note that you should spell the names like this: "_Sheldon_", "_Leonard_", "_Penny_", "_Rajesh_", "_Howard_" (without the quotes). In that order precisely the friends are in the queue initially. [samples]

Sheldon、Leonard、Penny、Rajesh 和 Howard 排队购买 "Double Cola" 饮料自动售货机的饮料；队列中没有其他人。队列中的第一个人（Sheldon）买了一罐饮料，喝掉后变成两个！这两个 Sheldon 排到队列末尾。接着队列中的下一个人（Leonard）买了一罐饮料，喝掉后变成两个 Leonard，也排到队列末尾，依此类推。这个过程无限持续下去。例如，Penny 喝掉了第三罐可乐后，队列将变为：Rajesh、Howard、Sheldon、Sheldon、Leonard、Leonard、Penny、Penny。编写一个程序，输出喝掉第 #cf_span[n]-罐可乐的人的名字。注意，最开始队列是这样的：Sheldon、Leonard、Penny、Rajesh、Howard。第一个人是 Sheldon。输入数据为一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 109]）。保证预测试会检查所有五个名字的拼写，即所有五个可能的答案都会出现。请输出一行——喝掉第 #cf_span[n]-罐可乐的人的名字。可乐罐编号从 1 开始。请注意，你必须严格按照以下形式拼写名字："_Sheldon_"、"_Leonard_"、"_Penny_"、"_Rajesh_"、"_Howard_"（不包含引号）。这正是初始队列中朋友们的顺序。 ## Input 输入数据为一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 109]）。保证预测试会检查所有五个名字的拼写，即所有五个可能的答案都会出现。 ## Output 请输出一行——喝掉第 #cf_span[n]-罐可乐的人的名字。可乐罐编号从 1 开始。请注意，你必须严格按照以下形式拼写名字："_Sheldon_"、"_Leonard_"、"_Penny_"、"_Rajesh_"、"_Howard_"（不包含引号）。这正是初始队列中朋友们的顺序。 [samples]

**Definitions** Let $ N = 5 $ be the number of people in the initial queue. Let $ P = [p_0, p_1, p_2, p_3, p_4] $ be the ordered list of names: $ p_0 = \text{Sheldon},\ p_1 = \text{Leonard},\ p_2 = \text{Penny},\ p_3 = \text{Rajesh},\ p_4 = \text{Howard} $. Let $ n \in \mathbb{Z} $ be the index of the can to be consumed ($ 1 \leq n \leq 10^9 $). **Process** At each step, the person at the front of the queue consumes one can and is replaced by two copies of themselves at the end of the queue. The queue evolves in rounds: - Round 0: Each of the 5 people appears once. - Round $ r \geq 1 $: Each person from round $ r-1 $ appears twice as many times as in the previous round. Thus, in round $ r $, each person appears $ 2^r $ times consecutively. The total number of cans consumed up to and including round $ r-1 $ is: $$ T_r = 5 \cdot \sum_{i=0}^{r-1} 2^i = 5 \cdot (2^r - 1) $$ **Constraints** $ 1 \leq n \leq 10^9 $ **Objective** Find the person $ p_j $ who drinks the $ n $-th can. Let $ r $ be the unique non-negative integer such that: $$ T_r < n \leq T_{r+1} \quad \text{where} \quad T_r = 5 \cdot (2^r - 1) $$ Then, within round $ r $, the position of the $ n $-th can is: $$ \text{pos} = n - T_r = n - 5 \cdot (2^r - 1) $$ Each person in round $ r $ occupies $ 2^r $ consecutive cans. The index of the person is: $$ j = \left\lfloor \frac{\text{pos} - 1}{2^r} \right\rfloor $$ Output: $ p_j $

Samples

Input #1

Output #1

Sheldon

Input #2

Output #2

Sheldon

Input #3

Output #3

Penny

API Response (JSON)

{
  "problem": {
    "name": "A. Double Cola",
    "description": {
      "content": "Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a \"Double Cola\" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF82A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a \"Double Cola\" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Sheldon、Leonard、Penny、Rajesh 和 Howard 排队购买 \"Double Cola\" 饮料自动售货机的饮料；队列中没有其他人。队列中的第一个人（Sheldon）买了一罐饮料，喝掉后变成两个！这两个 Sheldon 排到队列末尾。接着队列中的下一个人（Leonard）买了一罐饮料，喝掉后变成两个 Leonard，也排到队列末尾，依此类推。这个过程无限持续下去。\n\n例如，P...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N = 5 $ be the number of people in the initial queue.  \nLet $ P = [p_0, p_1, p_2, p_3, p_4] $ be the ordered list of names:  \n$ p_0 = \\text{Sheldon},\\ p_1 = \\text{Leonard},\\ p_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments