Войти Регистрация
Алгоритмы

45. Ближайшие банкоматы на нужную сумму

Средняя

Даны координаты пользователя user = [x, y], банкоматы atms, каждый — [id, x, y, остаток], и сумма amount.

Берите банкоматы от ближнего к дальнему (при равном расстоянии — по возрастанию id), пока сумма их остатков не станет ≥ amount. Верните id выбранных. Если всех вместе не хватает — верните [].

В работе: Подсказать в приложении, в какие банкоматы зайти, чтобы снять крупную сумму.

Пример 1

Ввод
user = [0, 0]
atms = [[1, 1, 0, 300], [2, 2, 0, 200], [3, 5, 0, 1000]]
amount = 400
Вывод
[1, 2]

Пример 2

Ввод
user = [0, 0]
atms = [[1, 1, 0, 300], [2, 2, 0, 200], [3, 5, 0, 1000]]
amount = 200
Вывод
[1]

Ограничения

  • 0 ≤ число банкоматов ≤ 10⁵
  • Координаты — целые, |x|, |y| ≤ 10⁶
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def nearest_with_cash(user, atms, amount):
СортировкаГеометрияцельO(n log n)

Источник: Альфа-Банк, наймовое соревнование Alfa Battle, 2020. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.