473,381 Members | 1,446 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,381 software developers and data experts.

somebody please solve this problem for me

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.
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
fido19
5
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
  1. fileList = open("in.txt").readlines()
  2. N_list = fileList[0].split()
  3. Q_list = fileList[1].split()
What would be next?
Jul 28 '08 #4
fido19
5
Have you written any code of your own? This reads the data file and creates two lists:
Expand|Select|Wrap|Line Numbers
  1. fileList = open("in.txt").readlines()
  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
fido19
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
fido19
5
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)


dataread = file("in.txt","r") ## reading input from file
output = file("out.txt","w")
male = []
female = []
a = 0
for line in dataread:
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...

# first possibility , if it is not found
# 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

Sign in to post your reply or Sign up for a free account.

Similar topics

6
by: lostinspace | last post by:
After four+ years of using FrontPage in a limited capacity and having created over 600 pages on my sites, I've finally (at least for the most part) abandoned FP, to begin the process of converting...
23
by: Jason | last post by:
Hi, I was wondering if any could point me to an example or give me ideas on how to dynamically create a form based on a database table? So, I would have a table designed to tell my application...
7
by: Mat | last post by:
I am developping multi-user windows application. i use Access database. user edit, add and delete data from database. Request: when an item is deleted ,added or modified by an user, all others...
5
by: CoreyWhite | last post by:
It is possible to use martingale probability theory to beat some games of chance. In a fair game of coin toss, where the odds reach an equilibrium of 50/50 chain reactions do occur. This can be...
5
by: settyv | last post by:
Hi, Below is the Javascript function that am trying to call from asp:Button control. <script language="javascript"> function ValidateDate(fromDate,toDate) { var fromDate=new Date();
1
by: shapper | last post by:
Hello, For the past hours I have been trying to solve a problem which is driving me crazy. I have to different codes where the problem to solve is the same: CODE 1 (Transforms a XML...
8
by: emekadavid | last post by:
Please can somebody show me a way to work around this. It works in IE6 but doesn't in Mozilla 2.0.0.4. the code is just a prototype that was written minutes ago and i tried commenting it a lot for...
2
by: Tin | last post by:
I bought a laptop and burned 4 recovery CDs for recovery purpose. Instead of burning as disc images, I just copied and pasted these 4 CDs to my USB HDD as 4 folders called "RecoveryCD 1",...
2
by: itsvineeth209 | last post by:
My task is to create login control without using login control in tools. I shouldnt use sqldatasource or any other. I should use only data sets, data adapters and data readers etc. U had created...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.