Đề thi Toán - Tin trong nhà trường Bài 100

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);
 var
 i, j, x, tg: Integer;
 begin
 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);
 end;
 procedure Prepare;
 var
 i, j: Integer;
 begin
 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;
 end;
 function View(n: Integer): LongInt;
 var
 i, j: Integer;
 lSum1, lSum2: LongInt;
 begin
 lSum1 := 0; lSum2 := v[n];
 for i := Ind[n - 1] + 1 to Ind[n] do
 begin
 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
 begin
 if Value[p[i]] = 0 then Value[p[i]] := View(p[j]);
 lSum2 := lSum2 + Value[p[j]];
 end;
 end;
 if lSum1 > lSum2 then
 begin
 View := lSum1;
 Pred[n] := n - 1;
 end
 else
 begin
 View := lSum2;
 Pred[n] := n - 2;
 end;
 end;
 procedure Calculator(n: Integer);
 var
 i, j: Integer;
 begin
 if Pred[n] = n - 2 then
 begin
 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])
 end
 else for i := Ind[n - 1] + 1 to Ind[n] do Calculator(p[i])
 end;
 procedure WriteOutput;
 var
 hFile: Text;
 i: Integer;
 sView: LongInt;
 begin
 Assign(hFile, Out);
 Rewrite(hFile);
 sView := View(p[1]);
 Calculator(p[1]);
 Writeln(hFile, lSum, ' ', sView);
 for i := 1 to n do
 if Ok[i] then Writeln(hFile, i);
 Close(hFile);
 end;
begin
 ReadInput;
 Prepare;
 WriteOutput;
end.
=========================== The End ============================