473,381 Members | 1,446 Online

# somebody please solve this problem for me

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
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
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
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.
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.
Jul 25 '08 #1
6 2244
Laharl
849 Expert 512MB
We're not going to do your homework for you. We will, however, help you with specific issues with code you've written yourself.
Jul 26 '08 #2
We're not going to do your homework for you. We will, however, help you with specific issues with code you've written yourself.
= well this isn't my homework i like to code at home and i look up challenges here and there to solve but this one has been buggin me and i cant solve it i just need to know how its coded thats all dont solve it or anything
Jul 28 '08 #3
bvdet
2,851 Expert Mod 2GB
Have you written any code of your own? This reads the data file and creates two lists:
Expand|Select|Wrap|Line Numbers
2. N_list = fileList[0].split()
3. Q_list = fileList[1].split()
What would be next?
Jul 28 '08 #4
Have you written any code of your own? This reads the data file and creates two lists:
Expand|Select|Wrap|Line Numbers
2. N_list = fileList[0].split()
3. Q_list = fileList[1].split()
What would be next?

hey thanks for that i am gonna post the part of the code that i have done see if you can find whats wrong i have already done the part where it reads from the text file and then the split part as well i will post it tonight
Jul 30 '08 #5
hey thanks for that i am gonna post the part of the code that i have done see if you can find whats wrong i have already done the part where it reads from the text file and then the split part as well i will post it tonight

import time

##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)

Input = file("in.txt","r") ## reading input from file
output = file("out.txt","w")
List = []

for line in Input:
line1 = line.rstrip()
nums = line1.split(" ")
List.append(nums)
lenght = len(list)

for i in range(female):
for j in range(male):
if male(i)<list[0]:
sum = "x"+list[0]
output.write(sum)
elif male(i)>list[-1]:
sum = list[-1]+"x"
output.write(sum)
elif list(i)<male(i)and list(i+1)>male(i):
sum = list(i)+list[i+1]
output.write(sum)
elif male(i)==list[0]:
sum = "x"+list[1]
output.write(sum)
elif male(i)==list[-1]:
sum = list(length)+"x"
output.write(sum)
input.close()
output.close()
##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)

this as far as i have done if anyone can help please let me know
Aug 1 '08 #6
import time

##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)

Input = file("in.txt","r") ## reading input from file
output = file("out.txt","w")
List = []

for line in Input:
line1 = line.rstrip()
nums = line1.split(" ")
List.append(nums)
lenght = len(list)

for i in range(female):
for j in range(male):
if male(i)<list[0]:
sum = "x"+list[0]
output.write(sum)
elif male(i)>list[-1]:
sum = list[-1]+"x"
output.write(sum)
elif list(i)<male(i)and list(i+1)>male(i):
sum = list(i)+list[i+1]
output.write(sum)
elif male(i)==list[0]:
sum = "x"+list[1]
output.write(sum)
elif male(i)==list[-1]:
sum = list(length)+"x"
output.write(sum)
input.close()
output.close()
##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)

this as far as i have done if anyone can help please let me know

import time

##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)

output = file("out.txt","w")
male = []
female = []
a = 0
line = line.rstrip()
templine = line.split(" ")
length = len(templine) #finding length of each line
if a == 0:
female = templine # list of female chimps
f_len = length # length of list of female chimps
else:
male = templine # list of male chimps
m_len = length # length of list of male chimps
a = a + 1
# there was a error while reading the file i have removed that ,

# 1) first for every height in male list ..you have to search in female list....there will be two possibilities...

# for eg. like in female list this one [ 2 3 5 7 ]

# if we have to search male height of [ 4 ]
# we will not be able to find 4

# so three cases arise which are

# 1) it can be less than first element of the list
# for example , if we have to search for [1]
#just we can print "x"+female[0]
# 2) it can be greater than the last element
# for example if we have to search for [9]
# so we can print female[-1]+"X"

# 3) or it can be in between the list
# for example , if we search [6]
# now 6 is in between the 5 and 7
# so we can just write in our condition like

# if list[x<6] amd list[x+1] >6
# print "list[x]" + "list[x+1]"

# these were the conditions only if the element for which we are searching is not found

# second possibility
# if it is found

# now again according to me there are 3 conditions
#1) it can be equal to the last element of the list like 7
#2) it can be equal to the first element of the list like 2
# 3) it can be in between the list for eg. 5

# now you have take care while applyine the conditions that a height can repeat itself for any number of times because the list may or maynot
# increase
Aug 1 '08 #7