{"problem":{"name":"[语言月赛202303] Coin Selection G","description":{"content":"Farmer John 和 Bessie 正在一起玩硬币选择游戏。 初始时桌面上有 $n$ 枚硬币，每枚硬币有一个面额，我们使用 $a _ 1, a _ 2, \\cdots, a _ n$ 分别代表第 $1, 2, \\cdots, n$ 枚硬币的面额。 他们还各有一个属于自己的钱包，初始时，钱包都是空的。 从 **Farmer John** 开始，双方轮流操作。每次操作中，当前的操作者会从桌","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P1"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3723"},"statements":[{"statement_type":"Markdown","content":"Farmer John 和 Bessie 正在一起玩硬币选择游戏。\n\n初始时桌面上有 $n$ 枚硬币，每枚硬币有一个面额，我们使用 $a _ 1, a _ 2, \\cdots, a _ n$ 分别代表第 $1, 2, \\cdots, n$ 枚硬币的面额。\n\n他们还各有一个属于自己的钱包，初始时，钱包都是空的。\n\n从 **Farmer John** 开始，双方轮流操作。每次操作中，当前的操作者会从桌面上剩余的硬币中选择**面值不超过当前自己钱包中硬币的总面额**的硬币中**面额最大的**一枚硬币，把它从桌子上拿走，放到自己的钱包里。如果桌面上剩余的**所有**硬币面值都**超过了自己钱包里已有硬币的总面额**，那么选择剩余的所有硬币中面额**最小**的一个。\n\n当桌面上没有硬币时，游戏结束。\n\n请你分别求出，\t游戏结束后，Farmer John 和 Bessie 钱包里硬币的总面额。\n\n## Input\n\n第一行为一个整数，代表初始时桌面上的硬币的数量 $n$。  \n第二行为 $n$ 个整数 $a _ 1, a _ 2, \\cdots, a _ n$，分别代表第 $1, 2, \\cdots, n$ 枚硬币的面额。\n\n## Output\n\n输出共一行两个整数，第一个整数表示 Farmer John 最终钱包里的总面额，第二个整数表示 Bessie 最终钱包里硬币的总面额，两个整数之间使用一个空格隔开。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\nFarmer John 开始时「自己钱包中硬币的总面额」为 $0$，小于桌面上的任何一枚硬币，因此他只能选择剩下的所有硬币中面值最小的一个，为 $2$。\n\n接下来 Bessie「自己钱包中硬币的总面额」为 $0$，小于桌面上的任何一枚硬币，因此只能选择剩下的所有硬币中面值最小的一个，为 $3$。\n\n### 数据规模与约定\n\n- 对 $20\\%$ 的数据，保证 $n \\leq 2$。\n- 另有 $20\\%$ 的数据，保证 $a_i = 1$。\n- 对 $60\\%$ 的数据，保证 $n \\leq 100$。\n- 对 $100\\%$ 的数据，保证 $1 \\leq n \\leq 10^3$，$1 \\leq a_i \\leq 10^{16}$。\n\nprovider：一扶苏一","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3723","tags":["2023","O2优化","数组","语言月赛"],"sample_group":[["2\n3 2","2 3"],["5\n1 2 3 4 5","9 6"]],"created_at":"2026-03-03 11:09:25"}}