27.07 Прочие прототипы
Ошибка.
Попробуйте повторить позже
В финал конкурса на получение грантов прошло три предприятия (назовем их 
). Заранее было посчитано и
отображено в сводной таблице, сколько каждое предприятие сможет производить единиц товара за определенное
количество единиц денежных средств.
Фонд, выдающий грант, преследует следующую цель — требуется раздать столько средств каждому из предприятий, чтобы их суммарное количество произведенных единиц товара было максимальным. Фонд может раздать все средства из гранта, либо часть.
Также фонд может выдать средства каждому предприятию лишь единожды. Например, для примера входных данных,
он может выдать предприятию 
денежных средств, но не 
и 
денежных средств одновременно, несмотря на
то, что фонду хватит на это денег.
В ответе укажите максимальную сумму произведенных единиц товара предприятий на деньги, полученные с гранта.
Имеется следующий набор данных:
В первой строке указано натуральное 
, 
— количество строк сводной таблицы. Во второй строке
указано натуральное число 
— общий размер денежных средств фонда для распределения грантов. В третьей строке
указано натуральное число 
— дискретизация распределения средств грантом. Т.е. фонд может выдать количество
денежных средств одному предприятию 
, но не большее, чем число 
. В последующих 
строках
подается 4 числа — шаг дискретизации, единицы товара для 
, единицы товара для 
единицы товара для
.
В ответе укажите два числа через пробел: искомое значение для файла A и для файла B.
Пример входных данных:
4
30
10
0 0 0 0
10 34 21 33
20 47 23 40
30 67 55 90
Эти данные можно представить в виде таблицы для большей наглядности:
Например, если фонд выдаст 
10 ед. денежных средств, то 
сможет произвести 34 единицы товара.
Выходные данные для приведённого выше примера: 
Выгоднее всего оказалось выдать 
ед. денежных средств предприятию 
(а остальным не выдать ничего), т.к. в
таком случае будет произведено наибольшее количество товара.
Неэффективное решение
f = open(’27A.txt’) n = int(f.readline()) s = int(f.readline()) k = int(f.readline()) g1, g2, g3 = [], [], [] for i in range(n): a = list(map(int, f.readline().split())) g1.append(a[1]) g2.append(a[2]) g3.append(a[3]) ans = 0 for i in range(n): for j in range(n): for w in range(n): if (i * k) + (j * k) + (w * k) <= s: if g1[i] + g2[j] + g3[w] > ans: ans = g1[i] + g2[j] + g3[w] print(ans)
Эффективное решение
f = open(’27B.txt’) n = int(f.readline()) s = int(f.readline()) k = int(f.readline()) g1, g2, g3 = [], [], [] for i in range(n): a = list(map(int, f.readline().split())) g1.append(a[1]) g2.append(a[2]) g3.append(a[3]) g = [g1, g2, g3] ans = [[0] * n for i in range(n)] F = [[0] * n for i in range(len(g))] F[0] = g[0].copy() for k in range(1, 3): for i in range(n): for j in range(n): if i - j >= 0: ans[i][j] = g[k][j] + F[k - 1][i - j] for i in range(n): F[k][i] = max(ans[i]) print(max(F[2]))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
