I. Rats

Codeforces

IDCF10250I

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Douglas is asking for your help to estimate the total number of rats in his area. Looking up in your statistics textbook, you propose using the Chapman estimator $hat(N)$, given by: $$ \widehat{N} = \left\lfloor \frac{(n_1+1)(n_2+1)}{n_{12}+1} -1\right\rfloor $$ where $floor.l x floor.r$ is the #cf_span(class=[tex-font-style-underline], body=[floor]) of a real number $x$, i.e., the closest integer less than or equal to $x$. The input consists of a single line, with three space-separated integers: $n_1$, $n_2$, $n_(12)$, in that order. *Limits* The output should contain a single line with the single integer $hat(N)$. ## Input The input consists of a single line, with three space-separated integers: $n_1$, $n_2$, $n_{12}$, in that order.*Limits* $0 <= n_1, n_2 <= 10000$; $0 <= n_{12} <= min (n_1, n_2)$. ## Output The output should contain a single line with the single integer $hat(N)$. [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ n, k \in \mathbb{Z} $ denote the number of people and shopkeepers, respectively. - Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of kiping requested by person $ i $. Let $ \mathcal{P} $ be the set of all partitions of $ A $ into $ k $ ordered lists (lines), where each person appears in exactly one line. **Constraints** 1. $ 1 \le t \le 100 $ 2. $ 1 \le n \le 10^5 $, $ 1 \le k \le 10^5 $ 3. $ 1 \le a_i \le 10^9 $ 4. The sum of all $ n $ across test cases is $ \le 10^5 $ **Objective** For each test case, compute: 1. **Minimum total waiting time**: $$ \min_{\mathcal{P}} \sum_{\ell=1}^{k} \sum_{j=2}^{|\ell|} \left( \sum_{i=1}^{j-1} a_{\ell_i} \right) $$ where $ \ell $ is a line (ordered list) of people, and $ \ell_i $ is the $ i $-th person in line $ \ell $. 2. **Number of distinct arrangements achieving the minimum total waiting time**, modulo $ 10^9 + 7 $. **Note**: The waiting time of a person is the sum of the $ a_i $ of all people ahead of them in their line. The total waiting time is the sum over all people.

API Response (JSON)

{
  "problem": {
    "name": "I. Rats",
    "description": {
      "content": "Douglas is asking for your help to estimate the total number of rats in his area. Looking up in your statistics textbook, you propose using the Chapman estimator $hat(N)$, given by: $$ \\widehat{N} = \\",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10250I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Douglas is asking for your help to estimate the total number of rats in his area. Looking up in your statistics textbook, you propose using the Chapman estimator $hat(N)$, given by: $$ \\widehat{N} = \\...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n, k \\in \\mathbb{Z} $ denote the number of people and shopkeepers, respectively.  \n- Let $ A = (...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments