题目详情题解（0）讨论（0）提交记录（0）

AT_agc056_d.[AGC056D] Subset Sum Game

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

黑板上写有 NN 个整数，其中第 ii 个整数为 AiA_i。已知 NN 是偶数。同时，给定整数 L,RL,R。

Alice 和 Bob 进行一场游戏。两人轮流操作，由 Alice 先手。每一回合，当前玩家从黑板上选择一个数并将其擦去。

经过 NN 回合后，游戏结束。此时，设 Alice 擦去的所有整数之和为 ss。如果 L≤s≤RL \leq s \leq R，则 Alice 获胜；否则 Bob 获胜。假设双方都采取最优策略，问最终谁会获胜。

输入格式

输入以如下格式从标准输入读入：

NN LL RR A1A_1 A2A_2 ⋯\cdots ANA_N

输出格式

如果 Alice 获胜，输出 Alice；如果 Bob 获胜，输出 Bob。

输入输出样例

  • 输入#1

    4 5 6
3 1 4 5

    输出#1

    Alice

  • 输入#2

    2 2 3
4 1

    输出#2

    Bob

  • 输入#3

    30 655 688
42 95 9 13 91 27 99 56 64 15 3 11 5 16 85 3 62 100 64 79 1 70 8 69 70 28 78 4 33 12

    输出#3

    Bob

  • 输入#4

    30 792 826
81 60 86 57 5 20 26 13 39 64 89 58 43 98 50 79 58 21 27 68 46 47 45 85 88 5 82 90 74 57

    输出#4

    Alice

说明/提示

限制条件

  • 2≤N≤50002 \leq N \leq 5000
  • NN 是偶数
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • 0≤L≤R≤∑1≤i≤NAi0 \leq L \leq R \leq \sum_{1 \leq i \leq N} A_i
  • 所有输入的值均为整数

样例解释 1

在本场游戏中，Alice 一定能够获胜。以下是游戏进行的一个例子：

  • Alice 擦去 11。
  • Bob 擦去 44。
  • Alice 擦去 55。
  • Bob 擦去 33。
    此时，Alice 擦去的整数之和为 66，满足 L≤6≤RL \leq 6 \leq R，因此 Alice 获胜。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页