Iste Week Overnight Coding

ISTE Week 1 Overnite Programming Contest

ISTE WEEK OVERNIGHT PROGRAMMING CONTEST RULES: 1) All questions carry equal weight. 2) Teams found indulging in unethical acts such as sharing of solutions or ideas will be disqualified. 3) Approaching the judges table is not allowed, you are supposed to call an organizer to you. 4) Decisions of the judges are final and any team found arguing will be disqualified immediately. 5) Do not close the PC ^2 window. 6) G++/GCC is the C/C++ compiler to be used and the file should be correctly compiled in that. 7) If using Java, use the file name strictly as per the question. For question no 1, use q1.java(note small caps), for 2 q2.java and so on...... 8) You are not allowed to leave the lab in between the contest unless they wish to quit. 9) Girls are not supposed to leave the lab without informing the organizers, as they will have to be provided appropriate permissions. 10)Usage of books is allowed but no (soft copies /internet) is allowed. For the code: – Do not use conio.h – The soln. should be exact as the question. Minor discrepancies will lead to failure. – Please use #include and not #include for C++ headers. C headers go as usual. – Do not use fflush, exit Scoring: – –

–

The team with maximum number of correct submissions win In case of ties, the individual submission time of all the submissions will be added and then the team with the lesser time wins. Which means it does not mean that you submit the last question first, you win, but in case of a tie, the team having a lead early on may carry an advantage. The scores will not be displayed instantaneously. It requires calculation time. The results will be displayed on the ISTE notice board on Wednesday, 20th Feb. at 12:00PM.

You are allowed to carry books in the finals.

ISTE Week 2 Overnite Programming Contest

A long way from here in a parallel universe we have no knowledge of, an epic battle is being fought that will change everything forever. It is a battle between the light warriors who are just, kind and righteous and the Dark Dominators who spread evil wherever they go. This battle shall also consequently affect the well being and the prosperity of the human race. In order to stop the Dark Dominators from spreading into our universe, the light warriors need your help. The future of this planet now lies in your hands.

Problem 1 The Light Warrior techies have just finished developing ‘The Obliterator’, a massive laser that destroys anything that comes in its path. However the amount of energy it uses is too large (even for the light warriors who are a gazillion light years ahead of us!!!). Hence the narrower the beam, the lesser the energy used and more focussed the destruction. Their scouts have just found several planet systems of the Dark Dominators. The Light Warriors firstly plan to make the width of the beam so narrow that the only way to destroy the system is to align it in such a way that the beam lies in the plane defined by the planets in the system. Secondly, they make the width so small in length that nothing bigger than the particular system can be covered by it. Finally, they take ‘The Obliterator’ to a strategic position close to the system, orient it in a way such that the beam lies in the system's plane and then fire it towards the constellation in a straight line until the whole system is obliterated. You are required to calculate the minimum width of the beam that will destroy the system given the location of the planets within that system. Input Format

Sample Input



1



5

<x1 y1>

20

<x2 y2>

02

.

00

<xn yn>

11

ISTE Week 3 Overnite Programming Contest

.

22 Sample Output

.

2.000

<x1 y1> <x2 y2> . <xm ym> Output Format .

ISTE Week 4 Overnite Programming Contest

Problem 2

N UCL EAR CAN DLE S

The Light Warrior battle ships used to fight on planets are very energy efficient. During daytime, they run on solar energy but at night they use fusion candles, candles which burn and release large amounts of energy to drive the ship. Thus each candle acts as a mini battery. Every ship takes a limited number of candles with it before disembarking from the mothership and going into war. On the first night of the journey, they will light one candle. At the end of the night, they will extinguish the candle. On each subsequent night, they need to light one more candle than they did on the previous night, so that on the nth night (indexed from 1) they will light n candles (and extinguish them all when they find the sun in the morning). Each night that they light a candle, its height decreases by 1 cm; once its height reaches 0 cm, they cannot use it anymore. You need to tell them the maximum number of nights a ship will last without returning to the mothership for refuelling. You are given a int[] candles, the ith element of which is the height of the ith candle that you own. For example, if you have three candles of height 2, you can light one the first night, the other two on the second night, and then all three candles on the third night. Input Format: . . . .

ISTE Week 5 Overnite Programming Contest

. .

Output Format: . . Sample Input: 1 3 2 2 2

Sample Output: 3

ISTE Week 6 Overnite Programming Contest

Problem 3 The Light Warriors’ hacker (which is you by the way) has just hacked into the Dark Dominators’ computer base, and you want to delete one of the operational files. But wait, why not make the Dark Dominators delete it themselves! As you keep watching them, you learn that they have a delete command typed in on their terminal which contains a 'pattern'. You want to rename the operational file to match this pattern so that it gets deleted once they issue the command. You must accomplish this by renaming the given file to a similar name. Other than lowercase letters, a pattern might contain '?' which represents exactly one character (so "a?b" matches "aab", "abb", "acb" etc). A move is defined as adding a character, deleting a character, or modifying a character from the 'filename'. Given two Strings, 'filename' and 'pattern', display the minimal number of moves required to make the file match the pattern. Input Format:

Sample Input :



1

<String1_filename for test case 1>

abcd

<String2_pattern for test case 1>

b??

<String1_filename for test case 2> <String2_pattern for test case 2> . removed)

Sample Output: 1 (First character needs to be

.

<String1_filename for test case n> <String2_pattern for test case n> Output Format:

.

ISTE Week 7 Overnite Programming Contest

Problem 4 Oh Oh! Looks like the Dark Dominators have just found out the location of the Abode of Light, the home system o the Light Warriors. It’s time to pull up the defences and prepare for battle before the darkness reaches the base. The Light Warriors use a highly advanced shield system that does not allow anything to penetrate through it. However it needs to be set up in a rather primitive manner. It consists of two mobile generators that need to be placed very strategically in the system, for the shield is actually an impenetrable sphere created using the distance between the two mobile generators as its diameter. You will be provided with a map of the home system (not more than 10X10) where ‘a’ represents the location of a planet and ‘-’ shows empty space in between the planets. You need to select two planets in the system where the generators will be placed so that the shield generated encloses all other planets in the system. Mark the selected planets with ‘@’ and return the map with the changes. Take the map as a 2D character matrix. Input Format Sample Output:

Sample Input:

5

---

-@ ( n represents n X n map )

----a

-

-----

-

-----

a

---<1st line of the map>

---<2nd line of the map>

----

ISTE Week 8 Overnite Programming Contest .

a----

@. Output Format

<1st line of the modified map> .

---a-

---

ISTE Week 9 Overnite Programming Contest

Problem 5: Victory seemed eminent, but the power of the ring could not be undone.

I am certainly not talking of the ring in the Lord of The Rings. The Dark Dominators were great I should say in their own sense. They had set up a ring of oblivion, the deeper you go, the more you forget. Even the wireless networks seemed to lose everything (As for the wired circuits, they went out of fashion like a million years ago!). However the forces of Darkness seem to be operating in all their fervour, seemingly immune to this ring. Yet luck has its own strange way. A faithful informant shared a very important piece of information with the Light Warriors. The enemy machines seem to be catching words through their iCode value, a value based on the punctuations present in the message sent. So that means, if we can remove all punctuations, the message will go through. The Light forces have a set of codes which must be transmitted if they are to survive in this chaos. The spaces pass luckily, but aaaargghhhh, the full-stops, the colons, the commas don’t go through. There may be many more that may not cross through. As far as they know for sure, only numbers, spaces and letters will pass. We can’t risk any more, lest the enemy might intercept and decipher. So now you’ve gotta plug in a program to do that for the Light Warriors. Time is slipping through your fingers, and the enemy forces are growing... (The maximum length of the input code is 500 characters) Input Format:

< A string to represent the code for testcase 2> . < A string to represent the code for testcase n>

Output Format:

. Sample Input:

“This is important!”!!. Encoded hereby: @JTHFKE**0933 $5 FFGHB Sample Output:

ISTE Week 10 Overnite Programming Contest

This is important Encoded hereby JTHFKE0933 5 FFGHB

Problem 6 It is time. The titans are set to clash. The end has begun. Due to your help, the Light Warriors have successfully vanquished the forces of evil from most parts of the universe. The Dark Dominators have now been pinned down in the Valley of Darkness, their home system. It’s time to exterminate the exceedingly evil and ever evolving forces of darkness and enrich the universe with the essence of excellence, energising , enlightening and exalting all from the extremities of lowness to the highest echelons of existence( the Light Warriors have a thing for the letter ‘e’ ). Now all that the Light Warriors need to do is to take ‘The Obliterator’ there and blow everything to smithereens. However in response to ‘The Obliterator’ the Dark Dominators have finally built ‘The Drain’ which is a series of mines so small that they are virtually untraceable but so powerful that a single mine can devastate ‘The Obliterator’. Thus they need a sweeping operation before they can move their master weapon into position. It’s a well known fact that the Dominators are crazy after prime numbers. So much so that most of their childhood is spent trying to calculate the biggest primes instead of playing ‘Hop Scotch’ or ‘Let’s kill the Light Warriors!!!’. A faithful informant has just revealed that the number of mines hidden in a particular sector of space is the same as the number of circular primes below the particular sector number. The number 197 is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97. Hence sector 100 has 13 mines hidden within it. Given a sector number, find out the number of circular primes below that number to help the Light Warriors quickly sweep out all the mines and

ISTE Week 11 Overnite Programming Contest

approach the Valley of Darkness safely, so that they can obliterate all the remaining scum of the universe from the very shred of existence. Input Format:

. .

Output Format:



. . Sample Input:

1 100

Sample Output:

13

ISTE Week 12 Overnite Programming Contest

-------------May the Light shine throughout--------------