Đề thi chọn HSG môn tin học lớp 11

GIÁO VÀ ĐÀO OỞ ẠH NG YÊNƯĐ CHÍNH TH CỀ Ứ(Đ thi có 02 trang)ề KỲ THI CH NỌ SINH GI THPT NHỌ NĂM 201Ọ 201 8Môn thi: TIN CỌTh gian làm bài: 180 phút (không th gian phát )ể ềT ng quan các bài thiổ ềTên bài Tên file ch ngươtrình File li vàoữ File quế ảBài 1Tính ngổ SUM SUM .INP SUM .OUTBài Bán hàng qua ngạ SORT.* SORT.INP SORT.OUTBài Hoán vị JOSEPHUS.* JOSEPHUS.INP JOSEPHUS.OUTChú trong tên file ch ng trình thay th PAS ho CPP tùy theo ngônấ ươ ượ ặng ng là PASCAL ho C++ ặHãy trình gi các bài toán sau:ậ ảBài 1: Tính ngổ đi m).ểCho dãy số nguyênồ ngươ a1 a2 …, aN và giá tr Kị Hãy các ph nế ầt aửi aj (i j).D li vào:ữ cho File SUM .INP hai dòng:ồ Dòng tiên ghiầ giá trị và (2 10 5, 10 5). Dòng hai ghi giá tr dãy a1 a2 …, aN (1 ai 10 5).K qu :ế ghi ra file SUM .OUT là ng tìm.ố ượ ầVí :ụSUM .INP SUM .OUT4 109 39 106 6Gi n:ớ ạ 80% test có ố≤ 1000. 20% test còn ng 1000 ớ≤ 100000.Bài 2: Bán hàng qua ng (7 đi m)ạ ểTrang là sinh THPT tr ng X. Là sinh nh ng em có thích vàộ ườ ởni đam mê trong lĩnh kinh doanh qua ng. hàng em bán là bút bi. Qua th iề ờgian kinh doanh, hàng ngày càng tăng, ng bút bi nh ngày càng nhi u. cóơ ượ ểth nhanh chóng giao hàng cho khách, Trang mu nh ng chi bút theo màu c.ể ắTrang có dãy bút bi các màu xanh, tím, ng. Vì ng bút là và không cóồ ượ ớnhi th gian nên Trang mu nh các sinh gi môn Tin tham gia kỳ thiề ọch sinh gi nh năm 2018 giúp. Em hãy giúp Trang dãy bútọ ạbi theo quy lu Xanh ng Tím.ậ ồD li vàoữ Cho file SORT.INP dòng:ồ Dòng 1: Ghi là ng bút bi (1 10ố ượ 6). Dòng 2: kí mô dãy bút bi Xanh, Tím, ng), các màu cồ ượphân cách nhau cách.ở ấTrang 1K quế Ghi ra file SORT.OUT qu dãy sau khi đã đúng th cácế ượ ựkí phân cách cách.ự ượ ấSORT.INP SORT.OUT4X T10X HGi n:ớ ạ 60% test có ố≤ 1000. 20% test còn ng 1000 ớ≤ 100000. 20% test còn ng 100000 ớ≤ 1000000.Bài 3: Hoán (6 đi m)ị ểT ng truy ng Josephus và chi sĩ ng La Mã bao vây trong tươ ươ ườ ộhang ng. quy nh ch không ch t. 41 ng ng thành vòng tròn vàộ ườ ứb theo chi vòng tròn, ng nào thì ph và ng iắ ườ ườk ti 1. Josephus không mu ch và đã ch trí mà ông taế ượ ịcùng ng là hai ng ng sót cu cùng theo quy lu này. Hai ng ngớ ườ ườ ườ ốsót sau đó đã hàng và gia nh quân La Mã (Josephus sau đó ch nói ng đó là mayầ ựm n, hay “bàn tay Chúa” giúp ông và ng kia ng sót).ắ ườ ốCó nhi truy thuy và tên khác nhau bài toán Josephus. Trong toánấ ềh c, ng ta phát bi bài toán ng trò ch i: Cho ng ng quanh vòng trònọ ườ ướ ườ ứtheo chi kim ng đánh n. ng th nh theo chi uề ườ ềkim ng ng nào (m n) thì lo kh vòng và ng ti uồ ườ ườ ầđ 1. Trò ch ti di cho khi vòng tròn ch còn ng i. ta hi uế ườ ệc ng này theo th lo kh vòng hoán (jủ ườ ượ ị1 j2 jn dãyủs (1,2, n) là hoán Josephus(n,m)ố ịVí 7, 3, hoán Josephus là (3,6,2,7,5,1,4). Bài toán ra là choụ ặtr hai n, hãy xác nh hoán Josephus(n,m).ướ ịD li vào:ữ Cho file JOSEPHUS.INP m:ồHai nguyên ng n, 10ố ươ 5.K qu :ế Ghi ra file JOSEPHUS.OUT m:ồHoán Josephus(n,m), phân cách nhau cách.ị ấJOSEPHUS.INP JOSEPHUS.OUT7 412 12 11 10Gi n:ớ ạ 60% test có ố≤ 100. 20% test còn ng 100 ớ≤ 10000. 20% test còn ng 10000 ớ≤ 100000.-------------- TẾ --------------Thí sinh không ng tài li u, cán coi thi không gi thích gì thêm.ử ảH và tên thí sinh:………………………………… SBD:………………………...............ọTrang 2Ch kí giám th …………………………………………………………………………….ữ ịTrang