Bangladesh Informatics Olympiad 2013

Venue: UITS, Dhaka. Date: 26th January, 2013

General Instructions
1. 2. 3. 4. The contest will run for 4 hours. There are 7 problems in total. You need to write a C/C++ code to solve the problems. Do not use any spaces in the file name that you will submit. This will give you compile error. 5. There is a glossary added in the last page. See that if you dont understand the meaning of any word. 6. During contest, you are not allowed to talk to a fellow contestant. Ask the volunteers for any help. 7. You are not allowed to use calculators, pen-drives, mobiles or any other digital instruments. You are not allowed to use any books or printed materials. Basically the things that you are allowed to use are pen, paper, computer and your brain.

A Discovering DNA
DNA is one of the major macromolecules that are essential for all known forms of life. Genetic information is encoded as a sequence of nucleotides in DNA. There are four types of nucleotide in DNA, Adenine (A), Guanine (G), Cytosine (C) and Thymine (T). These four nucleotides are expressed as A, G, C and T respectively. Little sheep is interested in DNA sequencing and found a sequence of nucleotides. He wonders whether this is a DNA or not. Help him to discover DNA. You will be given a string representing the sequence, tell him whether it is DNA or not. The sequence will be a DNA sequence if it only contains A, G, C and T.

Input
First line of the input contains an integer T (T<100), number of test cases. Each of the next T lines will represent one test case. Each test case consists of a single string S (length of S is less than 100) of uppercase letters (A Z).

Output
For each test case, print the test case number starting from 1 and YES, if the sequence S is DNA, NO, otherwise.

Sample Input
4 AC WATLE GOTAC ACGTAGT

Output for Sample Input

Case Case Case Case 1: 2: 3: 4: YES NO NO YES

B Kit-Kat-Koe
We all know the popular game tic-tac-toe. In this game we play in a three by three grid and put X or O in the cells. If the first player can put three consecutive Xs in a row, column or diagonal then he wins. Same goes for the second player, only he needs to put Os. Given a configuration of tic-tac-toe board, you are playing with X. Find if you can win by giving a single move in the current board. It is guaranteed that the board is not yet won by anybody. It is also guaranteed that, the board is a valid game position.

Input
First line contains T (T < 2500), number of cases. Then three lines for each case. Each line will contain three characters. These characters can be: X (Your move), O (Opponents move) or . (Empty cell). These three lines denote a board position.

Output
For each test case, print the test case number starting from 1 and YES, if you can win by giving a single move, NO, otherwise.

Sample Input
3 XXO ... OOX X.O OOX ..X O.. .X. .OX

Output for Sample Input

Case 1: YES Case 2: NO Case 3: NO

Explanation of the Sample Input

In the first sample, you can definitely win by giving a move in the middle square. The resulting grid will be XXO .X. OOX In the second sample, you may win based on what move your opponent plays. But you cant win in a single move. In the third sample, you will definitely win. But you need to make two moves for that.

C Depth of Erlang
Far over the misty mountains cold there was the great land of Shell. There lived many wizards, elves, hobbits, dwarves, men and programmers. The programmers were a brave bunch of people. Even though they didn't know much of magic like the wizards or crafts like elves they were never afraid of computers, dragons (one of them even called himself SnapDragon) or filthy orcs. You have knocked on the great iron door of Shell with a gleaming hope to become a programmer. Behold! The great programmers have asked you to complete a task to see how courageous you are and what amazing power you are hiding beneath your fingers! In Shell to ride and run the computers, programmers used an operating system called Erlang. Erlang was a beautiful system and poets of Shell have written thousands of lines of poetry about its beauty. But alas! It didn't have any graphical interface. For example, when asked what files are there in the system, Erlang replies with something like this computer ( A ( B C ( D ) ) ) This means, inside the computer there is a folder named A, which contains two things - a file B and a folder C. Inside folder C there is a file D. Like this pretty picture

But it's hard to navigate. For example, to access D one has to write the following commands: cd A cd C touch D Every time you want to go inside a folder you have to write cd X, where X is the name of the folder. And give the file a touch to access it. Now your task is - given the reply from Erlang and told which file you have to access, find how many lines of commands you have to write.
4

Input
The input file will contain only two lines. The first line of the input contains a single character - the name of the file to access. After that a single line follows containing the reply from Erlang. All file names and folder names are capital letter from A-Z. No two folders or files will have the same name. The file you'll have to access will be always in the system. Each folder name will always accompany with a left bracket '(' and content of that folder will end with a ')'. Of course a folder can have many files and folders within it. They will be all separated by a single white space. There will be a space between every ( and file name too.

Output
Print a single integer - how many lines of command you have to write to access it.

Sample Input
I computer ( A ( B C ( D ) E F G ( I ) ) )

Output for Sample Input

3

Explanation of the Sample Input

The three commands that you will need to execute are: cd A cd G touch I

D A Colorful World
This is the hardest level of the game. There are N stages in the level. In each stage you will be given Qi balls. Colors of the balls are denoted by an integer between 1 and K. You can pick up one ball from each stage or skip it (No ball). If you pick up a ball you will gain or lose some points depending on the last ball you have picked. You know color of the available balls of each stage and points you'll get for a certain combination. Can you figure out the maximum point you can get? Note that you wont gain or lose any point for the first ball you picked. If you skip a stage, you can never go back to that. Means you need to play in order.

Input
First line of input will contain number of test cases T (T < 150). In each case first line will contain two integers N (2 <= N <= 100) and K (1 <= K <= 100). Then there will be N lines which describe each stage. Each line contains an integer Qi (0 <= Qi <= 100) which denotes number of balls available in ith stage and then Qi integers will denote the colors of the balls in that stage. Then there will be K lines, each containing K integers, jth integer of ith line will indicate the point you will gain or lose if you pick a ball of color j after color i. Negative means you will lose point. Point gain or lose in a step will be at most 1000.

Output
For each test case, print the test case number starting from 1 and a single integer denoting the maximum point you can get.

Sample Input
2 2 3 3 2 3 2 4 1 1 3 3 1 5 0 1 0 2 -4 1 -5 4 4 1 4 2 3 1 2 2 4 3 4 2 2 -5 -2 3 2 -5 -1 2 0 3 4 5 -4 -3 -5 0 -4 Explanation of the Sample Input

Output for Sample Input

Case 1: 2 Case 2: 4

In sample 1, if you pick a ball of color 3 in 1st stage and color 1 in second you will lose 4 points. But if you pick ball of color 2 in first stage and color 3 in second stage you will get 2 which is maximum in this case.

E Stick to Triangle
You are given a stick of length N. You want to break it in three pieces such that it can form a triangle. How many distinct triangles can you make? Two triangles are equal if all the side lengths are same when sorted in ascending order of length. So (1, 3, 2) is same to (3, 1, 2) because their side lengths are same if we sort them, which is (1, 2, 3). But (1, 3, 4) is not same with (1, 2, 3). Suppose the lengths of three pieces are X, Y, Z (X <= Y <= Z) respectively. Following constraints should be maintained: 1. X, Y, Z > 0. 2. X, Y, Z is an integer. 3. X + Y >= Z 4. X + Y + Z = N For example if N = 14, then there are 7 triangles: (1, 6, 7), (2, 5, 7), (2, 6, 6), (3, 4, 7), (3, 5, 6), (4, 4, 6), (4, 5, 5).

Input
First line will give you the number of test cases, T (T<=100). Then each line will have an integer N (0< N <= 300000).

Output
For each test case, print the test case number starting from 1 and an integer denoting the number of distinct triangles possible.

Sample Input
3 3 6 14

Output for Sample Input

Case 1: 1 Case 2: 2 Case 3: 7

F Gifting
In the country of Giftland, everything is considered as 2D. Little Gugua has N friends. She wants to send gifts to all of her friends. All of her gift items can be considered as 2D filled circles of various radii. Gugua went to PackNsend Courier Service to send all of her gifts. PackNsend company offers 2D flexible boxes (you can consider those as flexible envelops) of various sized square shapes. Each gift requires one box. The gifts must be put in those square shaped envelops and then the square has to be adjusted to fit the gift in it tightly. That is, turn a square to a rhombus so that the circle touches all the sides. Length of the sides of the adjusted rhombus should be (obviously!) equal to the initial square. The company also charges 1unit/area of the enclosed adjusted envelop. Gugua collected N envelops of various sizes from the company. As Gugua is very little, all of her gifts were also very little. So she found that any of her gifts can be placed in any of those envelops, and then those envelops can be adjusted to fit the gifts. Gugua has to pay for the total area of all the adjusted rhombuses. Your job is to help Gugua to find the minimum area that is required to pack all her gifts using the square envelops and then adjusting them to rhombuses.

Input
First line specifies the test case number T (T <= 100). Then T test cases follow, each case starts with an integer, N (1 <= N <= 100), denoting the number of gifts/envelops. Then two lines follow. The first line contains N integers, Gi (1 <= i <= N), each denoting the radius of ith gift. Next line contains N integers, Sj, each denoting the length of side of jth square shaped envelops. No value will be greater than 1000. You can safely assume that, Si >= 2*Gj (for all 1 <= i,j <= N).

Output
For each line, print the case number, starting from 1, and then print the minimum total area of the adjusted envelops as described above.

Sample Input
2 4 1 1 1 1 2 2 2 2
4 1 2 3 4 8 9 10 11

Output for Sample Input

Case 1: 16 Case 2: 180

G Xorer Tree
Xorer are ancient race. They were very advance in their time. Their kingdom consisted of N cities numbered from 1 to N. Each city was connected with each other by a unique path of one or more roads. There was no cycle among the cities, means you cannot go from one city to another in more than one way without going to a city twice. We can say their road system can be modeled as a Tree of graph theory where each city is a node and each road is an edge connecting two cities. So there are N-1 roads. They had to give some tax for crossing each road. But for their strange economical system, whenever they cross 2 or more roads, their total tax needed was the Bitwise XOR ('^' operator in C/C++) of taxes of all the roads. Now we got a map of their road system. We want to know that, for some pair of cities U and V, how much tax one had to pay for going to city U to V in the cheapest path (Cheapest in terms of taxes).

Input
First line of the input is the test case number T (T <= 5). Then T test cases follow. Each case starts with two integers N (1 <= N <= 20000) and Q (1 <= Q <= 20000). N is the number of city of the road system. Q is the number of pair of cities for which you need to calculate the tax. In next N-1 lines, there will be 3 integer numbers U, V and W (1 <= U, V <= N and 0 <= W <= 1000000). This means there was a road from city U to city V and if anybody wants to go to only from U to V or V to U, he/she has to give W tax. Or if they are going to any other cities and they cross this road, the cost needed will be XORed with W. Then Q lines follow; in each line there will be 2 integer numbers U and V (1 <= U, V <= N).

Output
For each test case first print Case C: where C is the test case number. Then Q lines follow; each line consists of a single number, minimum tax needed for going from city U to city V in cheapest path.

Sample Input
2 3 1 2 1 3 1 6 6 1 2 3 2 3 3 2 1 6 1 2 4 1 2

Output for Sample Input

Case 1: 3 2 0 Case 2: 11 13 14 6 1 9
9

8 1 4

2 2 3 4 5 3 1 2

3 2 5 7 6 6 6 4 2 6

Explanation of the Sample Input

In the second sample, the road system is given below: Here in first query you have to determine the tax from city 3 to city 6. The path from city 3 to city 6 contains first city 3 to city 2 and the cost is 2. Then city 2 to city 1 where cost is 1 and total cost becomes 2 xor 1 = 3. Then city 1 to city 6 where the cost is 8 and total cost becomes 3 xor 8 = 11. From city 3 to city 6, total tax needed is 2 xor 1 xor 8 = 11. From city 4 to city 6, total tax needed is 4 xor 1 xor 8 = 13. From city 5 to city 6, total tax needed is 7 xor 1 xor 8 = 14. From city 3 to city 4, total tax needed is 2 xor 4 = 6. From city 1 to city 2, total tax needed is 1. From city 2 to city 6, total tax needed is 1 xor 8 = 9.

Figure: Road System for Second Sample

Properties of XOR (denoted by ^)

1^1=0^0=0 1^0=0^1=1 a^b=b^a (a ^ b) ^ c = a ^ (b ^ c) = a ^ b ^ c a^0=a a^a=0 if a ^ b = c then b ^ c = a and c ^ a = b When we bitwise XOR two numbers, then all its bits get XORed. For example, if we XOR 6 and 3, we will get 5. 6 = 110 3 = 011 ------5 = 101

10

Glossary
A Discovering DNA Sequence Uppercase Respectively B Kit-Kat-Koe Grid Cell Consecutive Diagonal Opponent Configuration Giving a single move Valid C Depth of Erlang Navigate Constraints F - Gifting 2D Filled circles Adjust Side Square Rhombus Radii Plural of Radius ( Command Access Enclosed Placed Assume Accompany D A Colorful World Denoted Pick up Skip Gain Lose Certain combination Figure out In order Cheapest G Xorer Tree Unique Cycle E Stick to Triangle Stick Triangle Side Distinct Sorted in ascending order