Cộng đồng chia sẻ tri thức Lib24.vn

Một số bài toán Tin học trẻ hay ôn thi HSG

4a161179399c36d79e9d8037334e649c
Gửi bởi: Nguyễn Minh Lệ 27 tháng 7 2021 lúc 17:55:15 | Được cập nhật: 19 giờ trước (13:02:10) | IP: 113.165.74.10 Kiểu file: DOC | Lượt xem: 619 | Lượt Download: 32 | File size: 0.071168 Mb

Nội dung tài liệu

Tải xuống
Link tài liệu:
Tải xuống

Các tài liệu liên quan


Có thể bạn quan tâm


Thông tin tài liệu

Câu 1: TÍNH TỔNG Trên một màn hình lớn, người ta lần lượt cho hiện ra các số của một dãy gồm N số nguyên không âm a1, a2, …, aN và cứ lặp đi lặp lại như thế. Mỗi người theo dõi màn hình được đề nghị tính tổng của K số nguyên liên tiếp xuất hiện trên màn hình bắt đầu từ số nguyên thứ B. Viết chương trình giúp cho những người theo dõi màn hình tính được tổng như đề nghị. Dữ liệu vào: chứa trong tệp văn bản SUM.INP gồm hai dòng + Dòng đầu tiên ghi ba số nguyên N, K và B, 1  N 100, 1  K 100, 1  B  109. + Dòng thứ hai chứa dãy số nguyên không âm a1, a2, …, aN. Dữ liệu ra: ghi vào tệp văn bản SUM.OUT gồm một dòng chứa tổng cần tính. Ví dụ: SUM.INP SUM.OUT 5 7 154 24 1 2 3 4 5 Chương trình tham khảo: PROGRAM Tinh_Tong; CONST fi=’SUM.INP’; fo=’SUM.OUT’; VAR N, K, B, i : longint; S : longint; a : array[0..100] of longint; f: text; PROCEDURE DocFile; Var f: text; i: integer; Begin Assign(f, fi); Reset(f); Readln(f, N, K, B); For i:=0 to N do Read(f, a[i]); Close(f) End; BEGIN Assign(f, fo); Rewrite(f); DocFile; S := 0; For i := B to B+K-1 do S := S + a[(i-1) mod N]; Write(f, S); Close(f); END. Câu 2: ĐẲNG THỨC Cho một đẳng thức sai có dạng A=S (với A, S là hai số nguyên không âm). Viết chương trình tìm cách thêm vào giữa các chữ số của số nguyên A một số phép cộng để nhận được một đẳng thức đúng, sao cho số phép cộng thêm vào là ít nhất có thể được. Dữ liệu vào: chứa trong tệp văn bản EQ.INP gồm một dòng là đẳng thức sai A = S. Dữ liệu ra: ghi vào tệp văn bản EQ.OUT gồm một dòng chứa đẳng thức đúng sau khi đã thêm vào các phép cộng. Ví dụ: EQ.INP EQ.INP 143175=120 5025=30 EQ.OUT EQ.OUT 14+31+75=120 5+025=30 Chương trình tham khảo: PROGRAM Dang_Thuc; CONST fi=’EQ.INP’; fo=’EQ.OUT’; inf = 1000000000; VAR n, S : longint; i, j : longint; ch : char; Trang 1 KQ: String; A : array[1..1000] of longint; B : array[1..1000] of longint; memo : array[1..1000,0..5000] of longint; PROCEDURE KhoiTao; Var f: text; Begin Assign(f, fi); Reset(f); n:=0; Read(f, ch); Repeat Inc(n); A[n]:= Ord(ch) – 48; Read(f, ch); Until ch=’=’; Readln(f, S); Close(f); B[n] := n; For i := n-1 downto 1 do if A[i] = 0 then B[i] := B[i+1] else B[i] := i; For i := 1 to n do For j := 0 to S do memo[i,j] := -1; KQ:=’’; End; PROCEDURE GhiFile; Var f: text; Begin Assign(f, fo); Rewrite(f); Write(f, KQ); Close(f); End; FUNCTION Opt( i, sum : longint ) : longint; Var j, broj : longint; Begin if i > n then begin if sum = 0 then opt := 0 else opt := inf; end else begin if memo[i,sum] = -1 then begin memo[i,sum] := inf; broj := 0; for j := B[i] to n do begin broj := broj * 10 + A[j]; if broj > sum then break; if 1 + opt( j+1, sum-broj ) < memo[i,sum] then memo[i,sum] := 1 + opt( j+1, sum-broj ); end; end; Opt := memo[i,sum]; end; End; PROCEDURE Xuly( i, sum : longint ); Var f: text; j, broj : longint; Trang 2 Begin if i > n then begin KQ:=KQ + '=’+ Str(S ); end else begin if i > 1 then KQ:=KQ + '+'; broj := 0; for j := i to n do begin KQ:=KQ + Chr(A[j]+48 ); broj := broj * 10 + A[j]; if opt( i, sum ) = 1 + opt( j+1, sum-broj ) then begin Xuly( j+1, sum-broj ); break; end; end; end; End; BEGIN KhoiTao; Xuly(1, S ); GhiFile; END. Câu 3: TRẠM CANH Tại một vùng đất nọ, người ta bố trí các trạm canh để cảnh báo nguy cơ cho toàn vùng. Mỗi trạm canh gồm có một đài lửa và một cung thủ được trang bị một số lượng tên nhất định. Khi có nguy cơ xuất hiện, một trạm được chỉ định làm trạm xuất phát sẽ tự đốt lửa báo hiệu, sau đó người cung thủ của trạm sẽ bắn tên để thắp lửa cho các trạm khác theo những chỉ thị cho sẵn. Đến lượt mình, mỗi trạm sau khi được thắp lửa, người cung thủ của trạm lại bắn tên để thắp lửa cho các trạm khác, cũng theo những chỉ thị cho sẵn. Việc bắn tên của mỗi cung thủ chỉ kết thúc khi đã sử dụng hết số tên được cấp hoặc khi tất cả các trạm đã được thắp lửa báo hiệu. Xem vùng đất như một mặt phẳng toạ độ và mỗi trạm canh được đặt tại một toạ độ nhất định. Viết chương trình xác định thời điểm mà mỗi trạm được thắp lửa báo hiệu. Giả sử thời gian để một cung thủ bắn tên thắp lửa cho trạm kế tiếp bằng khoảng cách giữa hai trạm (thời gian giữa các loạt bắn là không đáng kể) và trạm số 1 được chỉ định là trạm xuất phát. Ngoài ra, ta cũng giả sử mỗi cung thủ luôn bắn trúng đích. Dữ liệu vào: chứa trong tệp văn bản SPARK.INP có dạng như sau: + Dòng đầu chứa số nguyên dương N (1  N 100) cho biết số trạm canh. + N dòng tiếp theo mỗi dòng chứa N+2 số nguyên theo thứ tự cho biết các thông tin sau:  Hai số nguyên X, Y (1  X,Y 1000) cho biết toạ độ của trạm.  Số nguyên S (1  N 100) cho biết lượng cung tên được cấp cho trạm.  N-1 số nguyên cho biết thứ tự các trạm được chỉ định cho người cung thủ phải bắn tên để thắp lửa tiếp theo. Dữ liệu ra: ghi vào tệp văn bản SPARK.OUT gồm N dòng, mỗi dòng ghi thời điểm mà trạm tương ứng được thắp lửa báo hiệu. Các thời điểm ghi dưới dạng số thập phân với độ chính xác đến 0.001 Ví dụ: SPARK.INP 4 1 1 1 2 3 4 1 2 1 4 1 3 2 1 1 2 1 4 2 2 1 3 2 1 Trang 3 SPARK.OUT 0.000000 1.000000 3.000000 2.000000 Chương trình tham khảo: PROGRAM Tram_Canh; CONST fi=’SPARK.INP’; fo=’SPARK.OUT’; VAR n : longint; x, y, S : array[1..100] of longint; A : array[1..100,1..99] of longint; thoidiem : array[1..100] of real; daxet : array[1..100] of boolean; d : array[1..100,1..100] of real; PROCEDURE KhoiTao; Var f: text; i, j: integer; Begin Assign(f, fi); Reset(f); Readln(f, n); For i := 1 to n do begin read(f, x[i], y[i], S[i]); for j := 1 to n-1 do read(f, A[i,j]); thoidiem[i] := 1000000000; daxet[i] := false; end; Close(f); For i := 1 to n do for j := 1 to n do d[i,j] := sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) ); thoidiem[1] := 0; End; PROCEDURE Xuly; Var i, j: integer; truoc_i, tiep : longint; Begin For i := 1 to n do begin truoc_i := 0; for j := 1 to n do begin if daxet[j] then continue; if truoc_i = 0 then truoc_i := j; if thoidiem[j] < thoidiem[truoc_i] then truoc_i := j; end; daxet[truoc_i] := true; for j := 1 to n-1 do begin tiep := A[truoc_i,j]; if daxet[tiep] then continue; if thoidiem[truoc_i] + d[truoc_i,tiep] < thoidiem[tiep] then thoidiem[tiep] := thoidiem[truoc_i] + d[truoc_i,tiep]; S[truoc_i] := S[truoc_i] - 1; if S[truoc_i] = 0 then break; end; end; End; PROCEDURE GhiFile; Var f: text; i: integer; Trang 4 Begin Assign(f, fo); Rewrite(f); For i:=1 to n do Writeln(f, thoidiem[i]:10:10); Close(f); End; BEGIN KhoiTao; Xuly; GhiFile; END. Câu 1 (6 điểm) - Cặp số song sinh Hai số a, b được gọi là cặp số song sinh nếu như ở dạng biểu diễn nhị phân thì hai số này không được sai khác nhau quá 1 bit. Yêu cầu: Cho trước hai số nguyên dương a và b (a, b đều nhỏ hơn 1.000.000.000). Hãy kiểm tra hai số a, b có phải là cặp số song sinh hay không. Input: File văn bản s3.inp cấu trúc như sau: - Gồm một số dòng (nhỏ hơn 1.000.000); - Mỗi dòng chứa 2 số cần kiểm tra; - Mỗi số trên dòng cách nhau ít nhất một khoảng trắng. Output: File văn bản s3.out cấu trúc như sau: - Gồm 1 dòng, là những con số 0 hoặc 1 đứng liền nhau tạo thành một dãy số nhị phân. - Tính từ trái sang phải, kí tự thứ i là 1 nếu tại dòng thứ i của file input chứa cặp số song sinh; Ngược lại kí tự tại vị trí thứ i là 0 Ví dụ S3.inp 7 3 8 9 S3.out 11 Câu 2 (7 điểm) - Điền khuyết xâu kí tự Cho trước 2 xâu ký tự a, b (chiều dài của mỗi xâu không quá 100). Yêu cầu: Viết chương trình bổ sung một số ký tự vào a và một số ký tự vào b để hai xâu a và b trở nên giống nhau (phân biệt chữ hoa, thường). Tổng số kí tự bổ sung vào là ít nhất. Input: File văn bản fs.inp cấu trúc như sau: - Bao gồm một số dòng (là số chẵn, có thể lên đến 10.000 dòng). - Mỗi dòng là một xâu kí tự (không quá 100 kí tự). Output: File văn bản fs.out cấu trúc như sau: - Gồm một số dòng (là số dòng của file input chia 2) - Dòng thứ i chứa xâu kí tự là kết quả của việc bổ sung 2 xâu tại dòng thứ i*2-1 và i*2 trên file input. Ví dụ: Fs.inp Abcde Abdf Abcdef Câu 3 (7 điểm) - Dãy đặc biệt Dãy số an cho trước được gọi là dãy đặc biệt nếu thỏa 2 điều kiện : - n là số chính phương; - Các phần tử trong an đôi một khác nhau; Trang 5 - Các phần tử trong an có thể lần lượt sắp xếp vào ma trận vuông để tạo thành một ma phương. Chú ý: Ma phương là một ma trận vuông có tính chất sau: tổng các phần tử trên từng dòng bằng tổng các phần tử trên từng cột và cũng bằng tổng các phần tử trên 2 đường chéo. Yêu cầu: Cho dãy an (với -10.000 < ai < 10.000; n là số nguyên dương nhỏ hơn 3000). Viết chương trình kiểm tra xem dãy an có phải là dãy đặc biệt hay không. Nếu phải thì hãy xuất ma phương ra còn không phải thì xuất ra dòng chữ “khong phai day dac biet”. Input: file văn bản ddb.inp. Dòng đầu tiên chứa số n. Dòng tiếp theo chứa n số lần lượt là các phần tử trong dãy. Mỗi số cách nhau ít nhất một khoảng trắng. Output: file văn bản ddb.out. Dòng đầu tiên chứa số m là cấp của ma phương hoặc là chứa dòng chữ “khong phai day dac biet”. Nếu dòng đầu tiên chứa số m thì m dòng tiếp theo mỗi dòng chứa m số là lượt là các phần tử của ma phương (mỗi số cách nhau 1 khoảng trắng). Ví dụ: ddb.inp ddb.out 5 khong phai day dac biet 24356 (Vì n không phải là số chính phương) Bài 2: Var a:array[0..100,0..100] of byte; s1,s2,s3,s4:string; i,j:byte; Begin s1:='121212qqw12121212'; s2:='121wer21212121212'; s3:=''; For i:=0 to length(s1) do a[0,i]:=0; For i:=1 to length(s2) do a[i,0]:=0; For i:=1 to length(s1) do For j:=1 to length(s2) do Begin If s1[i]=s2[j] then a[i,j]:= a[i-1,j-1]+1 else If a[i-1,j]>a[i,j-1] then a[i,j]:= a[i-1,j] Else a[i,j]:= a[i,j-1]; End; i:= length(s1); j:= length(s2); Repeat Begin If (s1[i] = s2[j]) and (a[i,j] = a[i-1,j-1]+ 1) then Begin s3:=s1[i]+s3; dec(j); dec(i); End else If a[i,j] = a[i-1,j] then dec(i) else dec(j); End; Until (i*j=0); s4:=''; For i:=1 to length(s3) do Begin s4:=s4+ copy(s1,1,pos(s3[i],s1)-1); delete(s1,1,pos(s3[i],s1)); s4:=s4+ copy(s2,1,pos(s3[i],s2)-1); delete(s2,1,pos(s3[i],s2)); s4:=s4+s3[i]; Trang 6 End; s4:=s4+s1+s2; Write(s4); Readln; end. Trang 7