Tin hoc tre THCS và THPT ôn thi HSG
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (246.15 KB, 19 trang )
ĐỀ THI TIN HỌC TRẺ - TỈNH HÀ TĨNH
LẦN THỨ XVI - NĂM 2013
BẢNG B - KHỐI THCS
Thời gian 120 phút (Không kể thời gian giao đề)
TỔNG QUAN BÀI THI
Bài 1
Bài 2
Bài 3
Tên bài
Số ngoài dãy số
Thi tiếng hát
Đưa tin
Tệp bài làm
SNDS.PAS
TTH.PAS
DUATIN.PAS
Tệp dữ liệu vào
SNDS.INP
TTH.INP
DUATIN.INP
Tệp dữ liệu ra
SNDS.OUT
TTH.OUT
DUATIN.OUT
Sử dụng ngôn ngữ lập trình PASCAL lập chương trình giải các bài toán sau đây:
Bài 1. Số ngoài dãy số
Cho một dãy số A gồm các số nguyên dương: a 1, a2, …., aN (1≤N≤ 128). Hãy tìm tất cả
các số nguyên dương nằm trong đoạn giữa giá trị bé nhất và giá trị lớn nhất của dãy số đã
cho và không thuộc dãy số đó.
Dữ liệu vào là tệp văn bản SNDS.INP có cấu trúc như sau:
- Dòng thứ nhất ghi số nguyên N.
- Dòng thứ hai ghi các số của dãy số A; các số ghi cách nhau ít nhất là một ký tự
trống.
Dữ liệu ra là tệp văn bản SNDS.OUT chỉ có một dòng ghi lại các số tìm được; các số ghi
cách nhau ít nhất là một ký tự trống. Nếu không tìm được số nào theo yêu cầu thì ghi số -1.
SNDS.INP
5
13679
SNDS.OUT
2458
SNDS.INP
5
13254
SNDS.OUT
-1
Hướng dẫn giải chi tiết như sau:
* Để đọc được dữ liệu từ tệp em cần tạo tệp vào có tên SNDS.INP. Cách tạo tập SNDS.INP
như sau:
Em khởi động chương trình Pascal, vào file chọn New và tiến hành gõ nội dung của tệp (ví
dụ như ở trên: dòng 1 ta gõ số 5, dòng 2 ta gõ các số 1 3 6 7 9). Sau khi nhập dữ liệu xong
em vào file chọn save hoặc ấn phím F2 để lưu tệp. Khi lưu tệp em gõ đầy đủ tên tệp và
phần mở rộng (tức là phải gõ SNDS.INP).
* Cách đọc dữ liệu từ tệp lưu ra biến như sau:
Mở tệp SNDS.INP ra để đọc bằng 2 thủ tục:
Assign(f, ‘SNDS.INP’);
Reset(f);
+ Đọc dòng thứ nhất lưu vào biến N: thủ tục Readln(f, N); {dùng Readln vì đọc xong xuống
dòng đọc tiếp}
+ Đọc dòng thứ 2 lưu vào biến mảng A bằng câu lệnh:
For i:=1 to N do read(f, A[i]); {dùng lệnh Read vì đọc dữ liệu trên 1 dòng}
* Ý tưởng giải:
- Đầu tiên ta cần tìm giá trị bé nhất (Min) và lớn nhất (Max) của dãy số (chính là giá trị lớn
nhất và bé nhất của mảng A).
- Dùng 1 vòng For với biến đếm i chạy từ giá trị Min tới giá trị Max. Với mỗi giá trị của
biến đếm i ta so sánh nó với tất cả các phần tử của mảng A (dùng vòng For j:=1 to N để
1
duyệt mảng A) , nếu không tìm thấy phần tử nào của mảng A bằng i thì ta ghi i vào tệp
SNDS.OUT (để khẳng định có tìm thấy phần tử bằng i hay không ta sử dụng 1 biến đếm d.
Nếu sau N lần so sánh mà d=0 thì i không có trong A ngược lại i có trong A ). Ta sử dụng 1
biến đếm để đếm số phần tử có trong dãy số (lấy tên là sopt). Nếu hết các vòng lặp For mà
sopt=Max-Min+1 thì ghi số -1 vào tệp SNDS.OUT.
* Chương trình cụ thể như sau:
Program So_ngoai_day_so;
const fi='SNDS.INP';
fo='SNDS.OUT';
Nmax=128;
Var N:byte;
A:array[1..Nmax] of word;
i,j,Max,Min,sopt,d:word;
f:text;
(*===================*)
Procedure doctep;
Begin
Assign(f,fi);
reset(f);
Readln(f,N);
For i:=1 to N do read(f,A[i]);
close(f);
End;
(*===================*)
Procedure TimMax_min;
Begin
Max:=a[1]; Min:=A[1];
for i:=2 to N do
begin
if A[i]>Max then Max:=A[i];
if A[i]
end;
(*===================*)
Procedure motep;
begin
Assign(f,fo);
rewrite(f);
end;
(*===================*)
procedure xuli;
Begin
sopt:=0;
for i:=Min to Max do
begin
d:=0;
for j:=1 to N do if i=A[j] then d:=d+1;
if d=0 then write(f,i, ' ') else sopt:=sopt+1;
end;
if sopt=Max-Min+1 then write(f,-1);
2
end;
(*===================*)
BEGIN
doctep;
motep;
TimMax_Min;
xuli;
close(f);
END.
Bài 2. Thi tiếng hát
Trong một cuộc thi tiếng hát học sinh có M thí sinh tham gia (có số hiệu là: 1, 2, …,
M). Ban giám khảo cuộc thi gồm N người (có số hiệu là: 1, 2, …, N). Kết quả thi của mỗi
thí sinh là trung bình cộng điểm của các thành viên trong ban giám kháo cho thí sinh đó
(làm tròn đến một chữ số thập phân). Biết điểm của các thành viên trong ban giám khảo cho
mỗi thí sinh, hãy xác định thí sinh có thành tích cao nhất.
Dữ liệu vào là tệp văn bản TTH.INP có cấu trúc:
- Dòng đầu tiên ghi hai số nguyên dương M và N (1≤M,N≤100).
- M dòng tiếp theo, dòng thứ i (1≤i≤M) ghi N số là điểm của các thành viên ban
giám khảo cho thí sinh i theo vị trí tương ứng (vị trí thứ nhất của dòng ghi điểm của
giám khảo 1, …., vị trí thứ N ghi điểm của giám khảo N).
- Các số trên mỗi dòng ghi cách nhau ít nhất là một ký tự trống.
Dữ liệu ra là tệp văn bản TTH.OUT chỉ có một dòng ghi số hiệu thí sinh đạt thành tích
cao nhất và kết quả thi của thí sinh đó; các số ghi cánh nhau ít nhất là một ký tự trống.
Ví dụ:
TTH.INP
34
1142
5234
1123
TTH.OUT
2 3.5
Hướng dẫn giải:
* Cách đọc dữ liệu từ tệp TTH.INP:
+ Đọc dòng thứ 1 ghi vào 2 biến M và N
+ Đọc các dòng còn lại ghi ra mảng 2 chiều gồm M dòng , N cột
* Ý tưởng giải:
Đầu tiên phải đọc hiểu yêu cầu của đề ra. Với đề cho như ở ví dụ trên thì ta hiểu như sau:
Có 3 thí sinh tham gia thi tiếng hát học sinh và có 4 giám khảo (vì có M dòng nên có M thí
sinh (M=3), có N cột nên có N giám khảo(N=4))
- Thí sinh thứ 1: Các giám khảo cho điểm như sau
+ Giám khảo 1 cho 1 điểm
+ Giám khảo 2 cho 1 điểm
+ Giám khảo 3 cho 4 điểm
+ Giám khảo 4 cho 2 điểm
Điểm trung bình của thí sinh 1 là: (1+1+4+2)/4 = 2 điểm
- Thí sinh thứ 2: Các giám khảo cho điểm như sau
+ Giám khảo 1 cho 5 điểm
+ Giám khảo 2 cho 2 điểm
3
+ Giám khảo 3 cho 3 điểm
+ Giám khảo 4 cho 4 điểm
Điểm trung bình của thí sinh 2 là: (5+2+3+4)/4 = 3.5 điểm
- Thí sinh thứ 3: Các giám khảo cho điểm như sau
+ Giám khảo 1 cho 1 điểm
+ Giám khảo 2 cho 1 điểm
+ Giám khảo 3 cho 2 điểm
+ Giám khảo 4 cho 3 điểm
Điểm trung bình của thí sinh 3 là: (1+1+2+3)/4 = 1.75 điểm
Kết luận: thí sinh 2 có thành tích cao nhất là 3.5 điểm.
* Ý tưởng giải:
- Để tìm được thí sinh có điểm cao nhất chúng ta cần tính điểm trung bình của tất cả các thí
sinh và lưu kết quả tính được vào mảng 1 chiều A (mỗi phần tử của mảng A là điểm trung
bình của 1 thí sinh). Sau đó chúng ta áp dụng thuật toán tìm giá trị lớn nhất của một dãy số
để tìm ra phần tử có giá trị lớn nhất.
- Để chương trình ngắn ngọn thì trong quá trình đọc tệp, đọc được dòng nào ta tính tổng các
giá trị và tính giá trị trung bình của dòng đó rồi lưu vào mảng A.
- Chương trình nên xây dựng thành 2 hoặc 3 thủ tục. Nếu xây dựng 2 thủ tục thì 1 thủ tục
đọc tệp và 1 thủ tục xử li; còn 3 thủ tục thì 1 thủ tục đọc tệp, 1 thủ tục mở tệp, 1 thủ tục xử
lí.
* Chương trình cụ thể như sau
Program THI_TIENG_HAT;
Const fi='TTH.INP';
fo='TTH.OUT';
Nmax=100;
Mmax=100;
Var A:array[1..Mmax] of real;
tong,tb,x,Max:real;
i,j,M,N,cs:integer;
f:text;
(*==========================*)
Procedure doctep;
begin
Assign(f,fi);reset(f);
Readln(f,M,N);
for i:=1 to M do
begin
tong:=0;
for j:=1 to N do
Begin
Read(f,x);
tong:=tong+x;
end;
tb:=tong/N; A[i]:=tb;
readln(f);
end;
close(f);
end;
(*==========================*)
4
Procedure motep;
Begin
Assign(f,fo);
Rewrite(f);
end;
(*==========================*)
Procedure xuli;
Begin
Max:=A[1]; cs:=1;
for i:=2 to M do if A[i]>Max then
Begin
Max:=A[i];
cs:=i;
end;
write(f,cs,' ',Max:3:1);
close(f);
end;
(*==========================*)
BEGIN
doctep;
motep;
xuli;
END.
Bài 3. Đưa tin
Tại một quốc gia X, tin tức tình báo thu được cho thấy quân địch sắp mở cuộc tấn công
quy mô. Trạm tiền đồn biên giới cử người phóng ngựa về thủ đô báo cáo tình hình và xin
tiếp viện. Giữa tram tiền đồn và thủ đô có bố trí N trạm ngựa cách đều nhau, khi đến mỗi
trạm ngựa, lích cờ (người cầm cờ hiệu đưa tin) có thể trao đổi ngựa mới trong trạm. Ngựa
của trạm i có thể phi tới trạm kế tiếp sau thời gian Ti (1≤i≤N-1) giờ. Mỗi con ngựa đều đủ
khỏe để có thể đi một mạch tới tận thủ đô mà không thay đổi tốc độ.
Hãy xác định khoảng thời gian ngắn nhất mà tin tức tình báo được đưa về tới thủ đô.
Dữ liệu vào từ tệp văn bản DUATIN.INP có cấu trúc:
- Dòng thứ nhất ghi số nguyên dương N (<=10^6).
- Dòng thứ hai ghi N-1 số nguyên dương Ti, các số ghi cách nhau ít nhất là một ký
tự trống.
Ví dụ:
DUATIN.INP
DUATIN.OUT
2431
7
- Cách đọc tệp và lưu vào các biến như sau:
+ Đọc dòng 1 lưu vào biến N
+ Đọc dòng 2 lưu vào mảng 1 chiều A
* Ý tưởng giải:
Theo đề ra thì mỗi con ngựa đều đủ khỏe để có thể đi một mạch tới tận thủ đô mà không
thay đổi tốc độ. Do đó ta có ý tưởng giải như sau:
Gọi thời gian ngắn nhất cần tính là t.
5
- Xuất phát t=A[1]; cs:=1; {cs là biến lưu chỉ số phần tử đứng trước mà nhỏ hơn phần tử
đứng sau}
- Sau đó so sánh A[cs] với các phần tử còn lại của mảng A, nếu A[cs] mà lớn hơn A[i]
(i=2..N-1) thì t:=t+A[i], ngược lại t:=t+A[cs];
* Chương trình cụ thể như sau :
Program DUA_TIN;
Const fi='DUATIN.INP';
fo='DUATIN.OUT';
Nmax=1000000;
Var A:array[1..Nmax] of integer;
i,cs,t,N:integer;
f:text;
(*=======================*)
Procedure doctep;
Begin
Assign(f,fi);
reset(f);
Readln(f,N);
For i:=1 to N-1 do read(f,A[i]);
close(f);
End;
(*=======================*)
Procedure motep;
Begin
Assign(f,fo);
Rewrite(f);
End;
(*=======================*)
Procedure xuli;
Begin
t:=A[1];cs:=1;
For i:=2 to N-1 do
if A[i]
t:=t+A[i];
cs:=i;
end
else t:=t+A[cs];
write(f,t);
close(f);
End;
(*=======================*)
BEGIN
doctep;
motep;
xuli;
END.
- Thí sinh không được sử dụng tài liệu.
- Giám thị không giải thích gì thêm.
SỐ ĐƠN ĐIỆU
6
Các số nguyên dương: 3748, 58, 859, 32435465768 được gọi là các số đơn
điệu do nếu quan sát các chữ số của các số này, ta thấy chúng luân phiên tăng giảm
hoặc giảm tăng. Chẳng hạn:
3 < 7 > 4 < 8 và 3 > 2 < 4 > 3 < 5 > 4 < 6 > 5 < 7 > 6 < 8
Số chỉ có một chữ số là số đơn điệu chiều dài 1.
Nhiệm vụ:
Viết chương trình xác định số chữ số đầu tiên lớn nhất tạo thành số đơn điệu của một
số cho trước.
Tên tập tin chương trình:
WIGGLE.PAS
Dữ liệu:
Cho trong tập tin văn bản WIGGLE.IN, gồm một dòng duy nhất chứa một số nguyên
dương duy nhất có không quá 75 chữ số.
Kết quả:
Cho trong tập tin văn bản WIGGLE.OUT, chứa một số nguyên duy nhất chỉ số chữ
số đầu tiên lớn nhất tạo thành số đơn điệu của số tương ứng trong tập tin dữ liệu.
Ví dụ:
WIGGLE.IN
3748
WIGGLE.OUT
4
SỐ ĐỐI XỨNG
Một số mà đọc từ trái sang phải giống hệt như đọc từ phải sang trái gọi là số
đối xứng. Số 14541 là số đối xứng còn số 66667 không là số đối xứng. Hiển nhiên số
0330 không là số đối xứng (do số 0 đứng ở vị trí đầu tiên bên trái).
Số 21 (biểu diễn trong cơ số 10) không là số đối xứng, nhưng số 21 (biểu diễn trong
cơ số 10) là số đối xứng nếu biểu diễn trong cơ số 2 (10101).
Nhiệm vụ:
Viết chương trình đọc vào hai số (biểu diễn trong cơ số 10)
N (1 <= N <= 15)
S (0 < S < 10000)
và xuất ra (trong cơ số 10):
• N số đầu tiên lớn hơn S và là số đối xứng khi biểu diễn trong ít nhất hai cơ số c
khác nhau (2 <= c <= 10).
• Số số nguyên tố trong N số nói trên
Tên tập tin chương trình:
7
DUALPAL.PAS
Dữ liệu:
Cho trong tập tin văn bản DUALPAL.IN, gồm một dòng duy nhất chứa hai số
nguyên N và S, cách nhau một khoảng trắng.
Kết quả:
Cho trong tập tin văn bản DUALPAL.OUT, gồm N+1 dòng. Trên mỗi dòng của N
dòng đầu tiên là một số đối xứng khi được biểu diễn trong ít nhất hai hệ cơ số c (2 <=
c <= 10). Các số trong N dòng đầu tiên phải thỏa yêu cầu của đề bài và được sắp theo
thứ tự tăng dần. Trên dòng N+1 chứa một số nguyên duy nhất, chỉ số số nguyên tố
trong N dòng trên.
Ví dụ:
DUALPAL.IN
3 25
DUALPAL.OUT
26
27
28
0
Program csc;
Uses crt;
Var f1,f2:text;
n,s,c,e,dem,dem1,dem2,i:longint;
a:array[1..300] of integer;
Function ktnt(n:integer):boolean;
var i,m,e:integer;
begin
ktnt:=false;
if n<2 then exit;
for i:=2 to trunc(sqrt(n)) do
if n mod i =0 then exit;
ktnt:=true;
end;
Function ccs(n,e:integer):string;
var i,h,k,q:integer;
s,s1:string;
begin
s:='';
while n<>0 do
begin
k:=n mod e;
str(k,s1);
s:=s1 +s;
n:=n div e;
end;
ccs:=s;
end;
8
Function ktdx(n:string):boolean;
var i,e:integer;
begin
ktdx:=true;
for i:=1 to length(n) do
if n[i]<>n[length(n)-i+1] then ktdx:=false;
end;
BEGIN
clrscr;
assign(f1,'dualpal.inp');
assign(f2,'dualpal.out');
reset(f1);
rewrite(f2);
read(f1,n,s);
dem1:=0;
i:=0;
repeat
s:=s+1;
dem:=0;
for e:=2 to 10 do
if ktdx(ccs(s,e)) then dem:=dem+1;
if dem>=2 then
begin writeln(f2,s);
i:=i+1;
a[i]:=s;
dem1:=dem1+1;
end;
until dem1=n;
dem2:=0;
for i:=1 to n do
if ktnt(a[i]) then dem2:=dem2+1 ;
write(f2,dem2);
close(f1);
close(f2);
readln;
END.
SỐ NGUYÊN TỐ GHÉP
Xét dãy A các số nguyên tố 2, 3, 5, 7, 11, 13, 17, 19,...
và dãy B gồm các số thu được từ dãy A bằng cách ghép hai số liên tiếp trong A: 23,
57, 1113, 1719, ...
Trong dãy B có những phần tử là số nguyên tố. Chẳng hạn 23, 3137, 8389, 157163...
Các số nguyên tố trong dãy B gọi là số nguyên tố ghép.
Yêu cầu: Cho trước số nguyên dương K<500, hãy tìm số nguyên tố ghép thứ K.
Input
2
Output
3137
MUA VÉ
9
Có N người xếp hàng mua vé, đánh số 1 đến N theo thứ tự đứng trong hàng. Thời
gian phục vụ bán vé cho người thứ i là t i. Mỗi người cần mua một vé nhưng được
quyền mua tối đa 2 vé, vì thế một số người có thể nhờ người đứng ngay trước mình
mua hộ vé. Người thứ i nhận mua vé cho người thứ i+1 thì thời gian mua vé cho 2
người là ri.
Yêu cầu: Tính thời gian nhỏ nhất để bán vé xong cho N người.
Dữ liệu vào: Đọc từ file TICK.INP
• Dòng thứ nhất ghi số N.
• Dòng thứ hai ghi N số nguyên dương t1, t2, …, tN
• Dòng thứ ba ghi N – 1 số r1, r2, …, rN-1
Dữ liệu ra: Kết quả ghi ra file TICK.OUT
• Dòng thứ nhất ghi tổng thời gian phục vụ bán vé
• Các dòng tiếp theo ghi chỉ số của các khách hàng cần rời khỏi hàng, mỗi
dòng 10 số, ngược lại nếu không có ai rời khỏi hàng ghi số 0.
Giới hạn:
1 < N ≤ 2000.
Ví dụ:
TICK.INP TICK.OUT
5
17
25784
24
3 9 10 10
BÀI TẬP RA NGÀY 10/3/2015
Bài 1. Sắp xếp dãy số
Tên file bài làm: DAYSO.PAS
Cho dãy số nguyêna1, a2, ..., an (n ≤ 1000).
Hãy tìm cách thực hiện một số ít nhất phép đổi chỗ hai số hạng bất kỳ của dãy để thu
được dãy số mà số lẻ đứng ở vị trí lẻ, số chẵn đứng ở vị trí chẵn.
Dữ liệu: Vào từ file văn bản DAYSO.INP:
Dòng đầu tiên chứa số nguyên dương n;
Dòng thứ i trong số n dòng tiếp theo chứa số hạng ai của dãy đã cho (-32767 ≤
ai ≤ 32767, i = 1, 2, ..., n).
Kết quả: ghi ra file văn bản DAYSO.OUT:
Dòng đầu tiên ghi số lượng phép đổi chỗ cần thực hiện k (qui ước k = -1, nếu
không thể biến đổi được dãy đã cho thành dãy thoả mãn yêu cầu đầu bài);
Nếu k > 0, thì dòng thứ j trong số k dòng tiếp theo ghi chỉ số của hai số hạng cần
đổi chỗ cho nhau ở lần đổi chỗ thứ j ( j =1, 2, ..., k).
Ví dụ:
DAYSO.INP
DAYSO.OU
T
DAYSO.INP DAYSO.OUT
10
6
1
4
-1
1
56
1
2
3
3
2
4
5
6
5
Bài 2. Phép cộng kỳ quặc
Với mỗi số nguyên dương a, ta gọi số đồng dạng với a là số nguyên
dương thu được từ a bằng cách sắp xếp theo thứ tự không tăng các chữ số trong cách
viết a dưới dạng hệ đếm thập phân.
Ví dụ: Nếu a=6334 thì số đồng dạng với nó là 6433, còn nếu a=374 thì số đồng
dạng của nó là 743.
Cho a và b là 2 số nguyên dương. Ta gọi tổng đồng dạng của a và b là số đồng
dạng với tổng của số đồng dạng với a và số đồng dạng với b.
Ví dụ: Nếu a = 6334 và b = 374 thì tổng của số đồng dạng với a và số đồng
dạng với b là 6433 + 743 = 7176. Vì thế tổng đồng dạng của 6334 và 374 là 7761.
Yêu cầu: Cho 2 số a và b, hãy tính tổng đồng dạng của chúng.
Dữ liệu: File văn bản BL2.INP
Dòng thứ nhất chứa số a;
Dòng thứ hai chứa số b.
Số chữ số của a và b là không quá 50.
Kết quả: Ghi ra file văn bản BL2.OUT tổng đồng dạng của a và b.
Ví dụ:
BL2.INP
BL2.OUT
6334
7761
374
11
Bài 3. Y3K
Cho số nguyên N trong phạm vi từ 1000 đến 999999. Cần xác định số này có
phải là thông tin về một ngày tháng có trong thế kỷ 21 không. (Thế kỷ 21 bắt đầu từ 1
tháng 1 năm 2001 và kết thúc vào ngày 31 tháng 12 năm 3000. Biết rằng 2 chữ số
cuối của N là chỉ hai chữ số cuối của năm, các chữ số còn lại (ở đầu) xác định ngày
và tháng.
Ví dụ:
1111 tương ứng với 1 tháng 1 năm 2011;
21290 tương ứng với 2 tháng 12 năm 2090 hoặc 21 tháng 2 năm 2090;
131192tương ứng với 13 tháng 11 năm 2092;
32392 Không phải là thông tin về một ngày tháng nào cả;
311198 Không phải là thông tin về một ngày tháng nào cả;
29205 Không phải là thông tin về một ngày tháng nào cả;
Dữ liệu: Nhập vào số N từ bàn phím.
Kết quả: Đưa ra màn hình các ngày tháng năm tương ứng với N hoặc thông báo
là KHONG nếu N không phải là thông tin về một ngày tháng nào cả.
Ví dụ:
Giá trị của N
Thông báo ra màn hình tương ứng
1111
1-1-2011
21290
2-12-2090 HOAC 21-2-2090
29205
KHONG
Bài 4:
Cho dãy số nguyên a1,..,an (1
Vd
N=9
2 7 5 -3 -2 4 -9 -2 -1
2 8
Bài 5:
Cho dãy số nguyên a1,..,an (1
Bài 6. DÃY CON
Cho một dãy gồm n ( n ≤ 1000) số nguyên dương A1, A2, ..., An và số nguyên dương
k (k ≤ 50). Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các
phần tử của dãy con này chia hết cho k.
Dữ liệu vào: file văn bản DAY.INP
• Dòng đầu tiên chứa hai số n, k ghi cách nhau bởi ít nhất 1 dấu trống.
• Các dòng tiếp theo chứa các số A 1, A2, ..., An được ghi theo đúng thứ tự cách nhau
ít nhất một dấu trống hoặc xuống dòng (CR-LF).
Kết quả: ghi ra file văn bản DAY.OUT
• Dòng đầu tiên ghi m là số phần tử của dãy con tìm được.
12
• Các dòng tiếp theo ghi dãy m chỉ số các phần tử của dãy đã cho có mặt trong dãy
con tìm được. Các chỉ số ghi cách nhau ít nhất một dấu trắng hoặc một dấu xuống
dòng.
Ví dụ:
DAY.INP
10 3
2357
9 6 12 7
11 15
DAY.OUT
9
13245
6 7 10 8
Bài 7. TỔNG CÁC CHỮ SỐ
Cho trước hai số nguyên dương n và k (n ≤ 20, k ≤ 30).
Yêu cầu 1: Hãy cho biết có bao nhiêu số có ≤ n chữ số mà tổng các chữ số đúng bằng
k
Yêu cầu 2: Cho số nguyên dương p, hỏi nếu đem các số tìm được sắp xếp theo thứ tự
tăng dần thì số thứ p là số nào. (p không lớn hơn số lượng các số tìm được)
Dữ liệu: Vào từ file văn bản DIGITSUM.INP gồm 1 dòng chứa ba số n, k, p theo
đúng thứ tự cách nhau 1 dấu cách.
Kết quả: Ghi ra file văn bản DIGITSUM.OUT gồm 2 dòng
• Dòng 1: Ghi số lượng các số tìm được trong yêu cầu 1
• Dòng 2: Ghi số thứ p trong yêu cầu 2 tìm được
Ví dụ:
DIGITSUM.INP
3 8 10
DIGITSUM.OUT
45
107
Bài 8
Cho dãy số nguyên a = (a1, a2, ..., an), 1 ≤ n ≤ 60000; ∀i: -10000 ≤ ai ≤ 10000
Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy a: aL, aL+1, ..., aH có
tổng dương
Dữ liệu: Vào từ file văn bản SEGMENT.INP
• Dòng 1: Chứa số n
• Dòng 2: Chứa n số a1, a2, ..., an theo đúng thứ tự cách nhau ít nhất một dấu cách
Kết quả: Ghi ra file văn bản SEGMENT.OUT
Chỉ gồm một dòng ghi hai số L và H cách nhau ít nhất một dấu cách.
Ràng buộc: Có ít nhất một phần tử dương trong a
Ví dụ:
SEGMENT.INP
10
-5 -2 -3 4 -6 7 -8 9 -1 -20
SEGMENT.O
UT
39
Bài 9. DẴY ĐƠN ĐIỆU TĂNG DÀI NHẤT
Cho dãy số nguyên dương a = (a1, a2, ..., an) (1 ≤ n ≤ 10000; 1 ≤ ai ≤ 10000)
13
Hãy tìm dãy chỉ số dài nhất i1, i2, ..., ik thoả mãn:
• 1 ≤ i1 < i2 < ... < ik ≤ n
• ai1 < ai2 < ... < aik
Dữ liệu: Vào từ file văn bản INCSEQ.INP
• Dòng 1: Chứa số n
• Dòng 2: Chứa n số a1, a2, ..., an
Kết quả: Ghi ra file văn bản INCSEQ.OUT
• Dòng 1: Ghi số k
• Dòng 2: Ghi k số i1, i2, ..., ik
Các số trên một dòng của Input/Output file cách nhau ít nhất một dấu cách
Ví dụ:
INCSEQ.INP
8
12895679
INCSEQ.OUT
6
125678
14
Bài 10. Dự trữ nước
Ở miền Trung thường năm nào cũng có những đợt hạn hán nên ông Nam có những
thùng dự trữ nước. Do mua làm nhiều đợt nên N (1 ≤ N ≤ 1000) thùng chứa nước của
ông Nam có kích thước khác nhau, mỗi thùng có sức chứa Ci (1 ≤ Ci ≤ 10000, 1 ≤ i ≤
N). Dự đoán rằng năm nay sẽ có đợt hạn hán lớn nên ông Nam muốn đổ đầy nước hết
các thùng để dự trữ. Sau khi kiểm tra ông Nam thấy rằng có một số thùng vẫn còn
đầy, một số khác thì vơi đi một phần, còn một số thì đã hết. Ông quyết định các thùng
nào chưa đầy thì sẽ chở đi để đổ đầy nước. Nhưng do nơi lấy nước rất xa, và mỗi lần
chỉ chở đi được 1 thùng nên ông quyết định sẽ san nước giữa các thùng với nhau để
số thùng phải chở đi là ít nhất.
Yêu cầu: Cho dung lượng nước hiện có của thùng thứ i là Bi (0 ≤ Bi ≤ Ci, 1 ≤ i ≤
N), hãy giúp ông Nam xác định số lượng thùng ít nhất phải mang đi.
Dữ liệu: vào từ file văn bản WATER.INP có dạng sau:
- Dòng thứ nhất ghi một số tự nhiên N là số lượng các thùng nước.
- Dòng thứ i trong N dòng tiếp theo mỗi dòng có 2 số nguyên Bi và Ci (0 ≤ Bi ≤ Ci)
mô tả thông tin thùng thứ i, với Bi là nước còn trong thùng và Ci là sức chứa của
thùng, các số cách nhau ít nhất một khoảng trắng.
Kết quả: ghi ra file văn bản WATER.OUT chứa một số là số lượng ít nhất các thùng
nước tìm được.
Ví du:
WATER.INP
WATER.OUT
4
1
01
45
02
12
Bài 11: Dãy con chung tăng dần dài nhất
Cho 2 dãy số nguyên a1,a2,a3,…,aN và b1, b2, b3,…,bN. Hãy tìm dãy con chung
tăng dần dài nhất của 2 dãy A, B gồm các phần tử liên tiếp của 2 dãy .
Bài 12: Bày tranh
Cho n bức tranh mã số từ 1 .. n. Người ta cần chọn ra 1 bức để treo ở cửa phòng
tranh, số còn lại được treo thẳng hàng trong phòng tại m vị trí định sẵn mã số từ 1 đến
m từ trái qua phải. Các tranh phải được treo theo trật tự nghiêm ngặt sau đây: tranh có
số hiệu nhỏ phải được treo ở bên trái tranh có số hiệu lớn. Biết các thông tin sau về
mỗi bức tranh:
• Tranh thứ i treo tại cửa sẽ đạt giá trị thẩm mỹ c[i].
• Tranh thứ i treo tại vị trí j sẽ đạt giá trị thẩm mỹ v[i, j].
• n <= m+1; m <= 50.
• Các giá trị thẩm mỹ là những số tự nhiên không vượt quá 50.
Hãy xác định một phương án treo tranh để có tổng giá trị thẩm mỹ là lớn nhất.
Dữ liệu vào: cho trong tập tin văn bản TRANH.INP
Dòng thứ nhất: Hai giá trị n và m.
Dòng tiếp theo là n giá trị c[1], c[2], ... , c[n].
15
Tiếp đến là n dòng, dòng i gồm m giá trị v[i, 1], v[i, 2], ..., v[i, m]. Các số trên cùng
dòng cách nhau bởi dấu cách.
Dữ liệu ra: cho trong tập tin văn bản TRANH.OUT
Dòng thứ nhất: giá trị thẩm mỹ lớn nhất tìm được.
Dòng thứ hai: mã số bức tranh treo ở cửa phòng tranh.
Từ dòng thứ ba: n - 1 số tự nhiên sắp tăng dần biểu thị mã số các vị trí được chọn để
treo tranh trong phòng. Các số trong cùng dòng cách nhau bởi dấu cách.
Thí dụ
TRANH.INP
TRANH.OUT
34
40
1 20 1
2
1 10 1 3
24
21 22
1 3 0 10
Bài 13: Phân tích số.
Trong một giờ dạy tại lớp chuyên toán của trường THPT Chuyên Hà Tĩnh, thầy
giáo Lưu ra một bài toán như sau: cho một số tự nhiên N không lớn hơn 150. Hãy
phân tích số N thành tổng các số tự nhiên khác nhau sao cho tích của chúng là lớn
nhất.
Em hãy giúp các bạn lớp chuyên toán giải quyết bài toán mà thầy giáo lưu đã đưa
ra.
Dữ liệu vào là tệp văn bản PTS.INP ghi số N.
Dữ liệu ra là tệp văn bản PTS.OUT ghi thông tin về các số trong sự phân tích số
đã cho theo cấu trúc.
Dòng đầu tiên ghi số lượng các số;
Dòng tiếp theo ghi các số, mỗi số cách nhau 3 ký tự trống;
Dòng cuối cùng ghi giá trị tích của các số.
Ví dụ:
Tệp PTS.INP
Tệp PTS.OUT
5
2
2 3
6
Bài 14: Số nguyên tố đối xứng
Một số T được gọi là số nguyên tố đối xứng nếu thỏa mãn các yêu cầu sau:
- T là số nguyên tố
- T là một số đối xứng (đọc T từ trái qua phải thu được kết quả giống như đọc
T từ phải qua trái). Ví dụ 12321 là một số đối xứng.
Yêu cầu: cho 2 số nguyên dương A và B, hãy tìm số lượng các số nguyên tố đối
xứng T thỏa mãn A≤T≤B.
Dữ liệu: Vào từ file văn bản PRIME.INP gồm 1 dòng chứa 2 số nguyên dương A và
B (104≤A
Kết quả: Đưa ra file văn bản PRIME.OUT 1 số nguyên là số lượng số nguyên tố đối
xứng tìm được.
Ví dụ:
PRIME.INP
PRIME.OUT
11111
22222
23
Bài 15 - Dãy con lồi
Dãy giá trị nguyên A=(A1, A2, …, AN) được gọi là lồi, nếu nó giảm dần từ A 1
đến một Ai nào đó, rồi tăng dần tới AN.
Ví dụ dãy lồi: 10 5 4 2 −1 4 6 8 12
Yêu cầu: Lập trình nhập vào một dãy số nguyên, bằng cách xóa bớt một số
phần tử của dãy và giữ nguyên trình tự các phần tử còn lại, ta nhận được dãy con lồi
dài nhất.
Dữ liệu: Dayloi.inp có dạng
- Dòng đầu là N (N≤2000)
- Dòng tiếp theo là N số nguyên của dãy số (các số kiểu integer)
Kết quả: Dayloi.out gồm:
- Dòng đầu tiên ghi số phần tử lớn nhất của dãy con tìm được
- Dòng tiếp theo ghi các số thuộc dãy con (không thay đổi trật tự các
phần tử trong dãy ban đầu)
Ví dụ
17
Câu 16: TÍNH TỔNG
Trên một màn hình lớn, người ta lần lượt cho hiện ra các số của một dãy gồm N số
nguyên không âm a1, a2, …, aN và cứ lặp đi lặp lại như thế. Mỗi người theo dõi màn
hình được đề nghị tính tổng của K số nguyên liên tiếp xuất hiện trên màn hình bắt
đầu từ số nguyên thứ B.
Viết chương trình giúp cho những người theo dõi màn hình tính được tổng như đề
nghị.
Dữ liệu vào: chứa trong tệp văn bản SUM.INP gồm hai dòng
+ Dòng đầu tiên ghi ba số nguyên N, K và B, 1 ≤ N ≤100, 1 ≤ K ≤100, 1 ≤ B ≤ 109.
+ Dòng thứ hai chứa dãy số nguyên không âm a1, a2, …, aN.
Dữ liệu ra: ghi vào tệp văn bản SUM.OUT gồm một dòng chứa tổng cần tính.
Ví dụ:
SUM.INP
5 7 154
1 2 3 4 5
SUM.OUT
24
18
Ý tưởng giải bài 16: Để tìm vị trí bắt đầu tính tổng ta lấy B mod N được số dư bao nhiêu thì đó
chính là vị trí bắt đầu tính tổng.
Xuất phát d:=0, t:=0 (d là số lần cộng vào tổng, t là tổng cần tính).
Trong khi d<>k thì tiến hành cộng các giá trị vào tổng t, tăng biến d lên 1 đơn vị và vt tăng
lên 1 đơn vị, nếu vt>n thì vt quay lại nhận giá trị bằng 1.
Program Tinhtongcua_K_so_batdautuso_P;
Const fi='SUM.INP';
fo='SUM.OUT';
Var n,k,i:integer;
b:int64;
A:array[1..100] of word;
f:Text;
Procedure doctep;
Begin
Assign(f,fi);reset(f);
readln(f,N,K,B);
for i:=1 to N do read(f,A[i]);
close(f);
Assign(f,fo);rewrite(f);
End;
Procedure xuli;
var vt,d:word;
t:longint;
Begin
if B mod N<>0 then vt:=B mod N {dựa vào B mod N để tìm vị trí bắt đầu tính}
else vt:=N;
d:=0; t:=0;
While d<>k do
if vt<=N then
begin
t:=t+a[vt];
vt:=vt+1;
d:=d+1;
end
else vt:=1;
write(f,t);
close(f);
End;
BEGIN
doctep;
xuli;
END.
19
