L. Liesbeth and the String

Codeforces

IDCF10091L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Little Liesbeth likes to play with strings. Initially she got a string of length n, consisting of letters '_a_' only. Then Liesbeth performs next operations with the string: Liesbeth stops when she has the string of length 1. For example, if n = 4, she needs 6 operations : Liesbeth found that for some n number of operations is too big, and its hard to understand if the process is finite. So she asked You to write the program to help her. First line of the input contains one integer n (2 ≤ n ≤ 106) — length of the initial string. Print one integer — number of operations needed to obtain string of length 1. If process is infinite, print - 1 instead. ## Input First line of the input contains one integer n (2 ≤ n ≤ 106) — length of the initial string. ## Output Print one integer — number of operations needed to obtain string of length 1. If process is infinite, print - 1 instead. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the initial length of the string, with $ 2 \leq n \leq 10^6 $. Let $ f(n) $ denote the number of operations required to reduce the string to length 1, where each operation replaces the string of length $ k \geq 2 $ with a new string of length $ \left\lfloor \frac{k}{2} \right\rfloor $. **Constraints** $ 2 \leq n \leq 10^6 $ **Objective** Compute $ f(n) $, defined recursively by: $$ f(1) = 0, \quad f(k) = 1 + f\left(\left\lfloor \frac{k}{2} \right\rfloor\right) \quad \text{for } k \geq 2 $$ If the process is infinite, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "L. Liesbeth and the String",
    "description": {
      "content": "Little Liesbeth likes to play with strings. Initially she got a string of length n, consisting of letters '_a_' only.  Then Liesbeth performs next operations with the string: Liesbeth stops when she",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10091L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Little Liesbeth likes to play with strings. Initially she got a string of length n, consisting of letters '_a_' only. \n\nThen Liesbeth performs next operations with the string:\n\nLiesbeth stops when she...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the initial length of the string, with $ 2 \\leq n \\leq 10^6 $.  \nLet $ f(n) $ denote the number of operations required to reduce the string to length 1, w...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments