Prodaja

Interfejs

Pošaljite jedan C++23 izvorni fajl koji implementira sledeći interfejs:

long long Prodaja(int N, int K, int* A);

Tekst zadatka

Продаја Лука је продавац у радњи мистериозних кутија. Његова стратегија продаје је необична: уместо да на сваку кутију залепи фиксну цену, он погађа колико је муштерија спремна да плати, надајући се да ће погодити цену довољно ниску да муштерија прихвати, али и довољно високу да оствари што већу зараду. Данас је у радњу ушла муштерија спремна да за кутију плати неки тајни износ , где је цео број из скупа X X . Лука не зна {1, 2, … , N }

тачну вредност , али зна начин на који ће муштерија изабрати своју вредност: насумично! У радњи се налази кутија са папирића X N

са предложеним ценама. На сваком папирићу се налази један број из скупа , а Лука, као мудар трговац, зна колико има {1, 2, … , N }

папирића на којима је написан сваки број. Обележимо са (где је ) број папирића где је написан број у кутији. Муштерија Ai 1 ≤ i ≤ N i

ће папирић извући без гледања, те је шанса да било који од папирића буде извучен подједнака. A1 + A2 + … + AN

Лука муштерији може да предложи највише цена. Сваки предлог троши један од његових покушаја: Ако је : муштерија прихвата понуду, Лука зарађује динара, и купопродаја је завршена. K Y ∈ {1, … , N } K

Ако је : муштерија одбија (Лука то види) и може да предложи нову цену уколико му је остало још покушаја. Y ≤ X Y Y > X

Ако Лука исцрпи свих покушаја без прихваћене понуде, зарада му је . Лука игра оптимално, тако да максимизује своје добитке. K 0

Помозите Луки да израчуна оптималну очекивану зараду -- формалну дефиницију можемо наћи у секцији "Описи функција". S

Описи функција Потребно је да имплементирате функцију P rodaja(N , K, A[…]) . Ова функција ће бити позвана једном по примеру. представља дужину опсега за цене, а представља број дозвољених покушаја. N K

Низ од ненегативних целих бројева N представља бројеве папирића са написаним бројевима A1 , A2 , … , AN 1, 2, … , N

респективно. За фиксирану стратегију продавца и за сваку могућу вредност , нека је зарада коју продавац оствари у случају да је купчева X = i zi

непозната вредност управо (вредности зависе од изабране стратегије). Функција треба да врати максималну вредност збира i zi

S = A1 ⋅ z 1 + A2 ⋅ z 2 + ⋯ + AN ⋅ z N ,

посматрано преко свих могућих стратегија продавца. Може се показати да је овај максимум увек ненегативан цео број.

Пример Улаз Нека је , ,и . Функција треба да врати , због следећег објашњења. Објашњење примера N = 5 K = 2 А = [1, 1, 1, 1, 1] 12

Једна од оптималних стратегија: Лука прво предлаже Y = 4 . Ако купац одбије, у другом покушају предлаже Y = 2 . Тиме за сваку вредност добијамо зараду : : оба предлога су одбијена, . X = i zi

или : први предлог је одбијен, други прихваћен, . X = 1 z1 = 0

или : први предлог је прихваћен, . X = 2 X = 3 z2 = z3 = 2 X = 4 X = 5 z4 = z5 = 4

Збир за ову стратегију је , и може се показати да је то максимална могућа вредност. Ограничења S = 1 ⋅ 0 + 1 ⋅ 2 + 1 ⋅ 2 + 1 ⋅ 4 + 1 ⋅ 4 = 12

Означимо са суму свих елемената низа . D А

1 ≤ N ≤ 5000 9 0 ≤ K ≤ 10 9 1 ≤ D ≤ 10 0 ≤ ai ≤ D и ∑ N

i=1 ai = D

Тест примери су одвојени у дисјунктних група: 6

У тест примерима вредним 10 поена: K = 1и А = А = ⋯ = А

У тест примерима вредним 10 поена: и 1 2 N

У тест примерима вредним 10 поена: K = 2 А = А = ⋯ = А 1 2 N

У тест примерима вредним 25 поена: , K = 1

У тест примерима вредним 35 поена: N ≤ 200 K ≤ N

У тест примерима вредним 10 поена: без додатних ограничења K ≤ N

Детаљи имплементације Потребно је да пошаљете тачно један фајл prodaja.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке. Ваша функција мора бити следећег облика: long long Prodaja(int N, int K, int* А);

Низ је индексиран од 1. A

Вашим програмима је дозвољено да мењају садржај низова, али не смеју да приступају ван граница датих низова. Уз задатак, обезбеђен вам је template фајл code.cpp, који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp, који служи да лакше тестирате кодове.

Овај програм учитава са стандардног улаза следеће податке: У првом реду бројеве и . У другом реду бројева: . N K

N А[i]

Затим овај програм позива вашу функцију и исписује вредност P rodaja(N , K, А) у једином реду излаза.