1. Nuclear Reactor

Codeforces

IDCF1

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

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]

你正在为即将举行的线下编程竞赛制作若干条标语，每条标语上都要写有 "coderams"。然而，你拥有的字母贴纸数量有限。你只有一条包含 $n$ 个 lowercase 字母贴纸的长字符串。你的任务是，根据你拥有的字母贴纸，计算出最多能制作多少条完整的标语（标语必须完整写出 "coderams"，而不能只是部分字符串）。输入的第一行是一个正整数 $n$ $(1 \le n \le 10^5)$：表示你拥有的字母贴纸数量。第二行是一个长度为 $n$ 的字符串，每个字符代表一个贴纸上的字母。所有贴纸上的字母均为小写字母。请输出你能用现有贴纸制作出的完整标语的最大数量。 ## Input 输入的第一行是一个正整数 $n$ $(1 \le n \le 10^5)$：表示你拥有的字母贴纸数量。第二行是一个长度为 $n$ 的字符串，每个字符代表一个贴纸上的字母。所有贴纸上的字母均为小写字母。 ## Output 请输出你能用现有贴纸制作出的完整标语的最大数量。 [samples] ## Scoring 完整题目：6 分

**Definitions** Let $ n \in \mathbb{Z} $ be the number of letter stickers, with $ 1 \le n \le 10^5 $. Let $ S $ be a string of length $ n $, consisting of lowercase English letters, representing the available stickers. Let $ T = \text{"coderams"} $ be the target banner string, of length 8. **Constraints** - Each character in $ S $ is a lowercase letter from 'a' to 'z'. - Banners must be complete and identical to $ T $. **Objective** Compute the maximum number of complete copies of $ T $ that can be formed using the multiset of letters in $ S $, where each letter in $ S $ can be used at most once. Let $ f(c) $ denote the frequency of character $ c \in S $, and $ g(c) $ denote the frequency of $ c $ in $ T $. The maximum number of banners is: $$ \min_{c \in \text{"coderams"}} \left\lfloor \frac{f(c)}{g(c)} \right\rfloor $$

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": "CF1"
  },
  "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": "你正在为即将举行的线下编程竞赛制作若干条标语，每条标语上都要写有 \"coderams\"。然而，你拥有的字母贴纸数量有限。你只有一条包含 $n$ 个 lowercase 字母贴纸的长字符串。你的任务是，根据你拥有的字母贴纸，计算出最多能制作多少条完整的标语（标语必须完整写出 \"coderams\"，而不能只是部分字符串）。\n\n输入的第一行是一个正整数 $n$ $(1 \\le n \\le 10^5)$：...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of letter stickers, with $ 1 \\le n \\le 10^5 $.  \nLet $ S $ be a string of length $ n $, consisting of lowercase English letters, representing t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments