F. A Missing Problem in TCPC2017

Codeforces

IDCF10191F

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

While the judges of TCPC were busy preparing the problems, they encountered a strange problem. One of the problems was missing !! The judges remember that they prepared exactly N problems and that they were numbered from 1 to N. They also remembered that the problems were sorted according to their number. The judges started investigating but they realized that they don't have enough time, so they asked the contestants for help. The first line contains a single integer T, the number of test cases. The first line of each test case consists of a single integer N (2 ≤ N ≤ 12), denoting the number of problems. The second line of each test case contains N - 1 space separated integer denoting the number of each problem the judges didn't miss. Yet! it's guaranteed that the numbers are given in the increasing order. For each test case print a single line, containing a single integer, denoting the number of the missing problem. ## Input The first line contains a single integer T, the number of test cases. The first line of each test case consists of a single integer N (2 ≤ N ≤ 12), denoting the number of problems.The second line of each test case contains N - 1 space separated integer denoting the number of each problem the judges didn't miss. Yet!it's guaranteed that the numbers are given in the increasing order. ## Output For each test case print a single line, containing a single integer, denoting the number of the missing problem. [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of events, with $ 1 \leq N \leq 10^5 $. Let $ p_i \in \mathbb{R} $ be the success probability for event $ i $, with $ 0 \leq p_i \leq 1 $ and at most 4 decimal digits. **Constraints** Each $ p_i $ is given exactly (no rounding, truncation, or ceiling). **Objective** For each $ i \in \{1, \dots, N\} $, find the minimum positive integer $ n_i \in \mathbb{Z}^+ $ such that there exists an integer $ k_i \in \{0, 1, \dots, n_i\} $ satisfying: $$ \frac{k_i}{n_i} = p_i $$

API Response (JSON)

{
  "problem": {
    "name": "F. A Missing Problem in TCPC2017",
    "description": {
      "content": "While the judges of TCPC were busy preparing the problems, they encountered a strange problem. One of the problems was missing !! The judges remember that they prepared exactly N problems and that th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10191F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "While the judges of TCPC were busy preparing the problems, they encountered a strange problem. One of the problems was missing !!\n\nThe judges remember that they prepared exactly N problems and that th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of events, with $ 1 \\leq N \\leq 10^5 $.  \nLet $ p_i \\in \\mathbb{R} $ be the success probability for event $ i $, with $ 0 \\leq p_i \\leq 1 $ and...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments