A. Random Mood

Codeforces

IDCF10264A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

_This is a training contest on matrix exponentiation. See the tutorial along with hints and video solutions here._ Limak is always either happy or sad. His mood switches with probability $p$ every second. If Limak is happy right now, what is the probability that he's happy after $n$ seconds? An integer $n$ ($1 <= n <= 10^9$) and a real value $p$ ($0 < p < 1$) with at most 9 digits after floating point. Print one line with the answer. The absolute error allowed is $10^(-6)$. In the first sample test, there's probability $0. 7$ that Limak changes his mood from happy to sad. Otherwise (with probability $0. 3$), he stays happy. In the second sample test, the answer is $0. 1 dot.op 0. 1 + 0. 9 dot.op 0. 9 = 0. 82$ because we want Limak either to switch his mood twice or not to change the mood at all. ## Input An integer $n$ ($1 <= n <= 10^9$) and a real value $p$ ($0 < p < 1$) with at most 9 digits after floating point. ## Output Print one line with the answer. The absolute error allowed is $10^(-6)$. [samples] ## Note In the first sample test, there's probability $0. 7$ that Limak changes his mood from happy to sad. Otherwise (with probability $0. 3$), he stays happy.In the second sample test, the answer is $0. 1 dot.op 0. 1 + 0. 9 dot.op 0. 9 = 0. 82$ because we want Limak either to switch his mood twice or not to change the mood at all.

**Definitions** Let $ p \in (0,1) $ be the probability of mood switch per second. Let $ n \in \mathbb{Z}^+ $, $ 1 \leq n \leq 10^9 $, be the number of seconds. Let $ h_n $ be the probability that Limak is happy after $ n $ seconds, given he starts happy. **Constraints** $ 0 < p < 1 $, with at most 9 decimal digits. $ n \in \mathbb{Z}^+ $, $ 1 \leq n \leq 10^9 $ **Objective** Compute $ h_n $, where the state transition is governed by: $$ h_0 = 1, \quad h_{k} = (1 - p) h_{k-1} + p (1 - h_{k-1}) \quad \text{for } k \geq 1 $$ Equivalently: $$ h_n = \frac{1 + (1 - 2p)^n}{2} $$

API Response (JSON)

{
  "problem": {
    "name": "A. Random Mood",
    "description": {
      "content": "_This is a training contest on matrix exponentiation. See the tutorial along with hints and video solutions here._ Limak is always either happy or sad. His mood switches with probability $p$ every se",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10264A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_This is a training contest on matrix exponentiation. See the tutorial along with hints and video solutions here._\n\nLimak is always either happy or sad. His mood switches with probability $p$ every se...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ p \\in (0,1) $ be the probability of mood switch per second.  \nLet $ n \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 10^9 $, be the number of seconds.  \nLet $ h_n $ be the probability tha...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments