CFCF2180H2.Bug Is Feature (Conditional Version)
省选/NOI-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
这是该题的条件版本。这个版本与原问题的主要区别在于,“公差不减”这一条件的存在。只有你完成了所有版本的题目后,才能进行 Hack 操作。
请注意,这两个版本并不必然哪个更容易,并且它们可以独立地进行求解。
Bug 和 Feature 正沉浸在一种名为 Sequence 的游戏中。在这个独特版本的 Sequence 游戏中,游戏以三个正整数 a<b<c≤x 开始,并且三者构成一个等差数列(即 b−a=c−b)。每当轮到玩家时,可以选择将 a、b 或 c 的其中一个增加一个正整数。操作后,三个数仍需保持等差数列(可能顺序会变化),且新的公差不能小于之前的公差。此外,a、b、c 均不能超过 x。
Bug 和 Feature 并不满足与常规的 Sequence 游戏,于是他们决定同时玩 n 组 Sequence 游戏。对于第 i 组游戏,给定五个数 ai<bi<ci≤li≤ri。对于每一个 x∈[li,ri],他们要玩一个以 ai<bi<ci≤x 为初始状态的游戏(一共要玩 ∑i=1n(ri−li+1) 个游戏)。两人交替进行所有这些游戏的回合,Bug 先手,然后 Feature。每回合,玩家选择任意一个未结束的游戏执行一次有效操作。无法进行操作的一方视为失败。
那么,若两人均以最优策略博弈,最终谁会获得胜利?
输入格式
每个测试用例包含多组数据。第一行包含整数 t(1≤t≤105),表示测试用例的数量。
每个测试用例的第一行是一个整数 n(1≤n≤2×105),表示 Bug 和 Feature 要玩的游戏组数。
接下来的 n 行,每行包含五个整数 ai,bi,ci,li,ri(1≤ai<bi<ci≤li≤ri≤1018),表示第 i 组游戏的参数。ai、bi、ci 形成等差数列(即 ci−bi=bi−ai)。
所有测试用例的 n 之和不超过 2×105。
输出格式
对于每组测试数据,输出一行,若 Bug 获胜则输出 Bug,否则输出 Feature。
输入输出样例
输入#1
5 1 1 3 5 5 6 1 2 4 6 8 10 2 4 6 8 10 11 4 8 12 16 19 1 1 2 3 3 3 1 1000000000000 2000000000000 3000000000000 4000000000000 5000000000000
输出#1
Feature Bug Feature Feature Bug
说明/提示
在第一个样例中,游戏一开始就没有合法的操作。因此,Bug 无法进行任何操作,Feature 立即获胜。
在第二个样例中,有 3 个实例游戏,分别对应 x=8,9,10。每个实例初始序列均为 2, 4, 6。
Bug 可以这样取得胜利:
- 针对 x=10 的实例,Bug 将 b 从 4 增加到 10,此时序列变为 2,6,10。此时这个实例已经无法进行更多操作。
- 下一步 Feature 必须从剩余的两个实例中选择一个,将 a 从 2 增加到 8(无论是 x=8 还是 x=9 的游戏)。
- 无论 Feature 选择哪一个,Bug 都可以在另外一个实例中也将 a 变为 8。此时这个实例也变为无法再操作的状态。
这样,所有的实例都进入了无法进行操作的状态,从而确保了 Bug 的胜利。