{"problem":{"name":"F. Marmots (hard)","description":{"content":"Your task is the exact same as for the _easy_ version. But this time, the marmots subtract the village's population _P_ from their random number before responding to Heidi's request. Also, there are ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF802F"},"statements":[{"statement_type":"Markdown","content":"Your task is the exact same as for the _easy_ version. But this time, the marmots subtract the village's population _P_ from their random number before responding to Heidi's request.\n\nAlso, there are now villages with as few as a single inhabitant, meaning that .\n\nCan you help Heidi find out whether a village follows a Poisson or a uniform distribution?\n\n## Input\n\nSame as for the easy and medium versions. But remember that now 1 ≤ _P_ ≤ 1000 and that the marmots may provide positive as well as negative integers.\n\n## Output\n\nOutput one line per village, in the same order as provided in the input. The village's line shall state _poisson_ if the village's distribution is of the Poisson type, and _uniform_ if the answers came from a uniform distribution.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你的任务与_简单_版本完全相同。但这次，土拨鼠在响应海蒂的请求前，会从其随机数中减去村庄的人口 #cf_span[P]。\n\n此外，现在有些村庄的人口甚至只有一个人，即 。\n\n你能帮助海蒂判断一个村庄遵循的是泊松分布还是均匀分布吗？\n\n与简单版和中等版相同。但请注意，现在 #cf_span[1 ≤ P ≤ 1000]，且土拨鼠可能提供正整数或负整数。\n\n请为每个村庄输出一行，顺序与输入中给出的顺序一致。若村庄的分布为泊松型，则输出 _poisson_；若答案来自均匀分布，则输出 _uniform_。\n\n## Input\n\n与简单版和中等版相同。但请注意，现在 #cf_span[1 ≤ P ≤ 1000]，且土拨鼠可能提供正整数或负整数。\n\n## Output\n\n请为每个村庄输出一行，顺序与输入中给出的顺序一致。若村庄的分布为泊松型，则输出 _poisson_；若答案来自均匀分布，则输出 _uniform_。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Given:  \n- A sequence of $ n $ integers $ a_1, a_2, \\dots, a_n $, each representing a response from a marmot in a village.  \n- Each response is of the form $ r_i - P $, where $ r_i $ is a random sample from either:  \n  - A **Poisson distribution** with parameter $ \\lambda = P $, or  \n  - A **uniform distribution** over $ \\{1, 2, \\dots, P\\} $.  \n- $ 1 \\leq P \\leq 1000 $, and $ P $ is the population of the village.  \n- Responses $ a_i $ can be positive, negative, or zero.  \n\nObjective:  \nFor each village, determine whether the underlying distribution of the *original* random samples $ r_i $ is Poisson or uniform, based on the observed responses $ a_i = r_i - P $.\n\nFormally:  \nLet $ S = \\{a_1, a_2, \\dots, a_n\\} $ be the multiset of observed responses.  \nDefine the unobserved samples as $ r_i = a_i + P $.  \n\n- If $ r_i \\sim \\text{Poisson}(P) $, then $ r_i \\in \\mathbb{Z}_{\\geq 0} $, and $ \\mathbb{E}[r_i] = P $, $ \\text{Var}(r_i) = P $.  \n- If $ r_i \\sim \\text{Uniform}\\{1, 2, \\dots, P\\} $, then $ r_i \\in \\{1, 2, \\dots, P\\} $, $ \\mathbb{E}[r_i] = \\frac{P+1}{2} $, $ \\text{Var}(r_i) = \\frac{P^2 - 1}{12} $.  \n\nThus, the observed responses $ a_i = r_i - P $ satisfy:  \n- Under Poisson: $ a_i \\in \\{-P, -P+1, \\dots\\} $, $ \\mathbb{E}[a_i] = 0 $, $ \\text{Var}(a_i) = P $.  \n- Under Uniform: $ a_i \\in \\{1 - P, 2 - P, \\dots, 0\\} $, $ \\mathbb{E}[a_i] = \\frac{1 - P}{2} $, $ \\text{Var}(a_i) = \\frac{P^2 - 1}{12} $.  \n\nDecision Rule:  \nCompute sample mean $ \\bar{a} = \\frac{1}{n} \\sum_{i=1}^n a_i $ and sample variance $ s^2 = \\frac{1}{n-1} \\sum_{i=1}^n (a_i - \\bar{a})^2 $ (or use population variance if preferred, but consistently).  \n\n- If $ |\\bar{a}| < \\varepsilon $ and $ s^2 \\approx P $, classify as **poisson**.  \n- If $ \\bar{a} \\approx \\frac{1 - P}{2} $ and $ s^2 \\approx \\frac{P^2 - 1}{12} $, classify as **uniform**.  \n\nUse a threshold $ \\varepsilon $ (e.g., $ 0.1 $) to distinguish $ \\bar{a} \\approx 0 $ from $ \\bar{a} \\approx \\frac{1-P}{2} $.  \nSince $ P \\geq 1 $, $ \\frac{1-P}{2} \\leq 0 $, and for $ P > 1 $, $ \\left| \\frac{1-P}{2} \\right| \\geq 0.5 $, so $ |\\bar{a}| < 0.1 $ strongly suggests Poisson.  \n\n**Formal Output Rule:**  \nFor each village with population $ P $ and observed responses $ a_1, \\dots, a_n $:  \n- Compute $ \\bar{a} $ and $ s^2 $.  \n- If $ |\\bar{a}| \\leq 0.1 $ and $ |s^2 - P| \\leq \\delta \\cdot P $ (for small $ \\delta $, e.g., 0.2), output **poisson**.  \n- Else if $ \\left| \\bar{a} - \\frac{1 - P}{2} \\right| \\leq 0.1 $ and $ \\left| s^2 - \\frac{P^2 - 1}{12} \\right| \\leq \\delta \\cdot \\frac{P^2 - 1}{12} $, output **uniform**.  \n- (In practice, due to distinct expectations, comparing $ |\\bar{a}| $ to 0.1 suffices for high accuracy.)  \n\n**Final Decision (Simplified):**  \n$$\n\\boxed{\n\\begin{cases}\n\\text{poisson} & \\text{if } |\\bar{a}| \\leq 0.1 \\\\\n\\text{uniform} & \\text{otherwise}\n\\end{cases}\n}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF802F","tags":["math","probabilities"],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}