Bài 100/2002 - Mời khách dự tiệc
(Dành cho học sinh THPT)
program Guest;
const
Inp = 'Guest.inp';
Out = 'Guest.out';
var
n: Integer;
lSum: LongInt;
t, v, p, Pred, Ind: array[0..1005] of Integer;
Value: array[0..1005] of LongInt;
Ok: array[0..1005] of Boolean;
procedure ReadInput;
var
hFile: Text;
i: Integer;
begin
Assign(hFile, Inp);
Reset(hFile);
Readln(hFile, n);
for i := 1 to n do Readln(hFile, t[i], v[i]);
Close(hFile);
end;
procedure QuickSort(l, r: Integer);
i, j, x, tg: Integer;
i := l; j :=r; x := p[(l + r) div 2];
repeat
while t[p[i]] < t[x] do Inc(i);
while t[p[j]] > t[x] do Dec(j);
if i <= j then
begin
tg := p[i]; p[i] := p[j]; p[j] := tg;
Inc(i); Dec(j);
end;
until i > j;
if i < r then QuickSort(i, r);
if j > l then QuickSort(l, j);
procedure Prepare;
i, j: Integer;
FillChar(Value, SizeOf(Value), 0);
FillChar(Ok, SizeOf(Ok), False);
lSum := 0;
for i := 1 to n + 1 do p[i] := i;
t[n + 1] := n + 1;
QuickSort(1, n);
j := 2; Ind[0] := 1;
for i := 1 to n do
begin
while t[p[j]] = i do Inc(j);
Ind[i] := j - 1;
end;
function View(n: Integer): LongInt;
lSum1, lSum2: LongInt;
lSum1 := 0; lSum2 := v[n];
for i := Ind[n - 1] + 1 to Ind[n] do
if Value[p[i]] = 0 then Value[p[i]] := View(p[i]);
lSum1 := lSum1 + Value[p[i]];
for j := Ind[p[i] - 1] + 1 to Ind[p[i]] do
if Value[p[i]] = 0 then Value[p[i]] := View(p[j]);
lSum2 := lSum2 + Value[p[j]];
if lSum1 > lSum2 then
View := lSum1;
Pred[n] := n - 1;
end
else
View := lSum2;
Pred[n] := n - 2;
procedure Calculator(n: Integer);
if Pred[n] = n - 2 then
Ok[n] := True; Inc(lSum);
for i := Ind[n - 1] + 1 to Ind[n] do
for j := Ind[p[i] - 1] + 1 to Ind[p[i]] do Calculator(p[j])
else for i := Ind[n - 1] + 1 to Ind[n] do Calculator(p[i])
procedure WriteOutput;
sView: LongInt;
Assign(hFile, Out);
Rewrite(hFile);
sView := View(p[1]);
Calculator(p[1]);
Writeln(hFile, lSum, ' ', sView);
if Ok[i] then Writeln(hFile, i);
begin
ReadInput;
Prepare;
WriteOutput;
end.
Bạn đang xem bài 100/ - 100 DE TIN HSG CO DAP AN
