D. Jon and Orbs

Codeforces

IDCF768D

Time2000ms

Memory256MB

Difficulty—

dpmathprobabilities

English · Original

Chinese · Translation

Formal · Original

Jon Snow is on the lookout for some orbs required to defeat the white walkers. There are _k_ different types of orbs and he needs at least one of each. One orb spawns daily at the base of a Weirwood tree north of the wall. The probability of this orb being of any kind is equal. As the north of wall is full of dangers, he wants to know the minimum number of days he should wait before sending a ranger to collect the orbs such that the probability of him getting at least one of each kind of orb is at least , where ε < 10 - 7. To better prepare himself, he wants to know the answer for _q_ different values of _p__i_. Since he is busy designing the battle strategy with Sam, he asks you for your help. ## Input First line consists of two space separated integers _k_, _q_ (1 ≤ _k_, _q_ ≤ 1000) — number of different kinds of orbs and number of queries respectively. Each of the next _q_ lines contain a single integer _p__i_ (1 ≤ _p__i_ ≤ 1000) — _i_\-th query. ## Output Output _q_ lines. On _i_\-th of them output single integer — answer for _i_\-th query. [samples]

琼恩·雪诺正在寻找一些击败白 walkers 所需的 orbs。共有 #cf_span[k] 种不同类型的 orbs，他至少需要每种一个。每天，一粒 orb 会在墙北的鱼梁木树下生成，且每种类型的 orb 出现的概率相等。由于墙北充满危险，他希望知道最少需要等待多少天，再派遣游骑兵去收集 orbs，使得他收集到至少每种类型一个 orb 的概率至少为 #cf_span[\frac{p_i}{1000}]，其中 #cf_span[\varepsilon < 10^{-7}]。为了更好地准备自己，他希望知道对于 #cf_span[q] 个不同的 #cf_span[p_i] 值的答案。由于他正忙于与山姆设计作战策略，他向你寻求帮助。第一行包含两个用空格分隔的整数 #cf_span[k], #cf_span[q] (#cf_span[1 \leq k, q \leq 1000]) —— 不同类型 orbs 的数量和查询次数。接下来的 #cf_span[q] 行每行包含一个整数 #cf_span[p_i] (#cf_span[1 \leq p_i \leq 1000]) —— 第 #cf_span[i] 个查询。请输出 #cf_span[q] 行。第 #cf_span[i] 行输出一个整数 —— 第 #cf_span[i] 个查询的答案。 ## Input 第一行包含两个用空格分隔的整数 #cf_span[k], #cf_span[q] (#cf_span[1 \leq k, q \leq 1000]) —— 不同类型 orbs 的数量和查询次数。接下来的 #cf_span[q] 行每行包含一个整数 #cf_span[p_i] (#cf_span[1 \leq p_i \leq 1000]) —— 第 #cf_span[i] 个查询。 ## Output 请输出 #cf_span[q] 行。第 #cf_span[i] 行输出一个整数 —— 第 #cf_span[i] 个查询的答案。 [samples]

**Definitions** Let $ k \in \mathbb{Z}^+ $ be the number of distinct orb types. Let $ q \in \mathbb{Z}^+ $ be the number of queries. For each query $ p_i \in \{1, \dots, 1000\} $, define $ \varepsilon_i = \frac{p_i}{1000} $, so that $ \varepsilon_i \in [0.001, 1] $. **Constraints** 1. $ 1 \leq k \leq 1000 $ 2. $ 1 \leq q \leq 1000 $ 3. $ 1 \leq p_i \leq 1000 $ for all $ i \in \{1, \dots, q\} $ **Objective** For each query $ p_i $, find the smallest integer $ n_i \in \mathbb{Z}^+ $ such that the probability of collecting all $ k $ orb types in $ n_i $ days is at least $ \varepsilon_i $: $$ \mathbb{P}(\text{all } k \text{ types collected in } n_i \text{ days}) \geq \varepsilon_i $$ where the probability is computed under the uniform i.i.d. sampling model over $ k $ types.

Samples

Input #1

1 1
1

Output #1

Input #2

2 2
1
2

Output #2

2
2

API Response (JSON)

{
  "problem": {
    "name": "D. Jon and Orbs",
    "description": {
      "content": "Jon Snow is on the lookout for some orbs required to defeat the white walkers. There are _k_ different types of orbs and he needs at least one of each. One orb spawns daily at the base of a Weirwood t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF768D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Jon Snow is on the lookout for some orbs required to defeat the white walkers. There are _k_ different types of orbs and he needs at least one of each. One orb spawns daily at the base of a Weirwood t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "琼恩·雪诺正在寻找一些击败白 walkers 所需的 orbs。共有 #cf_span[k] 种不同类型的 orbs，他至少需要每种一个。每天，一粒 orb 会在墙北的鱼梁木树下生成，且每种类型的 orb 出现的概率相等。由于墙北充满危险，他希望知道最少需要等待多少天，再派遣游骑兵去收集 orbs，使得他收集到至少每种类型一个 orb 的概率至少为 #cf_span[\\frac{p_i}{1000...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of distinct orb types.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query $ p_i \\in \\{1, \\dots, 1000\\} $, define $ \\vare...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments