Programming Contest Questions.
Me, Sundar, Sanjith & Ananth organised The Programming Contest during SPANDAN 2005 in the college last week.We had a great time framing the questions(and those stories around them) . Stayed awake the whole night to (re)evaluate the solutions. Basically it was a much needed exercise for our grey cells.
This was the Question Paper:
Basic Rules:
Development Environment: C, C++, Java(No JDK 1.5)
Input: input will be in a file which will be passed as the first command line parameter.
Output: Output on stdout.
Prob 1. Double Trouble. 100 points
COWT is a Conference Of Wierd Twins. The twins are wearing T-shirts each with a single digit number (1-9 inclusive) printed on. The numbering is such that the sum of the jersey numbers on a pair of twins is 10. They are seated along a long straight table. The task at hand is to see if the seating arrangement is symmetric between each pair of twins. (For symmetry considerations the twins are identical).
Twins Tshirt Numbers:
1 & 9
2 & 8
3 & 7
4 & 6
Input:
1 2 3 4 6 7 8 9
Output:
Y
Input:
2 3 7 1 6 9 5
Output:
N
Prob 2. Saving Davidapuram . 500 points
Goliathahalli and Davidapuram are two villages that have been involved in regular wars. Golliathahalli,funded by ISI possesses state of the art weaponry and have uprooted the Davidapuram army. To fight back Davidapuram needs weapons and the only resource in Davidapuram are the Fictitia indica trees. Davida Gowda, their chief strategist moots the idea of making catapults from the trees.
The trees are interesting free trees (unrooted trees). A catapult can be made from exactly three branches connected together at a common point. A branch can not be used in two catapults.
The catapults:
As indicated by the ellipses.
Please note that the node labels are merely a means to specify the tree and should be assumed to be mere points of branching.
Input:
0--1;
0--2;
0--3;
3--4;
2--5;
3--6;
6--7;
2--8;
1--9;
9--10;
4--11;
4--12;
4--13;
0--14;
Output:
3
(Thats the maximum number of catapults possible.)
Prob 3. Kindly Connection 150 points.
A rectangular circuit board has a fixed number of points on its periphery. Any two of these points can be connected together using a wire to form an electrical circuit. Being a 2 dimensional board, no two wires should overlap or else there will be a short circuit.
Each line in the Input file contains a connected point-pair.
Each line in the Output file should contain two point-pairs (comma separated) which overlap.
Input File:
1 10
3 9
4 6
5 3
7 3
6 10
Output File:
6 10, 7 3
6 10, 3 9
3 5, 4 6
Assume that the number of points is the highest individual number appearing in the input. No number between 1 and the highest number remains unassigned even though it may NOT appear in the input (e.g. ‘8’ in this case). The order of the numbers in the point pair should remain the same as it is in the input.
Prob 4. Krishna’s Dilemma
In the Mahabharata war, there was a twist in the tale. Both armies were overrun by the Asuras. They captured both the Pandava army and kaurava army. There were N prisoners out of which P belonged to the pandava army and remaining to the kaurava army.
Asuras made all prisoners to stand in a circle and decided to execute N – P people. All pandavas stand together as do the kauravas. Asuras then asked Krishna to choose a number S, so they can select each “S”th (starting from the first pandava prisoner) prisoner to execute. Help Krishna choose this S so that he can save all the pandavas.
Prob 5. Knock Knock…350 points
At Hogwart's Castle, there is a sentinel at the door of every group. Dumbledoor has decided to place a sentinel computer at every door. The sentinel is given an expression. And unless the pass-string mentioned by the student matches the expression that has been given to it, the sentinel refuses to open the door. You are the programmer of the sentinel program!!!
You will be given the expression with *,+ and ? as the meta characters (the only metacharacters).
Alphabet is alpha numeric.
The input is of the format : [Regex] [string to be matched]. The output is 0 in case of failure and 1 in case of match.
Input:
grif+indo+r griffindor
Output:
1
Input:
Grif*indo?r ravenclaw
Output:
0
Prob 6. Silly Notes 150 points
I use "Silly Notes" as my mail client. Silly Notes changes my password everyday. Trinity and Persephone are the two smart ladies who sit on either side of my cubicle. Each of them gave a number(t,p) which lead to the password. I realised that the password was just the absolute difference of 2 power t and 2 power p. All I needed to do was input these numbers to the "Silly Notes", until that fateful day when Trinity gave me t > 32 and silly notes crashed.Can you help me write a code to generate my password?Ah,did I tell you,"Silly Notes" understands only hex?
Input File:
8 5
Output File:
E0
Input File:
17 3
Output File:
1FFF8
Prob 7. Narcissism redefined 175 points
Dorkut online community site decided to find out how people are related. They listed friends of each member and tried to find out if any person is transitively his/her/its own friend.
Input:
a: b c d
b: c f
c: d e
f: a
Output:
y
Prob 8. Yukon Ho ! 400 points
Yukon is a conurbation. Yukon consists of several agglomerations. John Calvin is the town planner who is tasked to design an outer ring road for Yukon satisfying the following requirements:
1. The ring road should be in the shape of a polygon with one agglomeration at each vertex.
2. Each agglomeration will either be on the vertices of the polygon or inside it.
3. The traffic incurs a cost when made to pass through an agglomeration. So, he needs to minimize the number of vertices of the polygon even while satisfying the above properties.
Input:
1 1
1 -1
-1 1
-1 -1
0 0
Output:
1 1
1 -1
-1 1
-1 -1
Prob 9. Cube with X's. 250 points
(problem obtained from third party)
Look at the image below. It is a drawing of a box with solid lines for the visible edges of the box, and dashed lines for the edges that would be hidden from view. Your task is to implement a program to draw a box like that shown below, given W, H, and D - the width, height and depth of the box (as shown in the image). More specifically, you should return a vector representing a bitmap, where character j of element i of the vector represents the pixel in row i, column j (character 0 of element 0 is the upper left corner of the image). The front of the box should have its left edge along column 0, and its bottom edge along the last element of the return. Naturally, it should be H pixels tall, and W pixels wide. The back of the box should have its lower left corner D pixels up and to the right from the lower left corner of the front of the box, its top edge in element 0 of the return, and its right hand edge in the right most column. To achieve the dashed lines, you should start with a black pixel where the lower left corner of the back of the box is, and then alternate between black and white pixels until you get to the end of the line. In the return, you should use the space character for white, and the 'X' character for black. See the examples for further clarification.
Input:
20 10 5
Output:
Prob 10. Sum-3 Partition. 175 points
Let S = {1,2,3, …. 3n}. We define a sum-3 partition of S to be a collection of n disjoint 3-subsets of S, Ai = {ai, bi, ci}; I = 1, …, n , such that the union A1UA2U….UAn is S, & within each triple Ai, some element is the sum of the other two. All sets A1, A2 … An are mutually exclusive.
Input:
12
Output:
1 5 6
2 9 11
3 7 10
4 8 12
Prob 11.Love Bug in The Middle 300 points
Romeo and Juliet spend most of the time in office chatting. Both of them have been smitten by the "love bug". For every message x sent, the love bug stealthily does the following -
1. It generates two copies of the message x - y and z by inserting random characters in x.
2. Also the set of random characters used to generate y and z the set of random characters used to generate z are mutually exclusive.
3. Sends across both y and z
Can you write a code that deciphers the message sent?
Input:
TTTTHKKJKJKJKJEKJJJJKJLLLjhjhjhO
asasasHswwqwqEqwqwqLwqwLO
Output:
HELLO
Development Environment: C, C++, Java(No JDK 1.5)
Input: input will be in a file which will be passed as the first command line parameter.
Output: Output on stdout.
Prob 1. Double Trouble. 100 points
COWT is a Conference Of Wierd Twins. The twins are wearing T-shirts each with a single digit number (1-9 inclusive) printed on. The numbering is such that the sum of the jersey numbers on a pair of twins is 10. They are seated along a long straight table. The task at hand is to see if the seating arrangement is symmetric between each pair of twins. (For symmetry considerations the twins are identical).
Twins Tshirt Numbers:
1 & 9
2 & 8
3 & 7
4 & 6
Input:
1 2 3 4 6 7 8 9
Output:
Y
Input:
2 3 7 1 6 9 5
Output:
N
Prob 2. Saving Davidapuram . 500 points
Goliathahalli and Davidapuram are two villages that have been involved in regular wars. Golliathahalli,funded by ISI possesses state of the art weaponry and have uprooted the Davidapuram army. To fight back Davidapuram needs weapons and the only resource in Davidapuram are the Fictitia indica trees. Davida Gowda, their chief strategist moots the idea of making catapults from the trees.
The trees are interesting free trees (unrooted trees). A catapult can be made from exactly three branches connected together at a common point. A branch can not be used in two catapults.
The catapults:
As indicated by the ellipses.
Please note that the node labels are merely a means to specify the tree and should be assumed to be mere points of branching.
Input:
0--1;
0--2;
0--3;
3--4;
2--5;
3--6;
6--7;
2--8;
1--9;
9--10;
4--11;
4--12;
4--13;
0--14;
Output:
3
(Thats the maximum number of catapults possible.)
Prob 3. Kindly Connection 150 points.
A rectangular circuit board has a fixed number of points on its periphery. Any two of these points can be connected together using a wire to form an electrical circuit. Being a 2 dimensional board, no two wires should overlap or else there will be a short circuit.
Each line in the Input file contains a connected point-pair.
Each line in the Output file should contain two point-pairs (comma separated) which overlap.
Input File:
1 10
3 9
4 6
5 3
7 3
6 10
Output File:
6 10, 7 3
6 10, 3 9
3 5, 4 6
Assume that the number of points is the highest individual number appearing in the input. No number between 1 and the highest number remains unassigned even though it may NOT appear in the input (e.g. ‘8’ in this case). The order of the numbers in the point pair should remain the same as it is in the input.
Prob 4. Krishna’s Dilemma
In the Mahabharata war, there was a twist in the tale. Both armies were overrun by the Asuras. They captured both the Pandava army and kaurava army. There were N prisoners out of which P belonged to the pandava army and remaining to the kaurava army.
Asuras made all prisoners to stand in a circle and decided to execute N – P people. All pandavas stand together as do the kauravas. Asuras then asked Krishna to choose a number S, so they can select each “S”th (starting from the first pandava prisoner) prisoner to execute. Help Krishna choose this S so that he can save all the pandavas.
Prob 5. Knock Knock…350 points
At Hogwart's Castle, there is a sentinel at the door of every group. Dumbledoor has decided to place a sentinel computer at every door. The sentinel is given an expression. And unless the pass-string mentioned by the student matches the expression that has been given to it, the sentinel refuses to open the door. You are the programmer of the sentinel program!!!
You will be given the expression with *,+ and ? as the meta characters (the only metacharacters).
Alphabet is alpha numeric.
The input is of the format : [Regex] [string to be matched]. The output is 0 in case of failure and 1 in case of match.
Input:
grif+indo+r griffindor
Output:
1
Input:
Grif*indo?r ravenclaw
Output:
0
Prob 6. Silly Notes 150 points
I use "Silly Notes" as my mail client. Silly Notes changes my password everyday. Trinity and Persephone are the two smart ladies who sit on either side of my cubicle. Each of them gave a number(t,p) which lead to the password. I realised that the password was just the absolute difference of 2 power t and 2 power p. All I needed to do was input these numbers to the "Silly Notes", until that fateful day when Trinity gave me t > 32 and silly notes crashed.Can you help me write a code to generate my password?Ah,did I tell you,"Silly Notes" understands only hex?
Input File:
8 5
Output File:
E0
Input File:
17 3
Output File:
1FFF8
Prob 7. Narcissism redefined 175 points
Dorkut online community site decided to find out how people are related. They listed friends of each member and tried to find out if any person is transitively his/her/its own friend.
Input:
a: b c d
b: c f
c: d e
f: a
Output:
y
Prob 8. Yukon Ho ! 400 points
Yukon is a conurbation. Yukon consists of several agglomerations. John Calvin is the town planner who is tasked to design an outer ring road for Yukon satisfying the following requirements:
1. The ring road should be in the shape of a polygon with one agglomeration at each vertex.
2. Each agglomeration will either be on the vertices of the polygon or inside it.
3. The traffic incurs a cost when made to pass through an agglomeration. So, he needs to minimize the number of vertices of the polygon even while satisfying the above properties.
Input:
1 1
1 -1
-1 1
-1 -1
0 0
Output:
1 1
1 -1
-1 1
-1 -1
Prob 9. Cube with X's. 250 points
(problem obtained from third party)
Look at the image below. It is a drawing of a box with solid lines for the visible edges of the box, and dashed lines for the edges that would be hidden from view. Your task is to implement a program to draw a box like that shown below, given W, H, and D - the width, height and depth of the box (as shown in the image). More specifically, you should return a vector representing a bitmap, where character j of element i of the vector represents the pixel in row i, column j (character 0 of element 0 is the upper left corner of the image). The front of the box should have its left edge along column 0, and its bottom edge along the last element of the return. Naturally, it should be H pixels tall, and W pixels wide. The back of the box should have its lower left corner D pixels up and to the right from the lower left corner of the front of the box, its top edge in element 0 of the return, and its right hand edge in the right most column. To achieve the dashed lines, you should start with a black pixel where the lower left corner of the back of the box is, and then alternate between black and white pixels until you get to the end of the line. In the return, you should use the space character for white, and the 'X' character for black. See the examples for further clarification.
Input:
20 10 5
Output:
Prob 10. Sum-3 Partition. 175 points
Let S = {1,2,3, …. 3n}. We define a sum-3 partition of S to be a collection of n disjoint 3-subsets of S, Ai = {ai, bi, ci}; I = 1, …, n , such that the union A1UA2U….UAn is S, & within each triple Ai, some element is the sum of the other two. All sets A1, A2 … An are mutually exclusive.
Input:
12
Output:
1 5 6
2 9 11
3 7 10
4 8 12
Prob 11.Love Bug in The Middle 300 points
Romeo and Juliet spend most of the time in office chatting. Both of them have been smitten by the "love bug". For every message x sent, the love bug stealthily does the following -
1. It generates two copies of the message x - y and z by inserting random characters in x.
2. Also the set of random characters used to generate y and z the set of random characters used to generate z are mutually exclusive.
3. Sends across both y and z
Can you write a code that deciphers the message sent?
Input:
TTTTHKKJKJKJKJEKJJJJKJLLLjhjhjhO
asasasHswwqwqEqwqwqLwqwLO
Output:
HELLO
posted by Praveer @ Tuesday, April 12, 2005
3 Comments:
Praveer et al, thanks again :)
Hey Sanket,
As I figured out the next morning, we could have had a much better participation.
Lot of guys came and told me, we could not participate because we did not have Linux. Sadly, they did not know abt ssh server.
Although, we enjoyed it thoroughly !
Hey Thanks for the memento guys :-)
Post a Comment
<< Home