Moving Intervals  ZCO 2018

All submissions for this problem are available.
There are C cakes in a row, numbered from 1 to C. There are N children, each of whom have selected a consecutive set of cakes to eat. That is, Child i has decided to eat all the cakes from S_{i} to E_{i}, end points inclusive. If there is a cake which appears in some two childrens' set, then they will fight because both of them want to eat that cake, and you don't want that to happen.
You will be given an integer K which will be either 0 or 1. If K is 0, then you should find out if some two children will fight. Print "Good" if no one fights, and "Bad" if someone fights.
If K is 1, then you can persuade at most one child to change his decision to some other set of cakes. But the number of cakes that he eats must be the same. That is, if Child i had initially decided that he wants to eat the cakes from S_{i} to E_{i}, then you could persuade the child to instead eat the cakes from X to Y instead, for any valid X and Y (ie. 1 ≤ X ≤ Y ≤ C), provided that the number of cakes is the same (ie. E_{i}  S_{i} + 1 = Y  X + 1). If after persuading at most 1 Child to change his decision, no fights happen, then print "Good". But if no matter what you do, someone will fight, then print "Bad".
Input
The first line of the input contains an integer T denoting the number of test cases. The description of each test case follows.
The first line of each test case contains three integers C, N and K denoting the number of cakes, number of children and K, respectively.
The ith of the next N lines contains two space separated integers S_{i} and E_{i} which denotes the initial decision of Child i. That is, Child i wants to eat from cake S_{i} to cake E_{i}.
Output
For each test case, output a single line containing "Good" or "Bad".
Constraints
 1 ≤ T ≤ 10
 1 ≤ C ≤ 10^{9}
 1 ≤ N ≤ 10^{5}
 0 ≤ K ≤ 1
 1 ≤ S_{i}, E_{i} ≤ C
Subtasks:
 Subtask #1 (15 points):
 K = 0
 1 ≤ N ≤ 1000
 E_{i} ≤ C/2, for all 1 ≤ i ≤ N
 Subtask #2 (10 points):
 1 ≤ N ≤ 1000
 E_{i} ≤ C/2, for all 1 ≤ i ≤ N
 Subtask #3 (25 points):
 1 ≤ N ≤ 1000
 Subtask #4 (50 points): Original constraints.
Example
Input: 3 5 2 0 2 2 3 5 5 2 1 2 2 2 5 5 2 1 2 3 2 5 Output: Good Good Bad
Explanation
Test case 1: Child 1 wants to eat the second cake, and Child 2 wants to eat Cakes 3, 4 and 5. So there is no fight, and the answer is "Good".
Test case 2: Child 1 wants to eat Cake 2, and Child 2 wants to eat Cakes 2, 3, 4 and 5. Both of them want to eat Cake 2, and hence it could lead to a fight. But because K = 1, we can persuade one of the children to change their decision. For instance, we could persuade Child 1 to change his decision from [2, 2] to [1, 1]. After this, there is no fight, and the hence answer is "Good".
Test case 3: Child 1 wants to eat Cake 2 and Cake 3, and Child 2 wants to eat Cakes 2, 3, 4 and 5. Both of them want to eat Cakes 2 and 3, and hence it could lead to a fight. And because K = 1, we can persuade one of the children to change their decision. For instance, we could persuade Child 1 to change his decision from [2, 3] to [1, 2]. But even after this, both of them want to eat Cake 2. You can verify that no matter how we persuade at most 1 child, they will end up fighting. Hence the answer is "Bad".
Author:  admin3 
Date Added:  11112017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions