Задача про грузовик

Новости математики. Задачи и головоломки.

Задача про грузовик

Сообщение Сключики » Вт ноя 02, 2021 12:49 pm

Уважаемые математики, информатики и просто неравнодушные граждане)). Застряли с ребёнком над задачей про грузовик. Вдруг кто-то захочет мимо проходя углубиться)). Заранее бескрайняя благодарность. Итак:
Петя собирается купить грузовичок и заняться перевозками. Он изучил рынок и выяснил, что в
его городе есть n потенциальных клиентов. Для i-го клиента есть mi вариантов контракта. Каждый
вариант задается двумя числами: wij — минимальная грузоподъемность грузовика, которая необходима, чтобы выполнить контракт, и cij — прибыль, которую получит Петя, если заключит этот
контракт. С каждым клиентом можно заключить не более одного контракта.
Сейчас Петя думает, какой грузовик лучше купить, чтобы получить нужную ему прибыль. У
него есть q вариантов. В i-м варианте Петя хочет, чтобы его прибыль была не меньше xi
. Помогите
ему для каждого из вариантов найти минимальную грузоподъемность грузовика, с которой можно
получить такую прибыль.
Формат входных данных
Первая строка содержит число n (1 <= n <= 105).
Далее следуют n блоков, описывающих варианты контракта для каждого из потенциальных
клиентов. Каждый такой блок начинается с числа mi
, далее следуют mi пар чисел wij , cij
Далее следует число q (1 <= q <= 105). Далее следуют q чисел xi (1 <= xi <= 109).
Формат выходных данных
Выведите q чисел — минимальную грузоподъемность грузовика, с которой можно получить требуемую прибыль, для каждого из вариантов. Если требуемую прибыль получить невозможно, выведите −1 для соответствующего варианта.
Пример во вложении. Тока не пишите пожалуйста "эта задача решается элементарным методом таким-то", имейте снисхождение)) если нужно по-русски перевести условия задачи, я переведу))
Вложения
Screenshot_1.jpg
Screenshot_1.jpg (4.42 КБ) Просмотров: 675
Аватара пользователя
Сключики
Бывалый
Бывалый
 
Сообщения: 2952
Зарегистрирован: Пт авг 13, 2021 2:50 pm
Медали: 2
Пол: Женский
Соционический тип: Робеспьер
Профессия: техническая

  • { SIMILAR_TOPICS }
    Ответы
    Просмотры
    Последнее сообщение

Вернуться в Математика

Кто сейчас на конференции

Зарегистрированные пользователи: cooler462, GoGo [Bot], Google [Bot], Google Search Appliance, MNick2017, Prokrust, Yandex 3.0 [Bot], Yandex [Bot], Zevs