Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án)

Nội dung text: Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án)

1. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn for j := i+1 to n do if d[i] < d[j] then begin t := d[i]; d[i] := d[j]; d[j] := t; end; end; procedure sortV; var i,j,t: integer; begin for i := 1 to m-1 do for j := i+1 to m do if v[i] > v[j] then begin t := v[i]; v[i] := v[j]; v[j] := t; end; end; begin readln(n,m); for i := 1 to n do read(d[i]); readln; for i := 1 to m do begin read(v[i]); idx[i] := i; end; sortD; sortV; total := 0; for i := 1 to n do begin total := total + int64(d[i]) * v[i]; writeln(idx[i]); end; writeln(total); end. DeThi.edu.vn
2. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn ĐỀ SỐ 3 TRƯỜNG THPT CẨM THUỶ 1 ĐỀ THI HỌC SINH GIỎI CẤP TRƯỜNG NĂM HỌC: Môn: Tin học Thời gian: 180 phút (không kể thời gian giao đề) ĐỀ BÀI: Câu 1: Số thân thiện (5 điểm) Số tự nhiên có rất nhiều tính chất thú vị: Ví dụ với số 29, số đảo ngược của nó là 92. Hai số này nguyên tố cùng nhau tức có ước chung lớn nhất là 1. Những số như thế được gọi là số thân thiện, tức là số 29 được gọi là số thân thiện, số 92 cũng được gọi là số thân thiện. Ví dụ : a = 110 ; b = 120. Có 6 số thân thiện từ 110 đến 120 gồm: 112 113 115 116 118 119 Dữ liệu: Vào file văn bản SOTTHIEN.INP chứa 2 số nguyên a, b (10 ≤ a ≤ b ≤ 20000). Kết quả: ghi vào tệp SOTTHIEN.OUT là các số thân thiện trong đoạn [a, b]. Nếu không có số thân thiện nào trong đoạn [a,b] thì in ra -1. SOTTHIEN.INP SOTTHIEN.OUT 110 120 112 113 115 116 118 119 Câu 2: Xoá ký tự trùng. (5 điểm) Viết chương trình xoá các ký tự liên tiếp giống nhau trong một xâu cho trước chỉ chừa lại 1 ký tự. Dữ liệu vào: Tệp văn bản ‘XOATRUNG.INP’ chứa một xâu ký tự không quá 500 ký tự Dữ liệu ra: Tệp văn bản ‘XOATRUNG.OUT’ chứa xâu sau khi xoá các ký tự trùng. XOATRUNG.INP XOATRUNG.OUT tttttthhhhppppttt ccammmthhhuuyy1111 thpt camthuy1 Câu 3: Tích lớn nhất (4 điểm) Cho một dãy gồm n số nguyên. Viết chương trình hiển thị ra màn hình 3 số trong dãy có tích T của chúng là lớn nhất. Input cho trong tệp ‘TICH.INP’ gồm: - Dòng 1: Nhập giá trị N (5 <= N <= 100000) - Dòng 2: Chứa N số nguyên A1, A2, , AN. (|Ai| <=100000) Output Ghi vào tệp “TICH.OUT’ 3 số có tích lớn nhất tìm được. Ví dụ: TICH.INP TICH.OUT 9 -45 -32 15 6 3 7 9 -32 10 -45 4 15 Câu 4: Dãy con liên tiếp (3 điểm) Cho số nguyên dương M và N số nguyên dương a1, a2, , aN. DeThi.edu.vn
3. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn Yêu cầu: Hãy chọn ra K số liên tiếp trong N số đã cho sao cho tổng của chúng chia hết cho M và K là nhỏ nhất. Dữ liệu vào: DCLT.INP - Dòng đầu chứa số M và N (M<32767, n<=10000) - Dòng thứ hai chứa N số a1, a2, , aN (ai<32767) Kết quả ghi vào tệp DCLT.OUT Dòng đầu là hai số nguyên K và J cách nhau ít nhất 1 dấu cách, trong đó: - K là số phần tử của dãy con liên tiếp có tổng chia hết cho M có ít phần tử nhất - J là chỉ số của phần tử đầu tiên trong dãy con liên tiếp tìm được (nếu có nhiều dãy con thỏa mãn thì J là chỉ số của phẩn tử trong dãy con đầu tiên). Dòng 2 ghi ra các phần tử của dãy con thõa mãn đầu tiên. Nếu không tìm được dãy con nào thì ghi số -1. Câu 5: Số lớn nhất (3 điểm) Trong giờ học môn toán, Cuội ngồi nghe cô giáo giảng bài rất chăm chú, còn Bờm, có vẻ như đang buồn ngủ vì sở thích của anh chàng là các môn Khoa học Xã hội. Để giúp Bờm tỉnh táo, Cuội tổ chức một trò chơi cho Bờm bằng cách viết ra giấy một số nguyên dương gồm N chữ số, yêu cầu Bờm tìm số lớn nhất có thể sau ghi gạch bỏ đi K chữ số trong số N chữ số đã cho. Dữ liệu: cho trong file văn bản NUMMAX.INP • Dòng đầu: ghi hai số nguyên N và K , cách nhau bởi một dấu cách. • Dòng thứ hai: ghi xâu N chữ số, chữ số đầu tiên luôn khác 0. Kết quả: ghi ra file văn bản NUMMAX.OUT kết quả tìm được trên một dòng duy nhất. Điều kiện: 1 ≤ K ≤ N ≤ 50000 Ví dụ: NUMMAX.INP NUMMAX.OUT NUMMAX.INP NUMMAX.OUT 3 1 99 4 2 94 991 1924 ----------------HẾT----------------- DeThi.edu.vn
4. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn ĐÁP ÁN Câu 1: program SOTHIEN; uses math; var a,b,i,x,y,t: longint; ok:boolean; function dao(n: longint): longint; var r: longint; begin r:=0; while n>0 do begin r:=r*10 + n mod 10; n:=n div 10; end; dao:=r; end; begin readln(a,b); ok:=false; for i:=a to b do begin x:=i; y:=dao(i); if gcd(x,y)=1 then begin write(i,' '); ok:=true; end; end; if not ok then write(-1); end. Câu 2: program XOATRUNG; var s,res:string; i:integer; begin DeThi.edu.vn
5. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn readln(s); res:=''; for i:=1 to length(s) do if (i=1) or (s[i]<>s[i-1]) then res:=res+s[i]; writeln(res); end. Câu 3: program TICH; var n,i: longint; a: array[1..100000] of int64; t1,t2:int64; procedure sort; var i,j:longint; t:int64; begin for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; end; begin readln(n); for i:=1 to n do read(a[i]); sort; t1:=a[n]*a[n-1]*a[n-2]; t2:=a[1]*a[2]*a[n]; if t1>t2 then writeln(a[n-2],' ',a[n-1],' ',a[n]) else writeln(a[1],' ',a[2],' ',a[n]); end. Câu 4: program DCLT; const MAX=10000; DeThi.edu.vn
6. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn var M,N,i,j:longint; a:array[1..MAX] of longint; sum:array[0..MAX] of longint; bestK,bestJ:longint; begin readln(M,N); for i:=1 to N do read(a[i]); sum[0]:=0; for i:=1 to N do sum[i]:=sum[i-1]+a[i]; bestK:=maxint; bestJ:=-1; for i:=1 to N do for j:=i to N do if (sum[j]-sum[i-1]) mod M = 0 then if (j-i+1<bestK) then begin bestK:=j-i+1; bestJ:=i; end; if bestJ=-1 then writeln(-1) else begin writeln(bestK,' ',bestJ); for i:=bestJ to bestJ+bestK-1 do write(a[i],' '); end; end. Câu 5: program NUMMAX; var n,k,i,top:longint; s:string; st:array[1..50000] of char; begin readln(n,k); readln(s); DeThi.edu.vn
7. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn top:=0; for i:=1 to n do begin while (top>0) and (k>0) and (st[top]<s[i]) do begin dec(top); dec(k); end; inc(top); st[top]:=s[i]; end; while k>0 do begin dec(top); dec(k); end; for i:=1 to top do write(st[i]); end. DeThi.edu.vn
8. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn ĐỀ SỐ 4 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TRƯỜNG TỈNH QUẢNG NAM NĂM HỌC ĐỢT 2 Môn thi: TIN HỌC 11 (CHUYÊN) ĐỀ CHÍNH THỨC Thời gian: 180 phút (không kể thời gian giao đề) Khóa thi ngày: (Đề gồm có 03 trang) TỔNG QUAN ĐỀ THI Bài Tên bài Tên file chương trình Dữ liệu vào Dữ liệu ra 1 SPORT SPORT.* SPORT.INP SPORT.OUT 2 GAME GAME.* GAME.INP GAME.OUT 3 MEGA MEGA.* MEGA.INP MEGA.OUT Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Free Pascal hoặc C++. Câu 1. (6,0 điểm) SPORT Một Sư đoàn A có chiến sĩ, các chiến sĩ có chỉ số thể lực tương ứng theo thứ tự 1, 2, , . Để chuẩn bị cho hội thao hàng năm giữa các Sư đoàn với nhau, Sư đoàn A tổ chức một hội thi để chọn ra các đội có kết quả cao nhất để tham gia hội thao. Sau một thời gian huấn luyện về thể lực, Sư đoàn cần chọn ra các đội gồm các chiến sĩ có chỉ số thể lực hoàn hảo để tham gia hội thao. Chỉ số thể lực hoàn hảo là đội gồm 3 chiến sĩ có vị trí là 푖,푗, , độ chênh lệch thể lực giữa 2 chiến sĩ trong đội là sao cho 푖 < 푗 < và 푖 ― ≥ 푗 푣à 푗 ― ≥ . Yêu cầu: Hãy đếm số đội có thể tham gia hội thao của sư đoàn A. Dữ liệu vào: Đọc từ tệp SPORT.INP - Dòng đầu tiên là số , . - Dòng tiếp theo ghi số nguyên 1, 2, , . Kết quả ra: Ghi ra tệp SPORT.OUT - Ghi ra một số duy nhất là số đội nhiều nhất có thể chọn. Ví dụ: SPORT.INP SPORT.OUT GIẢI THÍCH 5 2 4 Có 4 đội tham gia hội thao với độ 2 8 6 4 2 chênh lệch thể lực là: {8,6,4};{8,6,2}; {8,4,2};{6,4,2} Giới hạn: 5 9 - Subtask 1: 40% test có 1 ≤ ≤ 400;1 ≤ ≤ 10 ;| 푖| ≤ 10 ; 3 5 5 - Subtask 2: 30% test có 10 ≤ ≤ 10 ; = 1;| 푖| ≤ 10 ; 3 5 5 9 - Subtask 3: 30% test có 10 ≤ ≤ 10 ;1 ≤ ≤ 10 ;| 푖| ≤ 10 ; DeThi.edu.vn
9. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn Bài 2. (7,0 điểm) GAME Trong giờ học Toán, thầy giáo của An có ra một trò chơi để tạo không khí vui tươi và đoàn kết các bạn trong lớp. Trò chơi có nội dung như sau: cho dãy gồm 푛 số nguyên không âm, nhiệm vụ của các bạn trong lớp là hãy chia dãy thành k + 1 đoạn khác rỗng, để thu được k+1 đoạn, người chơi cần lặp lại các bước sau đây lần: Bước 1. Chọn một đoạn tuỳ ý với nhiều hơn một phần tử (đầu tiên người chơi chỉ có một đoạn, đó chính là dãy ban đầu). Bước 2. Chọn một vị trí nào đó ở giữa đoạn đã chọn để chia nó ra làm hai đoạn mới khác rỗng. Mỗi lần thực hiện xong hai bước này người chơi nhận được một điểm số bằng tích của hai tổng các số trong hai đoạn mới chia ra. Yêu cầu: Với cách chơi như trên, bạn hãy lập trình giúp An tìm ra cách để đạt được tổng điểm lớn nhất. Dữ liệu vào: Đọc từ tệp GAME.INP gồm: - Dòng đầu tiên chứa hai số nguyên dương 푛 và ( + 1 ≤ 푛 ≤ 3000); 4 - Dòng thứ hai chứa n số nguyên không âm a 1, a2, ..., an (0 ≤ ai ≤ 10 , 1 ≤ i ≤ n) là các phần tử của dãy số. Kết quả ra: Ghi vào tệp GAME.OUT Một số nguyên duy nhất là tổng điểm lớn nhất mà bạn đạt được. Ví dụ: GAME.INP GAME.OUT 7 3 108 1 3 4 0 2 3 4 Giải thích ví dụ: Trong ví dụ bạn có thể giành được 108 điểm theo cách sau: - Đầu tiên bạn có dãy số (1, 3, 4, 0, 2, 3, 4) gồm 1 đoạn. Bạn chia dãy ra thành hai đoạn sử dụng điểm chia sau phần tử thứ sáu và nhận được: (1 + 3 + 4 + 0 + 2 + 3) × 4 = 52 điểm. - Bạn đang có hai đoạn (1, 3, 4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ hai và nhận được: (1 + 3) × (4 + 0 + 2 + 3) = 36 điểm. - Bạn đang có ba đoạn (1, 3), (4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ tư và nhận được: (4 + 0) × (2 + 3) = 20 điểm. Như vậy, sau 3 bước thực hiện nói trên bạn chia dãy số thành 4 đoạn (1, 3), (4, 0), (2, 3), (4) và nhận được: 52 + 36 + 20 = 108 điểm. Giới hạn: - Subtask 1: Có 60% số test có n ≤ 300; - Subtask 2: Có 40% số test có n ≤ 3000. DeThi.edu.vn
10. Tuyển tập 14 Đề thi HSG cấp Trường môn Tin học 11 (Kèm đáp án) - DeThi.edu.vn Bài 3. (7,0 điểm) MEGA Đất nước Mega được mệnh danh là vùng đất có rất nhiều đảo đẹp và yên bình. Hàng năm có rất nhiều tàu thuyền khắp nơi trên thế giới ghé thăm đất nước Mega để tham quan, du lịch và kinh doanh. Để phát triển kinh tế, giao thương và thu hút đầu tư nước Mega đã kêu gọi sự đầu tư của nhiều công ty lớn trên thế giới đến xây dựng các cảng biển. Đến thời điểm hiện tại đã xây dựng được 푛 cảng biển, các cảng này được kết nối với nhau với hệ thống giao thông đường thủy gồm m đường 2 chiều, đảm bảo sự giao thương giữa 2 cảng bất kỳ (trực tiếp hoặc gián tiếp thông qua cảng trung gian). Giữa 2 cảng bất kỳ có không quá một đường đi trực tiếp. Việc đầu tư, vận hành, bảo trì các cảng này được giao cho 2 công ty lớn là Greek (G) và Yamato (Y) độc quyền đảm nhận. Các tàu thuyền hoạt động trên các cảng này đều thuộc quyền sở hữu của 2 công ty trên thực hiện. Các tàu thuyền khi vận chuyển hàng và người từ cảng này sang cảng khác thì chủ thuyền phải trả chi phí là 1 đơn vị tiền tệ, ngoài ra tàu thuyền khi đi qua cảng mà không phải do công ty mình quản lý thì chủ thuyền phải trả thêm 3 đơn vị tiền tệ. Tất nhiên, khi vận chuyển hàng hóa và người, chủ thuyền bao giờ cũng chọn con đường ứng với tổng chi phí nhỏ nhất. Yêu cầu: Cho biết 푛, và mạng giao thông trong Mega, hãy giúp công ty G và Y tính tổng chi phí vận chuyển hàng giữa tất cả các cảng biển thuộc tập đoàn của họ. Dữ liệu vào: Đọc từ tệp MEGA.INP có cấu trúc: - Dòng đầu tiên chứa hai số nguyên 푛, . - Dòng thứ hai chứa xâu gồm 푛 ký tự, mỗi ký tự là hoặc 푌, ký tự thứ 푖 cho biết cảng 푖 thuộc tập đoàn hay 푌. - Tiếp theo là dòng, mỗi dòng chứa hai số nguyên 푖, 푗 xác định đường nối cảng 푖 với cảng 푗. Kết quả ra: Ghi ra tệp MEGA.OUT có cấu trúc: - Gồm một dòng chứa hai số tương ứng là tổng chi phí vận chuyển hàng giữa tất cả các cảng thuộc tập đoàn và 푌. Ví dụ: MEGA.INP MEGA.OUT 5 5 5 11 YGYGY 1 2 2 3 3 4 4 5 5 1 Giới hạn: - Subtask 1: Có 60% số test có 푛 ≤ 100; ≤ 5000; - Subtask 2: Có 40% số test có 푛 ≤ 1000; ≤ 5000; ------------ Hết ---------- - Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm. DeThi.edu.vn