CFCF2180H1.Bug Is Feature (Unconditional 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。
他们不满足于传统 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)——表示想要玩的游戏组数。
接下来 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
Bug Bug Feature Feature Feature
说明/提示
在第一个样例中,有 2 个局面,分别对应 x 在 5 到 6 之间的每个取值。每局初始序列均为 1, 3, 5。
Bug 的制胜策略如下:
- 在 x=5 的局面中,Bug 将 a 从 1 改为 4,此时序列变为 3, 4, 5,此时无进一步操作。
- 接下来 Feature 只能在 x=6 的局面中将 a 从 1 改为 4。
- 然后 Bug 在 x=6 局面中将 b 从 3 改为 6,此时序列也被固定,无法继续操作。
因此,每一局在这样的步骤后均无法继续操作,从而保证了 Bug 的胜利。