1. Nuclear Reactor

Codeforces

IDCF102151

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Dream Land has $n$ nuclear reactor plants. Each of the plants is positioned on a straight line $p_i$ ($1 <= p_i <= 10^(18)$) At the beginning, all plants are inactive. The president of Dream Land wants to activate exactly $k$ ($1 <= k <= n$) plants in such away the distance between any two active plants is as large as possible. The president assigned this task to you. The first line of input consist of two integers $n$ ($1 <= n <= 10^5$) and $k$ ($1 <= k <= n$), the number of nuclear plants and the number of activated plants respectively. The second line consist of $n$ integers which are the positions of the nuclear reactor plants $p_i$ ($1 <= p_i <= 10^(18)$). The output consist of exactly $k$ integers the positions of activated plants such as the distance between any two activated plants is as large as possible. If there are multiple answers, print any of them. ## Input The first line of input consist of two integers $n$ ($1 <= n <= 10^5$) and $k$ ($1 <= k <= n$), the number of nuclear plants and the number of activated plants respectively. The second line consist of $n$ integers which are the positions of the nuclear reactor plants $p_i$ ($1 <= p_i <= 10^(18)$). ## Output The output consist of exactly $k$ integers the positions of activated plants such as the distance between any two activated plants is as large as possible. If there are multiple answers, print any of them. [samples]

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 1 \leq k \leq n \leq 10^5 $. Let $ P = (p_1, p_2, \dots, p_n) $ be a sequence of real numbers representing plant positions, with $ 1 \leq p_i \leq 10^{18} $. **Constraints** 1. $ P $ is not necessarily sorted. 2. Exactly $ k $ plants must be selected from $ P $. **Objective** Select a subset $ S \subseteq P $ with $ |S| = k $ such that the minimum distance between any two distinct selected plants is maximized. That is, maximize: $$ \min_{\substack{a, b \in S \\ a \ne b}} |a - b| $$ Output any such subset $ S $.

API Response (JSON)

{
  "problem": {
    "name": "1. Nuclear Reactor",
    "description": {
      "content": "Dream Land has $n$ nuclear reactor plants. Each of the plants is positioned on a straight line $p_i$ ($1 <= p_i <= 10^(18)$) At the beginning, all plants are inactive. The president of Dream Land want",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF102151"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Dream Land has $n$ nuclear reactor plants. Each of the plants is positioned on a straight line $p_i$ ($1 <= p_i <= 10^(18)$) At the beginning, all plants are inactive. The president of Dream Land want...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n \\leq 10^5 $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a sequence of real numbers representing plant positions, with $ 1 \\leq p_i \\le...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments