1
SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH BÌNH ĐỊNH
KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THCS
NĂM HỌC 2023-2024
Môn thi:TINHỌC
Bài 1. Số anh em (5,0 điểm)
Cho số tự nhiên A có N chữ số. Số anh em của một số A là số nhỏ nhất nhận được từ việc
thay đổi vị trí các chữ số của số A và lớn hơn số A
Cho số A, hãy tìm số anh em của số A
Dữ liệu: Vào từ file BRNUM.INP có cấu trúc:
Dòng đầu tiên là giá trị N (1 <N≤2*106).
Dòng thứ hai là số tự nhiên A
Kết quả: Ghi ra file BRNUM.OUT như sau:
Nếu có nghiệm thì ghi số anh em của số A.
Nếu vô nghiệm thì ghi chữ số 0.
Ví dụ:
BRNUM. INP
BRNUM.OUT
6
526431
531246
4
9876
0
Bài 2. Mã giảm giá (5,0 điểm)
Để kỷ niệm 10 năm thành lập, trung tâm thương mại S đã tổ chức một đợt siêu khuyến mãi
và tặng cho khách hàng của mình rất nhiều mã giảm giá khác nhau. Bạn là khách hàng kim
cương của S và đã được tặng M mã giảm giá. Mỗi mã giảm giá sẽ được dùng cho một sản
phẩm nào đó nếu giá tiền của sản phẩm không nhỏ hơn một con số nhất định.
Cụ thể hơn, bạn có thể sử dụng mã giảm giá thứ í nếu giá trị của sản phẩm không nhỏ hơn
Ri đồng và khi sử dụng mã giảm giá bạn sẽ được giảm D, đồng. Mỗi sản phẩm chỉ được áp
dụng tối đa một mã giảm giá và mỗi mã giảm giá chỉ được sử dụng tối đa một lần cho một
sản phẩm duy nhất. Bạn có dự định sẽ mua N sản phẩm trong dịp này. Bạn hãy tìm cách sử
dụng những mã giảm giả để bỏ ra số tiền nhỏ nhất có thể mua toàn bộ N sản phẩm.
Dữ liệu: Vào từ file COUPON.INP có cấu trúc gồm 3 dòng
- Dòng đầu tiên gồm hai số nguyên dương N và M (N,M≤100), lần lượt là số sản phẩm bạn
muốn mua và số mã giảm giá bạn được nhận
- Dòng thứ hai gồm N số nguyên dương P1. P2. P3 lần lượt là giả tiền của N sản phẩm bạn
muốn mua.
- Dòng thứ ba gồm M số nguyên dương R1, R2, Rỵ lần lượt là giả tiền tối thiểu để áp dụng
các mã giảm giá.
- Dòng thứ tư gồm M số nguyên dương D1, D2, Dg lẫn lượt là số tiền bạn sẽ được giảm nếu
áp dụng mã giảm giá tương ứng.
- Dữ liệu đảm bảo Di ≤ Ri, với mọi i từ 1 tới M.
2
- Tất cả các số trong đã liệu đầu vào sẽ không vượt quá 105
Kết quả: Ghi ra file COUPON.OUT gồm một số nguyên duy nhất là tổng số tiền ít nhất phải
bỏ ra để mua toàn bộ N sản phẩm.
Ví dụ:
COUPON. INP
COUPON. OUT
1 2
3
2 3
1 2
1
3 1
3 5 7
5
4
11
Giải thích:
- Ở ví dụ đầu tiên, có 1 sản phẩm duy nhất có giá tiền là 3. Bạn có 2 mã giảm giá lần lượt
như sau:
+ Mã giảm giá thứ nhất yêu cầu sản phẩm có giá tiền tối thiểu là 2 và nếu sử dụng sẽ giảm
giá của sản phẩm đó đi 1.
+ Mã giảm giá thứ hai yêu cầu sản phẩm có giả tiền tối thiểu là 3 và nếu sử dụng sẽ giảm
giá của sản phẩm đó đi 2.
=> Để giảm được nhiều tiền nhất, bạn có thể sử dụng mã giảm giả thứ hai cho sản phẩm.
Khi đó tổng số tiền phải bỏ ra sẽ trở thành 3-2=1.
- Ở ví dụ thứ hai, có 3 sản phẩm và 1 mã giảm giá duy nhất. Bạn có thể sử dụng mã giảm
giá đó cho sản phẩm có giá tiền là 5 hoặc 7 đều được. Khi đó, tổng số tiền bạn phải trả sẽ là
3+5+7-4=11. Lưu ý rằng, bạn không thể áp dụng mã giảm giá cho cả hai sản phẩm này vì
một mã giảm giả chỉ có thể sử dụng được một lần cho một sản phẩm duy nhất.
Bài 3. Chuyển đổi xâu (5,0 điểm)
Cho 3 xâu ký tự A, B, C. Với một thao tác, bạn có thể di chuyển một ký tự bất kỳ ở xâu C đi
và đặt nó vào một vị trí bất kỳ ở xâu A.
Ví dụ nếu xâu A là abcd và xâu C là efg, bạn có thể lấy đi ký tự ở của xãu C và đặt nó vào
trước xâu A để tạo thành xâu eabcd, hoặc đặt vào giữa xâu A để tạo thành abecd hay abced,
hoặc đặt vào cuối xảu A để tạo thành xâu abcde. Sau thao tác trên, xâu C sẽ trở thành fg
(không còn ký tự e).
Để chuyển đổi xâu, bạn có thể không áp dụng thao tác này hoặc áp dụng ít nhất một lần.
Với mỗi bộ 3 xâu ký tự A, B, C, hãy cho biết có thể chuyển đổi xâu A thành xâu b hay
không?
Dữ liệu: Vào từ file STRING.INP có cấu trúc:
- Dòng đầu tiên gồm một số nguyên dương Q (1 ≤ Q≤ 20) là số bộ câu hỏi mà bạn cần trả
lời.
- Các dòng tiếp theo là mô tả của Q bộ câu hỏi, trong đó mỗi bộ gồm 3 dòng gồm lần lượt là
3 xâu ký tự A, B,C.
- Dữ liệu đảm bảo các xâu ký tự chỉ gồm các ký tự chữ tiếng anh viết thường.
- Độ dài của các xâu không vượt quá 100.
3
Kết quả: Ghi ra file STRING OUT gồm 2 dòng, dòng thứ i là câu trả lời cho bộ câu hỏi thứ
i. Nếu có thể chuyển đổi xảu A thành xâu B, thì in ra "YES" (không có dấu ngoặc kép),
ngược lại thi in ra "NO".
Ví dụ:
STRING. INP
STRING.OUT
4
abc
abc
def
ab
ba
ababb
ab
babc
cbbaad
ab
abc
ab
YES
NO
YES
NO
Giải thích:
- Ở ví dụ đầu tiên, hai xâu A và B đã giống nhau (cùng là abc) nên ta không cần áp dụng
thao tác nào
- Ở ví dụ thứ hai, không thể biến đổi xâu A thành xâu B.
- Ở ví dụ thứ ba, ta có thể thực hiện biến đổi như sau:
A="ab", C"cbbaad"
A"bab", C= "cbaad"
A"babc", C= "baad"
Bài 4. Phần thường (5,0 điểm)
Sau khi tham gia kỳ thi học sinh giỏi cấp tỉnh lớp 9 THCS trở về, các học sinh trong đội
tuyển môn Tin học khá mệt mỏi sau thời gian ôn tập. Cô giáo phụ trách đội tuyển muốn
dành tặng các bạn một số phần thường. Tuy nhiên, để tăng tính giải trí, cô đã tạo ra một trò
chơi. Phần thường được trao cho người có điểm cao nhất.
Cách chơi như sau: Sân chơi là một hình chữ nhật đơn vị có kích thước m*n. Học sinh chọn
một ô bất kỳ ở cột 1 và bước vào ô đó. Sau đó bước vào ô ở cột liền kề bên phải theo hướng
chéo lên một ở hoặc sang phải một ô hoặc chéo đưới một ở. Tức là, nếu học sinh ở ô có tọa
độ (i,j) thì có thể bước sang các ô có tọa độ (i - 1, j + 1) hoặc (i,j + 1) hoặc (i + 1, j + 1)
Biết cách tính điểm khi bước vào ô có tọa độ (i,j) như sau: gọi a[i,j] là giá trị tại ô (i,j). Nếu
a[i,j] là số không âm thì tổng điểm của học sinh tăng lên a[i,j], ngược lại nếu a[i,j] là số âm
thì tổng điểm của học sinh giảm đi a[i,j] lần. Khi học sinh bước đến một trong các ở ở cột n
thì sau khi tỉnh điểm xong sẽ đứng lại, hoàn thành lượt chơi.
Ví dụ:
4
-2
6
-2
-2
3
2
-3
1
2
2
1
4
Với hình chữ nhật bên trên, ta có nhiều cách đi từ cột 1 đến cột 5
- Đi vào từ ô (1,1) => (2,2) => (1,3) => (1,4) => (1,5) thì tổng điểm bằng:
((4 + 3)/3)+6)/2 = 4.167
- Dì từ vào ô (1,1) => (2,2) => (1,3 ) => (3, 4) -> (3, 5) thì tổng điểm bằng:
(4 + 3)/3 + 2 + 1 = 5.3333
Yêu cầu: Hãy tìm cách đi để có tổng điểm cao nhất
Dữ liệu: Vào từ file GIFT.INP gồm nhiều dòng:
- Dòng 1: Ghi hai số nguyên dương m, n là kích thước của lưới ô vuông, m < 300, n<300
- m dòng tiếp theo, mỗi dòng ghi n số nguyên a[i,j], với a[i,j] < 105
Kết quả: Ghi ra file GIFT OUT tổng điểm cao nhất tìm quả được làm tròn đến 3 chữ số thập
phân.
GIFT INP
GIFT OUT
3 5
4 -2 -3 6 -2
-2 3 -9 2 -3
1 2 -3 2 1
5.333
HẾT