AT_agc056_d [AGC056D] Subset Sum Game

[problemUrl]: https://atcoder.jp/contests/agc056/tasks/agc056_d 黒板に $ N $ 個の整数が書かれており，そのうち $ i $ 番目の整数は $ A_i $ です． なお，$ N $ は偶数です． また，整数 $ L,R $ が与えられます． Alice と Bob がゲームをします． 二人は Alice からはじめて交互に手番をプレイします． 各手番では，プレイヤーは黒板に書かれている数を一つ選んで消します． $ N $ ターン後にゲームが終了します． ここで，Alice が消した整数の総和を $ s $ とします． $ L\ \leq\ s\ \leq\ R $ であれば Alice の勝利，そうでなければ Bob の勝利です． 両者が最適に行動した時，どちらが勝つか求めてください．

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 5000 $ - $ N $ は偶数 - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 0\ \leq\ L\ \leq\ R\ \leq\ \sum_{1\ \leq\ i\ \leq\ N}\ A_i $ - 入力される値はすべて整数である ### Sample Explanation 1 このゲームでは Alice が必ず勝ちます． ゲームの進行の一例を以下に示します． - Alice が $ 1 $ を消す． - Bob が $ 4 $ を消す． - Alice が $ 5 $ を消す． - Bob が $ 3 $ を消す． この時，Alice が消した整数の総和は $ 6 $ であり，$ L\ \leq\ 6\ \leq\ R $ なので，Alice の勝利です．