Chọn HSG lớp 9 - Đà Nẵng NH 2012 2013
- 1. SỞ GIÁO DỤC-ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 THÀNH PHỐ ĐÀ NẴNG NĂM HỌC 2012-2013 Môn: TIN HỌC Thời gian: 150 phút (không tính thời gian giao đề) ĐỀ CHÍNH THỨC Chú ý: Đề thi gồm có 3 bài trong 2 trang Tổng quan đề thi Bộ tam hợp Số lộn xộn Dãy số Tên bài làm BL1.* BL2.* BL3.* Dữ liệu vào TAMHOP.INP SOLONXON.INP DAYSO.INP Dữ liệu ra TAMHOP.OUT SOLONXON.OUT DAYSO.OUT Bài 1. B tam h pộ ợ Cho dãy s nguyên aố 1, a2, ..., an, các s khác nhau t ng đôi m t (3ố ừ ộ ≤ n ≤ 5000; v i m i i ta có |aớ ọ i| ≤ 106 ). B ba s aộ ố i, aj, ak (i ≠ j ≠ k) đ c g i là B tam h p n u cóượ ọ ộ ợ ế m t s b t kỳ trong ba s đó b ng trung bình c ng c a hai s còn l i.ộ ố ấ ố ằ ộ ủ ố ạ Yêu c u:ầ Hãy đ m s l ng b tam h p và tìm b tam h p có t ng giá tr c aế ố ượ ộ ợ ộ ợ ổ ị ủ ba s là l n nh t.ố ớ ấ D li u vào:ữ ệ Đ c t file văn b n có tên TAMHOP.INPọ ừ ả có c u trúc nh sauấ ư : - Dòng 1 ch a s n;ứ ố - Dòng 2 ch a n s aứ ố 1, a2, ..., an cách nhau ít nh t m t d u cáchấ ộ ấ D li u ra:ữ ệ Ghi ra file văn b n có tên TAMHOP.OUTả có c u trúc nh sauấ ư : - Dòng 1 ghi m t s nguyên d ng là s l ng b tam h p tìm đ c;ộ ố ươ ố ượ ộ ợ ượ - Dòng 2 ghi t ng giá tr ba s c a b tam h p là l n nh t.ổ ị ố ủ ộ ợ ớ ấ Ví d :ụ TAMHOP.INP TAMHOP.OUT 7 6 1 9 2 3 4 8 5 18 Gi i thích ví d :ả ụ Có 5 b tam h p tìm đ c là: (1, 2, 3); (2, 3, 4); (2, 4, 6); (4, 6, 8) ; (3, 6, 9)ộ ợ ượ Bài 2: S l n x nố ộ ộ M t s l n x n là m t xâu ch a các ch s và các d u ? (nh 36?1?8). Ta nóiộ ố ộ ộ ộ ứ ữ ố ấ ư m t s X thích h p v i s l n x n W n u chúng có đ dài gi ng nhau, và m i ký t ?ộ ố ợ ớ ố ộ ộ ế ộ ố ọ ự trong X đ c thay b ng m t ch s t i v trí t ng ng trong W (có th thay th m tượ ằ ộ ữ ố ạ ị ươ ứ ể ế ộ d u ? v i m t ch s b t kỳ). Ví d : 365198 thích h p v i s l n x n 36?1?8, nh ngấ ớ ộ ữ ố ấ ụ ợ ớ ố ộ ộ ư 360199, 361028, 36128 là không thích h p.ợ
- 2. Yêu c uầ : Cho s l n x n W và s X, c 2 có đ dài n (1 ≤ n ≤ 10), đ m s các số ộ ộ ố ả ộ ế ố ố có n ch s thích h p v i W và l n h n X.ữ ố ợ ớ ớ ơ D li u vào:ữ ệ Đ c t file văn b n có tên SOLONXON.INP g m nhi u test, m iọ ừ ả ồ ề ỗ test ch a hai dòng có đ dài gi ng nhau. Dòng đ u là s W và dòng hai là s nguyênứ ộ ố ầ ố ố X. K t thúc file là dòng ch a d u #.ế ứ ấ D li u ra:ữ ệ Ghi ra file văn b n có tên SOLONXON.OUT g m nhi u dòng, m iả ồ ề ỗ test đ a ra m t dòng là s l ng các s thích h p v i W và l n h n X.ư ộ ố ượ ố ợ ớ ớ ơ Ví d :ụ SOLONXON.INP SOLONXON.OUT 8?3 910 ? 5 # 0 4 Bài 3. Dãy số Cho m t dãy s nguyên {aộ ố n}=a1,a2,...,an. V i m i i>1,ớ ọ ai tho các yêu c u sau:ả ầ 1. ai là s nguyên nh nh tố ỏ ấ 2. ai > ai-1. 3. T ng các ch s c a aổ ữ ố ủ i b ng t ng các ch s c a aằ ổ ữ ố ủ i-1 sau khi đã nhân cho 4. Yêu c uầ : Cho a1 và n, tìm an. D li u vào:ữ ệ Đ c t file văn b n có tên DAYSO.INP ch m t dòng ch a hai s aọ ừ ả ỉ ộ ứ ố 1 (0<a1<20) và n (0<n<10000). D li u ra:ữ ệ Ghi ra file văn b n có tên DAYSO.OUT ch a m t s aả ứ ộ ố n. Ví d :ụ DAYSO.INP DAYSO.OUT 4 5 79 ------HẾT------ Gi i thích ví d : a1=4; a2=7; a3=19; a4=49; a5=79;ả ụ Chú ý: Cán b coi thi không gi i thích gì thêmộ ả