7493. Буфкрафт

Бренда наслаждается новой ролевой игрой Буфкрафт. Щиты, мечи, книги и другая ручная кладь не влияет на статус персонажа в Буфкрафт. Единственный способ увеличить статус Вашего персонажа – забодать его.

В Буфкрафте имеются две бодалки. Прямая бодалка увеличивает базовое значение статуса, в то время как процентная бодалка увеличивает базовое значение на некоторый процент. Если начальное значение статистики Вашего персонажа равно b, после чего Вы его отбодали n прямыми бодалками с силой d₁, d₂, ..., d_n и m процентными бодалками с силой p₁, p₂, ..., p_m, то результирующий статус будет равен (b + d₁ + d₂ + ... + d_n)(100 + p₁ + p₂ + ... + p_m) / 100. Отметим, что результат может иметь вид дроби.

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

Бренда собирается отправить своего персонажа в поход и хочет увеличить его здоровье до максимально возможного значения. Она имеет в своем распоряжении несколько прямых и процентных боданий и просит Вашей помощи выбрать из них такой набор, который даст персонажу максимально возможное значение здоровья.

Вход. Первая строка содержит четыре целых числа b, k, c_d и c_p – базовое здоровье героя, число слот для бодания, количество доступных прямых боданий и количество доступных процентных боданий.

Следующая строка содержит c_d целых чисел d_i – силы прямых боданий.

Последняя строка содержит c_p целых чисел p_i – силы процентных боданий.

Все числа больше или равны нулю, и не более пятидесяти тысяч.

Выход. В первой строке вывести два числа n и m – количество прямых и процентных боданий (0 ≤ n ≤ c_d, 0 ≤ m ≤ c_p, 0 ≤ n + m ≤ k), которые будут использованы.

В следующей строке вывести n различных чисел – индексы применяемых прямых боданий (бодания нумеруются с единицы).

В последней строке вывести m разных чисел – индексы применяемых процентных боданий (также нумеруются с единицы).

Результирующее здоровье после применения всех n + m боданий должно быть наибольшим.

Пример входа	Пример выхода
70 3 2 2 40 30 50 40	2 1 1 2 1

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Чтобы персонаж получил максимально возможное значение здоровья, силы боданий следует выбрать наибольшими. Отсортируем силы прямых и процентных боданий по убыванию. Поскольку имеются лишь k слотов для бодания, мы не знаем сколько следует совершить прямых n и сколько процентных m боданий (n + m ≤ k, n ≤ cd, m ≤ cp). Совершим перебор значений n и m и найдем ту пару, при которой здоровье персонажа будет максимальным.

Реализация алгоритма

Объявим рабочие массивы: силы прямых боданий d и силы процентных боданий p. Силы боданий будем хранить вместе с их индексами. Соответствующие частичные суммы посчитаем в массивах sumd и sump.

vector<pair<int,int> > d, p;

vector<int> sumd, sump;

Читаем входные данные. Заполняем массивы.

scanf("%d %d %d %d",&b,&k,&cd,&cp);

d.resize(cd+1); p.resize(cp+1);

sumd.resize(cd+1);sump.resize(cp+1);

for(i = 1; i <= cd; i++)

{

scanf("%d",&d[i].first);

d[i].second = i;

}

for(i = 1; i <= cp; i++)

{

scanf("%d",&p[i].first);

p[i].second = i;

}

Отсосртируем силы боданий по убыванию.

sort(d.begin(),d.end(),greater<pair<int,int> >());

sort(p.begin(),p.end(),greater<pair<int,int> >());

Вычислим частичные суммы сил боданий.

for(i = 1; i <= cd; i++)

sumd[i] = sumd[i-1] + d[i-1].first;

for(i = 1; i <= cp; i++)

sump[i] = sump[i-1] + p[i-1].first;

Совершим перебор значений n и m (n + m ≤ k), и найдем те, при которых результирующее здоровье персонажа res будет наибольшим. Учитываем ограничения: n ≤ cd, m ≤ cp. Сумма наибольших n прямых боданий находится в sumd[n]. Сумма наибольших m процентных боданий находится в sump[m].

res = 0;

for(n = 0; n <= min(cd,k); n++)

{

m = min(k - n,cp);

s = 1LL * (b + sumd[n]) * (100 + sump[m]);

if (s > res)

{

res = s;

Оптимальное количество прямых боданий сохраним в indn, а процентных в indm.

indn = n; indm = m;

}

}

Выводим ответ – количество прямых и процентных боданий, а также их индексы.

printf("%d %d\n",indn,indm);

if (indn > 0)

{

printf("%d",d[0].second);

for(i = 1; i < indn; i++)

printf(" %d",d[i].second);

}

printf("\n");

if (indm > 0)

{

printf("%d",p[0].second);

for(i = 1; i < indm; i++)

printf(" %d",p[i].second);

}

printf("\n");