{ tde } program Discount; {$APPTYPE CONSOLE} { Delphi } (* * Problem : DISCOUNT * Contest : UOI-2008 (LVIV) * Type : Solution * Date : March 18, 2008 * Version : 1.0 * Author : Shamil Yagiyayev * Language : Delphi * Compiler : Turbo Delphi 2006 * Link : * Algorithm: Author Solution *) const MAX_N = 10000; var n, i, sum : integer; A : array[1..MAX_N] of integer; procedure swap(var a : integer; var b : integer); var c : integer; begin c:=a; a:=b; b:=c; end; procedure rebuild(f, l: integer); var k : integer; begin while 2*f+1 <= l do begin if A[2*f] < A[2*f+1] then k:=2*f else k:=2*f+1; if A[f] > A[k] then begin swap(A[f], A[k]); f := k; end else break; end; if (2*f = l) and (A[f] > A[l]) then swap(A[f], A[l]); end; procedure heapSort; var i : integer; begin for i:=(n div 2) downto 1 do rebuild(i, n); for i:=n downto 2 do begin swap(A[1], A[i]); rebuild(1, i-1); end; end; begin Assign(input, 'discount.dat'); Reset(input); ReadLn(n); for i:=1 to n do Read(A[i]); Close(input); heapSort; sum := 0; for i := 1 to n do if i mod 3 <> 0 then sum := sum + a[i]; Assign(output, 'discount.sol'); Rewrite(output); Writeln(sum); Close(output); end.