ZOJ Problem Set - 3994
BaoBao receives lots of candies as his birthday gift. But this time he is not happy, because his heart was hurt by some terrible problem setters during the just-ended competitive programming contest season. To heal his heart, he invites his best friend DreamGrid to his dorm to enjoy the candies.
There are two kinds of candies: green and blue. BaoBao enjoys green candies best, and DreamGrid likes blue candies. They have arranged their candies into \(N\) piles, the \(i\)-th pile has \(a_i\) green candies and \(b_i\) blue candies, and they decides to play a game.
In one turn, BaoBao or DreamGrid can (and must, if possible) choose one pile of candies which contains his favorite candies, and eat any amount (at least one) of his favorite candies (That is to say, BaoBao can only eat green candies, and DreamGrid can only eat blue ones). The one who eats the last candy of all wins. If there is no candy for one to eat, his turn will be skipped.
They will eat in turn, and BaoBao eats first. Now the two want to know, if they both use the best strategy, who will win the game?
Fortunately, BaoBao has just learnt the SG Function during the contest season. But soon he discovers with dismay that this is not a Nim Game, and it's not even a fair one. This problem is so difficult for him to solve. Can you please comfort poor BaoBao by solving this problem?
The first line of the input is an integer \(T\) (about 10), which indicates the number of test cases. Then \(T\) test cases follow.
The first line of each test case contains one integer \(N\) (\(1 \le N \le 1000\)), indicating the number of candy piles.
The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 1000\)), and the third line contains \(N\) integers \(b_1, b_2, \dots, b_N\) (\(1 \le b_i \le 1000\)).
For each test case output one line. If BaoBao wins, output "BaoBao" (without quotes), otherwise output "DreamGrid" (without quotes).
2 2 2 5 3 3 2 3 3 2 5
Author: WENG, Caizhi
Source: ZOJ Monthly, January 2018