Sách Tin học dành cho học sinh PTNK - ĐHQG TPHCM - Tiến sĩ Đào Duy Nam

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. 7 PHẢN VẬT CHẤT. 8 CÁNH ĐỒNG CỎ. 11 TỔNG NHỎ NHẤT.

13 DÃY SỐ TRUNG BÌNH CỘNG. 14 THU NHẶT BÓNG. 23 XÂU KÝ TỰ NGOẶC. 24 KHÔI PHỤC NGOẶC.

28 PHÒNG THỦ PHÁO ĐÀI. 30 SÔ CÔ LA. 31 RẠP CHIẾU BÓNG. 32 GIAO THÔNG THÀNH PHỐ.

38 CÁC THÀNH PHẦN LIÊN THÔNG. 45 NGÀY THÁNG. 49 KHOẢNG CÁCH SỐ. 50 LÂY NHIỄM EBOLA.

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. 60 ĐÁNH CÁ TRÊN SÔNG KAMA. 62 ĐẶT QUẦY PHỤC VỤ.

65 ẾCH ĐỘT BIẾN GEN. 67 GEN VI KHUẨN. 70 BÀI TẬP VỀ NHÀ. 71 SỐ NGUYÊN TỐ.

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. 77 HIỆN SỐ BẰNG ĐÈN LED.

80 THÀNH PHỐ MAY MẮN. 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. 90 ĐẶT THÁP PHÒNG THỦ Ở CÁC NGỌN NÚI. 96 NGÔN NGỮ MUMBA. 97 CÁCH TIẾP THEO.

100 SỐ THÂN THIỆN. 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. 113 GIỜ THỂ DỤC.

115 PHẦN THƢỞNG. 118 ROBOT DI CHUYỂN. 119 THỰC NGHIỆM KỸ THUẬT ROBOT. 123 THAM QUAN THÀNH PHỐ.

127 CÁC MÁY CHỦ Ở SAO THỦY. 128 BẢY CHỮ SỐ. 133 KẾT QUẢ ĐẸP. 135 THIẾT BỊ KĨ THUẬT SỐ.

138 MUA VÉ XE. 140 ĐƢỜNG TRƢỢT. 142 QUAY XÂU KÝ TỰ. 143 CHÌA KHÓA TAM GIÁC.

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.

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 quên 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.OUT 28 Impossible Sách Tin Học dành cho học sinh PTNK 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.OUT 0 30 23 45 Sách Tin Học dành cho học sinh PTNK 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. 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. 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 ( 100 , 1 ≤ a ≤ 2 000 000 ). Sách Tin Học dành cho học sinh PTNK 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.OUT 1 17 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 ô vuông đơn vị có kích thƣớc bằng nhau. Tại mỗi ô vuông đơn vị, ngƣời ta trồng cỏ hoặc để trống dành chỗ cho 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 ô vuông đơ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 ô vuông đơ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ố nguyên 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.OUT 6 15 4 ******##******* *****##******** ******#######** #######****##** ******###**#*** **###***###**** Sách Tin Học dành cho học sinh PTNK 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 hoàn toàn nhất quán 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).