ĐỀ THI HỌC SINH GIỎI TRƯỜNG
MÔN: TIN HỌC 9
ĐỀ SỐ 1
Thời gian: 120 phút
Bài 1. Số bền
Năm 1973, nhà Toán học Neil Sloan đưa ra khái niệm độ bền của một số nguyên không
âm N như sau:
Nếu N có một chữ số thì độ bền của N bằng 0.
Nếu N có từ 2 chữ số trở lên thì độ bền của N bằng độ bền của số nguyên là tích
các chữ số của N cộng 1.
Cho N, tính độ bền của N.
Dữ liệu vào từ file văn bản: persist.inp
Dòng 1: Số nguyên N (0 ≤ N ≤ 2.000.000.000).
Kết quả ghi ra file văn bản: persist.out
Dòng 1: Số nguyên là độ bền của N.
Ví dụ
persist.inp
99
persist.out
2
Giải thích
Doben(99)=Doben(81)+1=Doben(8)+1+1=0+1+1=2
Bài 2. Đổi giày
Bờm là chủ một cửa hiệu bán giày. Một ngày nọ, Bờm kiểm tra kho và thấy trong kho
còn lại 2*N chiếc giày, trong đó có N chiếc giày chân trái với kích thước lần lượt là a 1, a2,
…, aN, N chiếc giày chân phải với kích thước lần lượt là b 1, b2, …, bN. Hai chiếc giày chỉ
có thể hợp thành một đôi nếu chúng là một cặp trái - phải có cùng kích thước. Bờm quyết
định mang một số giày đến nhà sản xuất để đổi.
Hãy xác định giúp Bờm số ít nhất các chiếc giày cần đổi nếu cậu ta muốn cửa hiệu của
mình có thể bán được N đôi giày.
Dữ liệu vào từ file văn bản: shoes.inp
1
Dòng 1: Số nguyên N (1 ≤ N ≤ 100).
Dòng 2: N số nguyên a1, a2, …, aN (1 ≤ ai ≤ 1000, i = 1, 2,…, N).
Dòng 3: N số nguyên b1, b2, …, bN (1 ≤ bi ≤ 1000, i = 1, 2,…, N).
Kết quả ghi ra file văn bản: shoes.out
Dòng 1: Số nguyên là số giày ít nhất cần đổi.
Ví dụ
shoes.inp
shoes.out
3
1
131
Giải thích
Đổi 1 chiếc giày chân trái kích thước 1 thành giày chân
trái kích thước 2 hoặc đổi 1 chiếc giày chân phải kích
thước 2 thành giày chân phải kích thước 1.
321
Bài 3. Đối xứng
Một số nguyên gọi là số đối xứng nếu viết dạng biểu diễn thập phân của số đó theo
chiều ngược lại vẫn thu được chính số đó. Cho số nguyên dương N có không quá 100 chữ
số. Hãy xác định số nguyên đối xứng nhỏ nhất lớn hơn N.
Dữ liệu vào từ file văn bản: nextpal.inp
Dòng 1: Số nguyên N
Kết quả ghi ra file văn bản: nextpal.out
Dòng 1: Số nguyên kết quả
Ví dụ
nextpal.inp
Nextpal.out
99
101
Hướng dẫn giải
Câu 1: Tư tưởng giải thuật:
2
- Xây dựng hàm tính tích các chữ số của N
- Khi nào N>9 thì tăng d, đồng thời gán N:=tich(N);
- Ra ngoài in ra d (chính là độ bền của N)
Bài giải:
Var f,g:text;
d,n:longint;
Function tich(x:longint):longint;
Var s,a:longint;
Begin
s:=1;
repeat
a:=x mod 10;
x:=x div 10;
s:=s*a;
until x=0;
tich:=s;
End;
BEGIN
Assign(f,'persist.inp'); Reset(f);
Assign(g,'persist.out'); Rewrite(g);
Read(f,n);
d:=0;
While n>9 do
begin
3
inc(d);
n:=tich(n);
end;
Write(g,d);
Close(g);
Close(f);
END.
Câu 2:
Tư tưởng thuật giải:
- Xét lần lượt từng chiếc dày bên trái.
- Tìm chiếc dày đầu tiên bên phải trùng với chiếc dày bên trài đang xét, nếu có trùng
thì đánh dầu chiếc dày đó, còn không có trùng thì xét chiéu tiếp theo.
- Đếm số chiếc dày chưa đánh dấu bên phải chính là số dày phải đem đi đổi.
Bài giải:
Var f,g:text;
n,j,i,d:longint;
a,b:array [1..1000] of longint;
4
ĐỀ THI HỌC SINH GIỎI TỈNH
MÔN: TIN HỌC 9
ĐỀ SỐ 3
Thời gian: 120 phút
Bài 1: (6điểm). PHẦN TỬ YÊN NGỰA
Cho mảng hai chiều có kích thước MxN số nguyên. Phần tử A[I,j] được gọi là phần tử
yên ngựa nếu nó là phần tử nhỏ nhất trong hàng I đồng thời là phần tử lớn nhất trong cột
j.
Em hãy lập chương trình tìm phân tử yên ngựa của mảng A.
Dữ liệu vào: Cho file PTYN.INP gồm
- Dòng đầu tiên gồm hai số M,N ( 0 M; N
100)
- M dòng tiếp theo, mỗi dòng gồm có N số nguyên của mảng A.
(các giá trị cách nhau ít nhất 1 khoảng cách).
Dữ liệu ra: Ghi file PTYN.OUT vị trí của các phân tử yên ngựa (nếu có) hoặc dòng
thông báo “Không có phần tử yên ngựa”.
Ví dụ:
PTYN.INP
PTYN.OUT
33
(2,2)
15
3
9
55
4
6
76
1
2
5
Hoặc
PTYN.INP
PTYN.OUT
33
Khong co phantu yen ngua
15
10 5
55
4
6
76
1
2
Bài 2: (7 điểm). TỔNG CÁC SỐ FIBONACI
Dãy Fibonaci là dãy gồm các số: 1; 1; 2; 3; 5; 8; … được xác định bởi công thức sau:
F1=1; F2=1; Fi=Fi-1+Fi-2 với i>2
Em hãy biểu diễn một số tự nhiên tành tổng ít nhất các số Fibonaci khác nhau.
Dữ liệu vào: Cho file FIBO.INP chứa số N (N 2000000000)
Dữ liệu ra: ghi vào file FIBO.OUT biễu diễn số N thành tổng ít nhất các số Fibonaci
khác nhau.
Ví dụ.
FIBO.INP
129
FIBO.OUT
129=89+34+5+1
Hoặc
FIBO.INP
8
FIBO.OUT
8=8
6
Bài 3. (7 điểm) CHỌN PHẦNTHƯỞNG
Trong kỳ thi học sinh giỏi môn tin học, em là người đạt giải đặc biệt. Ban tổ chức cho
phép em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy dược
đánh dấu từ số 1 đấn số N (0 N 10000), phần thưởng thứ I có giáo trị là ai (1 ai 100).
Em được phép chọn các phần thưởng cho mình theo nguyên tắc không chọn 3 phần
thưởng liên tiếp nhau trong dãy.
Viết chương trình để máy tính hướng dẫn em chọn các phần thưởng sao cho tổng giá trị
các phần thưởng nhận được là lớn nhất.
Dữ liệu vào: cho file PTHUONG.INP gồm các dòng:
- Dòng đầu tiên là số phần thưởng N
- N dòng tiếp theo là giá trị của các phần thương.
Dữ liệu ra: ghi vào file PTHUONG.OUT gồm các dòng:
- Dòng đầu tiên ghi tổng giá trị lớn nhất của phần thưởng đã chọn.
- Dòng tiếp theo ghi vị trí của các phần thưởng đã chọn theo thứ tự tăng dần.
Ví dụ:
PTHUONG.INP PTHUONG.OUT
5
23
6
1245
9
1
3
7
5
Hoặc
PTHUONG.INP PTHUONG.OUT
7
32
6
12467
9
1
3
5
10
4
8
Đáp án
Bài 1: (6điểm). PHẦN TỬ YÊN NGỰA
program yenngua;
uses crt;
type
mang=array[1..100,1..100] of integer;
var
a:mang;
n,i,j,d:integer;
f:text;
procedure nhap;
var
i,j:integer;
begin
assign(f,'PTYN.inp');
reset(f);
readln(f,n);
for i:=1 to n do
begin
9
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
end;
function maxc(h:integer):integer;
var
max, i:integer;
begin
max:=a[1,h];
for i:=1 to n do if max
a[h,i] then min:=a[h,i];
minh:=min;
end;
begin
clrscr;
nhap;
d:=0;
10
for i:=1 to n do
for j:=1 to n do
if ((a[i,j]=minh(i)) and (a[i,j]=maxc(j))) then d:=d+1;
assign(f,'PTYN.out');
rewrite(f);
for i:=1 to n do
for j:=1 to n do
if ((a[i,j]=minh(i)) and (a[i,j]=maxc(j))) then writeln(f,'(',i, ',',j,')');
if d=0 then write(f,'Khong co phan tu yen ngua');
close(f);
end.
Bài 2: (7 điểm). TỔNG CÁC SỐ FIBONACI
Program TongFIBONACi;
uses crt;
var
i,j,n,m:longint;
f:text;
function fi(h:integer):longint;
var
i:integer;
x,y,tg:longint;
begin
11
if (h=1) or (h=2) then fi:=1
else
begin
x:=1; y:=1;
for i:=1 to h do
begin
tg:=x;
x:=y;
y:=y+tg;
end;
fi:=y;
end;
end;
function vt(so:longint):integer;
var
i:integer;
begin
i:=1;
while fi(i)< so do i:=i+1;
if fi(i)= so then vt:=i
else vt:=i-1;
end;
procedure doc;
begin
12
assign(f,'FIBO.INP');
reset(f);
read(f,n);
close(f);
end;
begin
doc;
assign(f,'FIBO.OUT');
rewrite(f);
write(f,n,'=');
write(f,fi(vt(n)));
n:=n-fi(vt(n));
while n<>0 do
begin
m:=fi(vt(n));
n:= n-fi(vt(n));
write(f,'+',m );
end;
close(f);
end.
Bài 3. (7 điểm) CHỌN PHẦNTHƯỞNG
program phan_thuong;
uses crt;
13
type mang= array[0..10000 ] of byte;
var a,d,m:mang;
dd:array[1..20,1..400] of byte;
b:array [1..10000] of boolean;
r,dem, t,n,max,i,j:integer;
f:text;
procedure doc;
var i:integer;
begin
assign(f,'pthuong.inp');
reset(f);
readln(f,n);
for i:=1 to n do readln(f,d[i]);
close(f);
end;
function kt( c:mang):boolean;
var
i,j:longint;
q:boolean;
begin
i:=1; q:=true;
while (i<=r-2) and q do
begin
j:=1;
14
while c[i+j-1]+1=c[i+j] do j:=j+1;
if j>=3 then q:=false
else q:=true;
i:=i+1;
end;
kt:=q;
end;
Procedure print;
var i,tong: byte;
begin
if kt(a)=true then
begin
dem:=dem+1;
tong:=0;
for i:=1 to r do
begin
dd[dem,i]:= a[i];
tong:=tong+d[a[i]];
end;
m[dem]:=tong;
end;
end;
Procedure Find(k:byte);
var j: byte;
15
begin
if k>r then print
else
begin
for j:=1 to n do
if b[j] and (j>a[k-1]) then
begin
a[k]:=j;
b[j]:=false;
Find(k+1);
b[j]:=true;
end;
end;
end;
begin
clrscr;
doc;
dem:=0;
r:= n-(n div 3);
for t:=1 to n do b[t]:=true;
a[0]:=0;
Find(1);
max:=m[1];
16
for i:=1 to dem do if max< m[i] then max:=m[i];
assign(f,'PTHUONG.OUT');
rewrite(f);
writeln(f,max);
for i:=1 to dem do
if max=m[i] then
begin
j:=1;
while (dd[i,j] <>0) do
begin
write(f,dd[i,j]:2);
j:=j+1;
end;
end;
close(f);
end.
BEGIN
Assign(f,'shoes.inp');
Reset(f);
Assign(g,'shoes.out');
Rewrite(g);
Readln(f,n);
For i:=1 to n do read(f,a[i]);
17
Readln(f);
For i:=1 to n do read(f,b[i]);
d:=0;
i:=1;
repeat
j:=0;
repeat
inc(j);
until (a[i]=b[j]) or (j>n);
if a[i]=b[j] then b[j]:=0;
inc(i);
until i>n;
for i:=1 to n do
if b[i]<>0 then inc(d);
write(g,d);
Close(g);
Close(f);
END.
18
ĐỀ THI HỌC SINH GIỎI HUYỆN
ĐỀ SỐ 5
MÔN: TIN HỌC 9
Thời gian: 120 phút
Câu 1: (4 điểm)
Viết chương trình nhập vào tháng, năm và cho biết tháng đó có bao nhiêu
ngày.
Câu 2: (3 điểm)
Viết chương trình nhập vào từ bàn phím ba số tự nhiên a, b, c và hiển thị
kết quả thông báo ra màn hình bộ ba số đó có phải là bộ số Pitago hay không.
Câu 3: (3 điểm)
Cho abc là số có ba chữ số thỏa mãn điều kiện
viết chương trình tìm các số thỏa mãn điều kiện đã cho.
abc a 3 b 3 c 3 .
Hãy
Câu 4: (5 điểm)
Một người gửi tiền tiết kiệm vào ngân hàng với số tiền ban đầu là x triệu
đồng với lãi suất hàng tháng là k%. Biết rằng phương thức tính lãi suất là lũy kế
theo thời hạn, nghĩa là số tiền lãi hàng tháng được cộng dồn vào số tiền gốc với
chu kì (thời hạn) là c tháng và khi chưa đủ chu kì thì không được tính số tiền
lãi. Sau thời gian t tháng, người đó rút tiền cả vốn và lãi được b triệu đồng. Tính
b.
19
Hãy viết chương trình giải bài toán trên với x, k, c, t được nhập từ bàn
phím và b được viết ra màn hình.
Câu 5: (5 điểm)
Dùng ba biến mảng lần lượt biểu diễn số tiền cước phí về điện thoại, điện
và dịch vụ Internet của gia đình mình trong năm qua. Em hãy viết một chương
trình thực hiện các nhiệm vụ sau:
a. Nhập số tiền mà gia đình em đã chi cho ba dịch vụ từng tháng từ bàn
phím.
b. Tính và in ra màn hình: Tổng số tiền mà gia đình em phải trả cho các
dịch vụ này trong năm qua; dịch vụ có tổng chi lớn nhất và số tiền trung bình
mỗi tháng gia đình em phải trả cho các dịch vụ nói trên.
20