SKKN Các dạng bài tập luyện tập phân theo mức độ trong bồi dưỡng học sinh giỏi tỉnh môn Tin học

a file văn bản BALO1.OUT ghi tổng giá trị lớn nhất có thể cho các đồ vật vào trong túi
Ví dụ:
BALO1.INP
BALO1.OUT
5 10
63
3 1 7 3 6
1 2 4
20 19 30 24 15

Bài 10. Đổi tiền. Tên file chương trình nộp Doitien.*
Ở nước Omega người ta tiêu tiền xu. Có n loại tiền xu, loại thứ i có mệnh giá ai đồng. Số lượng mỗi loại mệnh giá là không hạn chế. Một người khách đến Omega du lịch với số tiền M đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiêu cho tiện. Ông cũng muốn số đồng xu đổi ra là ít nhất cho đỡ nặng. Bạn hãy giúp ông ta.
Yêu cầu: Tìm cách đổi tiền sao cho số lượng đồng xu đổi được là ít nhất?. Input: Dòng đầu ghi 2 số M và N (0 ≤ M ≤ 10000; 1 ≤ N ≤ 100).
N dòng sau, dòng thứ i ghi mệnh giá của đồng tiền i (ai ≤ 250). Output: Ghi tổng số đồng xu của cách đổi ít đồng xu nhất.
Ví dụ:
DOITIEN.INP
DOITIEN.OUT
35 3
10
1

2

4

Bài 11. Xâu con đối xứng dài nhất. Tên file chương trình nộp SUBSTR.*
Cho xâu ký tự S, ta có thể lấy ra từ S các ký tự để tạo ra xâu con của nó. Nếu ta lấy ra các ký tự liên tiếp nhau thì ta được xâu con các ký tự liên tiếp. Ta cũng có thể lấy ra lần lượt các ký tự từ đầu xâu về cuối xâu ở vị trí bất kỳ và ghép chúng lại thành xâu theo
thứ tự ấy, lúc đó ta được xâu con các ký tự ở vị trí bất kỳ. Độ dài của xâu con cũng chính là số lượng ký tự trong xâu con. Một xâu là đối xứng nếu đọc nó từ phải sang trái cũng thu được kết quả giống như đọc từ trái sang phải.
Ví dụ: cho xâu S là ‘thi hsg tin hoc cap tinh’, ta có xâu ‘hsg tin hoc’ là một xâu con các ký tự liên tiếp, còn ‘thi tin hoc’ là một xâu con các ký tự ở vị trí bất kỳ. Xâu ‘xaxa’ không phải là xâu đối xứng, xâu ‘xaax’ là xâu đối xứng có độ dài là 4.
Yêu cầu: Cho xâu S, hãy tìm xâu con đối xứng dài nhất? Dữ liệu: vào từ tệp văn bản SUBSTR.INP ghi xâu S. Kết quả: ghi ra tệp văn bản SUBSTR.OUT gồm:
Dòng 1: ghi độ dài của xâu con đối xứng dài nhất gồm các ký tự liên tiếp;
Dòng 2: ghi độ dài của xâu con đối xứng dài nhất gồm các ký tự ở vị trí bất kỳ.
Ví dụ:
SUBSTR.INP
SUBSTR.OUT
Giải thích
xaxaax
4
- Xâu con các ký tự liên tiếp đối xứng dài

5
nhất: xaax (xaxaax)


- Xâu con các ký tự ở vị trí bất kỳ đối


xứng dài nhất: xaxax (xaxaax, xaxaax)


hoặc xaaax (xaxaax)

Bài 12. Điền dấu. Tên file chương trình nộp EXP.*
Cho N số tự nhiên A1, A2, , An. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu “?” có dạng A1? A2? ?An. Cho trước số nguyên S, có cách nào thay các dấu ? bằng dấu + hay dấu – để được một biểu thức số học cho giá trị là S không.
Dữ liệu: vào từ file EXP.inp gồm:
+ Dòng đầu ghi số n là số đội bóng đặt sân bóng (với 1< n < 500)
+ Dòng 2 ghi n số A1, A2, , An (1 < Ai < 50).
+ Dòng 3 là một số S (-25000 < S < 25000)
Kết quả: ghi ra file EXP.out ghi chữ “YES” nếu tồn tại cách thỏa mãn, ra “NO” nếu không tồn tại.
Ví dụ:
EXP.inp
EXP.out
4
YES
1 2 3 4

4

5
NO
2 3 1 4 5

14


MỨC ĐỘ 6: BÀI TẬP CÓ VẬN DỤNG CẤU TRÚC DỮ LIỆU NÂNG CAO
Bài 1. CẶP XÂU ĐỐI XỨNG. Tên file chương trình nộp PALINPAIRS.*
Đền Trần là khu di tích lịch sử đã có từ lâu đời ở Nam Định và là một địa điểm du khách không thể bỏ qua khi ghé thăm mảnh đất này. Mỗi dịp Tết đến xuân về, cứ vào rằm tháng Giêng, nơi đây lại tổ chức khai ấn đền Trần để cầu cho năm mới quốc thái dân an, vạn sự như ý. Đặc biệt, mỗi người đến đây đều mong muốn xin được ấn đền Trần.
Để xin được ấn họ cần trả lời một câu đố. Câu đố là một chuỗi kí tự. Nhiệm vụ của người xin ấn là đếm số cặp xâu đối xứng không giao nhau trong xâu này. Tuy nhiên, vì độ dài xâu quá lớn nên không ai có thể trả lời được câu đố này. Bạn hãy lập trình giải bài toán trên để giúp cho ai cũng có ấn để mang về nhé!
Yêu cầu: Đếm số cặp xâu đối xứng không giao nhau trong xâu này. Cụ thể, đếm số bộ 4 (a,b,c,d) thỏa mãn:
- 1 ≤ a ≤ b < c ≤ d ≤ |S|.
- Sa..b đối xứng và Sc..d đối xứng.
Dữ liệu vào cho trong tệp PALINPAIRS.INP một dòng duy nhất là xâu S gồm các kí tự chữ cái thường.
Kết quả đưa ra tệp PALINPAIRS.OUT một số duy nhất là số lượng bộ 4 thỏa mãn.
Ví dụ:
PALINPAIRS.INP
PALINPAIRS.OUT
aba
3
Giới hạn:
Subtask 1 (25% số điểm): |S| ≤ 50.
Subtask 2 (25% số điểm): |S| ≤ 100.
Subtask 3 (25% số điểm): |S| ≤ 500.
-	Subtask 4 (25% số điểm): |S| ≤ 2000.
Bài 2. Dãy con chung không liền kề dài nhất. Tên file chương trình nộp LNACS.*
Dãy C = c1, c2, ..., ck là dãy con không liền kề của dãy A = a1, a2, ..., am nếu C có thể nhận được bằng cách chọn một dãy các phần tử không liền kề của A, nghĩa là tìm dược dãy các chỉ số i1, i2, ..., ik sao cho:
1 ≤ i1, i2, ..., ik ≤ m;
i1 < i2 - 1, i2 < i3 - 1, ..., ik < ik - 1;
c1 = ai1, c2 = ai2, ck = aik.
Ta gọi độ dài của dãy số là số phần tử của nó. Cho hai dãy: A = a1, a2, ..., am và B = b1, b2, ..., bn
Dãy C được gọi là dãy con chung không liền kề của hai dãy A và B nếu như nó vừa là dãy con không liền kề của A, vừa là dãy con không liền kề của B.
Yêu cầu
Cho hai dãy số A và B. Hãy tìm độ dài của dãy con chung không liền kề dài nhất của hai dãy đã cho.
Dữ liệu
Dòng đầu tiên chứa hai số nguyên dương m và n (2 ≤ m, n ≤ 103) được ghi cách nhau bởi dấu cách, lần lượt là số lượng phần tử của dãy A và dãy B.
Dòng thứ i trong m dòng tiếp theo chứa số nguyên không âm ai (ai ≤ 104), i = 1, 2,
..., m.
Dòng thứ j trong n dòng tiếp theo chứa số nguyên không âm bj (bj ≤ 104), j = 1, 2,
..., n.

Kết quả
Ghi ra trên một dòng duy nhất độ dài của dãy con chung không liền kề dài nhất của
hai dãy A và B.
Ví dụ
LNACS.INP
LNACS.OUT
4 5
2
4

9

2

4

1

9

7

3

4

Bài 3. Dãy con chung bội hai dài nhất. Tên file chương trình nộp LCS2X.*
Dãy C = c1, c2, .., ck được gọi là dãy con của dãy A = a1, a2, .., an nếu C có thể nhận được bằng cách xóa bớt một số phần tử của dãy A và giữ nguyên thứ tự của các phần tử còn lại, nghĩa là tìm được dãy các chỉ số 1 ≤ l1 < l2 <  < lk ≤ n sao cho c1 = a_l1, c2 = a_l2, , ck = a_lk. Ta gọi độ dài của dãy là số phần tử của dãy.
Cho hai dãy A = a1, a2, , am và B = b1, b2, , bn. Dãy C = c1, c2, , ck được gọi là dãy con chung bội hai của dãy A và B nếu C vừa là dãy con của dãy A, vừa là dãy con của dãy B và thỏa mãn điều kiện 2 × ci ≤ ci+1 (i = 1, 2, , k – 1).
Yêu cầu
Cho hai dãy A và B. Hãy tìm độ dài dãy con chung bội hai có độ dài lớn nhất của hai dãy A và B.
Input
Dòng đầu tiên chứa T là số lượng bộ dữ liệu. Tiếp đến là T nhóm dòng, mỗi nhóm cho thông tin về một bộ dữ liệu theo khuôn dạng sau:
Dòng đầu chứa 2 số nguyên dương m và n.
Dòng thứ hai chứa m số nguyên không âm a1, a2, ..., am mỗi số không vượt quá 10^9.
Dòng thứ ba chứa n số nguyên không âm b1, b2, ..., bn mỗi số không vượt quá 10^9.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Giới hạn
30% số test có m, n <= 15.
30% số test khác có m, n <= 150.
có 40% số test còn lại có m, n <= 1500.
Output: Ghi ra T dòng, mỗi dòng ghi một số nguyên là độ dài dãy con chung bội hai dài nhất của dãy A và B tương ứng với bộ dữ liệu vào.
Example
LCS2X.INP
LCS2X.OUT
1
5 5
5 1 6 10 20
1 8 6 10 20
3
Bài 4. Tổng Max. Tên file chương trình nộp Sumseq.*
Cho n số nguyên dương a1,a2..an.Ta cần tìm 3 chỉ số i,j,k (0<i<j<k≤n) để sao cho tổng 2a[i]+3a[j]-4a[k] là lớn nhất.
Yêu cầu: tìm tổng max thỏa mãn điều kiện trên(n≤106).
Input : Vào từ file SUMSEQ.INP gồm:
Dòng đầu: n{số phần tử của dãy}
Dòng hai ghi n số nguyên: a1,a2an{các phần tử của dãy}
Output: Ghi ra file SUMSEQ.OUT kl{tổng max tìm được}
Ví dụ:
SUMSEQ.INP
SUMSEQ.OUT
5
1 3 2 7 1
23
Bài 5. Dãy chung dài nhất của hai dãy số (Bản khó) - Tên file nộp LCSMX.*
Cho hai số nguyên dương M, N và hai dãy số nguyên: a1, a2, ..., am (A) và b1, b2, ,
bn (B). Tìm một dãy dài nhất C nhận được từ A bằng cách xoá đi một số số hạng và cũng nhận được từ B bằng cách xoá đi một số số hạng (nói chung không cùng chỉ số như đối với dãy A). Ta gọi C là dãy con chung dài nhất của hai dãy A, B.
Input: Cho trong file LCS.INP:
Dòng đầu tiên chứa hai số M, N (M < 103; N < 106)
Dòng thứ hai chứa M số a1, a2, ...., am (|ai| < 106 với i=1,2,3,..m)
Dòng thứ ba chứa N số b1, b2, ..., bn (|bi| < 106 với i=1,2,3,..m) Output: Ghi ra file LCS.OUT số K là số lượng số hạng của dãy C
Dòng 2: Dãy các phần tử tương ứng của dãy con chung dài nhất C tìm được
Ví dụ:
LCSMX.INP
LCSMX.OUT
9 9
7
1 2 7 3 4 8 5 6 9
1 2 3 4 5 6 9
1 2 3 4 5 6 7 8 9

Bài 6. Phần thưởng BONUS. Tên file chương trình nộp BONUS.*
Trong cuộc thi lập trình APOLO do công ty GRIS tổ chức, Tuấn đạt được danh hiệu “Coder xuất sắc”. Nhà tài trợ Bin Gate cho phép Tuấn được tự lựa chọn phần thưởng cho mình. Trên khán đài xếp một dãy 𝑛 hộp quà được đánh số thứ tự từ 1 đến n, mặt trước của hộp quà i ghi một số nguyên dương ai tương ứng với giá trị của món quà chứa trong nó, nghĩa là ai càng lớn thì món quà càng có giá trị cao. Tuấn được phép chọn các hộp quà tuỳ ý trong n hộp quà, tuy nhiên Tuấn không được phép chọn 𝑘 hộp quà liền nhau, đó là thử thách nhỏ của nhà tài trợ.
6
10
10
13
10
10
1	2	3	4	5	6
Yêu cầu: Bạn hãy cho biết Tuấn có thể chọn những hộp quà nào để tổng giá trị của các hộp quà mà Tuấn chọn là lớn nhất?.
Dữ liệu: Vào từ file văn bản BONUS.INP
Dòng 1 chứa hai số nguyên n và k (1≤ 𝑛 ≤ 106;2 ≤ 𝑘 ≤ 106);
Dòng 2 chứa n số nguyên dương a1, a2, , an tương ứng là giá trị của n hộp quà của nhà tài trợ theo thứ tự liệt kê từ hộp quà thứ nhất tới hộp quà thứ 𝑛.
Kết quả: Ghi ra file văn bản BONUS.OUT một số duy nhất là tổng giá trị lớn nhất của các hộp quà mà Tuấn có thể nhận được.
Ví dụ:
BONUS.INP
BONUS.OUT
6	3
6 10 10 13 10 10
40
Lưu ý: Các số nằm trên cùng một dòng trong các tệp dữ liệu vào được đặt cách nhau dấu cách.
Giới hạn:
Có 20/40 test với 1 < n, k < 1000, tương ứng 1,5 điểm;
Có 20/40 test với 1000 < n, k < 106 , tương ứng 1,5 điểm;
Bài 7. Phần thưởng BONUS2. Tên file chương trình nộp BONUS2.*
Trong cuộc thi Olympic Tin học của tỉnh BG, phần thưởng cho người thắng cuộc là tổng trọng số của tất cả các dãy con liên tiếp trong dãy số a cho trước.
Định nghĩa trọng số của một dãy số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy.
Yêu cầu: Cho dãy số nguyên dương a = (a1, a2,  , an). Hãy tìm phần thưởng cho người thắng cuộc.
Ví dụ với a = (1, 2, 3), những dãy con gồm các phần tử liên tiếp trong a là:
Dãy rỗng và các dãy có 1 phần tử (1), (2), (3) đều có trọng số 0;
Dãy (1, 2) và dãy (2, 3) đều có trọng số 1;
Dãy (1, 2, 3) có trọng số 2.
Phần thưởng cho người thắng cuộc bằng 0+1+1+2=4.
BONUS2.INP
BONUS2.OUT
3
1 2 3
4
4
3 1 7 2
31

Dữ liệu: Vào từ tệp văn bản BONUS2.INP có cấu trúc:
Dòng 1: Ghi số nguyên dương n (n < 106);
Dòng 2: Ghi n số nguyên dương a1, a2, , an có giá trị không vượt quá 106.
Kết quả: Ghi vào tệp văn bản BONUS2.OUT một số nguyên duy nhất là kết quả tìm được.
Giới hạn:
Có 10/30 test, tương ứng với 1 điểm có n < 103;
Có 20/30 test, tương ứng với 2 điểm có n < 106.
Bài 8. Dãy con tăng trọng số lớn nhất. Tên file chương trình nộp IS.*
Cho dãy số nguyên dương A=(a1, a2, , an), phần tử ai có trọng số là wi. Mỗi dãy (ai1, ai2, , aik) thỏa mãn:
được gọi là một dãy con tăng của dãy A. Chú ý rằng dãy chỉ gồm duy nhất một phần tử của A cũng được gọi là một dãy con tăng của dãy A.
Yêu cầu: Trong số các dãy con tăng của dãy A hãy chỉ ra một dãy có tổng trọng số các phần tử là lớn nhất có thể.
Dữ liệu: Vào từ file văn bản IS.INP
+ Dòng 1 chứa số nguyên dương n < 105
+ Dòng 2 chứa n số nguyên dương a1, a2, , an theo đúng thứ tự đó ("i: |ai| < 109)
+ Dòng 3 chứa n số nguyên dương w1, w2, , wn theo đúng thứ tự đó ("i: wi <109)
Kết quả: Ghi ra file văn bản IS.OUT
+ Dòng 1 ghi số phần tử trong dãy con tăng tìm được (m)
+ Dòng 2 ghi m chỉ số của các phần tử được chọn theo thứ tự tăng dần
Các số trên một dòng của Input/Output files được/phải ghi cách nhau ít nhất một dấu cách
Ví dụ:
IS.INP
IS.OUT
10








6





1 2 3
6
4 5
9
6 7
8



1
2
3
5
6
7
11 22
33
66
44
55
999
66
77
88







PHỤ LỤC SỐ 3: BIÊN BẢN XÁC NHẬN ÁP DỤNG GIẢI PHÁP Ở CÁC TRƯỜNG THPT TRONG TỈNH
Trường THPT Thái Thuận
Trường THPT DTNT Tỉnh
éø aï” ê”}iśi tag ș yța t§p pb§a ibœ m c aę tr ^g	: d^a^s*p:°!°* a*°!
liob”m6n Tin b”gc .
- E‘«i»ii: duiti•iØò«ägs.ë»-«
ia, Lp”tR cù?'ștțc ùhc oçN«
Tifï hpc" tü kÌşi thành Up tíèn dy d'õi
- usvètt»•g„g'a‹¡•s@*!ècsa:Ng*à^ D«***-"ñ""‘°:
Trường THPT Ngô Sĩ Liên
CONG HOÁ XÃ HQl CHÙ NGHİA Vl ËpT NAM
Dgc_1ßp_—Te dn- Hash phùc
VÁN BÁN XÁC NHAN ÛRG DING fiÁNG KIÉN
£2áe dø.ng bh i t8{› luy4n tip pt 3n theø múc dÿ‘trnug búi d ining bye sixth Mini
tinh mon Tin bgc
i. vòcu'vc iirnc u9Nc siNfi K‹aN
Tin	tÊ chic: Trirònq TI-íPT Ngó Sï Lîćn
BJs chí. So 143 duòng Ngíi Gia °I“ą, phuónp Ngíi Quyen. thánh pho Bac Giang,
tùih Bãc Giaøg
Øę vB tdo oguòi dfr•g dÉu to chúc: Luu Yün Xuán — Hiçu trudcg.
II. LKȚI ÎCII CÎJA VI;ČC Ú'NÜ DUNG SÁNC KïÈ.N
Ding chił'4gu}'en Tht Hgp vń dong chi Thún Tîq ßB Tnzózig TITPT Chuyè”n BÉc Giang dă lièn fie vói nhónz'Tin Age - Trzròzig TlJï'T'Ngô SI Lien de hÖ trg vičc ùng dțmg mpt giài phu:p N \u 'sïînj; kiln vśn yi/îriIš cłțy nn 1i hçc Minh gińi cÉy Minh oión Tin hpc lóp 11.
Ban łãnh dęo nhà trumg dà '*^^B Ś Chn dong chí Lč Anh TuB^ IB *^ *Ién Tin
hpc - TPCłvł truóng THFT Ngó St Lidn) tit hźnt źp d\zzg cóc giàî pl›śp cûa sing kìen “Căc dpug bãi @p ghżn theo múc dȘ tmng bui duchg hoc s›nh giói tinh món Tic boc' tù kbi thżnh lap tien diz dği ruy {thżng 1 1 n”ùn *O*3), nkm hgc *023-2024:
Giei phăp dugc áp dynş chu dui luçng hę sinh iew ttğl luden 1in hoc:
Sttt
Hq vè tin
cup


MgiøenTnngDuy1.nwg
1 lA I
Z
T İn Dúc D;rt
HA ł
3
Bùi Ngpc	°8
I lfil

1
Nam ?p”c
2D23 - 2024
5á- l«\<g ›1s II+»m gia	| ”sü fr:ja‹g I‹S-ôgt giai ühi- ciiú-
:D3
2. Kei qiiá thi chpn hpc sính, gióí càp tinh
Vói k§i quíi nhu titia‘,.c the noi viq‘c áp ding: :iii¿n: 'CÜ Õ;¡hg bài p phân ihéõ iiiin &i:nõng bói dtidn h9c sinh:gtói tinh in6n Tin h * cho tiiay dst thú dm¡ r ket quà iihiÍt djnh.dáng khích Ip, ‘hi›c:sirili có thói dç hçic tip nghiúm tííc. chu dgnd va ty tin:ván:.kitá nitrig.cúa bán thàn, lám thay doi.te:duy. thái dp’ hqc tjp; tag húng thúi/trón h‹¡›i Jp:và hlnií tliánh riàng luc phaoi’ ch‘at chõ hpc sinh trõn’g.qy’é.trinh ’úqc t}ap, bu c tu có””fii§u. ïiú üíÏng rihu ó üú dieu.Ü@'dÏ pó the nfiàzt i@ng. h”on núa, ph”ú hgp vói doi tuqr;g hoc sinh giói boc”TIJT'T tzén dts.bún tinh B@ ”Gian góp p@n nóng cao hi ”u qué Lgc @ mon Tiri hgc nói cbung vè m6n Up Irtnh nói ri5ng
TO c	*UNC	CMuÉN
HIÊU TRUÔNQ
TÀI LIỆU THAM KHẢO
Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Nguyễn Minh Hoàng, Nguyễn Thanh Hùng – Tài liệu giáo khoa Chuyên Tin Quyển 1 – Nxb Giáo dục Việt Nam
Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Nguyễn Minh Hoàng, Nguyễn Thanh Hùng – Tài liệu giáo khoa Chuyên Tin Quyển 2 – Nxb Giáo dục Việt Nam
Đỗ Xuân Lôi - Cấu trúc dữ liệu và Giải thuật – Nxb ĐHQG Hà Nội.
Nguyễn Đức Nghĩa - Cấu trúc dữ liệu và Giải thuật – Trung tâm TBVP 123 Lương Thế Vinh.
Nguyễn Xuân My – Một số vấn đề chọn lọc trong môn Tin học – Nxb Giáo dục.
Nguyễn Hoàng Phú – Ngôn ngữ lập trình C++, tập 1, 2, 3 – Nxb Thanh Hóa, 2018
Các trang web luyện tập cho học sinh và giáo viên tin