E. Marmots (medium)

Codeforces

IDCF802E

Time2000ms

Memory256MB

Difficulty—

math

English · Original

Chinese · Translation

Formal · Original

Good job! Now that Heidi is able to distinguish between Poisson and uniform distributions, she is in a good position to actually estimate the populations. Can you help Heidi estimate each village's population? ## Input Same as the easy version. ## Output Output one line per village, in the same order as provided in the input, containing your (integer) population estimate. Your answer is considered correct if it is an integer that falls into the interval , where _P_ is the real population of the village, used to create the distribution (either Poisson or uniform) from which the marmots drew their answers. [samples]

做得好！既然 Heidi 能够区分泊松分布和均匀分布，她现在有能力实际估算每个村庄的人口了。你能帮助 Heidi 估算每个村庄的人口吗？与简单版本相同。请为每个村庄输出一行，顺序与输入中提供的顺序一致，每行包含你的（整数）人口估计值。你的答案被认为是正确的，当且仅当它是一个整数，且落在区间 $[P - 0.5, P + 0.5)$ 内，其中 $P$ 是用于生成分布（泊松或均匀）的村庄真实人口，土拨鼠正是从该分布中抽取其答案的。 ## Input 与简单版本相同。 ## Output 请为每个村庄输出一行，顺序与输入中提供的顺序一致，每行包含你的（整数）人口估计值。你的答案被认为是正确的，当且仅当它是一个整数，且落在区间 $[P - 0.5, P + 0.5)$ 内，其中 $P$ 是用于生成分布（泊松或均匀）的村庄真实人口，土拨鼠正是从该分布中抽取其答案的。 [samples]

Given: - $ n $ villages, each with unknown real population $ P_i \in \mathbb{Z}^+ $. - For each village $ i $, $ m $ marmots independently report integer answers $ a_{i,j} \in \mathbb{Z}^+ $, $ j = 1, \dots, m $. - Each village's answers are drawn from one of two distributions: - **Poisson**: $ a_{i,j} \sim \text{Poisson}(\lambda_i) $, where $ \lambda_i = P_i $. - **Uniform**: $ a_{i,j} \sim \text{Uniform}\{1, 2, \dots, P_i\} $, where $ P_i \in \mathbb{Z}^+ $. - The distribution type (Poisson or Uniform) for each village is unknown. - Objective: Estimate $ \hat{P}_i \in \mathbb{Z}^+ $ for each village $ i $, such that $ \hat{P}_i \in [P_i - \delta, P_i + \delta] $ for some unknown $ \delta $ (i.e., estimate must be within the interval containing the true $ P_i $). Estimation rule: For each village $ i $: - Let $ \bar{a}_i = \frac{1}{m} \sum_{j=1}^m a_{i,j} $ be the sample mean. - If $ \bar{a}_i \leq 2 $, assume Uniform distribution: $$ \hat{P}_i = \left\lceil \bar{a}_i \right\rceil $$ - If $ \bar{a}_i > 2 $, assume Poisson distribution: $$ \hat{P}_i = \left\lfloor \bar{a}_i + 0.5 \right\rfloor $$ Output: $ \hat{P}_1, \hat{P}_2, \dots, \hat{P}_n $, one per line.

API Response (JSON)

{
  "problem": {
    "name": "E. Marmots (medium)",
    "description": {
      "content": "Good job! Now that Heidi is able to distinguish between Poisson and uniform distributions, she is in a good position to actually estimate the populations. Can you help Heidi estimate each village's p",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF802E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Good job! Now that Heidi is able to distinguish between Poisson and uniform distributions, she is in a good position to actually estimate the populations.\n\nCan you help Heidi estimate each village's p...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "做得好！既然 Heidi 能够区分泊松分布和均匀分布，她现在有能力实际估算每个村庄的人口了。\n\n你能帮助 Heidi 估算每个村庄的人口吗？\n\n与简单版本相同。\n\n请为每个村庄输出一行，顺序与输入中提供的顺序一致，每行包含你的（整数）人口估计值。\n\n你的答案被认为是正确的，当且仅当它是一个整数，且落在区间 $[P - 0.5, P + 0.5)$ 内，其中 $P$ 是用于生成分布（泊松或均匀）的村...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given:  \n- $ n $ villages, each with unknown real population $ P_i \\in \\mathbb{Z}^+ $.  \n- For each village $ i $, $ m $ marmots independently report integer answers $ a_{i,j} \\in \\mathbb{Z}^+ $, $ j ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments