D. Calculated risk

Codeforces

IDCF10241D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

We have a dice with $k$ sides that is rolled over and over again. You have to pay $£ 1$ for each time the dice is rolled. The prize is paid if at some you get a streak of $n$ consecutive ones (the dice shows 1). What is the mininum prize you should ask for in order to make profit from such game? _In other words what is the expected number of turns before streak of $n$ is hit._ For example let's say that the results of a regular $6$-sided dice are: $1, 3, 1, 1, 1$. For $n = 3$ you receive the prize after paying $£ 5$ for those $5$ turns. Input is two numbers $3 <= k <= 20$ and $1 <= n <= 5$. Print out the expected number of times you have to roll the dice to get a streak of $n$ ones. You can assume that the answer will be no bigger than $10^9$. We expect the accuracy of $10^(-4)$. ## Input Input is two numbers $3 <= k <= 20$ and $1 <= n <= 5$. ## Output Print out the expected number of times you have to roll the dice to get a streak of $n$ ones. You can assume that the answer will be no bigger than $10^9$. We expect the accuracy of $10^(-4)$. [samples]

**Definitions** Let $ G = (V, E) $ be an undirected graph with $ n = |V| $ nodes and $ m = |E| $ edges. Let $ a: V \to \mathbb{Z} $ be a function assigning to each node $ i \in V $ a value $ a_i \in [0, 2^{20}) $. **Constraints** 1. $ 1 \le n, m \le 3 \times 10^5 $ 2. $ 0 \le a_i < 2^{20} $ for all $ i \in V $ 3. $ E $ contains no self-loops; multiple edges are allowed. **Objective** Determine whether there exists a subset $ S \subseteq V $ and a value $ x \in [0, 2^{20}) $ such that, after updating $ a_i \leftarrow a_i \oplus x $ for all $ i \in S $, the resulting values $ a'_i $ satisfy: $$ \forall (u,v) \in E, \quad a'_u \ne a'_v $$ If such $ S $ and $ x $ exist, output: - First line: $ |S| $ and $ x $ - Second line: the elements of $ S $ Otherwise, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "D. Calculated risk",
    "description": {
      "content": "We have a dice with $k$ sides that is rolled over and over again. You have to pay $£ 1$ for each time the dice is rolled. The prize is paid if at some you get a streak of $n$ consecutive ones (the dic",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10241D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a dice with $k$ sides that is rolled over and over again. You have to pay $£ 1$ for each time the dice is rolled. The prize is paid if at some you get a streak of $n$ consecutive ones (the dic...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ n = |V| $ nodes and $ m = |E| $ edges.  \nLet $ a: V \\to \\mathbb{Z} $ be a function assigning to each node $ i \\in V $ a value $ a_i \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments