Stack Overflow на русском Asked on December 16, 2021
Имеется задача. Нужно по заданной высоте, ширине и количеству дипломов повесить их в квадратную рамку минимального размера. Если нужно, вот ссылка на задачу. Я написал код, и при попутке сдать его, из 21 теста 11 тестов не проходят из-за привышения лимита памяти. Объясните, что я сделал не так.
import math
h,w,n = map(int,input().split())
# размер рамки, от рамки, для которой условие точно не
# выполниться, до рамки для который условие точно выполниться.
ans = [i for i in range(1,math.ceil(math.sqrt(n))*(max(w,h))+1)]
def bin_search(a,x,w,h):#обычний бин. поиск по ответу
l = 0
r = len(a)-1
m = (l+r)//2
while r - l >1:
m = (l+r)//2
if (a[m] // w) * (a[m] // h) >= n:
r = m
else:
l = m
return a[r]
print(bin_search(ans,n,w,h))
Алгоритм выглядит правильным, но на кой вам хранить последовательные целые числа большого диапазона в списке?
Работайте с m
, возвращайте r
, а a[]
вообще исключите.
Answered by MBo on December 16, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP