Tài liệu De thi kscl doi tuyen hsg tin hoc 12 yen lac 2

SỞ GD&ĐT VĨNH PHÚC TRƯỜNG THPT YÊN LẠC 2 KÌ THI KSCL ĐỘI TUYỂN HỌC SINH GIỎI KHỐI 12 ĐỀ THI MÔN: TIN HỌC 12 NĂM HỌC 2018 - 2019 Thời gian làm bài 180 phút, không kể thời gian giao đề. Đề thi gồm có 03 bài 02 Trang. Tổng quan đề thi Tên bài File chương trình File Input File Output Thời gian Điểm Bài 1 DEM.* DEM.inp DEM.out 1s / test 6 Bài 2 TACH.* TACH.inp TACH.out 1s / test 6 Bài 3 ATM.* ATM.inp ATM.out 1s / test 8 Chú ý: Thí sinh thay * trong tên chương trình là PAS hoặc CPP tùy theo ngôn ngữ lập trình mà thí sinh sử dụng là PASCAL hoặc C++. Bài 1: Đếm số 0 bên phải Cho một số nguyên n. Hãy đếm xem trong kết quả của số n! (n giai thừa) có bao nhiêu chữ số 0 liên tiếp tính từ hàng đơn vị (hay bao nhiêu số 0 liên tiếp bên phải). Dữ liệu vào - Một dòng duy nhất chứa số nguyên n (1 ≤ n ≤ 1.000) Dữ liệu xuất: - Một dòng duy nhất ghi số lượng chữ số 0 liên tiếp tính từ hàng đơn vị của n!. Ví dụ Input Output 8 1 Giải thích 8! = 5040 Bài 2: Tách chuỗi đối xứng Chuỗi đối xứng (palindrome) là chuỗi mà nếu ta đọc từ trái sang phải hay từ phải sang trái thì đều giống nhau. Ví dụ chuỗi 'abcba' là chuỗi đối xứng. Một ký tự duy nhất cũng được gọi là chuỗi đối xứng. Một chuỗi S bất kỳ luôn có thể ghép được từ các chuỗi đối xứng. Ví dụ chuỗi 'bobseesanna' có một số cách ghép như sau: 1) 'b' + 'o' + 'b' + 'sees' + 'a' + 'n' + 'n' + 'a' 2) 'bob' + 'sees' + 'anna' 3) 'bob' + 's' + 'ee' + 's' + 'anna' Tổng quát S = P1 + P2 +...+ Pk. với P1, P2,... , Pk là các chuỗi đối xứng. Bạn hãy tìm cách biểu diễn S sao cho k là bé nhất. Trong ví dụ trên, k = 3 (cách ghép số 2). Dữ liệu vào: - Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 2.000) biểu thị chiều dài chuỗi S. - Dòng thứ hai là chuỗi S gồm n ký tự là các chữ cái la tinh thường từ a đến z. Dữ liệu ra: - Dòng thứ nhất là số nguyên k. VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí - Trong k dòng tiếp theo, tại dòng thứ i là chuỗi đối xứng Pi. Nếu có nhiều cách biểu diễn, chỉ cần in ra một cách bất kỳ. Ví dụ Input 11 bobseesanna output 3 bob sees anna Bài 3: Máy rút tiền ATM Vinh làm việc cho một công ty sản xuất máy ATM. Chức năng cơ bản của một máy ATM là rút tiền mặt. Khi một khách hàng muốn rút M đồng, máy ATM sẽ nhả ra m tờ tiền mà có tổng là W đồng. Trong máy ATM thế hệ tiếp theo, Vinh đang xây dựng một thuật toán để tìm được W (số lượng các tờ tiền) là ít nhất. Giả sử máy ATM có N loại tiền: 1, 2, 3, .., n; mỗi loại có 1 mệnh giá tương ứng là v[1] < v[2] < v[3] < ..< v[n]. Cho biết cách thanh toán cần ít số lượng tờ tiền nhất cho số tiền cần thanh toán là W. Bạn hãy giúp Vinh viết chương trình thực hiện yêu cầu trên. Biết rằng số tiền trong cây ATM lớn hơn số tiền cần rút. Dữ liệu vào: Gồm 2 dòng Dòng 1: Chứa số nguyên dương N và N số nguyên là các loại tiền đơn vị tính bằng đồng v[1]…v[N] Dòng 2: Chứa M là số tiền khách hàng muốn rút tính bằng đồng Dữ liệu xuất: Gồm nhiều dòng Dòng 1: Ghi số W là số lượng tờ tiền ít nhất Dòng 2 trở đi: Gồm 2 số W1 và W2 trong đó W1 là số tờ tiền tương ứng mệnh giá W2 Nếu không có cách rút tiền ghi ra file dòng chữ “nhap lai so tien” Ví dụ Input Output 4 10 20 50 100 450 5 4 100 1 50 --------------------------------Hết-------------------------------Thí sinh không sử dụng tài liệu để làm bài Cán bộ coi thi không giải thích gì them Họ và tên thí sinh:………………………………………Số báo danh:…………… VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí SỞ GD&ĐT VĨNH PHÚC TRƯỜNG THPT YÊN LẠC 2 ĐÁP ÁN KSCL ĐỘI TUYỂN HỌC SINH GIỎI KHỐI 12 ĐỀ THI MÔN: TIN HỌC 12 NĂM HỌC 2018 - 2019 Thời gian làm bài 180 phút, không kể thời gian giao đề. Đề thi gồm có 03 bài 02 Trang. Bài 1: Đếm số 0 bên phải Chương trình mẫu var a,d,i,e:longint; f1,f2 :text; begin assign(f1,’dem.inp’); reset(f1); assign(f2,’dem.out’);rewrite(f2); readln(f1,a); d:= 0; for i:=1 to a do begin e:=i; while e mod 5 = 0 do begin inc(d); e := e div 5; end; end; writeln(f2,d); close(f1); close(f2); end. Đáp án: Bài 2: Tách chuỗi đối xứng var i,j,n,m,t:longint; a:array[0..100000] of char; f:array[0..10000,0..10000] of longint; k,d,kt:array[-10000..10000] of longint; //f1, f2:text; procedure motep; begin assign(f1,'TACH.inp'); reset(f1); readln(f1,n); for i:=1 to n do read(f1,a[i]); assign(f2,'TACH.out'); rewrite(f2); end; procedure xuli; begin for i:=n downto 1 do begin f[i,i]:=1; if i<>n then if a[i]=a[i+1] then f[i,i+1]:=1; for j:=i+2 to n do if (a[i]=a[j]) and (f[i+1,j-1]=1) then f[i,j]:=1; VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí end; for i:=1 to n+1 do d[i]:=n*2; d[0]:=0; for i:=1 to n do for j:=1 to n do begin if f[i,j]=1 then if d[j]>=d[i-1]+1 then begin d[j]:=d[i-1]+1; kt[j]:=i; end; end; writeln(d[n]); t:=n; while t>0 do begin k[kt[t]-1]:=1; t:=kt[t]-1; end; for i:=1 to n do begin write(a[i]); if k[i]=1 then writeln; end; close(f1); close(f2); end; begin motep; xuli; end. Bài 3: Rút tiền ATM *Đặt lại bài toán: Có N loại tiền: 1, 2, 3, .., n; mỗi loại có 1 mệnh giá tương ứng là v[1] < v[2] < v[3] < ..< v[n]. Cho biết cách thanh toán cần ít số lượng tờ tiền nhất cho số tiền cần thanh toán là M. Cách giải Gọi F[i, j] số lượng tờ tiền cần trả (cách trả cần ít tờ tiền nhất) có sử dụng i loại tờ tiền (1, 2, 3,.., i) cho số tiền j. Giá trị cuối cùng: F[N, M] là kết quả của cách thanh toán; dùng N loại tờ tiền (1, 2, 3, ..., N) cho số tiền M. *Công thức truy hồi: với việc chọn tối ưu số loại tiền 1, 2, 3, .., i để thanh toán số tiền j, F[i, j] sẽ có 2 khả năng: 1). F[i, j] = F[i-1, j]; Không dùng được loại tiền i để thanh toán số tiền j. 2). F[i, j] = 1 + F[i, j-v[i]]; Có dùng loại tiền i để thanh toán số tiền j (đk: j >= v[i]). F[i, j] là cách trả cần ít tờ tiền nhất, cho nên sẽ là min trong 2 giá trị thu được ở trên. VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí *Cơ sở quy hoạch động: F[0, j] = vô cùng; (1<= j <= M) (quy định: nếu dùng các tờ tiền loại 0, có mệnh giá v[0] = 0 thì sẽ cần vô cùng tờ tiền mới thanh toán được cho số tiền j) F[i, 0] = 0; (1<=i<=N) không có cách trả cho số tiền = 0. {Quy Hoach Dong, Rut tien} Program OptimizeCurrency; Const NMax = 500; MMax = 65535; Var currency : Array[1..NMax] of Word; value : Array[1..NMax] of Word; F : Array[0..NMax, 0..MMax] of Word; N, M : Word; Procedure Init; Var i : Word; Begin assign(f1,'ATM.inp'); reset(f1); assign(f2,'ATM.out'); rewrite(f2); readln(f1,n); For i := 1 to N do Begin Read(f1,currency[i]); value[i] := currency[i]; End; Readln(f1); Readln(f1,M); For i := 1 to M do F[0, i] := M+1; For i := 1 to N do F[i, 0] := 0; End; Procedure Optimize; Var i,j : Word; Begin For i := 1 to N do For j := 1 to M do Begin F[i, j] := F[i-1, j]; If (j >= value[i]) And (F[i, j] >= 1 + F[i, j - value[i]]) Then F[i, j] := 1 + F[i, j - value[i]]; End; End; Procedure Result; Var i, j, c: Word; Begin If F[N, M] = M+1 Then Writeln(f2,'Khong the thanh toan!') Else Begin Writeln(f2,'So luong to tien can tra cho so tien ', M, ' la: ', F[N, M]); VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí Writeln('Cu the, cac loai to tien duoc thanh toan la: '); i := N; j := M; c := 1; While j > 0 do Begin If F[i, j] < F[i-1, j] Then Begin {Co dung loai tien i} Writeln('To tien thu ', c , ' - loai: ', currency[i]); j := j - value[i]; c := c + 1; End Else Begin {Khong dung loai tien i} i := i - 1; End; End; End; Readln; End; BEGIN Init; Optimize; Result; END. VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí Hướng dẫn chấm Bài 1 Test Input 1 4 2 8 3 20 4 25 5 49 6 124 7 625 8 874 9 875 10 999 Bài 2 Test 1 2 3 4 5 11 bobseesanna Output 0 1 4 6 10 28 156 215 218 246 Input 4 noon 2 ab 6 google 9 abcbxbcby 20 aaabbbbccccddddeeeef 6 7 8 100 aaaaaaaaaaaaaaaaaaabbbbbbbbbbbb bbbbbbbbccccccccccccccccccc cddddddddddddddddddddeeeeeeeee eeeeeeeeeeef 80 bcdefghijkkjihgfedcxbcdefghijkkjih gfedcbbcdefghijkkjihgfedcbbcdefgh Output 3 bob sees anna 1 noon 2 a b 3 goog l e 3 a bcbxbcb y 6 aaa bbbb cccc dddd eeee f 6 aaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbb cccccccccccccccccccc dddddddddddddddddddd eeeeeeeeeeeeeeeeeeee f 4 b cdefghijkkjihgfedc Điểm 0.5 0.5 0.5 0.5 0.5 0.5 0.75 0.75 0.75 0.75 Điểm 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.75 VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí ijkkjihgfedcb 9 81 abcdefghijkkjihgfedcbbcdefghijkkji hgfedcbbcdefghijkkjihgfedcbbcdefg hijkkjihgfedcb 100 bbcdabdcaacdaabdadaaacbbdcababa cacbbddcabadbaabdbaddbaddacccaa dbaaaadbacacadbadcccdbddbadccac dbabbbd 10 x bcdefghijkkjihgfedcbbcdefghijkkji hgfedcbbcdefghijkkjihgfedcb 2 a bcdefghijkkjihgfedcbbcdefghijkkji hgfedcbbcdefghijkkjihgfedcbbcdef ghijkkjihgfedcb 47 bb c d a b dcaacd aa b dad aaa c bb d c ababa cac bb dd c aba dbaabd b a dd b adda ccc aa d b aaaa d b acaca d b a dcccd bddb a d c 0.75 0.75 VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 11 Bài 3: Test cac d bab bb d 640 1 bcdefghijklmnopqrstuutsrqponmlkji bcdefghIjklmnopqrstuutsrqponmlk hgfedcbbcdefghijklmnopqrStuutsrqp jihgfedcbbcdEfghijklmnopqrstuuts onmlkjihgfedcbbcdefghijklmnopqrst rqponmlkjihgfedCbbcdefghijklmn uutsrqponmlkjihgfedcbbcdeFghijkl opqrstuutsrqponmlkjihgfEdcbbcde mnopqrstuutsrqponmlkjihgfedcbbcd fghijklmnopqrstuutsrqponmlkJihgf efghijklmnopqrstuutsrqponmlkjIhgf edcbbcdefghijklmnopqrstuutsrqpo edcbbcdefghijklmnopqrstuutsrqpon nmlkjihg ... mlkjihgfedcbbcdefghijklmnopqrstuu tsrqpOnmlkjihgfedcbbcdefghijklmn opqrstuutsrqponmlkjihgfedcbbcdefg hijklmnopqrstuutsrqponmlkjihgfedc bbcdefghijklmnopqrstuutsrqponmlkj i ... Input Output 1 4 10 20 50 100 450 5 4 100 1 50 Nhap lai so tien 2 5 10 20 50 100 200 755 3 5 10 20 50 100 200 10000 500 500 200 4 5 10 20 50 100 200 1240 62 60 200 2 20 0.75 Điểm 2.0 2.0 2.0 2.0 Xem thêm các bài tiếp theo tại: https://vndoc.com/tai-lieu-hoc-tap-lop-12 VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí