Bài 100/2002 - Mời khách dự tiệc

Bài 100/2002 - Mời khách dự tiệc

Công ty trách nhiệm hữu hạn “Vui vẻ” có n cán bộ đánh số từ 1 đến n. Cán bộ i có đánh giá độ vui tính là vi (i = 1, 2, ..., n). Ngoại trừ Giám đốc Công ty, mỗi cán bộ có 1 thủ trưởng trực tiếp của mình.

Bạn chỉ cần giúp Công ty mời một nhóm cán bộ đến dự dạ tiệc “Vui vẻ” sao cho trong số những người được mời không đồng thời có mặt nhân viên và thủ trưởng trực tiếp và đồng thời tổng đánh giá độ vui tính của những người dự tiệc là lớn nhất.

Giả thiết rằng mỗi một thủ trưởng có không quá 20 cán bộ trực tiếp dưới quyền.

- Dòng đầu tiên ghi số cán bộ của Công ty: n (1 < n < 1001);

- Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên dương ti, vi; trong đó ti là số hiệu của thủ trưởng trực tiếp và vi là độ vui tính của cán bộ i (i = 1, 2, ..., n). Quy ước ti = 0 nếu i là số hiệu của Giám đốc Công ty.
Kết quả: Ghi ra file văn bản GUEST.OUT

- Dòng đầu tiên ghi hai số m, v; trong đó m là tổng số cán bộ được mời còn v là tổng độ vui tính của các cán bộ được mời dự tiệc;

- Dòng thứ i trong số m dòng tiếp theo ghi số hiệu của cán bộ được mời thứ i (i = 1, 2, ..., m).

Ví dụ:

GUEST.INP	GUEST.OUT
3 0 3 1 6 2 4	2 7 1 3

GUEST.INP	GUEST.OUT
7 0 1 1 1 1 12 2 50 2 1 3 1 3 1	3 63 3 4 5

(Dành cho học sinh Tiểu học)

Tổng thời gian: 17 phút

(Dành cho học sinh THCS)

Program bai2;

uses crt;

const fi = 'P2.inp';

fo = 'P2.out';

type _type=array[1..2] of integer;

mang=array[1..200] of _type;

d,v:mang;

m,n:byte;
procedure input;

var i:byte;

begin

assign(f,fi);

readln(f,n,m);

for i:=1 to n do

begin

d[i,2]:=i;

end;

readln(f);

begin

v[i,2]:=i;

end;

close(f);

var d:_type;

i,j:byte;

begin

for j:=i+1 to n do

if m[j,1]m[i,1] then

begin

m[j]:=m[i];

m[i]:=d;

end;

tong:integer;

begin

input;

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:

Inp = 'P2.INP';

Out = 'P2.OUT';

var

Val, Pos: array[1..2, 1..8000] of Integer;

procedure ReadInput;

var

hf: Text;

begin

Assign(hf, Inp);

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[2, i] := i;

end;

end;

var

begin

i := l; j := r;

repeat

while Val[t, i] < x do Inc(i);

if i <= j then

begin

Tg := Val[t, i]; Val[t, i] := Val[t, j]; Val[t, j] := Tg;

Inc(i); Dec(j);

end;

until i > j;

if j > l then QuickSort(t, l, j);

end;

procedure WriteOutput;

i: Integer;

Sum: LongInt;

hf: Text;

begin

Sum := 0;

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;

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/1999;

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;

var i,j:byte;

begin

assign(f,fi);

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]);

close(f);

new(b);

new(c);

var i,j:byte;

begin

for i:=1 to m do

begin

write(b^[i,j]);

end;
end;
procedure trans(ch:char);

var i,j,d:byte;

begin

fillchar(c^,sizeof(mang),0);

for j:=1 to n do

begin

d:=b^[i,j];

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;

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;

end;
procedure output;

var i,j:byte;

begin

rewrite(f);

for i:=1 to m do

begin

writeln(f);

end;

close(f);

begin

input;

fillchar(c^,sizeof(mang),0);

for i:=1 to t do trans(s[i]);

output;

(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:

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.

Nếu cân nghiêng < thì 4 là đđ nhẹ, nếu cân nghiêng > thì 4 là đđ nặng.

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ẹ.

Cách làm tương tự trường hợp 2.2 mô tả trong mục IV ở trên.

Hoặc đđ là nhẹ trong 1, 2, 3, 4 hoặc đđ là nặng trong 5, 6, 7, 8.

Hoặc đđ là 5 nặng, hoặc đđ là 3 nhẹ.

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.';

Var i, kq1: integer;

kq2: string;

ch: char;

(* Thủ tục Kq *)

Procedure kq(a: integer; b: string);

Begin

kq1:=a;

End;

Procedure can(lan: integer; t1, t2, t3, t4, p1, p2, p3, p4: string);

Begin

Writeln('Lần cân thứ', lan, ' :');

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;

Until (ch in ['P', 'T', 'C']);

Writeln(ch);

Writeln(*==========================================*);

End;

(* Thủ tục Play *)

Begin

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', ' ');

Begin

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}

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

Begin

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;

Else If (ch='P') then {P}

Begin

can(2, '5', '6', '1', ' ', '7', '8', '2', ' ');

Begin

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}

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

Begin

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;

Else If (ch='C') then {C}

Begin

can(2, '9', '10', '11', ' ', '1', '2', '3', ' ');

{CT}

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

Begin

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

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;

Begin

play;

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;

(Dành cho học sinh THPT)

Program Bai7;
(* Tinh so giao diem cua n duong thang ko trung nhau *)
Uses Crt;
Const
fn = 'P7.INP';
fg = 'P7.OUT';
max = 100;
exp = 0.0001;
Var
a ,b ,c : array[1..max] of real;
n : integer;
smien : 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
smien := 1;
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 : integer;x ,y : real ) : boolean;
Var
ii : integer;
Begin
Thoaman := false;
For ii := 1 to i - 1 do
If bang( Giatri( ii ,x ,y ) ,0 ) then
exit;
Thoaman := true;
End;
(*--------------------------------------------------------------------------*)
Function Cattruoc( i : integer ) : integer;
Var
ii , gt : integer;
x, y : real;
Begin
gt:= 0;
For ii := 1 to i - 1 do
If Giaodiem( i ,ii ,x ,y ) then
If Thoaman( ii ,x ,y ) then Inc( gt );
cattruoc := gt;
End;
(*--------------------------------------------------------------------------*)
Procedure Tinhslmien;
Var
i : integer;
Begin
For i := 1 to n do
Inc( smien ,cattruoc( i ) + 1 );
End;
(*--------------------------------------------------------------------------*)
Procedure GhiKQ;
Begin
Writeln(So mien mat phang duoc chia la: ' ,smien );
End;
(*--------------------------------------------------------------------------*)
BEGIN
Clrscr;
Nhap;
Chuanbi;
Tinhslmien;
GhiKQ;
END.
Bài 8/1999 - Cân táo

(Dành cho học sinh Tiểu học)

Số lần cân ít nhất là 3. Cách cân như sau:

Lần 1: Chia 27 quả táo thành 3 phần, mỗi phần 9 quả. Đặt 2 phần lên 2 đĩa cân. Nếu cân thăng bằng thì quả táo nhẹ nằm ở phần chưa cân, nếu cân lệch thì quả táo nhẹ nằm ở đĩa cân nhẹ hơn. Sau lần cân thứ nhất, ta chọn ra được 9 quả táo trong đó có quả táo nhẹ.

Lần 2: Chia 9 quả táo, chọn được ra thành 3 phần, mỗi phần 3 quả. Đặt 2 phần lên 2 đĩa cân. Nếu cân thăng bằng thì quả táo nhẹ nằm ở phần chưa cân, nếu cân lệch thì quả táo nhẹ nằm ở đĩa cân nhẹ hơn. Sau lần cân thứ 2, ta chọn ra được 3 quả táo trong đó có quả táo nhẹ.

Lần 3: Lấy 2 trong số 3 quả táo chọn đặt lên 2 đĩa cân. Nếu cân thăng bằng thì quả táo nhẹ là quả táo còn lại, nếu cân lệch thì quả táo nhẹ nằm ở đĩa cân nhẹ hơn. Sau ba lần cân ta chọn ra được quả táo nhẹ.


Bài 9/1999 - Bốc diêm

(Dành cho học sinh Tiểu học)

Nếu số lượng que diêm của mỗi dãy là: 3, 5, 8 thì hai bạn Nga và An bạn nào bốc trước sẽ thắng. Có nhiều cách để người bốc trước sẽ thắng. Giả sử:

- Dãy thứ nhất cso 8 que diêm.

- Dãy thứ hai có 5 que diêm.

- Dãy thứ hai có 3 que diêm.

Nếu Nga là người bốc trước để thắng, Nga sẽ làm như sau:

1. Bốc hết 8 que diêm ở dãy đầu tiên. Như vậy còn 2 dãy tổng cộng 8 que. An sẽ phải bốc một số que ở một trong hai dãy này.

2. Trong trường hợp sau khi An bốc số diêm chỉ còn ở trên một dãy, Nga sẽ bốc tất cả số diêm còn lại và sẽ thắng. Nếu sau khi An bốc mà số diêm vẫn còn ở trên hai dãy thì Nga cũng sẽ phải bốc sao cho đưa An vào thế bất lợi: mỗi dãy trong 2 dãy cuối cùng còn đúng một que diêm. Nếu chưa đưa An được vào thế bất lợi thì phải bốc sao cho mình không phải ở thế bất lợi. Chẳng hạn như:

- An bốc 3 que diêm ở dãy thứ 2. Nga sẽ bốc 1 que ở dãy cuối cùng.

- An bốc 1 que diêm tiếp theo cũng ở dãy đó. Nga cũng sẽ bốc 1 que ở dãy thứ 3.

- An bốc 1 que tiếp theo. Khi đó, Nga bốc que diêm cuối cùng và thắng cuộc.

Các bạn cũng có thể thử cho các trường hợp khác.
Bài 10/1999 - Dãy số nguyên

(Dành cho học sinh THCS)

Dãy đã cho là dãy các số tự nhiên viết liền nhau:

123456789 101112...99 100101102...999 100010011002...9999 10000...

9 x 1 = 9

90 x 2 = 180

900 x 3 = 2700

9000 x 4 = 36000 ...

Ta có nhận xét sau:

- Đoạn thứ 1 có 9 chữ số;

- Đoạn thứ 2 có 180 chữ số;

- Đoạn thứ 3 có 2700 chữ số;

- Đoạn thứ 4 có 36000 chữ số;

- Đoạn thứ 5 có 90000 x 5 = 450000 chữ số ...

Với k = 1000 ta có: k = 9 + 180 + 3.270 + 1.

Do đó, chữ số thứ k là chữ số đầu tiên của số 370, tức là chữ số 3.

Chương trình:

Program Bai10;

Uses crt;

Var k: longInt;

(*--------------------------------------------*)

Function chuso(NN: longInt):char;

Var st:string[10];

dem,M:longInt;

Begin

dem:=0;

Repeat

dem := dem+length(st);

inc(M);

Until dem >= NN;

(*-------------------------------------*)

BEGIN

clrscr;;

Readln(k);

Writeln('Chu so thu', k,'cua day vo han cac so nguyen khong am');

write('123456789101112... la:', chu so(k));

Readln;

END.

var n, Result: LongInt;

begin

end;
procedure Solution;

var

i, Sum, Num, Digits: LongInt;

Sum := 9; Num := 1; Digits := 1;

while Sum < n do

begin

Inc(Sum, Num * 9 * Digits);

end;

Dec(Sum, Num * 9 * Digits); Dec(n, Sum);

n := (n - 1) mod Digits + 1;

for i := 1 to Digits - n do Num := Num div 10;

Result := Num mod 10;

end;
procedure WriteOutput;

begin

Readln;

begin

Solution;

WriteOutput;

end.
Bài 11/1999 - Dãy số Fibonaci

(Dành cho học sinh THCS)

{$R+}

Inp = 'P11.INP';

Out = 'P11.OUT';

Ind = 46;

var

n: LongInt;

procedure Init;

var

i: Integer;

Fibo[1] := 1; Fibo[2] := 1;

for i := 3 to Ind do Fibo[i] := Fibo[i - 1] + Fibo[i - 2];

end;

var

hfi, hfo: Text;

begin

Assign(hfi, Inp);

Assign(hfo, Out);

Rewrite(hfo);

while not Eof(hfi) do

begin

Readln(hfi, n);

i := Ind; while Fibo[i] > n do Dec(i);

Write(hfo, Fibo[i]);

Dec(n, Fibo[i]);

while n > 0 do

begin

if n >= Fibo[i] then

begin

Write(hfo, ' + ', Fibo[i]);

end;

Writeln(hfo);

end;

Close(hfo);

end;

Init;

end.
Bài 12/1999 - N-mino

(Dành cho học sinh THPT)

Program Bai12;{Tinh va ve ra tat ca Mino}

Procedure Nhap;

Procedure Chuanbi;

Function min2( a ,b : integer ) : integer;

Procedure Taobien( i ,j : integer );

Procedure Ghinhancauhinh;

Procedure Quaytrai;

Procedure Lathinh;

Procedure Daohinh;

Function Bethat : boolean;

Function Behon : boolean;

Function Xethinhvuong : boolean;

Function Xetchunhat : boolean;

Procedure Chuyensang( a : bang;Var b : bang );

Procedure Thughinhancauhinh;

Procedure Xetthem( i ,j : integer );

Procedure Xetbot( i ,j : integer );

Procedure Themdiem( ii : integer );

Procedure Bodiem( ii : integer );

Procedure Xethangcot( ii : integer );

Procedure Xetlaihangcot( ii : integer );

Procedure Duyet( i : integer;last : integer );

Procedure Duyetcauhinh( i ,j : integer );

Procedure Duyethinhbao;

Procedure Ghicuoi;

BEGIN
Clrscr;

(Dành cho học sinh THPT)

{Recommend:m,n<5}

const m=4;n=4;max=m*n;

var

   a: array[1..m,1..n] of byte;

   f: text;

   time: longint absolute $0:$46C;

   save: longint;

{------------------------------------}

procedure init;

begin

 for i1:=1 to m do

 dem:=0; daxep:=0; tg:=0;

end;

{------------------------------------}

begin

 begin

   writeln(f);

 end;

end;

procedure try(i,j: integer);

var i2,j2,flag: integer;

begin

 else

   flag:=j;

   while (flag

   if (a[i,flag]<>0) then flag:=flag-1;

   for i2:=i to m do for j2:=j to flag do

   begin

     for i1:=i to i2 do for j1:=j to j2 do a[i1,j1]:=dem;

     daxep:=daxep+(i2-i+1)*(j2-j+1);

     i1:=i;j1:=j2;

     while (a[i1,j1]<>0) do

     begin

       j1:=j1+1;

       if j1=n+1 then begin j1:=1; i1:=i1+1; end;

     end;

     try(i1,j1);

     daxep:=daxep-(i2-i+1)*(j2-j+1);

     for i1:=i to i2 do

       for j1:=j to j2 do a[i1,j1]:=0;

     dem:=dem-1;

   end;

 end;

{------------------------------------}

BEGEN

 init;

 save:=time;

 try(1,1);

 write(f,tg);

 close(f);

 write('Time is about:',(time-save)/18.2);

 readln;

END.
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)

Để tiện tính toán, ta sẽ đánh số lại quyển sách bằng các số 001, 002, 003,..., 009, 010, 011, 012, 013,..., 098, 099, 100, 101,... tức là mỗi số ghi bằng đúng 3 chữ số. Như vậy ta phải cần thêm 9x2=18 chữ số cho các số trước đây chỉ có 1 chữ số và 90 chữ số cho các số trước đây chỉ có 2 chữ số, tổng cộng ta phải dùng thêm 108 chữ số. Với cách đánh số mới này, ta phải cần tới 1392+108=1500 chữ số. Vì mỗi số có đúng 3 chữ số nên có tất cả 1500:3=500 số, bắt đầu từ 001. Vậy quyển sách có 500 trang.

(Dành cho học sinh Tiểu học)

Để tiện tính toán, cứ mỗi một cặp bạn trai-bạn gái quen nhau ta sẽ nối lại bằng một sợi dây. Như vậy mỗi bạn sẽ bị "buộc" bởi đúng N sợi dây vì quen với N bạn khác giới. Gọi số bạn trai là T thì tính được số dây nối là TxN. Gọi số bạn gái là G thì tính được số dây nối là GxN. Nhưng vì 2 cách tính cho cùng kết quả là số dây nối nên TxN=GxN, suy ra T=G. Vậy trong hội nghị đó số các bạn trai và các bạn gái là như nhau.
Bài 16/2000 - Chia số

(Dành cho học sinh THCS)

Lập một bảng 2NxN ô. Lần lượt ghi N² số 1, 2, 3,...,  N²-1, N² vào N cột, mỗi cột N số theo cách sau:

Trong N hàng trên, tổng i số trong hàng thứ i là:

i+[N+(i-1)]+[2N+(i-2)]+...+[(i-1)N+1]

= N[1+2+...+(i-1)]+[i+(i-1)+(i-2)+...+1]

= Ni(i-1)/2+i(i+1)/2

= (Ni²-Ni+i²+i)/2

Trong N hàng dưới, tổng (N-i) số trong hàng thứ N+i là

(i+1)N+[(i+2)N-1]+[(i+3)N-2]+...+[N²-(N-i-1)]

= N[(i+1)+(i+2)+...+N]-[1+2+...+(N-i-1)]

= N(N+i+1)(N-i)/2 - (N-i-1)(N-i)/2

= (N²+Ni+i+1)(N-i)/2

= (N³+Ni+N-Ni²-i²-i)/2

Cắt đôi bảng ở chính giữa theo đường kẻ đậm và ghép lại thành một bảng vuông như sau:

Khi đó tổng các số trong hàng thứ i là

(Ni²-Ni+i²+i)/2 + (N³+Ni+N-Ni²-i²-i)/2  =  (N³+N)/2 = N(N²+1)/2

Rõ ràng trong mỗi hàng có N số và tổng các số trong mỗi hàng là như nhau.

(Dành cho học sinh THCS)

Có thể viết chương trình như sau:

Program Nttd;

Var M,N,d,i: integer;

{------------------------------------}

Function USCLN(m,n: integer): integer;

Var r: integer;

Begin

 While n<>0 do

   r:=m mod n; m:=n; n:=r;

 end;

 USCLN:=m;

{------------------------------------}

BEGIN

 Write('Nhap M,N: '); Readln(M,N);

 While d<>1 do

 begin

   If d mod i =0 then

     While d mod i=0 do d:=d div i;

     While M mod i=0 do M:=M div i;

     While N mod i=0 do N:=N div i;

   end;

   Inc(i);

 If M*N=1 then Write('M va N nguyen to tuong duong.')

 Else Write('M va N khong nguyen to tuong duong.');

 Readln;

(Dành cho học sinh THCS và THPT)

Ta có thể thấy ngay là con sên phải đi N bước (vì xi₊₁ = xi+1), và nếu đi lên k bước thì lại di xuống k bước (vì yN = y₀ = 0). Do đó, h = N div 2;

Chương trình có thể viết như sau:

Program Senbo;

Uses Crt, Graph;

Var f:Text;

gd, gm, N, W,xo,yo:Integer;

Procedure Nhap;

Begin

If N>50 Then N:=50;

End;

Procedure Veluoi;

Begin

yo:=GetMaxY-100;

xo:=(GetMaxX-W*N) Div 2-25;

For i:=0 To N Do

For j:=0 To N Div 2 Do

Begin

y:=yo-J*W;

Bar(x-1,y-1,x+1,y+1);

End;

Var i,j,xo,yo,x,y:Integer;

Sx,Sy,S:String;

Begin

Writeln(f,N:2,N Div 2:3);

SetColor(2);

OutTextXY(xo,yo+5,'(0,0)');

For i:=1 To N Do

Begin

Else If j>0 Then Dec(j);

Writeln(f,i:2,j:3);

x:=i*W+xo;y:=yo-j*W;

Line(xo,yo,x,y);

Str(i,sx);str(j,sy);

S:='('+sx+','+sy+')');

OutTextXY(x,y+5,s);

Delay(10000);

xo:=x;yo:=y;

End;

End;
Begin

Assign(F,'P5.Out');

ReWrite(F);

Dg:=Detect;

InitGraph(Gd,Gm,'');

VeLuoi;

Readln;

CloseGraph;

End.
Bài 19/2000 - Đa giác

(Dành cho học sinh THPT)

Ta sẽ chứng minh khẳng định sau cho n 3:

Các số thực dương a₁, a₂, a₃,..., an lập thành các cạnh liên tiếp của một đa giác n cạnh khi và chỉ khi với mọi k=1, 2,..., n ta có các bất đẳng thức sau:

a₁ + a₂ +... (thiếu k)... + an > ak                   (1)

(tổng của n-1 cạnh bất kỳ phải lớn hơn độ dài cạnh còn lại)

Chứng minh

Chứng minh được tiến hành qui nạp theo n. Với n = 3 thì (1) chính là bất đẳng thức tam giác quen thuộc.

Giả sử (1) đúng đến n. Xét (1) cho trường hợp n+1.

Trước tiên ta có nhận xét sau: Các số a₁, a₂,..., an, an₊₁ lập thành một đa giác n +1 cạnh khi và chỉ khi tồn tại một số g sao cho a₁, a₂, a₃,..., an_-1, g tạo thành một đa giác n cạnh và g, an, an₊₁ tạo thành một tam giác.

Giả sử a₁, a₂, a₃,..., an, an₊₁ lập thành một đa giác n +1 cạnh. Khi đó theo nhận xét trên thì tồn tại đa giác n cạnh a₁, a₂, a₃,..., an_-1, g và tam giác g, an, an₊₁. Do đó ta có các bất đẳng thức sau suy từ giả thiết qui nạp và bất đẳng thức tam giác:

a₁ + a₂ + a₃ +.... + an_-1 > g                             (2)

an + an₊₁ > g > |an - an₊₁|                                (3)

Do vậy ta có

a₁ + a₂ + a₃ +.... + an_-1 > |an - an₊₁|                 (4)

từ (4) suy ra ngay các khẳng định sau:

a₁ + a₂ + a₃ +.... + an_-1 + an > an₊₁                    (5)

a₁ + a₂ + a₃ +.... + an_-1 + an₊₁ > an                    (6)

Mặt khác từ giả thiết qui nạp cho đa giác n cạnh a₁, a₂, a₃,..., an_-1, g, tương tự như (2) ta có các bất đẳng thức sau với k < n:

a₁ + a₂ +... (thiếu k)... + an_-1 + g > ak

thay thế vế trái của (3) ta phải có với k

a₁ + a₂ +... (thiếu k)... + an_-1 + an + an₊₁ > ak    (7)

Các bất đẳng thức (5), (6) và (7) chính là (1). Điều kiện cần được chứng minh.

Giả sử ngược lại, hệ bất đẳng thức (1) thoả mãn, ta có

a₁ + a₂ +... + an_-1 + an > an₊₁                            (8)

a₁ + a₂ +... + an_-1 + an₊₁ > an                            (9)

và với mọi k < n ta có:

a₁ + a₂ +...(thiếu k)... + an_-1 + an + an₊₁ > ak     (10)

Từ (8) và (9) ta có ngay:

a₁ + a₂ +... + an_-1 > |an - an₊₁|                            (11)

Từ (10) suy ra với mọi k < n ta có:

an + an₊₁ > ak - a₁ - a₂ -...(thiếu k)... - ak           (12)

Từ các bất đẳng thức (11) và (12) suy ra tồn tại một số dương g thỏa mãn đồng thời các điều kiện sau:

an + an₊₁ > g > |an - an₊₁|                                (13)

a₁ + a₂ +... + an_-1 > g                                       (14)

g > ak - a₁ - a₂ -...(thiếu k)... - ak                     (15)

Các bất đẳng thức (13), (14) và (15) chính là điều kiện để tồn tại đa giác n cạnh a₁, a₂, a₃,..., an_-1, g và tam giác g, an, an₊₁. Điều kiện đủ đã được chứng minh.

Program Dagiac;

Uses Crt;

Const fn = 'P6.INP';

Var i,j,N: integer;

    a: array[1..100] of real;

    s: real;

    Kq: boolean;

{------------------------------------}

Procedure Nhap;

Var f: text;

Begin

 Readln(f,N);

 For i:=1 to N do Read(f,a[i]);

 Close(f);

End;

{------------------------------------}

 Nhap;

 For i:=1 to N do

 begin

   s:=0;

   If s<=a[i] then Kq:=false;

 end;

 If Kq then Write('Co.') Else Write('Khong.');

END.
Bài 20/2000 - Bạn Lan ở căn hộ số mấy?

(Dành cho học sinh Tiểu học)

Ta coi như các căn hộ được đánh số từ 1 đến 64 (vì ngôi nhà có 8 tầng, mỗi tầng có 8 căn hộ). Ta có thể hỏi như sau:

- Có phải số nhà bạn lớn hơn 32?

Sau khi Lan trả lời, dù "đúng" hay "không" ta cũng biết chính xác căn hộ của Lan ở trong số 32 căn hộ nào. Giả sử câu trả lời là "không" ta cũng biết chính xác căn hộ của Lan ở trong số 32 căn hộ nào. Giả sử câu trả lời là "không", ta hỏi tiếp:

-  Có phải số nhà bạn lớn hơn 16?

Sau câu hỏi này ta biết được 16 căn hộ trong đó có căn hộ Lan đang ở. 

Tiếp tục hỏi như vậy đối với số đứng giữa trong các số còn lại. Sau mỗi câu trả lời khoảng cách giữa các số giảm đi một nửa. Cứ như vậy, chỉ cần 6 câu hỏi, ta sẽ biết được căn hộ Lan ở.
Bài 21/2000 - Những trang sách bị rơi

(Dành cho học sinh Tiểu học)

Nếu trang bị rơi đầu tiên đánh số 387 thì trang cuối cùng sẽ phải đánh số lớn hơn và phải là số chẵn. Do vậy trang cuối cùng phải là 738.

Như vậy, có 738 - 378 + 1= 352 trang sách (176 tờ ) bị   rơi.

(Dành cho học sinh THCS)

a) Có tất cả 8 đường đi từ A đến B sao cho mỗi đường đi qua một đỉnh nào đó chỉ đúng một lần. Cụ thể:

A B

A E F B

A E F C B

A E D C B

A E F D C B

A E D F C B

b). Có tất cả 8 đường đi từ A đến D, sao cho đường đi đó qua mội cạnh nào đó chỉ đúng một lần, cụ thể:

A B C D

A B E D

A B F D

A E D

A E B F D

A E B C D

A E F D

A E F C D

c). Các đường đi qua tất cả các cạnh của hình, qua mỗi cạnh đúng một lần (điểm bắt đầu và điểm kết thúc trùng nhau):

-
+ Các đường đi qua tất cả các cạnh của hình, qua mỗi cạnh đúng một lần (điểm bắt đầu và điểm kết thúc không trùng nhau):

- Điểm bắt đầu là C và điểm kết thúc là D:

CFBCDFEBAED

CFBCDFEABED

CDFCBFEBAED

....

Tương tự như thế với điểm bắt đầu là D và điểm kết thúc là C ta cũng tìm được các đường thoả mãn tính chất này.

Bài 23/2000 - Quay Rubic

(Dành cho học sinh THPT)

Khai triển mặt rubic và đánh số các mặt như hình vẽ sau:

Khi đó ta có thể xây dựng thủ tục Quay (mặt thứ i) để đổi màu 8 mặt con của mặt này và 12 mặt con kề với mặt này. Trên cơ sở đó giải được 2 bài toán này. Chương trình có thể viết như sau:

Program Rubic;

uses Crt;

Type  Arr= array[0..5, 0..7] of byte;

const color: Array [0..5] of char=('F', 'U','R', 'B', 'L', 'D');

Var

A1, A2, A0, A: Arr;

        X, X1, X2: String;

        k: byte;

Procedure Nhap;

Var   i, j: byte;

Begin

       Clrscr;

       Writeln ('Bai toan 1. So sanh hai xau:');

       Writeln ('Nhap xau X1:');

       Readln (X1);

       Writeln (' Nhap xau X2:');

       Readln (X2);

       Writeln ('Bai toan 2. Tinh so lan xoay:');

       Write ('Nhap xau X:');

       Readln (X);

      For i:= 0 to 5 do

          For j:= 0 to 7 do A[i, j]:= i; 

       A:=A0; A1:=A0; A2:=A0;

End;

Procedure Quay (Var A: Arr; k: byte);

Const Dir : array

[0.. 5, 0.. 3, 0.. 3] of byte = ( ( (1,2,5,4), (6,0,2,4), (5,7,1,3), (4,6,0,2) ),

( (0,4,3,2), (0,0,4,0), (1,1,5,1), (2,2,6,2) ),

( (0,1,3,5), (4,4,4,4), (3,3,3,3), (2,2,2,2) ),

( (1,4,5,2), (2,0,6,4), (1,7,5,3), (0,6,4,2) ),

( (0,5,3,1), (0,0,0,0), (7,7,7,7),(6,6,6,6) ),

( (0,2,3,4), (6,6,2,6), (5,5,1,5), (4,4,0,4) ) );

var i,j,tg: byte;

Begin

tg:=A[k,6];

for i:=3 downto 1 do A[k,0] := A[k,2*i-2];

A[k,0]:=tg;

tg:=A[k,7];

for i:=3 downto 1 do A[k,2*i] := A[k,2*i -2];

A[k,1]:=tg;

for i:=1 to 3 do

begin

tg:=A[dir[k,0,3], Dir[k,i,3];

for j:=3 downto 1 do A[ dir[k,0,j], Dir[k,i,j] ]:= A[ dir[k,0,j-1], Dir[k,i,j-1] ];

A[ [dir[k,0,0], Dir[k,i,0] ]:=tg;

end;

End;

Function Eq(A,B:Arr):Boolean;

Var i,j,c:byte;

Begin

c:=0;

for i:=1 to 5 do

for j:=1 to 7 do

If A[i,j] <> B[i,j] then inc(c);

If c=0 then Eq:=true else Eq:=false;

End;

Procedure QuayXau(x:string; var A: arr);

Var i,j:byte;

Begin

for i:=1 to length(X) do

begin

for j:= 1 to 5 do

If Color[j] = X[i] then Quay(A,j);

end;

End;

Procedure Bai1;

Begin

QuayXau(X1,A1);

QuayXau(X2,A2);

End;

Procedure Bai2;

Begin

k:=0;

Repeat

QuayXau(X,A);

Inc(k);

Until Eq(A,A0);

End;

Procedure Xuat;

Var i,j:byte;

Begin

writeln;

writeln('Ket qua:');

writeln('Bai toan 1. So sanh 2 xau:') ;

If Eq(A1,A2) then writeln('Hai xau X1 va X2 cho cung mot ket qua.');

writeln('Can ap dung xau X ',k,' lan de Rubic quay ve trang thai ban dau.');

Readln;

End;

Begin

Nhap;

Bai1;

Bai2;

Xuat;

END.

Каталог: img -> file
file -> BỘ giáo dục và ĐÀo tạO
file -> NGÂn hàng nhà NƯỚc việt nam
file -> Bé Gi¸o dôc vµ ®µo t¹o Hå s¬ data\1101. Dbf danh s¸ch §¨ng ký XÐt tuyón n¡M 2014
file -> TRƯỜng đẠi học kinh tế tp. Hcm cộng hòa xã HỘi chủ nghĩa việt nam
file -> Mẫu số 3D/GDĐT-156
file -> TRƯỜng đh kiến trúc tp. HỒ chí minh phòng đÀo tạO&ctsv cộng hòa xã HỘi chủ nghĩa việt nam
file -> THÔng báo v/v Ghi danh học lại, học cải thiện và thời gian đăng ký học phần
file -> PHÒng đÀo tạo số: 723 /đt 2014
file -> ĐỘng trong tháng 10 thư ngỏ
file -> QuyếT ĐỊnh về việc ban hành Chương trình cải cách hành chính

tải về 1.1 Mb.

Chia sẻ với bạn bè của bạn: