Lời giải 100 đề tin học và nhà trường

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "Lời giải 100 đề tin học và nhà trường": http://123doc.vn/document/550341-loi-giai-100-de-tin-hoc-va-nha-truong.htm

if m[j,1]m[i,1] then
begin
d:=m[j];
m[j]:=m[i];
m[i]:=d;
end;
end;
var i:byte;
tong:integer;
begin
input;
sapxeptang(d,n);
sapxeptang(v,m);
tong:=0;
for i:=1 to n do tong:=tong+v[n-i+1,1]*d[i,1];
for i:=1 to n do v[i,1]:=d[n-i+1,2];
xapxeptang(v,n);
assign(f,fo);
rewrite(f);
writeln(f,tong);
for i:=1 to n do writeln(f,v[i,2]);
close(f);
end.
Nhận xét: Chương trình trên sẽ chạy chậm nếu chúng ta mở rộng bài toán (chẳng hạn n <= m <=
8000). Sau đây là cách giải khác:
const
Inp = 'P2.INP';
Out = 'P2.OUT';
var
n, m: Integer;
Val, Pos: array[1 2, 1 8000] of Integer;
procedure ReadInput;
var
i: Integer;
hf: Text;
begin
Assign(hf, Inp);
Reset(hf);
Readln(hf, n, m);
for i := 1 to n do Read(hf, Val[1, i]);
Readln(hf);
for i := 1 to m do Read(hf, Val[2, i]);
Close(hf);
for i := 1 to m do
begin
Pos[1, i] := i;
Pos[2, i] := i;
end;
end;
procedure QuickSort(t, l, r: Integer);
var
x, tg, i, j: Integer;
begin
x := Val[t, (l + r) div 2];
i := l; j := r;
repeat
while Val[t, i] < x do Inc(i);
while Val[t, j] > x do Dec(j);
if i <= j then
begin
Tg := Val[t, i]; Val[t, i] := Val[t, j]; Val[t, j] := Tg;
Tg := Pos[t, i]; Pos[t, i] := Pos[t, j]; Pos[t, j] := Tg;
Inc(i); Dec(j);
end;
until i > j;
if i < r then QuickSort(t, i, r);
if j > l then QuickSort(t, l, j);
end;
procedure WriteOutput;
var
i: Integer;
Sum: LongInt;
hf: Text;
begin
Sum := 0;
for i := 1 to n do Inc(Sum, Val[1, n - i + 1] * Val[2, i]);
for i := 1 to n do Val[1, Pos[1, n - i + 1]] := Pos[2, i];
Assign(hf, Out);
Rewrite(hf);
Writeln(hf, Sum);
for i := 1 to n do Writeln(hf, Val[1, i]);
Close(hf);
end;
begin
ReadInput;
QuickSort(1, 1, n);
QuickSort(2, 1, m);
WriteOutput;
end.
Bài 3/1999 - Mạng tế bào
(Dành cho học sinh THPT)
Program Bai3;
uses crt;
const fi = 'P3.inp';
fo = 'P3.out';
type mang=array[0 201,0 201] of byte;
var m,n,t:byte;
s:string;
a:mang;
f:text;
b,c:^mang;
procedure input;
var i,j:byte;
begin
assign(f,fi);
reset(f);
readln(f,m,n,t);
readln(f,s);
for i:=1 to m do
begin
for j:=1 to n do read(f,a[i,j]);
end;
close(f);
new(b);
new(c);
end;
procedure hien;
var i,j:byte;
begin
for i:=1 to m do
for j:=1 to n do
begin
gotoxy(j*2,i);
write(b^[i,j]);
end;
end;
procedure trans(ch:char);
var i,j,d:byte;
begin
fillchar(c^,sizeof(mang),0);
for i:=1 to m do
for j:=1 to n do
begin
d:=b^[i,j];
case a[i,j] of
1:inc(c^[i,j-1],d);
2:inc(c^[i,j+1],d);
3:inc(c^[i-1,j],d);
4:inc(c^[i+1,j],d);
5:begin inc(c^[i-1,j],d);inc(c^[i+1,j],d); end;
6:begin inc(c^[i,j-1],d);inc(c^[i,j+1],d); end;
7:begin inc(c^[i,j-1],d);inc(c^[i-1,j],d); end;
8:begin inc(c^[i,j+1],d);inc(c^[i+1,j],d); end;
end;
end;
if ch<>'X' then b^[1,1]:=ord(ch)-48;
for i:=1 to m do
for j:=1 to n do
if (i<>1) or (j<>1) then b^[i,j]:=byte(c^[i,j]<>0);
hien;
readln;
end;
procedure output;
var i,j:byte;
begin
assign(f,fo);
rewrite(f);
for i:=1 to m do
begin
for j:=1 to n do write(f,' ',b^[i,j]);
writeln(f);
end;
close(f);
end;
var i:byte;
begin
clrscr;
input;
fillchar(b^,sizeof(mang),0);
fillchar(c^,sizeof(mang),0);
for i:=1 to t do trans(s[i]);
output;
end.
Bài 4/1999 - Trò chơi bốc sỏi
(Dành cho học sinh Tiểu học)
Huy sẽ là người thắng cuộc. Thật vậy số sỏi ban đầu là 101 là một số có dạng 5k+1, nghĩa là số
nếu chia 5 sẽ còn dư 1. Hoàng phải bốc trước, do số sỏi của Hoàng phải lấy là từ 1 đến 4 do đó sau
lượt đi đầu tiên, số sỏi còn lại sẽ lớn hơn 96. Huy sẽ bốc tiếp theo sao cho số sỏi còn lại phải là 96,
nghĩa là số dạng 5k+1. Tương tự như vậy, Huy luôn luôn chủ động được để sau lần bốc của mình
số sỏi còn lại là 5k+1. Lần cuối cùng số sỏi còn lại chỉ là 1 và Hoàng bắt buộc phải bốc viên cuối
cùng và thua.
Bài toán tổng quát: có thể cho số viên bi là 5k+1 viên.
Bài 5/1999 - 12 viên bi
(Dành cho học sinh THCS)
Ta sẽ chỉ ra rằng tồn tại 3 lần cân để chỉ ra được viên bi đặc biệt đó.
Gọi các viên bi này lần lượt là 1, 2, , 12. Trong khi mô tả thuật toán ta dùng ký hiệu
để mô tả quả hòn bi thứ n
để mô tả một hòn bi bất kỳ
Mô tả một phép cân.
Ta gọi viên bi có trọng lượng khác là đđ.
I. Lần cân thứ nhất. Lấy ra 8 hòn bi bất kỳ và chia làm 2 phần để cân:
Có 2 trường hợp xảy ra:
1.1. Cân trên cân bằng. Suy ra viên bi đđ (không rõ nặng nhẹ) nằm trong 4 viên bi còn lại (không
mang ra cân)
1.2. Cân trên không cân bằng.
1.2.1. Nếu (1) nhẹ hơn (2) suy ra hoặc đđ là nhẹ nằm trong (1) hoặc đđ là nặng nằm trong (2).
1.2.2. Nếu (1) nặng hơn (2) suy ra hoặc đđ là nặng nằm trong (1) hoặc đđ là nhẹ nằm trong (2).
Dễ thấy các trường hợp 1.2.1. và 1.2.2. là tương tự nhau.
Trong mọi trường hợp ta có kết luận đđ nằm trong số 8 viên hoặc nhẹ trong 4 hoặc nặng trong 4
còn lại.
II. Xét trường hợp 1.1: Tìm được 4 viên bi chứa đđ
Gọi các hòn bi này là 1, 2, 3, 4
Lần cân thứ hai:
Xét các trường hợp sau:
2.1. Cân thăng bằng. Kết luận: viên bi 4 chính là đđ.
2.2. Trường hợp cân trái nhẹ hơn phải (dấu <). Suy ra hoặc 3 là đđ nặng, hoặc 1 hoặc 2 là đđ nhẹ.
2.3. Trường hợp cân trái nặng hơn phải (dấu >). Suy ra hoặc 3 là đđ nhẹ, hoặc 1 hoặc 2 là đđ nặng.
Dễ thấy rằng các trường hợp 2.2. và 2.3. là tương tự nhau.
III. Xét trường hợp 2.1: viên bi 4 chính là đđ
Lần cân thứ ba:
Nếu cân nghiêng < thì 4 là đđ nhẹ, nếu cân nghiêng > thì 4 là đđ nặng.
IV. Xét trường hợp 2.2. Hoặc 3 là đđ nặng, hoặc 1 hoặc 2 là đđ nhẹ.
Lần cân thứ ba:
Nếu cân thăng bằng thì ta có 1 là hòn bi đđ nhẹ.
Nếu cân nghiêng > thì ta có 3 là hòn bi đđ nặng.
Nếu cân nghiêng < thì ta có 2 là hòn bi nhẹ.
V. Xét trường hợp 2.3. Hoặc 3 là đđ nhẹ, hoặc 1 hoặc 2 là đđ nặng.
Cách làm tương tự trường hợp 2.2 mô tả trong mục IV ở trên.
VI. Xét trường hợp 1.2.1.
Hoặc đđ là nhẹ trong 1, 2, 3, 4 hoặc đđ là nặng trong 5, 6, 7, 8.
Lần cân thứ hai:
6.1. Trường hợp cân thăng bằng. Suy ra đđ sẽ phải nằm trong 4, 7, 8, và do đó theo giả thiết của
trường hợp này ta có hoặc đđ là 4 nhẹ, hoặc đđ là nặng trong 7, 8. Dễ nhận thấy trường hợp này
hoàn toàn tương tự như 2.2. Bước tiếp theo làm tương tự như mô tả trong IV.
6.2. Trường hợp cân nghiêng <, suy ra hoặc đđ là nhẹ rơi vào 1, 2 hoặc đđ là 6 nặng. Trường hợp
này cũng hoàn toàn tương tự như 2.2. Bước tiếp theo làm tương tự như mô tả trong IV.
6.3. Trường hợp cân nghiêng >, suy ra hoặc đđ là 5 nặng, hoặc đđ là nhẹ 3.
VII. Xét trường hợp 6.3.
Hoặc đđ là 5 nặng, hoặc đđ là 3 nhẹ.
Lần cân thứ ba:
Nếu cân thăng bằng, suy ra 5 là đđ nặng.
Nếu cân nghiêng < suy ra 3 là đđ nhẹ.
Tất cả các trường hợp của bài toán đã được xem xét.
Sau đây là chương trình chi tiết.
Program bai5;
Uses crt;
Const
st1=' nang hon.';
st2=' nhe hon.';
Var i, kq1: integer;
kq2: string;
ch: char;
(* Thủ tục Kq *)
Procedure kq(a: integer; b: string);
Begin
kq1:=a;
kq2:=b;
End;
(* Thủ tục Cân *)
Procedure can(lan: integer; t1, t2, t3, t4, p1, p2, p3, p4: string);
Begin
Writeln('Lần cân thứ', lan, ' :');
Writeln;
Writeln(' ', t1, ' ', t2, ' ', t3, ' ', t4, ' ', p1, ' ', p2, ' ', p3, ' ', p4);
Writeln;
Write(' Bên nào nặng hơn? Trái(t)/Phải(p)/ Hay cân bằng(c)');
Repeat
ch:=readkey;
ch:=upcase(ch);
Until (ch in ['P', 'T', 'C']);
Writeln(ch);
Writeln(*==========================================*);
End;
(* Thủ tục Play *)
Procedure play;
Begin
Writeln('Có 12 quả cân: 1 2 3 4 5 6 7 8 9 10 11 12');
Writeln('Cho phép bạn chọn ra một quả cân nặng hơn hay nhẹ hơn những quả khác.');
can(1, '1', '2', '3', '4', '5', '6', '7', '8');
If (ch='T') then {T}
Begin
can(2, '1', '2', '5', ' ', '3', '4', '6', ' ');
If (ch='T') then {TT}
Begin
can(3, '1', '6', ' ', ' ', '7', '8', ' ', ' ');
If ch='T' then kq(1, st1); {TTT}
If ch='P' then kq(6, st2); {TTP}
If ch='C' then kq(2, st1); {TTC}
End
Else If (ch='P') then {TP}
Begin
can(3, '3', '5', ' ', ' ', '7', '8', ' ', ' ');
If ch='T' then kq(3, st1); {TPT}
If ch='P' then kq(5, st2); {TPP}
If ch='C' then kq(4, st1); {TPC}
End
Else If (ch='C') then {TC}
Begin
can(3, '7', ' ', ' ', ' ', ' ', '8', ' ', ' ');
If ch='T' then kq(8, st2); {TCT}
If ch='P' then kq(7, st2); {TCP}
If ch='C' then
Begin
Writeln('Trả lời sai!'); kq2:=st2;
End;
End;
End
Else If (ch='P') then {P}
Begin
can(2, '5', '6', '1', ' ', '7', '8', '2', ' ');
If (ch='T') then {PT}
Begin
can(3, '5', '2', ' ', ' ', '3', '4', ' ', ' ');
If ch='T' then kq(5, st1);
If ch='P' then kq(2, st2);
If ch='C' then kq(6, st1);
End
Else If (ch='P') then {PP}
Begin
can(3, '7', '1', ' ', ' ', '3', '4', ' ', ' ');
If ch='T' then kq(7, st1);
If ch='P' then kq(1, st2);
If ch='C' then kq(8, st1);
End
Else If (ch='C') then {PC}
Begin
can(3, '3', ' ', ' ', ' ', ' ', '4', ' ', '');
If ch='T' then kq(4, st2);
If ch='P' then kq(3, st2);
If ch='C' then
Begin
Writeln('Trả lời sai !'); kq2:=st2;
End;
End;
End
Else If (ch='C') then {C}
Begin
can(2, '9', '10', '11', ' ', '1', '2', '3', ' ');
If (ch='T') then
{CT}
Begin
can(3, '9', ' ', ' ', ' ', '10', ' ', ' ', ' ');
If (ch='T') then kq(9, st1);
If (ch='P') then kq(10, st1);
If (ch='C') then kq(11, st1);
End
Else If (ch='P') then {CP}
Begin
can(3, '9', ' ', ' ', ' ', '10', ' ', ' ', ' ');
If (ch='T') then kq(10, st2);
If (ch='P') then kq(9, st2);
If (ch='C') then kq(11, st2); End
Else If (ch='C') then {CC}
Begin
can(3, '12', ' ', ' ', ' ', '1', ' ', ' ', ' ');
If (ch='T') then kq(12, st1);
If (ch='P') then kq(12, st2);
If (ch='C') then Writeln('Trả lời sai!');
kq1:=12;
End;
End;
End;
(* Chương trình chính*)
Begin
Clrscr;
play;
Writeln(' Quả thứ', kq1, kq2);
Writeln(' Nhấn Enter kết thúc ');
Readln;
End.
Bài 6/1999 - Giao điểm các đường thẳng
(Dành cho học sinh THPT)
Program Bai6;
(* Tinh so giao diem cua n duong thang 0 trung nhau *)
Uses Crt;
Const
fn = 'P6.INP';
fg = 'P6.OUT';
max = 100;
exp = 0.0001;
Var
a ,b ,c : array[1 max] of real;
n : integer;
sgd : integer;
Procedure Nhap;
Var
f: text;
i: integer;
Begin
Assign( f ,fn ); Reset( f );
Readln( f ,n );
For i := 1 to n do
Readln( f ,a[i] ,b[i] ,c[i] ); { ax + by = c }
Close( f );
End;
(* *)
Procedure Chuanbi;
Begin
sgd := 0;
End;
(* *)
Function Giaodiem( i ,j : integer;Var x ,y : real ) : boolean;
Var
d ,dx ,
dy : real;
Begin
d := a[i] * b[j] - a[j] * b[i];
dx := c[i] * b[j] - c[j] * b[i];
dy := a[i] * c[j] - a[j] * c[i];
If d <> 0 then
begin
x := dx / d;
y := dy / d;
end;
giaodiem := d <> 0;
End;
(* *)
Function Giatri( i : integer;x ,y : real ) : real;
Begin
Giatri := a[i] * x + b[i] * y - c[i];
End;
(* *)
Function bang( a ,b : real ) : boolean;
Begin
bang := abs( a - b ) <= exp;
End;
(* *)
Function Thoaman( i ,j : integer;x ,y : real ) : boolean;
Var
ii: integer;
Begin
Thoaman := false;
For ii := 1 to i - 1 do
If (ii <> j) and bang( giatri( ii ,x ,y ) ,0 ) then
exit;
Thoaman := true;
End;
(* *)
Function Catrieng( i : integer ) : integer;
Var
ii , gt:integer;
x, y : real;
Begin
gt := 0;
For ii := 1 to i do
If giaodiem( i ,ii ,x ,y ) then
If thoaman( i ,ii ,x ,y ) then Inc( gt );
catrieng := gt;
End;
(* *)
Procedure Tinhsl;
Var
i : integer;
Begin
For i := 1 to n do
Inc( sgd ,catrieng( i ) );
End;
(* *)