E. Explosion Exploit

Codeforces

IDCF10193E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

In a two player card game, you have $n$ minions on the board and the opponent has $m$ minions. Each minion has a health between $1$ and $6$. You are contemplating your next move. You want to play an "Explosion" spell which deals $d$ units of damage randomly distributed across all minions. The damage is dealt one unit at a time to some remaining minion on the board. Each living minion (including your own) has the same chance of receiving each unit of damage. When a minion receives a unit of damage, its health is decreased by one. As soon as the health of a minion reaches zero, it is immediately removed from the board, before the next damage is dealt. If there are no minions left on the board, any excess damage caused by the spell is ignored. Given the current health of all minions, what is the probability that the Explosion will remove all of the opponent's minions? Note that it does not matter if all your own minions die in the process as well, and the damage continues to be dealt even if all your own minions are gone. The first line of input contains the three integers $n$, $m$, and $d$ ($1 <= n, m <= 5$, $1 <= d <= 100$). Then follows a line containing $n$ integers, the current health of all your minions. Finally, the third line contains $m$ integers, the current health of all the opponent's minions. All healths are between $1$ and $6$ (inclusive). Output the probability that the Explosion removes all the opponent's minions, accurate up to an absolute error of $10^(-6)$. ## Input The first line of input contains the three integers $n$, $m$, and $d$ ($1 <= n, m <= 5$, $1 <= d <= 100$). Then follows a line containing $n$ integers, the current health of all your minions. Finally, the third line contains $m$ integers, the current health of all the opponent's minions. All healths are between $1$ and $6$ (inclusive). ## Output Output the probability that the Explosion removes all the opponent's minions, accurate up to an absolute error of $10^(-6)$. [samples]

**Definitions** Let $ n, m, d \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 5 $, $ 1 \leq d \leq 100 $. Let $ H_p = (h_{p,1}, \dots, h_{p,n}) \in \{1,\dots,6\}^n $ be the health vector of your minions. Let $ H_o = (h_{o,1}, \dots, h_{o,m}) \in \{1,\dots,6\}^m $ be the health vector of opponent’s minions. Let $ \mathcal{S} $ be the set of all valid damage distribution sequences of length $ d $, where each unit of damage is assigned to a living minion (with removal upon health reaching 0), and the assignment is uniform over current living minions at each step. **Constraints** - At each step $ t \in \{1, \dots, d\} $, the set of living minions is updated by removing those with health $ \leq 0 $ after damage is applied. - Damage is distributed sequentially: at step $ t $, a minion is chosen uniformly at random from the current living minions. - If no minions remain, remaining damage is ignored. **Objective** Compute the probability: $$ P = \mathbb{P}\left( \bigwedge_{j=1}^{m} \text{health of opponent minion } j \leq 0 \text{ after } d \text{ damage units are dealt} \right) $$ over all possible damage distribution sequences in $ \mathcal{S} $, under uniform random selection at each step.

API Response (JSON)

{
  "problem": {
    "name": "E. Explosion Exploit",
    "description": {
      "content": "In a two player card game, you have $n$ minions on the board and the opponent has $m$ minions. Each minion has a health between $1$ and $6$. You are contemplating your next move. You want to play an ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10193E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In a two player card game, you have $n$ minions on the board and the opponent has $m$ minions. Each minion has a health between $1$ and $6$.\n\nYou are contemplating your next move. You want to play an ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, d \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 5 $, $ 1 \\leq d \\leq 100 $.  \nLet $ H_p = (h_{p,1}, \\dots, h_{p,n}) \\in \\{1,\\dots,6\\}^n $ be the health vector of your minion...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments