#python #algorithm
#python #алгоритм
Вопрос:
У нас есть ряд из X гнезд, и у нас есть Y птиц. У каждой птицы есть гнездо. Птицы не любят друг друга и хотят сидеть в своих гнездах как можно дальше от других птиц и в концах ряда, насколько это возможно. Поскольку птица сидит в гнезде, она больше не двигается. Птицы прилетают к гнездам одна за другой. Нужно найти, сколько свободных гнезд справа и слева от последней птицы.
Например, если у нас есть 10 гнезд и 1 птица: Ответ: (4, 5) 10 гнезд и 2 птицы: (1, 3) 10 гнезд и 3 птицы: (2, 1) и т.д. Количество гнезд может составлять около 5 000 000 000.
Моя попытка:
def rec(x, y):
y -= 1
z = x // 2
print('y =', y)
if y == 0:
if z % 2 == 0:
return x - z - 1, x - z
elif z % 2 != 0:
return x-z, x-z
if z == 4:
return 1, 2
elif z == 3:
return 1, 1
else:
return rec(z, y)
Но я не могу учесть тот факт, что, например, если гнезд 17, то третья птица будет сидеть на гнезде справа от первой, а не между первой и второй.
Комментарии:
1. Я думаю, что меня могут немного смутить параметры алгоритма. Извините, но я не понимаю, как, если есть 10 гнезд и только одна птица, как мы узнаем, где эта единственная птица выберет. Например, (9,0) может быть возможным, или это должно быть (4,5)?
2. «Птицы не любят друг друга и хотят сидеть в своих гнездах как можно дальше от других птиц и на концах ряда» — это означает, что птица каждый раз будет выбирать середину свободного гнезда. Если 10 гнезд свободны, мы будем считать это как 4 слева и 5 справа.
3. @OstenGibson, (9,0) не сработает, потому что птицам также не нравятся концы строки, но это может быть так же легко (5,4), как (4,5), кажется, есть какое-то правило для разрыва связей, которое было исключено из описания. И (1,3) для сценария с 2 птицами не имеет смысла, предположительно, вторая птица отправится в середину цикла из 5 гнезд, получив ответ (2,2).
4. @jasonharper, я полагаю, что не имеет значения, будет ли это (5,4) или (4,5) изначально, потому что ответ будет таким же (по-видимому).
5. Ах, извините, да, формулировка меня немного смутила. ands сокрушили мой мозг. И да, как @jasonharper, сценарий с двумя птицами также своеобразен.
Ответ №1:
Как указал @jasonharper, утверждение для сценария 2 bird неверно (с использованием общей логики). Если цель — это то, что вы описали, то решение представлено ниже:
nests = 17
birds = 3
free = [(1, nests)]
for b in range(birds):
t = max(free, key = lambda p: abs(p[1] - p[0]))
break_point = (t[0] t[1])//2
free.remove(t)
free.append((t[0], break_point-1))
free.append((break_point 1, t[1]))
left, right = free[-2], free[-1]
answer = (left[1]-left[0] 1, right[1]-right[0] 1)
print(answer)
Объяснение
В списке free хранятся кортежи, обозначающие разные диапазоны (начиная с 1) пустых гнезд (это объединение диапазонов пустых гнезд).
На каждой итерации мы выбираем самый широкий диапазон, удаляем его из списка, останавливаем в середине и добавляем два результирующих диапазона в конец списка. После того, как все птицы размещены, мы выбираем последние два диапазона в списке (поскольку нас интересует только последняя птица) и печатаем желаемый результат.
Это, вполне возможно, не самое быстрое и не самое эффективное решение с точки зрения памяти. Он просто отображает логику проблемы в удобочитаемом виде.