5
Once upon a time, there lived a chimpanzee called Luycha Bandor (aka Playboy Chimp).
Luycha was unhappily married to Bunty Mona, a short but cute little lady chimp. Luycha
was tall and handsome – he was feeling uncomfortable taking Bunty to public places
along with him. People would stare at them all the while. At one point, Luycha could not
stand it anymore and he decided to do some justice to his name. He started looking for a
new hope in the Lady Chimps’ College. Every day Luycha would climb up a bamboo tree
and wait for the morning drill to start. From there he could see each and every lady chimp
doing their routine drill. Incidentally, some of Luycha’s friends learned about this college
and got interested in looking for someone for themselves.
Now, Luycha and all his friends have a very specific criterion. That is, each chimp was
looking for the tallest lady chimp that would be shorter than he; he would also like to
consider someone a little taller than he. But someone of his same height will never be on
any of their list. Every morning Luycha and his friends looks at the line of lady chimps
and finds the best two according to their set criterion. Their job has been made easy by
the fact that the lady chimps in the line are ordered by their height, the shortest one is in
the front and the tallest one is at the back. Your task is to help Luycha and his friends, on
one particular day, to find two lady chimps: for each chimp the tallest lady chimp shorter
than he and the shortest one taller than he.
INPUT SPECIFICATION
The first line of input gives you N (1≤N≤50000) integers. Each integer is in the range 1 to
231-1, giving the heights of the N lady chimps. There would be a single space after every
number. You can assume that the chimps are ordered in non-decreasing1 order of their
heights.
In the second and last line you would have Q (1≤Q≤25000) integers. Each integer is in
the range 1 to 231-1, giving the number of queries (these Q numbers give the heights of
Luycha and his friends). As before, you would find a single space after every query
number. The query numbers are not supposed to come in any particular order.
IT IS CRUCIAL to remember that the input will be read from a file named in.txt. You
have to write your program so that it tries to open a file named in.txt from the folder
where the program itself (ie – your py file) is located. Moreover, when you create an
in.txt file with some numbers to test your code, you have to put JUST ONE SPACE after
each number on a line. Of course, as stated above, you would have N such numbers on
the first line, and Q such numbers on the second line. Between the 2 lines there should be
NO OTHER LINES. There should be no other lines after the 2 lines.
I will provide test sets in the portal for you to test your program. There will be
instructions associated with these sets so please read them carefully.
If you do not follow these instructions for file formats then your program will not execute
for me and you will end up not getting any marks for it. So please pay attention to details
in this assignment.
OUTPUT SPECIFICATION
For each query height, print two numbers in one line. The first one would be the height of
the tallest lady chimp that is shorter than a male chimp (or the query height), and the next
number would be the height of the shortest lady chimp that is taller than he (or the query
height). These two numbers are to be separated by a single space. Whenever it is
impossible to find any of these two heights, replace that height with an uppercase ‘X’.
The output should be printed in a file named out.txt. Again this should be in the same
folder as your program (your py file).
SAMPLE INPUT (from file) and OUTPUT (to file)
Case 1(same as example before):
in.txt looks like this:
1 4 5 7
4 6 8 10
out.txt looks like this:
1 5
5 7
7 X
7 X
1 Non-decreasing: A non-decreasing sequence of numbers is a sequence that is not decreasing, but not
necessarily increasing either hence it is different from an increasing sequence.
For example the following is a non-decreasing sequence: 1 1 5 6 7 7 8 9. Notice, how every number is
either same or more than the previous number, but never less.
Case 2:
in.txt looks like this:
420141419 729181235 961956525 1003587949 1178594928 1519311812 1911606276
1403517511 1733936571 1771883419
out.txt looks like this:
1178594928 1519311812
1519311812 1911606276
1519311812 1911606276
Case 3:
in.txt looks like this:
1 1 4 5 7 7
1 4 6 8
out.txt looks like this:
X 4
1 5
5 7
7 X
Note: these are all valid inputs with corresponding outputs.
How to time your program?
We already talked about python modules. One such module is time. It has one very useful
function that you can use to time your program and the function is called time.clock().
This function returns a floating value for the time in seconds. Now what you can do is
call this function right at the beginning of your code and store the output. You can do this
again at the end of your code and calculate the difference to see how long it took for your
program to run. Remember to import the time module at the very top of your program (py
file). Lets see an example,
import time
def Factorial(n):
"""
This is a function that calculates the factorial
of a number (n!). For example, if n = 5 the
program outputs 120.
"""
##variable to store the partial multiplication
##results on the way to calculating the factorial
factorial = 1
##looping through all numbers and multiplying them
for i in range(n):
factorial = factorial*(i+1)
##returning the result
return factorial
##Remember this is the starting point
##getting the current seconds on my computer clock
startTime = time.clock()
##printing for debug purposes
print "Start Time: " + str(startTime)
##setting the number for which i want the factorial.
number = 20
##calling the function which computes the factorial
factorial = Factorial(number)
print "\n\n\nFactorial: " + str(factorial) + "\n\n\n"
##getting the current seconds on my computer clock
endTime = time.clock()
##printing for debug purposes
print "End Time: " + str(endTime)
##calculating the time it took for my program to run
runTime = endTime - startTime
##printing the run time of this program
print "RUN TIME: " + str(runTime)
When you run the above code you see the following output:
Start Time: 1410.2520094
Factorial: 2432902008176640000
End Time: 1410.42397036
RUN TIME: 0.171960961519
This means the program took approximately 0.17 second to run.
I will be timing your program on one of the machines in the lab, therefore you should
time it on one of these machines too. I am not interested in how fast a computer you have
at home! When you time your program, it is good to time it on different machines in the
lab at different times of the day. The same program may show slight variations in timing
even on the same computer. In this case just make sure the average of these times is
within the range I specified. You DONT have to write a program to calculate this
average, just do it on a piece of paper by hand. You SHOULD INCLUDE the time code
in your program, regardless of whether or not you have made it efficient.
ACKNOWLEDGEMENTS
The original version of this assignment was set as a programming challenge on ACM
(http://acm.uva.es/p/v106/10611.html). This is a slightly modified version of the original
problem, because in the original problem you have to write the fastest code to get any
marks.
