100 đề Toán tin, tin học và nhà trường

100 đề Toán Tin 
 Tin học & Nhà trường
Hà Nội - 2002
Phần 1: ĐỀ BÀI
Bài 1/1999 - Trò chơi cùng nhau qua cầu 
(Dành cho học sinh Tiểu học)
Bốn người cần đi qua một chiếc cầu. Do cầu yếu nên mỗi lần đi không quá hai người, và vì trời tối nên phải cầm đèn mới đi được. Bốn người đi nhanh chậm khác nhau, qua cầu với thời gian tương ứng là 10 phút, 5 phút, 2 phút và 1 phút. Vì chỉ có một chiếc đèn nên mỗi lần qua cầu phải có người mang đèn trở về cho những người kế tiếp. Khi hai người đi cùng nhau thì qua cầu với thời gian của người đi chậm hơn. Ví dụ sau đây là một cách đi:
- Người 10 phút đi với người 5 phút qua cầu, mất 10 phút.
- Người 5 phút cầm đèn quay về, mất 5 phút.
- Người 5 phút đi với người 2 phút qua cầu, mất 5 phút.
- Người 2 phút cầm đèn quay về, mất 2 phút.
- Người 2 phút đi với người 1 phút qua cầu, mất 2 phút.
Thời gian tổng cộng là 10+5+5+2+2 = 24 phút.
Em hãy tìm cách đi khác với tổng thời gian càng ít càng tốt, và nếu dưới 19 phút thì thật tuyệt vời! Lời giải ghi trong tệp văn bản có tên là P1.DOC
Bài 2/1999 - Tổ chức tham quan 
(Dành cho học sinh THCS)
Trong đợt tổ chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức hội thi Tin học trẻ tổ chức cho N đoàn ( đánh từ số 1 đến N) mỗi đoàn đi thăm quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm ở cách Khách sạn Hoàng Đế di km (i=1,2,...., N). Hội thi có M xe taxi đánh số từ 1 đến M (M³N) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km.
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.
Dữ liệu: File văn bản P2.INP:
- Dòng đầu tiên chứa hai số nguyên dương N, M (N£M£200);
- Dòng thứ hai chứa các số nguyên dương d1, d2, ..., dN;
- Dòng thứ ba chứa các số nguyên dương v1, v2, ..., vM.
- Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng.
Kết quả: Ghi ra file văn bản P2.OUT:
- Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi thăm quan (không tính lượt về);
- Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1, 2, ..., N).
Ví dụ:
P2.INP
P2.OUT
3 4
7 5 9
17 13 15 10
256
2
3
4
Bài 3/1999 - Mạng tế bào 
(Dành cho học sinh THPT)
Mạng tế bào có dạng một lưới ô vuông hình chữ nhật. Tại mỗi nhịp thời gian: mỗi ô của lưới chứa tín hiệu là 0 hoặc 1 và có thể truyền tín hiệu trong nó cho một số ô kề cạnh theo một qui luật cho trước. Ô ở góc trên bên trái có thể nhận tín hiệu từ bên ngoài đưa vào. Sau nhịp thời gian đó, tín hiệu ở một ô sẽ là 0 nếu tất cả các tín hiệu truyền đến nó là 0, còn trong trường hợp ngược lại tín hiệu trong nó sẽ là 1. Một ô không nhận được tín hiệu nào từ các ô kề cạnh với nó sẽ giữ nguyên tín hiệu đang có trong nó. Riêng đối với ô trên trái, sau khi truyền tín hiệu chứa trong nó đi, nếu có tín hiệu vào thì ô trên trái sẽ chỉ nhận tín hiệu này, còn nếu không có tín hiệu nào thì ô trên trái cũng hoạt động giống như các ô khác. ở trạng thái đầu tín hiệu trong tất cả các ô là 0.
Yêu cầu: Cho trước số nhịp thời gian T và dãy tín hiệu vào S là một dãy gồm T ký hiệu S1, ..., ST, trong đó Si là 0 hoặc 1 thể hiện có tín hiệu vào, ngược lại Si là X thể hiện không có tín hiệu vào tại nhịp thời gian thứ i (1£ i £T), hãy xác định trạng thái của lưới sau nhịp thời gian thứ T.
Dữ liệu: vào từ file văn bản P3.INP:
- Dòng đầu tiên chứa 3 số nguyên M, N, T theo thứ tự là số dòng, số cột của lưới và số nhịp thời gian (1<M, N £ 200; T £ 100);
- Dòng thứ hai chứa xâu tín hiệu vào S;
- M dòng tiếp theo mô tả qui luật truyền tin. Dòng thứ i trong số M dòng này chứa N số ai1, ai2, ..., aiN, trong đó giá trị của aij sẽ là 1, 2, 3, 4, 5, 6, 7, 8 tương ứng lần lượt nếu ô (i, j) phải truyền tin cho ô kề cạnh bên trái, bên phải, bên trên, bên dưới, bên trên và bên dưới, bên trái và bên phải, bên trên và bên trái, bên dưới và bên phải (xem hình vẽ); còn nếu ô (i, j) không phải truyền tín hiệu thì aij = 0.
2
1
3
4
5
7
6
8
Kết quả: Ghi ra file văn bản P3.OUT gồm M dòng, mỗi dòng là một xâu gồm N ký tự 0 hoặc 1 mô tả trạng thái của lưới sau nhịp thời gian thứ T.
Ví dụ:
P3.INP
P3.OUT
2 2 5
101XX
2 4
2 1
11
01
Quá trình biến đổi trạng thái được diễn tả trong hình dưới đây:
0
0
1
0
0
1
1
0
1
1
1
1
0
0
0
0
0
0
0
1
1
0
0
1
Bài 4/1999 - Trò chơi bốc sỏi 
(Dành cho học sinh Tiểu học)
Trên mặt đất có một đống sỏi có 101 viên. Hai em học sinh Hoàng và Huy chơi trò chơi như sau: Mỗi em đến lượt đi phải bốc ra từ đống sỏi trên tối thiểu là 1 viên và tối đa là 4 viên. Người thua là người phải bốc viên sỏi cuối cùng. Giả sử Hoàng là người được bốc trước, Huy bốc sau. Các em thử nghĩ xem ai là người thắng cuộc, Hoàng hay Huy? Và người thắng cuộc phải suy nghĩ gì và thực hiện các bước đi của mình ra sao?
Bài 5/1999 - 12 viên bi 
(Dành cho học sinh THCS)
Có 12 hòn bi giống hệt nhau về kích thước, hình dáng và khối lượng. Tuy nhiên trong chúng lại có đúng một hòn bi kém chất lượng: hoặc nhẹ hơn hoặc nặng hơn bình thường. Dùng một cân bàn hai bên, bạn hãy dùng 3 lần cân để tìm ra được viên bi đó. Cần chỉ rõ rằng viên bi đó là nặng hơn hay nhẹ hơn.
Viết chương trình mô phỏng việc tổ chức cân các hòn bi trên. Dữ liệu về hòn bi kém chất lượng do người sử dụng chương trình nắm giữ. Yêu cầu trình bày chương trình đẹp và mỹ thuật.
Bài 6/1999 - Giao điểm các đường thẳng 
(Dành cho học sinh THPT)
Trên mặt phẳng cho trước n đường thẳng. Hãy tính số giao điểm của các đường thẳng này. Yêu cầu tính càng chính xác càng tốt.
Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0, ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào của bài toán cho trong tệp B6.INP có dạng sau:
- Dòng đầu tiên ghi số n
- n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài toán thể hiện trên màn hình.
Bài 7/1999 - Miền mặt phẳng chia bởi các đường thẳng 
(Dành cho học sinh THPT)
Xét bài toán tương tự như bài 6/1999 nhưng yêu cầu tính số miền mặt phẳng được chia bởi n đường thẳng này:
Trên mặt phẳng cho trước n đường thẳng. Hãy tính số miền mặt phẳng được chia bởi các đường thẳng này. Yêu cầu tính càng chính xác càng tốt.
Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0, ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào của bài toán cho trong tệp B7.INP có dạng sau:
- Dòng đầu tiên ghi số n
- n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài toán thể hiện trên màn hình.
Bài 8/1999 - Cân táo 
(Dành cho học sinh Tiểu học)
Mẹ đi chợ về mua cho Nga 27 quả táo giống hệt nhau về kích thước và khối lượng. Tuy nhiên người bán hàng nói rằng trong số các quả táo trên có đúng một quả có khối lượng nhẹ hơn. Em hãy dùng một chiếc cân bàn hai bên để tìm ra quả táo nhẹ đó. Yêu cầu số lần cân là nhỏ nhất.
Các em hãy giúp bạn Nga tìm ra quả táo nhẹ đó đi. Nếu các em tìm ra quả táo đó sau ít hơn 5 lần cân thì đã là tốt lắm rồi.
Bài 9/1999 - Bốc diêm 
(Dành cho học sinh Tiểu học)
Trên bàn có 3 dãy que diêm, số lượng que diêm của các dãy này lần lượt là 3, 5 và 8. Hai bạn Nga và An chơi trò chơi sau: Mỗi bạn đến lượt mình được quyền (và phải) bốc một số que diêm bất kỳ từ một dãy trên. Người thắng là người bốc được que diêm cuối cùng.
Ai là người thắng cuộc trong trò chơi trên? Và bạn đó phải bốc diêm như thế nào? Các bạn hãy cùng suy nghĩ với Nga và An nhé.
Bài 10/1999 - Dãy số nguyên 
(Dành cho học sinh THCS)
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314..... (1)
Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?
Em hãy làm bài này theo hai cách: Cách 1 dùng suy luận logic và cách 2 viết chương trình để tính toán và so sánh hai kết quả với nhau.
Tổng quát bài toán trên: Chương trình yêu cầu nhập số K từ bàn phím và in ra trên màn hình kết quả là số nằm ở vị trì thứ K trong dãy (1) trên. Yêu cầu chương trình chạy càng nhanh càng tốt.
Bài 11/1999 - Dãy số Fibonaci 
(Dành cho học sinh THCS)
Như các bạn đã biết dãy số Fibonaci là dãy 1, 1, 2, 3, 5, 8, .... Dãy này cho bởi công thức đệ qui sau:
F1 = 1, F2 =1, Fn = Fn-1 + Fn-2 với n > 2
1. Chứng minh khẳng định sau:
Mọi số tự nhiên N đều có thể biểu diễn duy nhất dưới dạng tổng của một số số trong dãy số Fibonaci.
N = akFk + ak-1Fk-1 + .... a1F1
Với biểu diễn như trên ta nói N có biểu diễn Fibonaci là akak-1...a2a1.
2. Cho trước số tự nhiên N, hãy tìm biểu diễn Fibonaci của số N.
Input: 
Tệp văn bản P11.INP bao gồm nhiều dòng. Mỗi dòng ghi một số tự nhiên.
Output:
Tệp P11.OUT ghi kết quả của chương trình: trên mỗi dòng ghi lại biểu diễn Fibonaci của các số tự nhiên tương ứng trong tệp P11.INP.
Bài 12/1999 - N-mino 
(Dành cho học sinh THPT)
N-mino là hình thu được từ N hình vuông 1´1 ghép lại (cạnh kề cạnh). Hai n-mino được gọi là đồng nhất nếu chúng có thể đặt chồng khít lên nhau.
Bạn hãy lập chương trình tính và vẽ ra tất cả các N-mino trên màn hình. Số n nhập từ bàn phím.
Ví dụ: Với N=3 chỉ có hai loại N-mino sau đây:
 	 3-mino thẳng 3-mino hình thước thợ
Chú ý: Gọi Mn là số các n-mino khác nhau thì ta có M1=1, M2=1, M3=2, M4=5, M5=12, M6=35,... 
Yêu cầu bài giải đúng và trình bày đẹp.
Bài 13/1999 - Phân hoạch hình chữ nhật 
(Dành cho học sinh THPT)
Một hình vuông có thể chia thành nhiều hình chữ nhật có các cạnh song song với cạnh hình vuông (xem Hình vẽ). Xây dựng cấu trúc dữ liệu và lập chương trình mô tả phép chia đó. Tính xem có bao nhiêu cách chia như vậy. 
 Input
Dữ liệu nhập vào từ tệp P13.INP bao gồm hai số tự nhiên là n, m - kích thước hình chữ nhật.
Output
Dữ liệu ra nằm trong tệp P13.OUT có dạng sau:
- Dòng đầu tiên ghi số K là tổng số các phép phân hoạch.
- Tiếp theo là K nhóm, mỗi nhóm cách nhau bằng một dòng trống.
- Mỗi nhóm dữ liệu bao gồm các cặp tọa độ của các hình chữ nhật nằm trong phân hoạch.
Bài 14/2000 - Tìm số trang sách của một quyển sách 
(Dành cho học sinh Tiểu học)
 ... ng}
uses crt;
const fi ='input.txt';
 fo ='output.txt';
 coso =100;
type mg =array[-maxint..maxint]of byte;
var L :array[1..3]of ^mg;
 n,lap :longint;
 kq :integer;
 time :longint;
 clock :longint absolute $00:$0046c;
procedure tao_test;
var f :text;
 k :longint;
 begin
 n:=1000000;
 assign(f,fi);
 rewrite(f);
 writeln(f,n);
 for k:=1 to N do
 if random(2)=1 then write(f,random(maxint),#32)
 else write(f,-random(maxint),#32);
 close(f);
 end;
procedure danhdau(x:integer);
var i :integer;
 begin
 for i:=3 downto 1 do
 if L[i]^[x]<coso then
 begin
 inc(L[i]^[x]);
 break;
 end
 else L[i]^[x]:=0;
 end;
procedure lam;
var f :text;
 k :longint;
 x :integer;
 begin
 for k:=1 to 3 do
 begin
 new(L[k]);
 fillchar(L[k]^,sizeof(L[k]^),0);
 end;
 assign(f,fi);
 reset(f);
 read(f,n);
 for k:=1 to n do
 begin
 read(f,x);
 danhdau(x);
 end;
 close(f);
 lap:=0;
 for k:=-maxint to maxint do
 if L[1]^[k]*sqr(coso)+L[2]^[k]*coso+L[3]^[k]>lap then
 begin
 lap:=L[1]^[k]*sqr(coso)+L[2]^[k]*coso+L[3]^[k];
 kq:=k;
 end;
 for k:=1 to 3 do dispose(L[k]);
 end;
procedure ghif;
var f :text;
 begin
 assign(f,fo);
 rewrite(f);
 write(f,kq);
 writeln('So lan lap :',lap);
 close(f);
 end;
BEGIN
 {tao_test;}
 time:=clock;
 lam;
 ghif;
 writeln((clock-time)/18.2:10:10);
END.
Bài 92/2002 - Dãy chia hết 
(Dành cho học sinh THPT)
program DayChiaHet;
uses crt;
const inp='div.inp';
 out='div.out';
var a:array[0..1] of set of byte;
 g:text;
 k,n,t,i,j,l:longint;
function f(x:longint):byte;
begin
 x:=x mod k;
 if x<0 then f:=x+k else f:=x;
end;
begin
 clrscr;
 assign(g,inp);reset(g);
 readln(g,n,k);
 t:=0;
 read(g,j);
 a[0]:=[f(j)];
 for i:=2 to n do
 begin
 t:=1-t;
 a[t]:=[];
 read(g,j);
 for l:=0 to k-1 do
 if l in a[1-t] then
 begin
 a[t]:=a[t]+[f(l+j)];
 a[t]:=a[t]+[f(l-j)];
 end;
 end;
 close(g);
 assign(g,out);rewrite(g);
 if 0 in a[t] then write(g,1) else write(g,0);
 close(g);
 write('Complete - Open file ',out,' to view the result');
 readln;
End.
(Lời giải của bạn Vũ Lê An - 12T2 - Lê Khiết - Quảng Ngãi)
Mở rộng bài toán:
1. Tìm dãy con liên tiếp có tổng bé nhất.
2. Tìm dãy con liên tiếp các phần tử thuộc dãy bằng nhau dài nhất.
3. Cho ma trận MxN hãy tìm hình chữ nhật có tổng lớn nhất (nhỏ nhất) với M,N<=100
4. Cho ma trận MxN hãy tìm hình chữ nhật có diện tích lớn nhất có các phần tử bằng nhau.
Cách giải bài toán 2 giải giống với bài toán 1, bài toán 3 và 4 giải giống nhau dựa trên cơ sở bài 1,2. 
Cách giải bài toán 3: Xét hình các hình chữ nhật có toạ độ cột trái là i toạ độ cột phải là j (mất O(N2)). Coi mỗi dòng như một phần tử, để tìm hình chữ nhật có diện tích lớn nhất ta phải mất O(N) nữa. Như vậy độ phức tạp là O(N3).
Bài 93/2002 - Trò chơi bắn bi
(Dành cho học sinh Tiểu học)
Có 3 đường đi đạt số điểm lớn nhất là: 32. 
Bài 94/2002 - Biểu diễn tổng các số Fibonaci
(Dành cho học sinh THCS)
Cách giải: Ta sẽ tìm số Fibonacci gần với số N nhất. Đây sẽ chính là số hạng đầu tiên nằm trong dãy kết quả. Sau đó, lấy hiệu của số N và số Fibonacci gần với số N nhất, tiếp tục tìm số Fib gần với hiệu trên và cứ thế cho đến khi hiệu đó là một số Fib. Kết quả các số Fibonacci sẽ được liệt kê theo thứ tự từ lớn đến nhỏ.
Chương trình:
Program BdFib;{Bai 94/2002: Bieu dien tong cac so Fibonacci}
uses crt;
var n:longint;
 f:array[1..1000] of longint;
function fib(k:integer): longint;
begin
 f[1]:=1;
 f[2]:=1;
 f[3]:=2;
 if f[k]=-1 then f[k]:=fib(k-1)+fib(k-2);
 fib:=f[k];
end;
procedure xuly;
var i,j:longint;
begin
 for i:=1 to 1000 do f[i]:=-1;
 while n>0 do
 begin
 i:=1;
 while fib(i)<=n do
 inc(i);
 j:=fib(i-1);
 write(j,' + ');
 n:=n-j;
 end;
 gotoxy(wherex-2,wherey);
 writeln(' ');
end;
procedure test;
begin
 clrscr;
 write('Nhap n='); readln(n);
 clrscr;
 write('n=');
 xuly;
end;
BEGIN
 test;
 readln;
END.
(Lời giải của bạn Cao Lê Thăng Long - Lớp 8E Nguyễn Trường Tộ - Hà Nội)
Bài 95/2002 - Dãy con có tổng lớn nhất
(Dành cho học sinh THPT)
Program subseq;
const inp = 'subseq.inp';
 out = 'subseq.out';
var n, dau, cuoi, d:longint;
 max, T:longint;
 f, g:text;
Procedure input;
begin
 assign(f,inp); reset(f);
 assign(g,out); rewrite(g);
 Readln(f,n);
End;
Procedure solve;
 var i,j:longint;
begin
 dau:=1; cuoi:=1; d:=1;
 max:=-maxlongint; T:=0;
 for i:=1 to n do
 begin
 readln(f,j); T:=T + j ;
 If T > max then 
 begin
 max:=T;
 dau:=d; cuoi:=i;
 end;
 If T<0 then begin T:=0; d:=i+1; end;
 end;
End;
Procedure output;
Begin
 writeln(g,dau);
 writeln(g,cuoi);
 writeln(g,max);
 Close(f); Close(g);
End;
BEGIN
 input;
 solve;
 output;
END.
(Lời giải của bạn Võ Xuân Sơn - Lớp 11A2 THPT Phan Bội Châu - Nghệ An)
Bài 96/2002 - Số chung lớn nhất
(Dành cho học sinh THPT)
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
uses crt;
const maxn = 251;
 fi = 'string.inp';
 fo = 'string.out';
var pa : array[0..maxn,0..maxn] of byte;
 s1,s2,skq : string;
 max : byte;
procedure docf;
var f : text;
begin
 assign(f,fi);
 reset(f);
 readln(f,s1);
 read(f,s2);
 close(f);
end;
function maxso(a,b:byte) : byte;
begin
 maxso := (abs(a-b)+a+b) div 2;
end;
procedure Idonotknow;
var i,j : byte;
begin
 for i := length(s1) downto 1 do
 for j := length(s2) downto 1 do
 if s1[i] = s2[j] then pa[i,j] := pa[i+1,j+1] +1
 else pa[i,j] := maxso(pa[i+1,j] , pa[i,j+1] );
 max := pa[1,1];
end;
procedure wastingtime;
var ch : char;
 i,j,so,is,js : byte;
begin
 is := 1; js := 1;
 so := 0;
 repeat
 for ch := '9' downto '0' do
 begin
 i := is; j := js;
 while (s1[i] ch)and(i <= length(s1)) do inc(i);
 while (s2[j] ch)and(j <= length(s2)) do inc(j);
 if pa[i,j] = max - so then
 begin
 skq := skq + ch;
 is := i+1; js := j+1;
 break;
 end;
 end;
 inc(so);
 until max=so;
 while (skq[1] = '0')and(skq'0') do delete(skq,1,1);
end;
procedure ghif;
var f : text;
begin
 assign(f,fo);
 rewrite(f);
 if max = 0 then write(f,' Khong co xau chung !!!...')
 else
 begin
 wastingtime;
 write(f,skq);
 end;
 close(f);
end;
BEGIN
 docf;
 idonotknow;
 ghif;
END.
Bài 97/2002 - Thay số trong bảng
(Dành cho học sinh Tiểu học)
4
5
6
 1 2 3
a
b
c
d
e
f
g
h
i
Ngang
4 - Bội số nguyên của 8;
5 - Tích của các số tự nhiên liên tiếp đầu tiên; 
6 - Tích các số nguyên tố kề nhau
Dọc
1 - Bội nguyên của 11;
2 - Tích của nhiều thừa số 2;
3 - Bội số nguyên của 11.
Giải:
Từ (5) - Tích của các số tự nhiên đầu tiên cho kết quả là một số có 3 chữ số chỉ có thể là 120 hoặc 720 (1x2x3x4x5 = 120; 1x2x3x4x5x6 = 720).
Do đó, (5) có thể là 120 hoặc 720. Suy ra: f = 0; e = 2; d = 1 hoặc d = 7.
Tương tự, ta tìm được (6) có thể là 105 hoặc 385 (3x5x7 = 105; 5x7x11 = 385). Suy ra: i = 5; h = 0 hoặc h = 8; g = 1 hoặc g = 3.
Từ (4) suy ra c chỉ có thể là số chẵn. Do f = 0, i = 5, từ (3) ta tìm được c = 6.
Từ (2) - tích của nhiều thừa số 2 cho kết quả là một số có 3 chữ số chỉ có thể là một trong các số: 128, 256, 512. Mà theo trên e = 2 nên ta tìm được (2) là 128. Vậy b = 1, h = 8, g = 3.
Từ (4) - Bội số nguyên của 8, do đó ta có thể tìm được (4) có thể là một trong các số: 216, 416, 616, 816. 
Tức là, a có thể bằng 2, 4, 6, hoặc 8. Kết hợp với (1), giả sử d = 1, như vậy ta không thể tìm được số nào thoả mãn (1).
Với d = 7, ta tìm được a = 4 thoả mãn (1). 
Vậy a = 4, b = 1, c = 6, d = 7, e = 2, f = 0, g = 3, h = 8, i = 5.
Và ta có kết quả như sau:
4
1
6
7
2
0
3
8
5
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 ============================