TIN HỌC DÀNH CHO HỌC SINH PHỔ THÔNG NĂNG KHIẾU
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 (4.55 MB, 153 trang )
TRƢỜNG PHỔ THÔNG NĂNG KHIẾU – ĐHQG TPHCM
HIGH SCHOOL FOR THE GIFTED – VNU HCM
SÁCH TIN HỌC
DÀNH CHO HỌC
SINH PTNK
Tiến sĩ Đào Duy Nam
PTNK – ĐHQG TPHCM
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
Làm trai phải lạ ở trên đời,
Há để càn khôn tự chuyển dời
Sách Tin Học dành cho học sinh PTNK
Page 2
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
MỤC LỤC
ĐỒNG HỒ BÁO THỨC ............................................................................................................................... 6
BÁO THỨC .................................................................................................................................................. 7
PHẢN VẬT CHẤT....................................................................................................................................... 8
CÁNH ĐỒNG CỎ ...................................................................................................................................... 10
TÁC GIẢ .................................................................................................................................................... 11
TỔNG NHỎ NHẤT .................................................................................................................................... 12
ĐẤU GIÁ .................................................................................................................................................... 13
DÃY SỐ TRUNG BÌNH CỘNG ................................................................................................................ 14
THU NHẶT BÓNG .................................................................................................................................... 15
HỆ ĐẾM ..................................................................................................................................................... 16
HẢI LY ....................................................................................................................................................... 17
ĐƢỜNG ĐI BFS......................................................................................................................................... 19
CẦU PHAO ................................................................................................................................................ 20
CẦU KHỈ .................................................................................................................................................... 21
SỐ ĐẸP ....................................................................................................................................................... 23
XÂU KÝ TỰ NGOẶC ............................................................................................................................... 24
KHÔI PHỤC NGOẶC ................................................................................................................................ 25
LỊCH BYTELAND ..................................................................................................................................... 26
HỘP KẸO ................................................................................................................................................... 27
ĐUA XE ..................................................................................................................................................... 28
PHỊNG THỦ PHÁO ĐÀI.......................................................................................................................... 29
BÀN CỜ ..................................................................................................................................................... 30
SƠ CƠ LA .................................................................................................................................................. 31
RẠP CHIẾU BĨNG ................................................................................................................................... 32
GIAO THƠNG THÀNH PHỐ.................................................................................................................... 33
MÃ HÓA ĐA LỚP ..................................................................................................................................... 34
CÁC ĐỒNG XU ......................................................................................................................................... 36
LẮP RÁP MÁY TÍNH ............................................................................................................................... 37
ĐIỀU HỊA NHIỆT ĐỘ.............................................................................................................................. 38
CÁC THÀNH PHẦN LIÊN THÔNG ........................................................................................................ 39
DÃY LIÊN TIẾP ........................................................................................................................................ 40
BAO LỒI .................................................................................................................................................... 41
BỎNG NẾP ................................................................................................................................................. 42
VƢỢT SUỐI ............................................................................................................................................... 43
ĐƢỜNG THỦY .......................................................................................................................................... 44
CẮT VẢI .................................................................................................................................................... 45
NGÀY THÁNG .......................................................................................................................................... 46
ƢỚC SỐ ...................................................................................................................................................... 48
GIẢI MÃ SỐ............................................................................................................................................... 49
KHOẢNG CÁCH SỐ ................................................................................................................................. 50
LÂY NHIỄM EBOLA ................................................................................................................................ 51
BẦU CỬ ..................................................................................................................................................... 52
XÓA SỐ ...................................................................................................................................................... 53
EQUATION ................................................................................................................................................ 54
XÂY DỰNG HÀNG RÀO ......................................................................................................................... 55
Sách Tin Học dành cho học sinh PTNK
Page 3
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
HỘI KHỎE PHÙ ĐỔNG ............................................................................................................................ 56
TÔ MÀU ..................................................................................................................................................... 57
XÂU FIBONACCI ..................................................................................................................................... 58
XÂU FIBONACCI 2 .................................................................................................................................. 59
LỌC SỐ ...................................................................................................................................................... 60
ĐÁNH CÁ TRÊN SÔNG KAMA .............................................................................................................. 61
TẶNG HOA ................................................................................................................................................ 62
ĐẶT QUẦY PHỤC VỤ ............................................................................................................................. 63
THỨ SÁU NGÀY 13.................................................................................................................................. 64
ẾCH ............................................................................................................................................................ 65
ẾCH ĐỘT BIẾN GEN ................................................................................................................................ 66
HÀM SỐ ..................................................................................................................................................... 67
GEN VI KHUẨN ........................................................................................................................................ 68
QUÀ TẶNG ................................................................................................................................................ 69
SẾU ............................................................................................................................................................. 70
BÀI TẬP VỀ NHÀ ..................................................................................................................................... 71
SỐ NGUYÊN TỐ ....................................................................................................................................... 72
THẦN TƢỢNG .......................................................................................................................................... 73
DÃY CON ĐƠN ĐIỆU TĂNG DÀI NHẤT .............................................................................................. 74
TỐI GIẢN PHÂN SỐ ................................................................................................................................. 75
BA LÔ DU LỊCH........................................................................................................................................ 76
TÁO QUÂN ................................................................................................................................................ 77
HIỆN SỐ BẰNG ĐÈN LED....................................................................................................................... 78
NGƠN NGỮ ............................................................................................................................................... 79
KHĨA SỐ ................................................................................................................................................... 80
THÀNH PHỐ MAY MẮN ......................................................................................................................... 81
LŨY THỪA CỦA 2.................................................................................................................................... 82
ĐƢỜNG VÀNH ĐAI ................................................................................................................................. 83
CÁC THỎI NAM CHÂM .......................................................................................................................... 84
TẦN SỐ XUẤT HIỆN NHIỀU NHẤT ...................................................................................................... 85
DƢA HẤU Ở CÁNH ĐỒNG KỲ DIỆU .................................................................................................... 86
HỖN HỢP ................................................................................................................................................... 87
MODULO ................................................................................................................................................... 88
TIỀN ........................................................................................................................................................... 89
KHẢM TRANH.......................................................................................................................................... 90
ĐẶT THÁP PHÒNG THỦ Ở CÁC NGỌN NÚI ....................................................................................... 91
MP3 PLAYER ............................................................................................................................................ 96
NGÔN NGỮ MUMBA............................................................................................................................... 97
CÁCH TIẾP THEO .................................................................................................................................... 98
KHÔNG ĐƠN GIẢN ................................................................................................................................. 99
NTFS ......................................................................................................................................................... 100
SỐ THÂN THIỆN .................................................................................................................................... 101
NUMPOS .................................................................................................................................................. 102
TRÕ CHƠI VỚI DÃY SỐ ........................................................................................................................ 103
CON SỐ BÍ ẨN ........................................................................................................................................ 104
LUYỆN TẬP DỰ THI HỌC SINH GIỎI ................................................................................................. 105
SẮP XẾP ẢO ............................................................................................................................................ 106
HỆ ĐIỀU HÀNH ...................................................................................................................................... 108
Sách Tin Học dành cho học sinh PTNK
Page 4
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
SỐ ĐỐI XỨNG......................................................................................................................................... 109
TRƠNG XE .............................................................................................................................................. 110
ĐỖ XE ...................................................................................................................................................... 111
DỊ TÌM MẬT KHẨU .............................................................................................................................. 112
ĐỒNG DIỄN ............................................................................................................................................ 113
GIỜ THỂ DỤC ......................................................................................................................................... 114
ĐA GIÁC .................................................................................................................................................. 115
PHẦN THƢỞNG...................................................................................................................................... 116
BÌA ĐỤC LỖ ............................................................................................................................................ 117
ĐƢỜNG CHẠY........................................................................................................................................ 118
ROBOT DI CHUYỂN .............................................................................................................................. 119
THỰC NGHIỆM KỸ THUẬT ROBOT ................................................................................................... 120
RÔ BỐT .................................................................................................................................................... 122
QUAY BẢNG ........................................................................................................................................... 123
THAM QUAN THÀNH PHỐ .................................................................................................................. 124
VỆ TINH................................................................................................................................................... 125
DÃY SỐ .................................................................................................................................................... 126
DÃY SỐ .................................................................................................................................................... 127
CÁC MÁY CHỦ Ở SAO THỦY.............................................................................................................. 128
BẢY CHỮ SỐ .......................................................................................................................................... 130
BÁN HÀNG.............................................................................................................................................. 131
ỐC SÊN .................................................................................................................................................... 132
GA HÀNG HÓA....................................................................................................................................... 133
KẾT QUẢ ĐẸP......................................................................................................................................... 134
CHÒM SAO.............................................................................................................................................. 135
THIẾT BỊ KĨ THUẬT SỐ ........................................................................................................................ 137
TỔNG ....................................................................................................................................................... 138
MUA VÉ XE............................................................................................................................................. 139
XÂY THÁP .............................................................................................................................................. 140
ĐƢỜNG TRƢỢT ..................................................................................................................................... 141
TÀU ĐIỆN ................................................................................................................................................ 142
QUAY XÂU KÝ TỰ ................................................................................................................................ 143
CHÌA KHĨA TAM GIÁC ........................................................................................................................ 144
DÃ NGOẠI ............................................................................................................................................... 145
MẠNG GIAO THÔNG ............................................................................................................................ 146
SỐ SINH ĐÔI ........................................................................................................................................... 147
ĐIỀU KHIỂN MÁY QUAY PHIM .......................................................................................................... 148
PHÉP TÍNH XOR ..................................................................................................................................... 150
TƠ MÀU ................................................................................................................................................... 151
D Y DẪN ................................................................................................................................................ 152
TỪ DÀI NHẤT ......................................................................................................................................... 153
Sách Tin Học dành cho học sinh PTNK
Page 5
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
ĐỒNG HỒ BÁO THỨC
An rất mê đồng hồ loại hiển thị bằng số điện tử sử dụng 7 đèn LED để biểu diễn các số từ 0 đến
9 nhƣ hình bên dƣới.
An thƣờng mân mê chỉnh chiếc đồng hồ xinh xắn của mình để đặt báo thức vào mỗi tối. Đêm
qua cơ bé đã mơ về chiếc đồng hồ yêu quý của mình, nhƣng khơng may khi tỉnh dậy lại qn
thời gian đã hiển thị trên đồng hồ mà chỉ còn nhớ số vạch LED hiển thị
trên đồng hồ.
Thời gian hiển thị trên đồng hồ của An đƣợc biểu diễn bởi 4 chữ số, 2
chữ số cho giờ và 2 chữ số cho phút, và đƣợc thiết lập hiển thị ở chế độ 24h. Ví dụ hình bên biểu
diễn cho 9h30 (có số 0 ở đầu).
Dữ liệu: vào từ tập tin văn bản ALARM.INP số nguyên
là số vạch hiển thị trên
đồng hồ.
Kết quả: xuất ra tập tin văn bản ALARM.OUT 5 kí tự hiển thị theo định dạng “hh:mm” là thời
gian hợp lệ hiển thị trên đồng hồ
.
-
Nếu có nhiều kết quả thì in ra kết quả bất kỳ
-
Nếu khơng tìm đƣợc kết quả thì in ra thơng báo “Impossible”
Ví dụ:
ALARM.INP
23
ALARM.OUT
09:30
ALARM.INP
28
Sách Tin Học dành cho học sinh PTNK
ALARM.OUT
Impossible
Page 6
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
BÁO THỨC
Mỗi sáng, khi tiếng chuông đồng hồ báo thức vang lên, Steve truồi ra khỏi giƣờng rồi tất bật
chuẩn bị đi học trong trạng mơ màng ngái ngủ. Do đãng trí, đôi khi Steve vẫn để chuông cả vào
chủ nhật. Tuy vậy điều đó cũng khơng làm Steve phải phiền lịng nhiều. Thật là thú vị khi đƣợc
nằm trên giƣờng đệm êm ấm cho đến khi thực sự tỉnh ngủ. Steve ƣớc gì ngày nào cũng đƣợc nhƣ
vậy. Một ngƣời bạn đã mách cho Steve một giải pháp đơn giản: đặt chuông sớm 45 phút và
Steve làm theo lời khuyên.
Đồng hồ của Steve thuộc loại 24giờ, nghĩa là sau 23 giờ 59 phút sẽ là 00 giờ 00 phút.
Yêu cầu: Cho h và m là giờ và phút mà Steve cần dậy. Hãy xác định x và y – giờ và phút Steve
cần dặt báo thức theo lời khuyên của bạn bè.
Dữ liệu: Vào từ file văn bản ALARM.INP gồm một dòng chứ 2 số nguyên h và m.
Kết quả: Đƣa ra file văn bản ALARM.OUT trên một dòng hai số nguyên x và y.
Ví dụ:
ALARM.INP
0 30
Sách Tin Học dành cho học sinh PTNK
ALARM.OUT
23 45
Page 7
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
PHẢN VẬT CHẤT
Công ty kiểm tra công nghệ nhận phản vật chất sử dụng trong chất lƣợng nhiên liệu trong tàu vũ
trụ liên hành tinh. Phản vật chất nhận đƣợc trong kết quả của các thí nghiệm đặc biệt trong lị
phản ứng.
Đƣợc biết n loại thí nghiệm, diễn ra để nhận phản vật chất. Trong kết quả diễn ra thử nghiệm thứ
loại thứ i trong bể chứa lò phản ứng đƣợc thêm vào từ li đến ri gram phản vật chất. Từ việc đảm
bảo an toàn nghiêm cấm đƣa vào bể chứa lò phản ứng nhiều hơn a gram phản vật chất.
Chi phí để tiến hành thí nghiệm loại thứ i là ci, cịn chi phí của một gram phản vật chất nhận
đƣợc là 109.
Nếu sau khi tiến hành thí nghiệm trong bể chứa hình thành t gram phản vật chất, cịn tổng chi phí
tiến hành thí nghiệm trong lị phản ứng là s, thì lợi nhuận đƣợc xác định theo cơng thức
(t . 109 – s ). Công ty cần phát triển chiến lƣợc tiến hành thí nghiệm cho phép nhận đƣợc lợi
nhuận lớn nhất mà đảm bảo có thể nhận đƣợc.
Sự phụ thuộc vào kết quả của chiến lƣợc thí nghiệm trƣớc xác định thí nghiệm loại nào tiến hành
hoặc quyết định bỏ thực nghiệm thí nghiệm. Chiến lƣợc cho phép đảm bảo nhận đƣợc lợi nhuận
x, nếu trong bất kỳ kết quả tiến hành thí nghiệm: đầu tiên, trong bể chứa lị phản ứng đƣợc chỉ ra
khơng nhiều hơn a gram phản vật chất, thứ hai lợi nhuận đạt đƣợc khơng nhỏ hơn x.
Ví dụ, có thể chỉ một loại thí nghiệm làm ra từ 4 đến 6 gram phản vật chất, chi phí cho nó là 10,
cịn cơng suất bể chứa đạt đƣợc 17 gram. Khi đó sau hai lần tiến hành thí nghiệm trong bể có từ
8 đến 12 gram phản vật chất. Nếu nhận 12 gram phản vật chất thì khơng thể tiến hành thí nghiệm
thêm nữa nhƣ trong trƣờng hợp nhận 6 gram phản vật chất bể chứa có thể bị tràn. Các trƣờng
hợp cịn lại có thể tiến hành thí nghiệm trong ba lần và nhận đƣợc từ 12 đến 17 gram phản vật
chất. Trong trƣờng hợp xấu nhất tiến hành thí nghiệm ba lần chi phí là 30, lợi nhuận
( 12 . 109 – 30 ) = 11 999 999 970.
Yêu cầu: Viết chƣơng trình xác định lợi nhuận lớn nhất x, mà đảm bảo có thể nhận đƣợc.
Dữ liệu vào
Dịng đầu tiên chứa hai số nguyên n – số lƣợng các loại thí nghiệm và a – số lƣợng phản vật chất
lớn nhất cho phép trong bể chứa (
Sách Tin Học dành cho học sinh PTNK
100 , 1 ≤ a ≤ 2 000 000 ).
Page 8
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
Tiếp theo n dòng chứa ba số nguyên li, ri và ci – số lƣợng nhỏ nhất, lớn nhất phản vật chất nhận
đƣợc trong kết quả thí nghiệm loại i, và chi phí của thí nghiệm loại này ( 0 ≤ li ≤ ri ≤ a, 0 ≤ ci ≤
100 ).
Dữ liệu ra
Đƣa ra một số nguyên x là lợi nhuận lớn nhất mà đảm bảo có thể nhận đƣợc.
Ví dụ:
ANTI.INP
1 17
ANTI.OUT
11999999970
4 6 10
2 11
9999999890
2 2 100
355
Sách Tin Học dành cho học sinh PTNK
Page 9
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
CÁNH ĐỒNG CỎ
Ngƣời ta chia một cánh đồng hình chữ nhật thành
ơ vng đơn vị có kích thƣớc bằng
. Tại mỗi ơ vuông đơn vị, ngƣời ta trồng cỏ hoặc để trống dành chỗ cho
nhau
lối đi. Ban đầu cỏ đƣợc trồng để chia cánh đồng thành rất nhiều vùng khác nhau, ngăn cách giữa
các vùng đất trồng cỏ là các lối đi. Tuy nhiên do giống cỏ dại phát triển rất nhanh nên sau một
thời gian, một số ô của lối đi đã bị cỏ mọc phủ lên làm một số vùng cỏ khác nhau trƣớc đây bị
sáp nhập lại, 2 vùng cỏ bị sáp nhập nếu chúng tồn tại 2 ô vng đơn
vị có chung cạnh với nhau.
Thơng tin về các vùng cỏ trên cánh đồng đƣợc vệ tinh ghi nhận lại
dƣới dạng một bản đồ với các kí hiệu sau: 1 dấu * thể hiện vùng cỏ
mọc trên một ô vuông đơn vị, 1 dấu # thể hiện 1 ô vng đơn vị
dành làm lối đi. Ví dụ dƣới đây minh họa kết quả ghi nhận của vệ
******##*******
*****##********
******#######**
#######****##**
******###**#***
**###***###****
tinh đối với cánh đồng bị chia thành 4 vùng cỏ:
Yêu cầu: Hãy đếm số vùng cỏ còn lại trên cánh đồng.
Dữ liệu: Đọc từ tập tin văn bản AREA.INP
-
Dòng đầu chứa 2 số ngun dƣơng
-
Trong
.
dịng tiếp theo, mỗi dịng chứa
kí tự là dấu * hoặc dấu # biểu diễn dữ liệu của
cánh đồng.
Kết quả: Xuất ra tập tin văn bản AREA.OUT số vùng cỏ trên cánh đồng.
ụ:
AREA.INP
6 15
******##*******
*****##********
******#######**
#######****##**
******###**#***
**###***###****
Sách Tin Học dành cho học sinh PTNK
AREA.OUT
4
Page 10
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
TÁC GIẢ
Các phát minh khoa học lớn thƣờng đƣợc đặt bằng tên các nhà khoa học đã tìm ra chúng. Ví dụ,
hệ thống mã hóa phi đối xứng RSA do các nhà bác học Rivest, Shamir và Adleman đề xuất. Một
ví dụ quen thuộc khác – giải thuật Knuth – Morris – Pratt đƣợc gọi bởi tên các tác giả là Knuth,
Morris và Pratt.
Các tài liệu khoa học có rất nhiều và khơng hồn tồn nhất qn khi đặt tên giải thuật. Có khi
ngƣời ta dùng phƣơng án ngắn gọn – dùng chữ cái đầu của tên tác giả (nhƣ RSA), có khi dùng
phƣơng án đầy đủ – tên các tác giả, nối với nhau bằng ký tự “-“ ( nhƣ Knuth – Morris – Pratt).
Trong phạm vi một bài báo, việc dùng cả hai dạng đặt tên là thiếu thẩm mỹ, vì vậy, nên chuẩn
hóa theo một cách gọi, chẳng hạn – phƣơng án ngắn gọn.
Yêu cầu: Cho xâu chứa tên tên giải thuật theo phƣơng án đầy đủ, có độ dài không quá 100 ký tự,
bao gồm các chữ cái la tinh hoa và thƣờng và ký tự “-“ (Mã ASCII là 45). Tên mỗi tác giả bắt
đầu bằng chữ cái hoa. Hãi xác định phƣơng án ngắn gọi tên giải thuật của các tác giả này.
Dữ liệu: Vào từ file văn bản AUTHOR.INP gồm một dòng chứa xâu ký tự tên giải thuật phƣơng
án đầy đủ.
Kết quả: Đƣa ra file văn bản AUTHOR.OUT một dòng chứa tên giải thuật theo phƣơng án ngắn
gọn.
Ví dụ:
AUTHOR.INP
Knuth-Morris-Pratt
Sách Tin Học dành cho học sinh PTNK
AUTHOR.OUT
KMP
Page 11
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
TỔNG NHỎ NHẤT
Cho hai dãy số ngun
và một phần tử
trong dãy
và
có
hãy tìm một phần tử
là nhỏ nhất có thể
trong dãy
.
Dữ liệu: vào từ tập tin văn bản ASUMMIN.INP
-
Dòng 1 chứa hai số nguyên dƣơng
-
Dòng 2 chứa
số nguyên
-
Dòng 3 chứa
số nguyên
(
(
)
)
Kết quả: ghi ra tập tin văn bản ASUMMIN.OUT hai chỉ số và của hai phần tử tƣơng ứng tìm
đƣợc.
Ví dụ
ASUMMIN.INP
45
1829
-5 -6 3 -7 -4
ASUMMIN.OUT
24
Giải thích:
Sách Tin Học dành cho học sinh PTNK
Page 12
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
ĐẤU GIÁ
Sở giao thông Hà Nội quyết định bán đấu giá các biển số xe đẹp để lấy tiền ủng hộ đồng bào lũ
lụt miền Trung. Một biển số xe đƣợc gọi là đẹp nếu nó thỏa mãn các điều kiện sau:
-
Là một số nguyên dƣơng
-
là một số nguyên tố;
-
là một số đối xứng (đọc
trong đó
mà
là hai số nguyên dƣơng cho trƣớc;
từ trái qua phải thu đƣợc kết quả giống nhƣ đọc
từ phải qua
trái).
Yêu cầu: Cho hai số nguyên dƣơng
và , hãy tìm số lƣợng các biển số xe đẹp.
Dữ liệu: vào từ tập tin văn bản AUCTION.INP chứa hai số nguyên
Kết quả: ghi ra tập tin văn bản AUCTION.OUT số lƣợng biển số xe đẹp tìm đƣợc.
Ví ụ:
AUCTION.INP
11111 22222
Sách Tin Học dành cho học sinh PTNK
AUCTION.OUT
23
Page 13
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
DÃY SỐ TRUNG BÌNH CỘNG
Mirko vừa nghĩ ra một cách luyện tập các phép toán số học mà cậu cho là thú vị nhƣ sau: trƣớc
tiên Mirko viết một dãy gồm các số . Sau đó, bên dƣới mỗi phần tử của dãy số đầu tiên, Mirko
viết một con số là giá trị trung bình cộng các phần tử của
Chẳng hạn, dãy
có giá trị
thì giá trị của dãy
tính từ đầu dãy đến vị trí hiện tại.
sẽ là
Yêu cầu: cho giá trị các phần tử của dãy . Hãy tìm dãy
ban đầu phù hợp với cách tính của
Mirko.
Dữ liệu: vào từ tập tin văn bản AVGSEQ.INP
-
Dòng đầu tiên chứa số nguyên dƣơng
-
Dòng tiếp theo chứa dãy số nguyên
Kết quả: ghi ra tập tin văn bản AVGSEQ.OUT gồm 1 dòng chứa dãy số
Dữ liệu vào đƣợc cho đảm bảo dãy
tìm đƣợc.
tìm đƣợc là dãy số ngun và có giá trị khơng vƣợt q
.
ụ:
AVGSEQ.INP
4
3235
Sách Tin Học dành cho học sinh PTNK
AVGSEQ.OUT
3 1 5 11
Page 14
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
THU NHẶT BĨNG
Trong một trị chơi vận động, đội chơi sẽ cử ngƣời thực hiện một số lƣợt để lấy hết tất cả
quả
bóng của ban tổ chức theo luật chơi. Lƣợt thứ nhất, ngƣời chơi chỉ đƣợc lấy tối đa 1 quả, lƣợt thứ
2 chỉ đƣợc lấy tối đa
lƣợt thứ
quả, lƣợt thứ 3 chỉ đƣợc lấy tối đa
ngƣời chơi chỉ đƣợc lấy tối đa
quả. Tổng quát,
quả bóng.
Yêu cầu: cho số nguyên dƣơng , hỏi đội chơi cần thực hiện ít nhất là bao nhiêu lƣợt để lấy hết
tất cả
quả bóng của ban tổ chức.
Dữ liệu: vào từ tập tin văn bản BALLOONS.INP số nguyên dƣơng
.
Kết quả: ghi ra tập tin văn bản BALLOONS.OUT số lƣợt ít nhất mà đội chơi cần thực hiện để
lấy hết tất cả
quả bóng.
ụ:
BALLOONS.INP
16
Sách Tin Học dành cho học sinh PTNK
BALLOONS.OUT
4
Page 15
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
HỆ ĐẾM
Steve rất hào hứng với các bài tập chuyển đổi cơ số. Sau khi làm xong các bài tập về nhà, Steve
ngồi viết lần lƣợt các số tự nhiên 1, 2, 3, . . . sang dạng biểu diển ở cơ số b (2 < b ≤ 36). Để biểu
diễn chữ số, Steve dùng các ký tự từ 0 đến 9 và các chữ cái từ a đến z. Sau đó Steve gạch đi tất
cả những số có dạng biểu diễn tƣơng ứng với một số nào đó trong cơ số c (2 ≤ c < b).
Ví dụ, với b = 3, dãy số tự nhiên sau khi chuyển cơ số sẽ là 1, 2, 10, 11, 12, 20,21, . . . Nếu gạch
khỏi dãy tất cả các số tƣơng ứng với một số nào đó trong hệ đếm c = 2, dãy các số còn lại sẽ là
2, 12, 20, 21, . . .
Ngắm nhìn dãy số cịn lại Steve chợt nghĩ: “Cần phải kiểm tra xem mình có bỏ sót số khi viết
hoặc chuyển hệ đếm sai hay khơng”. Một trong các cách kiểm tra là tính số thứ n còn lại trong
dãy và so sánh với kết quả dếm trực tiếp trên dãy.
Yêu cầu: Cho 3 số nguyên n, b và c ( 1 ≤ n ≤ 1012, 2 ≤ c < b ≤ 36). Hãy xác định và đƣa ra ( ở
hệ thập phân) số thứ n còn lại trong dãy. Các số còn lại đƣợc đánh số từ 1.
Dữ liệu: Vào từ file văn bản BASES.INP gồm một dòng chứa 3 số nguyên n, b và c.
Kết quả: Đƣa ra file văn bản BASES.OUT một số ngun – số tìm đƣợc.
Ví dụ:
BASES.INP
BASES.OUT
2 3 2
5
Sách Tin Học dành cho học sinh PTNK
Page 16
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
HẢI LY
Hải ly là lồi vật rất thơng minh và nổi tiếng là bậc thầy trong việc xây dựng các đập ngăn sông
suối.
Hải ly đứng trƣớc một hàng cây dài vô tận (cả về hai phía).Với chú hải ly, một cây có thể thuộc
loại tốt hay xấu. Khi chú gặm một cây, tùy theo tình hình cụ thể, loại cây có thể vẫn giữ nguyên
hoặc chuyển từ tốt sang xấu hay ngƣợc lại. Ban đầu tất cả các cây dều thuộc loại tốt.
Chú hải ly có thể có một trong năm trạng thái tình cảm: A – Dận dữ (Agry), B – Bận rộn (Busy),
C – Hứng khởi (Creative), D – Chán nản (Despaired), E – Mệt mỏi (Exhausted). Ban đầu hải ly ở
trạng thái A.
Khi hải ly đứng trƣớc một cây, phụ thuộc vào trạng thái tính cảm của mình và loại cây nó sẽ làm
những việc sau:
Gặm cái cây, loại cây có thể sẽ bị thay đổi,
Giữ nguyên hoặc thay đổi trạng thái tình cảm của mình,
Chuyển sang cây kề cạnh bên phải hoặc bên trái.
Với một tổ hợp tình cảm và loại cây trƣớc mặt hải ly tự cho là đập đã hoàn thành và cảm thấy vui
sƣớng (Happy). Cũng có thể hải ly khơng bao giờ thấy sung sƣớng trong suốt q trình hoạt
động khơng ngừng của mình.
u cầu: Cho bộ quy tắc hành động của hải ly, bao gồm 10 từ, mỗi từ 3 ký tự. Từ thứ nhất xác
định hành động của hải ly khi ở trạng thái A và đứng trƣớc cây tốt, từ thứ hai xác định hành
động của hải ly khi ở trạng thái A và đứng trƣớc cây xấu, từ thứ ba xác định hành động của hải
Sách Tin Học dành cho học sinh PTNK
Page 17
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
ly khi ở trạng thái B và đứng trƣớc cây tốt, từ thứ tƣ xác định hành động của hải ly khi ở trạng
thái B và đứng trƣớc cây xấu, . . . Giả thiết từ có dạng αβγ.
1 – Biến cây thành xấu,
0 – Biến cây thành tốt
αβγ
L – Chuyển sang cây bên trái,
R – Chuyển sang cây bên phải
Trạng thái mới của hải ly.
H –Vui sướng..
Hãy xác định xem đến một lúc nào đó hải ly sẽ cảm thấy vui sƣớng hay không.
Dữ liệu: Vào từ file văn bản BEAVER.INP, gồm một dòng chứa 10 từ, các từ cách nhau một dấu
cách.
Kết quả: Đƣa ra file văn bản BEAVER.OUT thông báo happy beaver hoặc unhappy
beaver tùy theo kết quả nhận đƣợc.
Ví dụ:
BEAVER.INP
1RB 1LC 1RC 1RB 1RD 0LE 1LA 1LD 1RH 0LA
Sách Tin Học dành cho học sinh PTNK
BEAVER.OUT
happy beaver
Page 18
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
ĐƯỜNG ĐI BFS
Cho đồ thị có hƣớng
gồm
đỉnh và
đỉnh
sao cho
cung,
và
là hai đỉnh của . Một dãy các
đƣợc gọi là một đƣờng đi
từ tới .
Biết rằng tồn tại ít nhất một đƣờng đi từ
tới , hãy chỉ ra đƣờng đi đơn qua ít cung nhất. Nếu có
nhiều đƣờng đi đơn cùng qua ít cung nhất, hãy chỉ ra đƣờng đi có thứ tự từ điển nhỏ nhất trong
số đó.
Dữ liệu: vào từ tập tin văn bản BFS.INP
-
Dòng 1 chứa số đỉnh
, số cung
, đỉnh xuất phát , đỉnh cần đến .
dòng tiếp theo, mỗi dịng chứa hai số ngun dƣơng
-
đỉnh
thể hiện có cung nối từ đỉnh
tới
trong đồ thị.
Kết quả: ghi ra tập tin văn bản BFS.OUT các đỉnh theo đúng thứ tự trên đƣờng đi tìm đƣợc, bắt
đầu từ đỉnh , kết thúc ở đỉnh
ụ:
BFS.INP
8 12 1 8
12
13
23
24
31
35
37
46
62
68
78
76
Sách Tin Học dành cho học sinh PTNK
BFS.OUT
1378
1
2
3
4
7
6
8
5
Page 19
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
CẦU PHAO
Mƣa to liên tục mấy ngày liền đã biến con suối ven làng thành một con sông thực sự. Để học
sinh có thể đi học an tồn ngƣời ta quyết định bắc tạm một cầu phao.Nguyên vật liệu làm cầu
đƣợc một cơng trƣờng gần đó cho mƣợn, bao gồm x súc
gỗ tròn độ dài a và y súc gỗ tròn độ dài b. Tất cả chúng
đều có cùng một bán kính.
Cầu phao phải đƣợc ghép từ m hàng gỗ. Mỗi hàng bao
gồm một hoặc một vài súc gỗ. Các súc gỗ phải đƣợc giữ
nguyên, không đƣợc cƣa ngắn.
Ngƣời ta muốn xây dựng cây cầu với độ rộng lớn nhất
có thể. Độ rộng của cầu đƣợc xác định bởi độ dài của
hàng nhỏ nhất.
Ví dụ, cầu cần xây dựng có 7 hàng và ta có 6 súc gỗ độ dài 3, mƣời súc gỗ độ dài 2, khi đó độ
rộng tối đa của cầu là 5.
Yêu cầu: Cho x, a, y, b và m, tất cả đều nguyên và có giá trị không vƣợt quá 150. Tổng số lƣợng
các súc gỗ không ít hơn m. Hãy xác định độ rộng tối đa của cây cầu.
Dữ liệu: Vào từ file văn bản BRIDGE.INP, gồm dòng chứa 5 số nguyên x, a, y, b và m.
Kết quả: Đƣa ra file văn bản BRIDGE.OUT một số nguyên – độ rộng tối đa của cây cầu.
Ví dụ:
BRIDGE.INP
BRIDGE.OUT
6 3 10 2 7
5
Sách Tin Học dành cho học sinh PTNK
Page 20
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
CẦU KHỈ
Sách Tin Học dành cho học sinh PTNK
Page 21
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
SỐ Ô ĐEN TRÊN BÀN CỜ
Một bàn cờ gồm
dòng,
cột, các dòng và cột đƣợc đánh thứ tự
1
từ 1 (hình minh họa). Mỗi ô đƣợc sơn đen hoặc trắng đan xen
1
nhau tƣơng tự bàn cờ vua. Ơ ở dịng
cột
2
của bàn cờ đƣợc sơn màu đen. Hãy xác định có bao
3
nhiêu ơ đƣợc sơn màu đen.
2
3
4
5
4
Dữ liệu: vào từ tập tin văn bản BCELLS.INP chứa bốn số
trên cùng dòng và cách nhau khoảng trắng
nguyên
Kết quả: ghi ra tập tin văn bản BCELLS.OUT số ô đƣợc sơn màu đen.
Ví dụ:
BCELLS.INP
4534
Sách Tin Học dành cho học sinh PTNK
BCELLS.OUT
10
Page 22
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
SỐ ĐẸP
Một số nguyên dƣơng đƣợc gọi là số đẹp nếu tổng các chữ số của nó (trong hệ thập phân) chia
hết cho số chữ số. Các số đƣợc xét không chứa số 0 khơng có nghĩa. Ví dụ, 15 là một số đẹp vì
1+5 chia hết cho 2.
Các số đẹp đƣợc đánh số từ 1 trở đi theo thứ tự tăng dần của giá trị.
Yêu cầu: Cho số nguyên dƣơng n (1 ≤ n ≤ 100 000). Hãy tìm số đẹp thứ n.
Dữ liệu: Vào từ file văn bản BEAUTY.INP gồm nhiều tests, mỗi test ghi trên một dòng chứa
một số nguyên n.
Kết quả: Đƣa ra file văn bản BEAUTY.OUT, kết quả mỗi test đƣa ra trên một dịng.
Ví dụ:
BEAUTY.INP
1
15
Sách Tin Học dành cho học sinh PTNK
BEAUTY.OUT
1
20
Page 23
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
XÂU KÝ TỰ NGOẶC
Xét xâu chỉ chứa các ký tự ngoặc tròn (, ), ngoặc vuông [, ] và ngoặc nhọn {, }. Để ngắn gọn, ta
gọi nó là xâu ngoặc.
Định nghĩa xâu ngoặc đúng:
Xâu rỗng đƣợc coi là xâu ngoặc đúng,
Nếu a là xâu ngoặc đúng thì (a), [a], {a} cũng là các xâu ngoặc đúng,
Nếu a và b là các xâu ngoặc đúng thì ab cũng là xâu ngoặc đúng.
Cho xâu S độ dài n. Xâu sksk+1sk+2…sns1 s2…sk-1 đƣợc gọi là xâu đẩy vòng của S. Bản thân S
cũng là một xâu đẩy vòng của S.
Yêu cầu: Cho xâu ngoặc S có độ dài khơng q 1000. Hãy xác định có tồn tại một xâu đẩy vịng
của S là xâu ngoặc đúng hay không và đƣa ra câu trả lời Yes hoặc No.
Dữ liệu: Vào từ file văn bản BRACKETS.INP gồm một dòng chứa xâu S.
Kết quả: Đƣa ra file văn bản BRACKETS.OUT câu trả lời Yes hoặc No.
Ví dụ:
BRACKETS.INP
}{}(){
Sách Tin Học dành cho học sinh PTNK
BRACKETS.OUT
Yes
Page 24
Tiến sĩ Đào Duy Nam PTNK – ĐHQG TPHCM
KHÔI PHỤC NGOẶC
Một dãy dấu ngoặc hợp lệ là một dãy các ký tự "(" và ")" đƣợc định nghĩa nhƣ sau:
-
Dãy rỗng (khơng có ký tự nào) là một dãy dấu ngoặc hợp lệ
-
Nếu A là một dãy dấu ngoặc hợp lệ thì (A) là dãy dấu ngoặc hợp lệ. Dấu ngoặc mở và dấu
ngoặc đóng hai bên dãy A đƣợc gọi là tƣơng ứng với nhau
-
Nếu A và B là hai dãy dấu ngoặc hợp lệ thì AB là dãy dấu ngoặc hợp lệ.
Ví dụ: ((()))(())()() là một dãy dấu ngoặc hợp lệ. các dấu mở ngoặc ở các vị trí: 1, 2, 3, 7, 8, 11,
13 tƣơng ứng lần lƣợt với các dấu đóng ngoặc ở các vị trí: 6, 5, 4, 10, 9, 12, 14.
Ban đầu có một dãy dấu ngoặc hợp lệ, ngƣời ta viết vào dƣới mỗi dấu ngoặc mở một số là số dấu
ngoặc (cả đóng và mở) nằm giữa dấu ngoặc mở đó và dấu ngoặc đóng tƣơng ứng:
(
(
(
4
2
0
Sau đó xố đi dãy ngoặc.
)
)
)
(
2
(
0
)
)
(
0
)
(
0
)
u cầu: cho biết dãy số cịn lại, hãy khơi phục lại dãy ngoặc ban đầu
Dữ liệu: vào từ tập tin văn bản BRACKETS.INP
-
Dòng 1: Ghi số
là số phần tử của dãy số còn lại
-
Dòng 2: Ghi lần lƣợt các số trong dãy
Kết quả: xuất ra tập tin văn bản BRACKETS.OUT dãy dấu ngoặc khơi phục đƣợc.
Ví dụ:
BRACKETS.INP
7
4202000
Sách Tin Học dành cho học sinh PTNK
BRACKETS.OUT
((()))(())()()
Page 25
