Answer the question
In order to leave comments, you need to log in
How to optimize a simple code?
There is such a task
Printers work with unequal speed. One prints a page in X seconds and the other in Y.
So now John and Mary are trying to figure out the minimum time they can take to print the entire document.
The input contains the number of test cases in the first line.
The tests themselves follow, one on each line.
Each of them contains three integers - XYN, where N does not exceed 1,000,000,000.
The response must contain the minimum print times for each case, separated by a space.
I solved it for small input values.
But if we take s1=24342423 s2= 23423413 pages=45234524
then everything will be fine.
Prompt algorithm
def twoprinters(s1,s2,pages):
seconds=1
r=0
while True:
r=(int(seconds/s1)+int(seconds/s2))
if r>=pages:break
else:
seconds=seconds+1
return seconds
Answer the question
In order to leave comments, you need to log in
Optimizing the wrong solution is useless. There are 2 options:
1) Implement a binary search. You already have the right idea how to determine that in a given number of seconds you can print as many or more pages (floor(seconds/s1)+floor(seconds/s2) >= n). Now, instead of increasing seconds linearly, double it. Those. instead of seconds = seconds+1 do seconds = seconds*2. Then do a binary search on the interval [1,seconds].
2) Apply math. We need to find the minimum x such that floor(x/s1)+floor(x/s2) >= n.
Let's round off and solve x/s1 + x/s2 >= n.
x = ceil(n*s1*s2/(s1+s2)).
But. this will be an upper estimate, because we have omitted rounding, which reduces the real value of the number of pages printed in x seconds. But, attention, the actual number of pages will be a maximum of 2 pages less, because rounding knocks off a maximum of 1 page.
Now let's increase x to increase the number of printed pages. If you just add 1 every time, then almost always the value will not change, because x / s1 will still be fractional. The increment will only occur when x/s1 or x/s2 is an integer. The next such number can be easily found (it will be x divisible by s1 or s2. So the solution is:
def twoprinters(s1,s2,pages):
seconds= int(pages*s1*s2 + s1 + s2 - 1)/(s1+s2)
while int(seconds/s1)+int(seconds/s2) < pages:
a = seconds - seconds%s1 + s1
b = seconds - seconds%s2 + s2
seconds = min(a,b)
Of course, I understand that Python is slow (because it sucks to compile line by line), but I did the optimization anyway:
seconds=1
r=0
if (r<pages):
seconds += 1
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question