C. Ants

Codeforces

IDCF10250C

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Charles's program works as follows. It first scans the whole colony, building the list of tags of the ants that are recognized. Then it assigns fresh tags to the new ants. To do so, the program simply picks the first natural number (i.e., nonnegative integer) that is not currently assigned to any ant, and so on. Due to some glitches in the image recognition device and in the program, there are sometimes negative or very large numbers that appear in the input list. These are simply ignored by Charles's program. Your job is to reimplement the part of Charles's program that finds a fresh tag to assign to a new ant. The input consists of the following lines: The input satisfies $0 <= N <= 10^6$ . Each integer $X_i$ has less than 100 digits. The smallest natural number that does not belong to the set ${X_1, \\dots, X_N}$. ## Input The input consists of the following lines: on the first line: an integer $N$; on the next $N$ lines: some integers $X_1, \\dots, X_N$ , one per line. *Limits*The input satisfies $0 <= N <= 10^6$ . Each integer $X_i$ has less than 100 digits. ## Output The smallest natural number that does not belong to the set ${X_1, \\dots, X_N}$. [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, t\} $: - $ n_k \in \mathbb{Z} $ is the length of the string. - $ s_k \in \{ \text{TJ}, \text{si}, \text{log} \}^* $ is a string composed of concatenated substrings "TJ", "si", and "log". **Constraints** 1. $ 1 \le t \le 10^5 $ 2. $ 1 \le n_k \le 10^5 $ for each $ k $ 3. $ \sum_{k=1}^{t} n_k < 10^5 $ 4. $ s_k $ is a valid concatenation of the tokens "TJ", "si", and "log" in some order. **Objective** For each test case $ k $, determine: - $ h_k $: number of occurrences of "TJ" (hotdog servings), - $ r_k $: number of occurrences of "si" (fried rice servings), - $ e_k $: number of occurrences of "log" (egg servings). Output $ (h_k, r_k, e_k) $ for each $ k $.

API Response (JSON)

{
  "problem": {
    "name": "C. Ants",
    "description": {
      "content": "Charles's program works as follows. It first scans the whole colony, building the list of tags of the ants that are recognized. Then it assigns fresh tags to the new ants. To do so, the program simply",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10250C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Charles's program works as follows. It first scans the whole colony, building the list of tags of the ants that are recognized. Then it assigns fresh tags to the new ants. To do so, the program simply...",
      "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 $ k \\in \\{1, \\dots, t\\} $:  \n- $ n_k \\in \\mathbb{Z} $ is the length of the string.  \n- $ s_k \\in \\{ \\text{T...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments