AT_arc234_d.Greedy Balancer
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is one red plate and one blue plate. There are also N stones numbered from 1 to N, and stone i has weight Wi.
An initial state is a state in which each stone is placed on one of the two plates. A plate may be empty.
You repeat the following operation until the total weight of the stones on the red plate equals the total weight of the stones on the blue plate.
- From the plate with the larger total weight, choose one of the lightest stones and move it to the other plate. If there are multiple lightest stones, you may choose any of them.
Find the number, modulo 998244353, of initial states for which this process terminates after a finite number of operations (possibly zero). Here, two initial states are distinguished when there is a stone that is on different plates in them. Stones with different numbers are distinguished.
有一个红色托盘和一个蓝色托盘。另有 N 颗编号为 1 至 N 的石子,其中石子 i 的重量为 Wi。
一个初始状态是指每颗石子被放置在两个托盘之一上的状态(某个托盘可以为空)。
你重复执行以下操作,直到红色托盘上石子的总重量等于蓝色托盘上石子的总重量:
- 在总重量较大的那个托盘上,选择一颗最轻的石子,将其移动到另一个托盘上;若存在多颗最轻的石子,则可任选其一。
求满足该过程能在有限步操作后(可能为零步)终止的初始状态个数,并对 998244353 取模。注意:若两个初始状态中存在某颗编号相同的石子位于不同托盘上,则视为不同的初始状态;编号不同的石子彼此可区分。
输入格式
The input is given from Standard Input in the following format:
N
W1 W2 … WN
输入从标准输入中按以下格式给出:
N
W1 W2 … WN
输出格式
Output the answer.
输出答案。
输入输出样例
输入#1
5 4 5 6 7 8
输出#1
16
输入#2
4 2 2 2 2
输出#2
16
输入#3
2 1 3
输出#3
0
输入#4
20 17 4 23 8 15 4 29 11 6 19 8 25 3 14 21 6 27 12 9 31
输出#4
557536
说明/提示
Sample 1 Explanation:
- If only stones 1,2 are on the red plate in the initial state, moving stone 3 from the blue plate makes both total weights 15, and the process terminates.
- If only stones 2,4 are on the red plate in the initial state, stone 1 keeps going back and forth between the two plates, so the process does not terminate.
There are 16 initial states that satisfy the condition.
Sample 2 Explanation:
From any initial state, the process reaches a state with two stones on each plate and terminates. Since stones with different numbers are distinguished even if they have the same weight, the answer is 24=16.
Constraints
- 2≤N≤500
- 1≤Wi≤500
- All input values are integers.
样例 1 解释:
- 若初始状态下仅有石子 1,2 位于红色托盘上,则将石子 3 从蓝色托盘移至红色托盘后,两托盘总重量均为 15,过程终止。
- 若初始状态下仅有石子 2,4 位于红色托盘上,则石子 1 将在两个托盘之间不断来回移动,因此过程不会终止。
满足条件的初始状态共有 16 种。
样例 2 解释:
从任意初始状态出发,该过程最终都会到达每个托盘上恰好有两颗石子的状态并终止。由于编号不同的石子即使重量相同也被视为不同,因此答案为 24=16。
约束条件
- 2≤N≤500
- 1≤Wi≤500
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?