[XJTUPC 2024] 最后一块石头的重量

Luogu

IDLGP10527

Time2000ms

Memory256MB

DifficultyP5

2024O2优化高校校赛

有一堆石头，用整数数组 $a$ 表示。其中 $a_i$ 表示第 $i$ 块石头的重量。每一回合，从中选出**任意两块石头**，然后将它们一起粉碎。假设石头的重量分别为 $x$ 和 $y$，且 $x \le y$。那么粉碎的可能结果如下： - 如果 $x = y$，那么两块石头都会被完全粉碎； - 如果 $x \neq y$，那么重量为 $x$ 的石头将会完全粉碎，而重量为 $y$ 的石头新重量为 $y-x$。最后，**最多只会剩下一块**石头。输出此石头**最小的可能重量**。如果没有石头剩下，就输出 $0$。 ## Input 输入数据共两行。第一行输入一个整数 $n$ ($1 \leq n \leq 10000$)，表示石子的数量；第二行输入 $n$ 个整数 $a_i$ ($1 \leq a_i \leq 5000$)，表示第 $i$ 块石头的重量。 ## Output 输出数据共一行。第一行输出一个整数表示答案。 [samples]

Samples

Input #1

6
2 7 4 1 8 1

Output #1

Input #2

5
31 26 33 21 40

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[XJTUPC 2024] 最后一块石头的重量",
    "description": {
      "content": "有一堆石头，用整数数组 $a$ 表示。其中 $a_i$ 表示第 $i$ 块石头的重量。 每一回合，从中选出**任意两块石头**，然后将它们一起粉碎。假设石头的重量分别为 $x$ 和 $y$，且 $x \\le y$。那么粉碎的可能结果如下： - 如果 $x = y$，那么两块石头都会被完全粉碎； - 如果 $x \\neq y$，那么重量为 $x$ 的石头将会完全粉碎，而重量为 $y$ 的石头新重",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10527"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一堆石头，用整数数组 $a$ 表示。其中 $a_i$ 表示第 $i$ 块石头的重量。\n\n每一回合，从中选出**任意两块石头**，然后将它们一起粉碎。假设石头的重量分别为 $x$ 和 $y$，且 $x \\le y$。那么粉碎的可能结果如下：\n\n- 如果 $x = y$，那么两块石头都会被完全粉碎；\n- 如果 $x \\neq y$，那么重量为 $x$ 的石头将会完全粉碎，而重量为 $y$ 的石头新重...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments