SỞ GIÁO DỤC VÀ ĐÀO TẠO
HẢI DƯƠNG
--------------------

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 12
NĂM HỌC 2016 - 2017
Môn: Tin học
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
(Đề thi gồm 05 bài trong 03 trang)
Ngày thi: thứ Bảy, ngày 08/10/2016

ĐỀ CHÍNH THỨC

Tổng quan về các bài thi trong đề
TT
1
2
3
4
5

File
Chương trình
BAI1.*
BAI2.*
BAI3.*
BAI4.*
BAI5.*

Tên bài
VAT

1s
1s
1s

Điểm
2.5
2.5
2.0
1.5
1.5

Chú ý:
- Dấu * là phần mở rộng của File chương trình là PAS hoặc CPP tùy theo ngôn ngữ lập trình sử
dụng là Pascal hoặc C++
- Chương trình chỉ in kết quả theo yêu cầu của đề bài, không in bất cứ thông tin nào khác.
- Chương trình sử dụng lệnh in (write, writeln đối với Passcal; printf (…), cout đối với C++) để in
kết quả.
- Đối với các bài tập đọc và in dữ liệu từ file văn bản, tên của các file này phải đặt đúng theo yêu
cầu đề bài, không có đường dẫn phía trước.
Viết chương trình giải các bài toán sau:
Bài 1. VAT
Lan là nhân viên của một công ty, Lan vừa được giao nhiệm vụ đi mua một số thiết bị để
phục vụ cho phòng chức năng. Lan nhận được một khoản kinh phí nhất định để đi mua hàng, mỗi
thiết bị Lan mua có giá khác nhau. Vì khi mua hàng Lan không lấy hóa đơn, nên khi giao bảng kê
chi phí cho kế toán của công ty thì Lan được yêu cầu phải thống kê ra giá gốc của từng thiết bị, và
chi phí thuế VAT cho từng thiết bị đó.
Bạn hãy giúp Lan thống kê giá gốc và thuế VAT phải nộp cho các thiết bị đã mua, biết rằng
các thiết bị Lan mua đều chịu mức thuế VAT là 10% của giá gốc.
Dữ liệu: Nhập từ bàn phím một số nguyên N (0≤N≤109) là tổng tiền mà Lan đã mua hàng.
Kết quả: In ra màn hình hai giá trị là giá gốc và thuế VAT, mỗi số gồm hai chữ số thập phân, cách


Dữ liệu xuất
YES

Ghi chú: Bài được chấm qua 10 test, mỗi test 0,25 điểm.
Bài 3. Đếm cặp số
Vào giờ toán, thầy Dũng viết hai dãy số thành hai cột trên bảng. Cột thứ nhất lần lượt viết
các số nguyên từ 1 đến

và cột thứ hai lần lượt viết các số nguyên từ 1 đến

.

Câu hỏi của thầy Dũng như sau: Hãy đếm xem có bao nhiêu cách chọn hai số
số được viết ở cột thứ nhất và

là một số được viết ở cột thứ hai sao cho tổng

và

với

là một

chia hết cho 5?

Là một học sinh giỏi tin học trong lớp, bạn hãy viết một chương trình nhỏ để thực hiện yêu cầu trên
của thầy.
Dữ liệu: Nhập từ bàn phím lần lượt hai số nguyên dương


Với

các giá trị

hợp lệ là 2,7,12

•

Với

các giá trị

hợp lệ là 1,6,11

•

Với

các giá trị

hợp lệ là 5, 10

•

Với

các giá trị

hợp lệ là 4, 9


•

Dòng đầu tiên ghi

- sô lượng bộ dữ liệu

dòng tiếp theo, mỗi dòng ghi một số nguyên dương

Kết quả: Ghi ra file văn bản BAI5.OUT gồm

dòng, mỗi dòng là kết quả ứng với số

trong file dữ

liệu vào theo thứ tự.
Ví dụ:
BAI5.INP
1
4

BAI5.OUT
13

Ghi chú: Bài thi được chấm trên 6 test, mỗi test 0,25 điểm:
•

2 test có:

•


4
5

File
Chương trình
BAI1.*
BAI2.*
BAI3.*
BAI4.*
BAI5.*

Tên bài
VAT
Xếp
Đếm
Dãy
Dãy

hàng
cặp số
chia hết
nhị phân

Dữ liệu nhập
(input)
bàn phím
bàn phím
bàn phím
BAI4.INP
BAI5.INP

- Đối với các bài tập đọc và in dữ liệu từ file văn bản, tên của các file này phải đặt đúng theo yêu
cầu đề bài, không có đường dẫn phía trước.
Viết chương trình giải các bài toán sau:
Bài 1. VAT
Lan là nhân viên của một công ty, Lan vừa được giao nhiệm vụ đi mua một số thiết bị để
phục vụ cho phòng chức năng. Lan nhận được một khoản kinh phí nhất định để đi mua hàng, mỗi
thiết bị Lan mua có giá khác nhau. Vì khi mua hàng Lan không lấy hóa đơn, nên khi giao bảng kê
chi phí cho kế toán của công ty thì Lan được yêu cầu phải thống kê ra giá gốc của từng thiết bị, và
chi phí thuế VAT cho từng thiết bị đó.
Bạn hãy giúp Lan thống kê giá gốc và thuế VAT phải nộp cho các thiết bị đã mua, biết rằng
các thiết bị Lan mua đều chịu mức thuế VAT là 10% của giá gốc.
Dữ liệu: Nhập từ bàn phím một số nguyên N (0≤N≤109) là tổng tiền mà Lan đã mua hàng.
Kết quả: In ra màn hình hai giá trị là giá gốc và thuế VAT, mỗi số gồm hai chữ số thập phân, cách
nhau một dấu cách.
Ví dụ:
Dữ liệu nhập
5

Dữ liệu xuất
4.55
0.45

Thuật toán:
Gọi giá gốc của thiết bị là x, giá trị thuế VAT là y.
Ta có: x + y = 5
y = x/10.
Giải hệ tìm ra x và y
Bài 2. Xếp hàng

Trang: 4


và cột thứ hai lần lượt viết các số nguyên từ 1 đến

.

Câu hỏi của thầy Dũng như sau: Hãy đếm xem có bao nhiêu cách chọn hai số
số được viết ở cột thứ nhất và

là một số được viết ở cột thứ hai sao cho tổng

và

với

là một

chia hết cho 5?

Là một học sinh giỏi tin học trong lớp, bạn hãy viết một chương trình nhỏ để thực hiện yêu cầu trên
của thầy.
Dữ liệu: Nhập từ bàn phím lần lượt hai số nguyên dương

. Hai số này cách nhau bởi dấu

trống hoặc dấu xuống dòng.
Kết quả: Ghi ra màn hình một số nguyên là số lượng cặp thỏa mãn yêu cầu của thầy.
Ví dụ:
Dữ liệu nhập
6 12


hợp lệ là 2,7,12

=> 3 + 2 = 5 /5; 3 + 7 = 10 /5; 3 + 12 = 15 /5

•

Với

các giá trị

hợp lệ là 1,6,11

=> 4 + 1 = 5 /5; 4 + 6 = 10 /5; 4 + 11 = 15 /5

•

Với

các giá trị

hợp lệ là 5, 10

=> 5 + 5 = 10 /5; 5 + 10 = 15 /5;
Trang: 5


•

Với


for i:=1 to 4 do ans:=ans+a[i]*b[5-i];
writeln(ans);
END.
Bài 4. Dãy chia hết
Xét một dãy số vô hạn A từ dãy các số nguyên dương tăng dần bằng cách lần lượt xét các số
tự nhiên bắt đầu từ 1 và lần lượt chọn các số cho dãy A theo quy tắc: chọn một số nhỏ nhất chia hết
cho 1 (hiển nhiên là số 1), sau đó là hai số nhỏ nhất chia hết cho 2, tiếp theo là 3 số nhỏ nhất chia
hết cho 3, 4 số nhỏ nhất chia hết cho 4, 5 số nhỏ nhất chia hết cho 5…. Như vậy các số đầu tiên của
dãy A là: 1, 2, 4, 6, 9, 12, 16, 20, 24, 28, 30, 35, 40, 45, 50, 54, …..
Yêu cầu: Cho số tự nhiên N. Hãy xác định số thứ N của dãy số.
Dữ liệu: File BAI4.INP Chứa duy nhất số N (1≤ N ≤105).
Kết quả: Ghi ra file BAI4.OUT số thứ N tìm được.
Ví dụ:
BAI4.INP
BAI4.OUT
13
40
Thuật toán:
Xác định quy tắc để nhập dữ liệu vào cho dãy A: 1 / 1; 2,4/2; 6,9,12/3; 4,12,16,20/4;
20,30,35,40,45/5 ……
Nhập số thứ tự trong dãy A.
Tìm ra giá trị của số ứng với số thứ tự vừa nhập bằng cách duyệt từng phần tử trong dãy A
đến khi có chỉ số bằng với chỉ số vừa nhập, khi đó giá trị của số có vị trí đã duyệt là số cần tìm.
Code:
program Bai4;
const
tfi='bai4.inp';
tfo='bai4.out';
var
Trang: 6


mà không có ba số 1 liên tiếp đứng

cạnh nhau? Vì con số này có thể rất lớn nên bạn chỉ cần lấy phần dư của chúng khi chia cho 109+7
Dữ liệu: Vào từ file văn bản BAI5.INP
•
•

Dòng đầu tiên ghi

- sô lượng bộ dữ liệu

dòng tiếp theo, mỗi dòng ghi một số nguyên dương

Kết quả: Ghi ra file văn bản BAI5.OUT gồm

dòng, mỗi dòng là kết quả ứng với số

trong file dữ

liệu vào theo thứ tự.
Ví dụ:
BAI5.INP
1
4

BAI5.OUT
13

Thuật toán:

như sau:
với
Chuẩn bị trước mảng

có

phần tử và sau đó mỗi truy vấn chỉ còn

. Độ phức tạp thuật toán

là

Code:
program BAI5;
{$M 10000000,0,10000000}
const
tfi='bai5.inp';
tfo='bai5.out';
D=1000000007;
var f: array[0..100000] of longint;
procedure main;
var i, T, n: longint;
begin
assign(input,tfi); reset(input);
assign(output,tfo); rewrite(output);
f[1]:=2; f[2]:=4; f[3]:=7;
for i:=4 to 100000 do
begin
f[i]:=(f[i-1]+f[i-2]) mod D;
f[i]:=(f[i]+f[i-3]) mod D;

Ngày thi: thứ Bảy, ngày 08/10/2016

ĐỀ CHÍNH THỨC

Tổng quan về các bài thi trong đề
TT
1
2
3
4
5

File
Chương trình
BAI1.*
BAI2.*
BAI3.*
BAI4.*
BAI5.*

Tên bài
VAT
Bầu
Đếm
Dãy
Dãy

cử
cặp số
chia hết

1.5
1.5

Chú ý:
- Dấu * là phần mở rộng của File chương trình là PAS hoặc CPP tùy theo ngôn ngữ lập trình sử
dụng là Pascal hoặc C++
- Chương trình chỉ in kết quả theo yêu cầu của đề bài, không in bất cứ thông tin nào khác.
- Chương trình sử dụng lệnh in (write, writeln đối với Passcal; printf (…), cout đối với C++) để in
kết quả.
- Đối với các bài tập đọc và in dữ liệu từ file văn bản, tên của các file này phải đặt đúng theo yêu
cầu đề bài, không có đường dẫn phía trước.
Viết chương trình giải các bài toán sau:
Bài 1. VAT
Lan là nhân viên của một công ty, Lan vừa được giao nhiệm vụ đi mua một số thiết bị để
phục vụ cho phòng chức năng. Lan nhận được một khoản kinh phí nhất định để đi mua hàng, mỗi
thiết bị Lan mua có giá khác nhau. Vì khi mua hàng Lan không lấy hóa đơn, nên khi giao bảng kê
chi phí cho kế toán của công ty thì Lan được yêu cầu phải thống kê ra giá gốc của từng thiết bị, và
chi phí thuế VAT cho từng thiết bị đó.
Bạn hãy giúp Lan thống kê giá gốc và thuế VAT phải nộp cho các thiết bị đã mua, biết rằng
các thiết bị Lan mua đều chịu mức thuế VAT là 10% của giá gốc.
Dữ liệu: Nhập từ bàn phím một số nguyên N (0≤N≤109) là số tiền mà Lan mua một thiết bị.
Kết quả: In ra màn hình hai giá trị là giá gốc và thuế VAT, mỗi số gồm hai chữ số thập phân, cách
nhau một dấu cách.
Ví dụ:
Dữ liệu nhập
5

Dữ liệu xuất
4.55
0.45


.

Câu hỏi của thầy Dũng như sau: Hãy đếm xem có bao nhiêu cách chọn hai số
số được viết ở cột thứ nhất và

là một số được viết ở cột thứ hai sao cho tổng

và

với

là một

chia hết cho 5?

Là một học sinh giỏi tin học trong lớp, bạn hãy viết một chương trình nhỏ để thực hiện yêu
cầu trên của thầy Dũng.
Dữ liệu: Nhập từ bàn phím lần lượt hai số nguyên dương

. Hai số này cách nhau bởi dấu

cách hoặc dấu xuống dòng.
Kết quả: Ghi ra màn hình một số nguyên là số lượng cặp thỏa mãn yêu cầu của thầy.
Ví dụ:
Dữ liệu nhập
6 12

Dữ liệu xuất
14

các giá trị

hợp lệ là 1,6,11

•

Với

các giá trị

hợp lệ là 5, 10

•

Với

các giá trị

hợp lệ là 4, 9

Ghi chú: Bài được chấm qua 8 test, mỗi test 0,25 điểm trong đó:
•

5 test có

•

2 test có

•

Dữ liệu: Vào từ file văn bản BAI5.INP
•
•

Dòng đầu tiên ghi

- số lượng bộ dữ liệu

dòng tiếp theo, mỗi dòng ghi một số nguyên dương

Kết quả: Ghi ra file văn bản BAI5.OUT gồm

dòng, mỗi dòng là kết quả ứng với số

trong file dữ

liệu vào theo thứ tự.
Ví dụ:
BAI5.INP
1
4

BAI5.OUT
13

Ghi chú: Bài thi được chấm trên 6 test, mỗi test 0,25 điểm:
•

2 test có:


2
3
4
5

File
Chương trình
BAI1.*
BAI2.*
BAI3.*
BAI4.*
BAI5.*

Tên bài
VAT
Xếp
Đếm
Dãy
Dãy

hàng
cặp số
chia hết
nhị phân

Dữ liệu nhập
(input)
bàn phím
bàn phím
bàn phím

- Chương trình sử dụng lệnh in (write, writeln đối với Passcal; printf (…), cout đối với C++) để in
kết quả.
- Đối với các bài tập đọc và in dữ liệu từ file văn bản, tên của các file này phải đặt đúng theo yêu
cầu đề bài, không có đường dẫn phía trước.
Viết chương trình giải các bài toán sau:
Bài 1. VAT
Lan là nhân viên của một công ty, Lan vừa được giao nhiệm vụ đi mua một số thiết
bị để phục vụ cho phòng chức năng. Lan nhận được một khoản kinh phí nhất định để đi mua hàng,
mỗi thiết bị Lan mua có giá khác nhau. Vì khi mua hàng Lan không lấy hóa đơn, nên khi giao bảng
kê chi phí cho kế toán của công ty thì Lan được yêu cầu phải thống kê ra giá gốc của từng thiết bị,
và chi phí thuế VAT cho từng thiết bị đó.
Bạn hãy giúp Lan thống kê giá gốc và thuế VAT phải nộp cho các thiết bị đã mua, biết rằng
các thiết bị Lan mua đều chịu mức thuế VAT là 10% của giá gốc.
Dữ liệu: Nhập từ bàn phím một số nguyên N (0≤N≤109) là số tiền mà Lan mua một thiết bị.
Kết quả: In ra màn hình hai giá trị là giá gốc và thuế VAT, mỗi số gồm hai chữ số thập phân, cách
nhau một dấu cách.
Ví dụ:
Dữ liệu nhập
5

Dữ liệu xuất
4.55
0.45

Thuật toán:
Gọi giá gốc của thiết bị là x, giá trị thuế VAT là y.
Ta có: x + y = 5
y = x/10.
Giải hệ tìm ra x và y
Code:

- Nhập 3 phần tử nguyên.
- So sánh các phần tử, tìm max của ba phần tử.
- Xét các trường hợp với max, nếu tồn tại hai giá trị max thì BAU LAI, nếu tồn tại một max
thì công bố người trúng cử.
Code:
Cách 1:
var p,q,r: word;
begin
readln(p,q,r);
if (p>q) and (p>r) then write('An');
if (q>p) and (q>r) then write('Vinh');
if (r>q) and (r>p) then write('Quang');
IF (p=q) and (rp) and (q>r) then max:=q;
if (r>q) and (r>p) then max:=r;
end;
begin
readln(p,q,r);
Trang: 14



Dữ liệu: Nhập từ bàn phím lần lượt hai số nguyên dương

. Hai số này cách nhau bởi dấu

trống hoặc dấu xuống dòng.
Kết quả: Ghi ra màn hình một số nguyên là số lượng cặp thỏa mãn yêu cầu của thầy.
Ví dụ:
Dữ liệu nhập
6 12

Dữ liệu xuất
14

Thuật toán:
•

Với

các giá trị

hợp lệ là 4, 9

=> 1 + 4 = 5 / 5; 1 + 9 = 10 / 5

•

Với

các giá trị


hợp lệ là 5, 10

=> 5 + 5 = 10 /5; 5 + 10 = 15 /5;

•

Với

các giá trị

hợp lệ là 4, 9

=> 6 + 4 = 10 /5; 6 + 9 = 15 /5

Thử tất cả các cặp

bằng hai vòng lặp, với những cặp

tăng biến đếm. Độ phức tạp là

có

thì

.

Code:
var n, m: longint;
a, b: array[0..4] of int64;
ans: int64;

Xác định quy tắc để nhập dữ liệu vào cho dãy A: 1 / 1; 2,4/2; 6,9,12/3; 4,12,16,20/4;
20,30,35,40,45/5 ……
Nhập số thứ tự trong dãy A.
Tìm ra giá trị của số ứng với số thứ tự vừa nhập bằng cách duyệt từng phần tử trong dãy A
đến khi có chỉ số bằng với chỉ số vừa nhập, khi đó giá trị của số có vị trí đã duyệt là số cần tìm.
Code:
program Bai4;
const
tfi='bai4.inp';
tfo='bai4.out';
var
n: longint;
procedure main;
var res, i, j, k: longint;
begin
assign(input,tfi); reset(input);
assign(output,tfo); rewrite(output);
read(n);
k:=trunc((-1+sqrt(1+8.0*n))/2);
if k*(k+1) div 2=n then dec(k);
i:=k+1;
j:=n-k*(k+1) div 2;
if i=1 then res:=1 else
begin
Trang: 16


res:=1;
for k:=2 to i-1 do res:=(res div k+k)*k;
res:=(res div i+j)*i;

trong file dữ

liệu vào theo thứ tự.
Ví dụ:
BAI5.INP
1
4

BAI5.OUT
13

Thuật toán:
Thuật toán 1 (
trong khoảng từ 0 đến

: Có thể thấy mỗi dãy nhị phân là biểu diễn của một số nguyên nằm
. Do vậy thuật toán đơn giản là thử các số nguyên từ 0 đến

với

mỗi số nguyên phân tích nó thành số nhị phân và kiểm tra xem nó có ba số 1 liên tiếp hay không.
Nếu không có thì tăng biến đếm. Hàm dưới đây kiểm tra dãy bit của số có 3 bit 1 liên tiếp hay
không:
function ok(x: integer): boolean;
begin
dem:=0;
while x>0 do
begin
if x mod 2=1 then inc(dem) else dem:=0;
if dem>=3 then exit(false);

var f: array[0..100000] of longint;
procedure main;
var i, T, n: longint;
begin
assign(input,tfi); reset(input);
assign(output,tfo); rewrite(output);
f[1]:=2; f[2]:=4; f[3]:=7;
for i:=4 to 100000 do
begin
f[i]:=(f[i-1]+f[i-2]) mod D;
f[i]:=(f[i]+f[i-3]) mod D;
end;
read(T);
for i:=1 to T do
begin
readln(n);
writeln(f[n]);
end;
close(input); close(output);
end;
BEGIN
main;
END.

--------------------------Hết--------------------------

Trang: 18