#agc056d. [agc056_d]Subset Sum Game

[agc056_d]Subset Sum Game

一块黑板上写着 nn 个整数。第 ii 个整数记作 aia_i。保证 nn 是偶数。此外,给定 L,RL,R

Alice 和 Bob 在玩一个游戏。他们轮流操作,Alice 先手。在每一轮中,玩家需要选择一个写在黑板上的数,并擦掉它。

游戏会在 nn 轮后结束。令 ss 为 Alice 擦掉的数之和。若 LsRL \le s \le R,则 Alice 胜利,反之 Bob 胜利。你需要输出当两方都采取最优策略情况下的赢家。

$2\le n\le 5000,\ 1\le a_i\le 10^9, 0\le L \le R \le \sum_{1\le i\le n} a_i$。