The Computer Society of MIT started conducting Juggernaut from this September as a monthly campus event. The event includes several rounds including Puzzles, problem solving, algorithms(for circuit brchs), programming(for circuit brchs), core tech qns(for mech stream), computer designing (for mech stream). The Chairman told me while asking for comments about the event “Some Third yr student suggested doing programming contests thro Computer Society to Ramgopal and he approached me regarding this and thats how we started this event”. He did not know then that “Some Third yr student” was me !! :D.
Ok Coming to the event, It was very nice having 3 rounds. I and Suryanarayanan were a team and we completed all the 3 rounds and became Winners of Juggernaut sep07 !! hehe…. Another thing i would always remember bout the event is about the teamname. Initially we had given a team-name “Anything for Namitha” cool ha… The co-ords said durin round 1 to change the team name or else they may disqualify us !! 
Thus, We were already famous before the whole event started…. so we changed our teamname to “code-freaks”…. hmm… In the finals we beat Siddharth’s team. They had sufficient amount of time penalty to become runner ups !!!
I give here the questions and our solutions of those qns we solved during the final programming round of the event:
Password Cracking :
Mario is a student of Final Year IT. Mario is a typical gethu MIT student who rarely attends class.Now he’s so much worried over the issue of Marks for attendance. His attendance marks would definitely be zero only.If he somehow manages to get marks in it he’ll clear the final year.
So he thinks of breaking into the COE office and changing the attendance marks in the computer there.The computer that holds the marks of students are placed in a secured room which no one can break into. The computer wont allow the third time wrong entering of the password and would raise an alarm and would get caught.The only way to get into is through the entrance which is protected by a security computer.Only after typing the password in the keyboard there one can enter the room.
The password cant be guessed or hacked through any means.The only way is to bring out the password from the hands of the COE officer,Mr.Paritchai Vendhan.The COE officer has a low memory.So he has a list of passwords in hand stored in a file .Once in fifteen days he selects one word from the list and sets as the password.Mario somehow managed to get that password file consisting of words N > 3 . But the only problem is that he has to get that correct password from it.So he devised one method.
Mario gifted Mr.Paritchai Vendhan a pen as a gift which was coated with a fluorescent marking material.When he took the pen in his hands ,his hands were stained with that invisible fluorescent marking material.What ever objects he touched were stained with that material which is invisible under normal light but can be viewed under a fluorescent light.Without knowing these he typed his password (with his stained hands )and entered the room . That night Mario came to that Computer room and he used a fluorescent light to look through the keys which were stained with that material,(ie) the keys that the COE officer used to type the password.As everyone knew our Mario is strong enough in action & adventures but very poor in logics and computers.
So with that password file in hand and the key strokes that he could decipher from the keyboard , now help Mario in finding the password and help him clear the final year,after all he’s your senior.It is noted that all passwords are in lowercase and numbers can also appear.
Input:
Input consists of T,the no of test cases ,where T<=10
Each test case consists of N , where 3<N<40 followed by N words each on a new line.
Each word doesnt exceed 15 characters.
K , no of keys that has a stain impression on it followed by K keys on a single line.
Output :
It must print one word for each test case each on a separate line.
If no words are matchin print NOP
if more than one words match print each word separated by a space on a single line in ascending order
Sample Input:
2
5
monkey
honey
donkey
sad
honest
6
ykonme
4
are
busy
mine
worse
4
mtbi
Sample Output:
monkey
NOP
Sum Of Perfect Cubes :
A perfect cube is an integer whose cube root is an integer ie a whole number . Eg : 1 , 8 , 27 , 64 , 125 are perfect cubes .
You are given an int low and an int high . You have to find the sum of all perfect cubes that lie between low and high also including low and high .
NOTE : Here we have sizeof(int) as 4 since we are using 32 bit rep.
CONSTRAINTS :
-
The first line in the input file contains no. of test cases .
-
Each test case is separated by an empty line.
-
Each test case satisfies the following conditions :
-
Value of low(first line) ranges from 2 to 2^31-1 both inclusive.
-
Value of high(second line) ranges from low to 2^31-1 both inclusive.
-
The output should contain one line for every test case.
-
Each line in the output must be the sum of all the perfect cubes cubes in the given range.
Sample Input :
3
1
1
7
63
7
65
Sample Output:
1
35
99
Graph Printing :
A scientist needs to analyze his research based on the graphical representation of his experiment’s output. All the results need to be plotted in a two dimensional graph of which X-axis and Y-axis represents some parameter. The graph will contain only three symbols as follows:
“/ “– Represents a unit increase in the previous value of Y-axis
“_“- Represents no change in the previous value of the Y-axis.
“\“- Represents a unit decrease in the previous value of the Y-axis.
(Quotes for clarity only)
X-value increases uniformly at the rate of one unit.
You are provided with the sequence of these symbols based on the result. Your task is to print the representation of the graph with X and Y value starting from 0. X-value increases by one for each Y-value. Sample input and output is given below.
Constraints :
-
First line of input contains no. of test cases.
-
Each test case has a single line containing either of the 3 characters ‘_‘,’/’and ’\’.
-
Each test case has between 2 characters and 20 characters both inclusive.
-
Ouput should contain the representation for each test case.
Sample Input:
4
////___\\\\
\\\/\/\
/_\_/_\
___///
Sample Output:
___
/ \
/ \
/ \
/ \
\
\
\/\/\
_ _
/ \_/ \
/
/
___/
SOLUTION TIME!!!
PASSWORD CRACKING
The problem can be reduced to : From a given list of words W, find the words which contain all but only the letters in the word L. Many ways to solve this problem. One way is to use 2 flag arrays for each of the words: 1 for letters of size 26 and 1 for numbers of size 10. The index in the flag arrays corresponding to a word is 1 if that letter or number appears in the word.
Have a flag array pair for each of the words in W and one flag array pair for the word L. Output all words in W whose flag array pair is same as flag pairs corresponding to L. if none of them exist, output NOP.
SUM OF PERFECT CUBES
A Brute Force Approach could solve this problem.
long long i;
for(i = 1; i*i*i <= high; i++)
{
if(i*i*i >= low) sum += i*i*i;
}
print sum
But If u Belive u are decendents of ramanujam try to solve d prob in o(1) mathmatically !!
GRAPH PRINTING
With atmost 20 characters, the graph cannot go away from horizontal range 0-20 and vertical range of 20 to -20. Wot we can do it declare an array of size 50*25 say… arr[50][25]. Start plotting ur graph from the point arr[25][0]…
After that for each character in the given string S…. S[i] ull plot it in the graph at the position arr[j][i]… j is determined by the graph positon for the character S[i-1] and the character S[i-1] itself. A little thot on this is the only thing left which is left as exercise for the reader !!
|
|
