How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?
Learn More

Zonal Computing Olympiad 2018 Questions.

These are the Questions from Zonal Computing Olympiad 2018  Exam of International Infromatics Olympiad held in Tsukuba, Japan.

Problem 1 : BIRTHDAY-CAKES
In a birthday party, there are C cakes and N children. There is also an integer k, given.
But since eating too much of cakes can give you toothache, each of the children have been prescribed by doctors to eat cakes that fall only within a specific interval (a,b) both inclusive.

If k = 0, you have answer if any of the students' ranges clash or not.
That is print "GOOD" ( without quotes ) if ranges do not clash and "BAD" ( without quotes ) if they will fight over their share of cakes.

If k=1, then you have a chance to stop them to stop them from fighting. You are allowed to move at max 1 child from his place and allot him a different range, PROVIDED THAT HE IS STILL ABLE  TO HAVE THE SAME NUMBER OF CAKES AS HE WOULD HAVE HAD IN HIS PREVIOUS RANGE.
If you can prevent all the fights among the children, by 'moving' only one child , print "GOOD"  ( without quotes ) , else print "BAD" ( without quotes ).

Input Format

A single line containing an integer t, denoting the number of test cases.
For each test case, input 3 space separated integers denoting N, C and k
For each test cases, lines follow, denoting the ranges within which the children can enjoy cakes.

Output Format
t
lines.
Each line containing either "GOOD" or "BAD" , as applicable.

Sample Testcases

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

In the second test case, the child at [2,2] can be moved to [1,1] so that there are no fights anymore. Also, note that the child can still enjoy 1 cake as he would have done, had his position not been 'moved'.

Problem 2: IMPORTANT STRINGS

After having cakes at the birthday, you've got to study some English.
You may feel strings are a random collection of characters, but no they are important, and this is how.
Suppose you have a string S of length N consisting of XY, and .
A string is 'good' if it starts with a 'X' , ends with a 'Z' and has a length divisible by 3. ( That is permissible lengths are 3, 6, 9....and so on )

The importance of a string is the number of good string it intersects with.

Given the string S and a length k, find a string of length exactly k and minimize it's importance.
Your job is to print the minimum importance.

Input Format

The first line contains a single integer t, denoting the number of test cases.
Each test case contains two lines.
The first line of each test case contains two space separated integers denoting and k.
The second line of each test case contains the string S.

Output Format
lines.
Each line contains a single integer denoting the required minimum importance.

Sample Testcases

Input
2
9 3
X Y Z Z Y X X Y Z
4 2
Y X Y Z

Output
1
1

Explanation
In the first testcase, the good strings are in the ranges [0,2] [0,8] and [6,8]. ( 0-based indexing has been used )
Now consider the string at [5,8]. It is of length k=3. It intersects with only one good string [0,8] ; ( the entire one ).
That's the best we can do. So it has importance 1, and that's our desired output.

You may visit this link to see the solutions:- https://www.cheenta.com/zonal-computing-olympiad-2018-solutions-i/

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
CAREERTEAM
support@cheenta.com