Codeforces Global Round 31 (Div. 1 + Div. 2)
H1
Bug Is Feature (Unconditional Version)
Codeforces
3400
原题
← GH2 →
翻译中…

This is the unconditional version of the problem. The difference between the versions is that in this version, there is no "non-decreasing common difference" condition. You can hack only if you solved all versions of this problem.

翻译中…

Note that neither version is necessarily easier than the other, and they can be solved independently.

翻译中…

Bug and Feature are immersed in a game of Sequence. In this unique version of the Sequence game, a sequence begins with three positive integers $a \lt b \lt c \le x$, forming an arithmetic progression (i.e., $b-a=c-b$). During each turn, a player can selectively increase one of $a$, $b$, or $c$ by a positive integer. After the move, the numbers must retain their arithmetic progression, possibly with a new order. Moreover, none of $a$, $b$, or $c$ should exceed $x$.

翻译中…

Not content with the conventional Sequence game, Bug and Feature decide to engage in a $n$ series of Sequence games simultaneously. For the $i$-th series, they are provided with five numbers $a_i \lt b_i \lt c_i \le l_i \le r_i$. They will play a game with numbers $a_i \lt b_i \lt c_i \le x$ for every integer $x$ in the range $[l_i, r_i]$ (resulting in a total of $\sum_{i=1}^n (r_i - l_i + 1)$ games). Taking turns, they play all the games together, with Bug starting first and then Feature. In each turn, a player selects an unfinished game and makes a move in that game. The player who cannot make a move loses.

翻译中…

Now, the question is: if both players play optimally, who will emerge victorious?

翻译中…

Input

翻译中…

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

翻译中…

The first line of each test case consists of a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of series of games that Bug and Feature wish to play.

翻译中…

Each of the next $n$ lines contains five integers $a_i, b_i, c_i, l_i, r_i$ — ($1 \le a_i \lt b_i \lt c_i \le l_i \le r_i \le 10^{18}$), representing the specifications of the $i$-th series of games. $a_i$, $b_i$, and $c_i$ form an arithmetic progression. $(c_i-b_i=b_i-a_i)$

翻译中…

The sum of $n$ over all test cases is at most $2 \cdot 10^5$.

翻译中…

Output

翻译中…

For each test, output $\mathtt{Bug}$ if Bug wins, and $\mathtt{Feature}$ if Feature wins.

翻译中…

Note

翻译中…

In the first test case, there are $2$ instances of the game, corresponding to each value of $x$ in the range $5$ to $6$. The sequence in each instance is initially $1,\;3,\;5$.

翻译中…

Bug can secure a winning strategy as follows:

翻译中…
  1. In the instance with $x = 5$, Bug changes $a$ from $1$ to $4$. Consequently, the sequence becomes $3,\;4,\;5$, and it is easy to verify that no further move is possible in this instance.
  2. Next, Feature must play by changing the value of $a$ from $1$ to $4$ in the instance with $x = 6$.
  3. Then, Bug responds by changing $b$ from $3$ to $6$ in the instance with $x = 6$. After this move, the sequence in that instance also becomes fixed, and no further operation can be performed.
翻译中…

Thus, after these moves, both instances reach states where no player can make any additional move, ensuring Bug's victory.

翻译中…

样例

Input #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
Output #1
Bug
Bug
Feature
Feature
Feature
InputCopy OutputCopy
题目信息
题号
2180H1
时间限制
2 s
内存限制
256 MB
标签
博弈论

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。