[海淀区普及组 2025 T4] 抽奖游戏

Luogu
IDLGB4456
Time2000ms
Memory512MB
DifficultyP5
2025北京初中活动
元旦联欢会的最后自然少不了抽奖环节!这次抽奖,小橙志在必得…… 有编号为 $1$ 到 $n$ 的 $n$ 个同学和小橙(编号为 $n+1$)来参加抽奖。每个人都收到了一张写有 $0$ 到 $m$ 之间整数的奖券。 抽奖的规则是:将在 $0$ 到 $m$ 之间均匀随机抽取一个整数作为目标数,奖券上数字与目标数最接近的 $k$ 张奖券持有者(如果参与者不足 $k$ 人,则是全部参与者)中奖。如果有多张奖券与目标数的距离相同,则之中编号较小的那些人优先中奖。 现在,小橙知道其它 $n$ 位参与者奖券上的数字,他可以任意选择自己奖券上的数字。为了赢得抽奖,他想知道以下两个问题的答案: 1. 最大化自己的获胜概率时,有多少目标数可以让他获胜? 2. 应该选择哪个数字,才能最大化自己获胜的概率?如果有多个这样的数字,他想知道最小的那个。 ## Input 输入的第一行包含整数 $n$、$m$ 和 $k$($1 \leq n \leq 10^6$,$0 \leq m \leq 10^{18}$,$1 \leq k \leq 10^6$)。 接下来一行有 $n$ 个用空格分隔的整数,第 $i$ 个数字表示编号为 $i$ 的学生奖券上的数字,这些数字是 $0$ 到 $m$ 之间的整数。 ## Output 你需要输出两个用空格分隔的整数。第一个是小橙在最优选择下能获胜的目标数的个数,第二个是他应选择的奖券数字。 [samples] ## Note 样例说明: 第一个例子中,如果小橙选择数字 $2$,那么当目标数为 $0、1、2、3$ 时他会获胜,共有 $4$ 种情况,这是最优且最小的选择。如果他选择 $3$,同样可以获胜 $4$ 次,但不是最小的选择。 数据范围: |占比 |n |m |k | |:-:|:-------:|:-------:|:---:| |$15\%$|$\le 400$|$\le 400$|无额外限制| |$5\%$ |无额外限制|无额外限制|$\gt n$| |$15\%$|无额外限制|无额外限制|=1| |$15\%$|无额外限制|$\le 2000$|无额外限制| |$20\%$|$\le 2000$|无额外限制|无额外限制| |$15\%$|无额外限制|$\le 10^6$|无额外限制| |$15\%$|无额外限制|无额外限制|无额外限制|
Samples
Input #1
3 6 2
1 4 5
Output #1
4 2
Input #2
7 7 1
2 4 7 3 0 1 6
Output #2
1 5
API Response (JSON)
{
  "problem": {
    "name": "[海淀区普及组 2025 T4] 抽奖游戏",
    "description": {
      "content": "元旦联欢会的最后自然少不了抽奖环节!这次抽奖,小橙志在必得…… 有编号为 $1$ 到 $n$ 的 $n$ 个同学和小橙(编号为 $n+1$)来参加抽奖。每个人都收到了一张写有 $0$ 到 $m$ 之间整数的奖券。 抽奖的规则是:将在 $0$ 到 $m$ 之间均匀随机抽取一个整数作为目标数,奖券上数字与目标数最接近的 $k$ 张奖券持有者(如果参与者不足 $k$ 人,则是全部参与者)中奖。如果有",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4456"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "元旦联欢会的最后自然少不了抽奖环节!这次抽奖,小橙志在必得……\n\n有编号为 $1$ 到 $n$ 的 $n$ 个同学和小橙(编号为 $n+1$)来参加抽奖。每个人都收到了一张写有 $0$ 到 $m$ 之间整数的奖券。\n\n抽奖的规则是:将在 $0$ 到 $m$ 之间均匀随机抽取一个整数作为目标数,奖券上数字与目标数最接近的 $k$ 张奖券持有者(如果参与者不足 $k$ 人,则是全部参与者)中奖。如果有...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments