// PascalABC.NET 3.3, сборка 1607 от 31.12.2017// Внимание! Если программа не работает, обновите версию!const cunit=1000; DISCOUNT_PER_UNIT=500; MAX_DISCOUNT=0.2;function getTotalCost(firstCost,secondCost,fullUnits:real):real;begin var couponSum:=fullUnits*DISCOUNT_PER_UNIT; var secondCostWithDiscount:= secondCost-Min(MAX_DISCOUNT*secondCost,couponSum); Result:=firstCost+secondCostWithDiscountend;function solveKnapsack(weights:array of integer; totalWeight:integer): array of integer;begin var maxUnits:=Trunc(totalWeight/cunit+1); var old:=ArrFill(maxUnits+1,totalWeight); old[0]:=0; var cur:=new integer[maxUnits+1]; var n:=weights.Length; for var pos:=0 to n-1 do begin cur.Fill(t->totalWeight); for var units:=0 to maxUnits do begin cur[units]:=Min(cur[units],old[units]); var add:=Trunc(weights[pos]/cunit); if units-add >= 0 then cur[units]:=Min(cur[units],old[units-add]+weights[pos]) end; cur.CopyTo(old,0); end; Result:=old; end;function getSolution(costs:array of integer):real;begin var n:=costs.Length; var totalCost:=0; for var i:=0 to n-1 do totalCost+=costs[i]; var minForUnits:=solveKnapsack(costs,totalCost); Result:=totalCost; var maxUnits:=Trunc(totalCost/cunit+1); for var units:=0 to maxUnits do begin var cur:real:=minForUnits[units]; Result:=Min(Result,getTotalCost(minForUnits[units],totalCost-cur,units)) endend;begin Writeln(getSolution(ReadArrInteger(ReadInteger)):0:2)end.
Пример151131 2764 1249 3885 4971 2526 1506 1919 520 3094 2183 2503 277 2293 447730415.40