[海淀区小学组 2023] 分数线

Luogu

IDLGB4192

Time500ms

Memory512MB

DifficultyP2

2023北京前缀和科创活动小学活动

一次比赛中，所有参加比赛的选手都获得了一个分数 $ s $。已知有 $ c_1 $ 个同学得 $1$ 分，$ c_2 $ 个同学得 $2$ 分，……，$ c_m $ 个同学得 $ m $ 分。请你划定一个分数线 $ k $，使得不低于分数线 $ k $ 的人数 $ n_1 $ 和低于分数线 $ k $ 的人数 $ n_2 $ 均在给定的一个范围 $[x, y]$ 之内，即 $ x \leq n_1 \leq y $，$ x \leq n_2 \leq y $。保证 $ s $ 和 $ k $ 一定是整数，且 $ 1 \leq s \leq m $，$ 1 \leq k \leq m $。 ## Input 第一行仅有一个正整数 $ m $；第二行包含 $ m $ 个整数 $ c_1, c_2, \ldots, c_m $，两两之间以空格分隔，数据保证至少有一个 $ c_i $ 大于 $0$；第三行包含两个用空格分隔的整数 $ x $ 和 $ y $。 ## Output 如果不存在满足条件的分数线，输出 $0$。否则，输出一个分符合题目要求的分数线。如果有多个答案，输出符合条件的答案中最小的那一个。 [samples] ## Background 2023 年海淀区中小学生信息学竞赛小学组复赛题目，数据为洛谷自造。为更好区分不同做法，本题时限下调到 500 毫秒。 ## Note ### 样例解释在样例 $1$ 中，如果把分数线划定为 $3$，则有 $7$ 个学生低于分数线，$6$ 个同学不低于分数线，人数都在 $[6,8]$ 范围内。在样例 $2$ 中，分数线划定为 $3$ 和 $4$ 都可以，但按照题目的要求应该输出更小的答案，应该是 $3$。 ### 数据范围对于 $50\%$ 的数据，$ 2 \leq m \leq 100 $，$ 0 \leq c_i \leq 100 $，$ 1 \leq x \leq y \leq 10000 $。对于 $100\%$ 的数据，$ 2 \leq m \leq 10^5 $，$ 0 \leq c_i \leq 10^5 $，$ 1 \leq x \leq y \leq 10^9 $。

Samples

Input #1

5
3 4 3 2 1
6 8

Output #1

Input #2

5
0 3 3 4 2
3 10

Output #2

Input #3

2
2 5
3 6

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[海淀区小学组 2023] 分数线",
    "description": {
      "content": "一次比赛中，所有参加比赛的选手都获得了一个分数 $ s $。已知有 $ c_1 $ 个同学得 $1$ 分，$ c_2 $ 个同学得 $2$ 分，……，$ c_m $ 个同学得 $ m $ 分。 请你划定一个分数线 $ k $，使得不低于分数线 $ k $ 的人数 $ n_1 $ 和低于分数线 $ k $ 的人数 $ n_2 $ 均在给定的一个范围 $[x, y]$ 之内，即 $ x \\leq n",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4192"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一次比赛中，所有参加比赛的选手都获得了一个分数 $ s $。已知有 $ c_1 $ 个同学得 $1$ 分，$ c_2 $ 个同学得 $2$ 分，……，$ c_m $ 个同学得 $ m $ 分。\n\n请你划定一个分数线 $ k $，使得不低于分数线 $ k $ 的人数 $ n_1 $ 和低于分数线 $ k $ 的人数 $ n_2 $ 均在给定的一个范围 $[x, y]$ 之内，即 $ x \\leq n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments