mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
73 lines
2.0 KiB
Python
73 lines
2.0 KiB
Python
from math import ceil, floor
|
|
|
|
|
|
def find(t, k):
|
|
"""
|
|
Annettuna on lista kokonaislukuja, jotka kaikki ovat väliltä 1…k.
|
|
Listalle halutaan lisätä uusi kokonaisluku väliltä 1…k,
|
|
jonka etäisyys lähimpään listalla jo valmiiksi olevaan lukuun on mahdollisimman
|
|
suuri. Kuinka suuri tuo etäisyys voi korkeintaan olla?
|
|
|
|
Voit olettaa, että listalla on korkeintaan 105 lukua ja k on korkeintaan 109.
|
|
Tavoitteena on, että algoritmin aikavaativuus on O(n) tai O(nlogn).
|
|
|
|
Toteuta tiedostoon distance.py funktio find,
|
|
joka ilmoittaa suurimman mahdollisen etäisyyden.
|
|
"""
|
|
t.sort()
|
|
result = 0
|
|
dict = {}
|
|
# print(t)
|
|
|
|
prev_val = None
|
|
for i, x in enumerate(t):
|
|
if prev_val == x:
|
|
continue
|
|
if i == 0:
|
|
dict[x] = x - 1
|
|
prev_val = x
|
|
else:
|
|
dict[x] = x - t[i - 1]
|
|
prev_val = x
|
|
|
|
# print(dict)
|
|
|
|
for i, x in enumerate(dict):
|
|
# print(f"x, k, distance: {x}, {k}, {dict[x]}")
|
|
|
|
if i == 0:
|
|
result = dict[x]
|
|
if i == len(dict) - 1:
|
|
last_value = k - x
|
|
if last_value > result:
|
|
result = last_value
|
|
|
|
# jos max pituus on pienempi kuin dictin väli aiempaan // 2 + index
|
|
# if k < ceil(dict[x] // 2) + x:
|
|
# print(
|
|
# f"if k > x + (dict[x] // 2): {x} + ({ceil(dict[x] // 2)}) = {x+ceil((dict[x] // 2))}"
|
|
# )
|
|
|
|
division = dict[x] / 2
|
|
if x > k:
|
|
if k > x - floor(division):
|
|
return result
|
|
|
|
elif x <= k:
|
|
if floor(division) > result:
|
|
result = division
|
|
|
|
return floor(result)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print(find([1, 2, 9], 11)) # 3
|
|
print(find([2, 1, 3], 3)) # 0
|
|
print(find([7, 4, 10, 4], 10)) # 3
|
|
print(find([15, 2, 6, 4, 18], 20)) # 4
|
|
print(
|
|
find([41222388, 392676742, 307110407, 775934683, 25076911], 809136843)
|
|
) # 191628970
|
|
print(find([2, 11, 9, 10, 10], 15)) # 4
|
|
print(find([2], 15))
|