183. Number Destruction

Codeforces

IDCF10269183

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

After destroying half of all life in the universe, Thanos decides to destroy one-third of all positive integers in the universe. Thanos starts by destroying 0, and then proceeds to destroy any positive integers that are a multiple of 3. Your task is to find the first $n$ integers that are left (have not been destroyed) after Thanos applies this operation. For example, the first 5 integers that are left are 1, 2, 4, 5, and 7. The only line of input consists of a single positive integer $n$: the number of integers to print. Output $n$ lines: the first $n$ integers that were not destroyed by Thanos. ## Input The only line of input consists of a single positive integer $n$: the number of integers to print. ## Output Output $n$ lines: the first $n$ integers that were not destroyed by Thanos. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of surviving integers to output. Let $ D = \{ 3k \mid k \in \mathbb{Z}_{\geq 0} \} $ be the set of destroyed integers. Let $ S = \mathbb{Z}^+ \setminus D $ be the set of surviving positive integers. **Constraints** $ 1 \leq n \leq \text{large enough to ensure at least } n \text{ survivors} $ **Objective** Output the first $ n $ elements of $ S $ in increasing order: $$ \min^{(1)}(S), \min^{(2)}(S), \dots, \min^{(n)}(S) $$ where $ \min^{(k)}(S) $ denotes the $ k $-th smallest element of $ S $.

API Response (JSON)

{
  "problem": {
    "name": "183. Number Destruction",
    "description": {
      "content": "After destroying half of all life in the universe, Thanos decides to destroy one-third of all positive integers in the universe. Thanos starts by destroying 0, and then proceeds to destroy any positiv",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269183"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After destroying half of all life in the universe, Thanos decides to destroy one-third of all positive integers in the universe. Thanos starts by destroying 0, and then proceeds to destroy any positiv...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of surviving integers to output.  \nLet $ D = \\{ 3k \\mid k \\in \\mathbb{Z}_{\\geq 0} \\} $ be the set of destroyed integers.  \nLet $ S = \\mathbb{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments