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

127. Два подарка в пределах бюджета

Средняя

В подборке Ozon «Подарки к 8 Марта» лежат товары с ценами prices в рублях. Покупатель берёт ровно два разных товара и готов потратить не больше budget рублей.

Посчитайте, сколько существует пар товаров (порядок не важен), сумма цен которых не больше budget. Товары с одинаковой ценой — разные товары.

В работе: Блок «Соберите набор до 3000 ₽»: если пар меньше 10, блок не показываем.

Пример 1

Ввод
prices = [1200, 700, 2500, 900, 400]
budget = 1700
Вывод
4

Подходят 1200+400, 700+900, 700+400, 900+400 — четыре пары.

Пример 2

Ввод
prices = [3000]
budget = 5000
Вывод
0

Один товар — пар нет.

Ограничения

  • 0 ≤ n ≤ 10⁵
  • 1 ≤ prices[i] ≤ 10⁶
  • 1 ≤ budget ≤ 2·10⁶
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def gift_pairs(prices, budget):
Два указателяСортировкацельO(n log n)

Источник: наша задача на данных Ozon. Условие пересказано своими словами.