Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết)

 Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
Giới hạn dữ liệu:
- Có 80% số test ứng với 80% số điểm có giá trị n ≤ 103;
- Có 20% số test ứng với 20% số điểm có giá trị n ≤ 105.
 -----------HẾT-----------
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
 ĐÁP ÁN
Bài 1. (7,0 điểm) PHƯƠNG TRÌNH BẬC HAI. Gồm 10 bộ test, mỗi bộ test 0,7 điểm.
 Test PTB2.OUT Điểm
 1 30 82 0,7
 2 70 236 0,7
 3 120 372 0,7
 4 175 462 0,7
 5 250 604 0,7
 6 285 252 0,7
 7 300 132 0,7
 8 2993 20 0,7
 9 3000 13158 0,7
 10 99997 4999600008 0,7
Bài 2. (7,0 điểm) ĐOÀN XE QUA CẦU. Gồm 10 bộ test, mỗi bộ test 0,7 điểm.
 Test DOANXE.INP DOANXE.OUT Điểm
 1 11010 0.17 0,7
 2 32030 1.20 0,7
 3 53050 2.80 0,7
 4 85080 22.53 0,7
 5 96085 26.97 0,7
 6 105065 20.04 0,7
 7 508090 115.60 0,7
 8 808070 203.77 0,7
 9 100100100 428.19 0,7
 10 1000100100 4600.12 0,7
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
Bài 3. (6,0 điểm) VẬN CHUYỂN. Gồm 10 bộ test, mỗi bộ test 0,6 điểm.
 Test VANCHUYEN.INP VANCHUYEN.OUT Điểm
 1 101539 2 0,6
 2 10011155100 252 0,6
 3 1501607999 54 0,6
 4 27930076153 1024 0,6
 5 50050042465 878 0,6
 6 700800268527 2898 0,6
 7 950955418894 4472 0.6
 8 100010007663 479 0,6
 9 99991000009991132 3493 0.6
 10 100000100000999911234 41726 0,6
Hướng dẫn thuật toán:
Bài 1. (7,0 điểm) PHƯƠNG TRÌNH BẬC HAI
Nhận xét: Vì phương trình bậc hai ax2 +bx + c = 0 có nghiệm x = 1 nên thay x = ―1 vào 
phương trình, ta có a ⋅ ( ― 1)2 ―b ⋅ ( ― 1) + c = 0⇔a ― b + c = 0⇔a + c = b
Bài toán đưa về đếm số bộ ba phần tử của dãy số thoả điều kiện tổng hai phần từ bằng phần 
từ còn lại.
- Subtask 1 : n ≤ 300
Dùng 3 lệnh lặp duyệt 3 chỉ số 푖,푗, sao cho [푖] + [푗] = [ ] (với 푖 ≠ 푗)
Độ phức tạp : O(n3).
- Subtask 2 : 푛 ≤ 3000
Vì các phân tử của dãy là số dương nên ta có a,c < b.
Sắp xếp dãy theo thứ tự tăng dần, duyệt xét từng phần tử b = u[k].
Với mỗi giá trị k, duyệt các chỉ số i và tìm kiếm nhị phân tìm chỉ số j. 
Độ phức tạp O 푛2log 푛
Hoặc dùng phương pháp 2 con trỏ tìm hai chỉ số 푖,푗, Độ phức tạp (푛2).
 5
- Subtask 3: n ≤ 10 ,ui ≤ n
Vì các phần tử của dãy là đôi một khác nhau và 푖 ≤ 푛 nên dãy đã cho chính là hoán vị của n 
số nguyên dương đầu tiên.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
Với mỗi giá trị k(1 ≤ k ≤ n), sử dụng công thức để tính số cách chọn cặp số i,j sao cho i +
j = k. Độ phức tạp O(n).
Bài 2. (7,0 điểm) ĐOÀN XE QUA CẦU
Gọi 퐹[푖] là thời gian ngắn nhất khi các xe từ xe 1 đến xe i qua cầu, ta có:
 퐹[푖] = Min{퐹[푗 ― 1] + (푗,푖)},푗 = 1,푖 ― 1
với T(j,i) là thời gian để nhóm từ xe thứ j đến thứ i qua cầu cùng lúc, T(j,i) = L/min(vj,.,vi)
khiwj + + wi ≤ P
Độ phức tạp thuật toán (푛2).
Bài 3. (6,0 điểm) VẬN CHUYỂN 
Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ s đến t.
- Subtask 1 : n ≤ 103
Sử dụng thuật toán Dijkstra thông thường.
- Subtask 2 : n ≤ 105
Sử dụng thuật toán Dijkstra kết hợp cấu trúc dữ liệu Heap.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
 ĐỀ SỐ 4
 SỞ GD VÀ ĐT THANH HÓA ĐỀ KIỂM TRA CHẤT LƯỢNG ĐỘI TUYỂN 
 TRƯỜNG THPT TRIỆU SƠN 4 HSG CẤP TRƯỜNG
 Môn: Tin học - Lớp 12 THPT
 Thời gian: 180 phút (không kể thời gian giao đề)
 Tổng quan bài thi
 Tên bài File chương trình File dữ liệu vào File kết quả
Bài 1 Cặp số Lucasa BAI1.* BAI1.INP BAI1.OUT
Bài 2 Số anh em BAI2.* BAI2.INP BAI2.OUT
Bài 3 Hạt nhân BAI3.* BAI3.INP BAI3.OUT
Bài 4 Phần tử chung BAI4.* BAI4.INP BAI4.OUT
Bài 5 Giả thuyết của Collatz BAI5.* BAI5.INP BAI5.OUT
Dữ liệu vào là đúng đắn, không cần phải kiểm tra. Trong các file dữ liệu vào, nếu dữ liệu 
trên cùng một dòng thì được cách nhau bởi ít nhất 1 dấu cách. Dấu (*) trong tên file chương 
trình biểu thị đuôi file tùy thuộc vào NNLT sử dụng ('pas' đối với NNLT PASCAL, ‘c’ đối với 
NNLT C,...).
Bài 1 (6 điểm): Cặp số Lucasa
Cặp số (a,b) được gọi là lucasa nếu: b là bình phương của a và các chữ số của a xuất hiện lần 
lượt ở cuối trong các chữ số của b.
Ví dụ: (1,1); (25,625) là các cặp số lucasa còn (15,225) không phải là cặp số lucasa.
Cho số tự nhiên N (N ≤ 1012). Đếm số cặp số lucasa không lớn hơn N và in ra các cặp số đó 
theo thứ tự từ bé đến lớn và a<=b.
Dữ liệu vào: trong file BAI1.INP ghi số tự nhiên N.
Kết quả: ghi ra file BAI1.OUT dòng đầu tiên là số k – số cặp số lucasa, k dòng sau mỗi 
dòng là một cặp số lucasa từ nhỏ đến lớn.
 BAI1.INP BAI1.OUT
 10000 5
 1 1
 5 25
 6 36
 25 625
 76 5776
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
Bài 2 (5 điểm): Số anh em 
Ước thực sự của số tự nhiên N là ước nguyên dương khác 1 và chính nó. Hai số được gọi là 
anh em nếu chúng có tổng các ước thực sự bằng nhau.
Ví dụ: 6 và 25 được gọi là hai số anh em vì các ước thực sự của 6 là 2 và 3 có tổng bằng 5 và 
các ước thực sự của 25 là 5 có tổng là 5.
Yêu cầu: Viết chương trình để kiểm tra hai số có phải là hai số anh em không?
Dữ liệu vào: từ file văn bản BAI2.INP: Gồm các dòng, mỗi dòng chứa hai số nguyên dương 
M, N (0 < M, N < 104) cách nhau ít nhất một ký tự trống.
Kết quả: ghi file văn bản BAI2.OUT: Gồm các dòng, mỗi dòng chứa xâu ‘YES’ nếu M, N là 
hai số anh em, ngược lại ghi ra xâu ‘NO’.
Ví dụ: 
 BAI2.INP BAI2.OUT
 6 25 YES
 12 13 NO
Bài 3 (4 điểm): Hạt nhân
Xâu u được gọi là hạt nhân của xâu v nếu u là xâu ngắn nhất sao cho ghép một số lần u thì 
nhận được v. Cho xâu S, tìm hạt nhân của nó.
Dữ liệu vào: từ file BAI3.INP gồm một xâu S (có độ dài ≤ 100000 ký tự).
Dữ liệu ra: ghi ra file BAI3.OUT là hạt nhân của xâu S.
Ví dụ:
 BAI3.INP BAI3.OUT
 abcabcabc abc
Bài 4 (3 điểm): Phần tử chung
Cho k dãy số nguyên, các số trong dãy thuộc đoạn [-109..109] . Hãy viết chương trình tìm số 
xuất hiện trong cả k dãy. Nếu không có số nào xuất hiện trong cả k dãy thì ghi kí tự “x”, còn 
nếu có nhiều số cùng xuất hiện trong k dãy thì ghi số nhỏ nhất tìm được.
Dữ liệu vào: từ file BAI4.INP 
Dòng 1: chứa số nguyên dương;
Dòng 2: gồm số lần lượt là độ dài từng dãy; dòng sau, mỗi dòng mô tả một dãy số, biết rằng 
tổng số lượng số trong dãy không vượt quá 500000 số.
Kết quả: ghi ra file BAI4.OUT: Ghi số tìm được hoặc ghi kí tự “x”
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
Ví dụ:
 BAI4.INP BAI4.OUT
 2 2
 3 4
 1 2 3
 4 3 2 -1
Bài 5 (2 điểm) Giả thuyết của Collatz
Collatz đưa ra giả thuyết: Với một số nguyên dương X, nếu X chẵn ta gán X=Xdiv 2, nếu X 
lẻ ta gán X = X*3 + 1 thì sau một số hữu hạn bước ta sẽ có X=1.
Ví dụ: Với X=10, các bước tiến hành như sau:
1) X=10 (chẵn) X=10 div 2 = 5
2) X=5 (lẻ) X= 5*3 + 1 = 16
3) X=16 (chẵn) X=16 div 2 = 8
4) X=8 (chẵn) X=8 div 2 =4
5) X=4 (chẵn) X=4 div 2 =2
6) X=2 (chẵn) X= 2 div 2 =1
Cứ cho giả thuyết Collatz là đúng đắn, bài toán đặt ra là:
Cho trước một số 1 cùng với hai phép toán *2 và div 3, hãy sử dụng một cách hợp lí hai phép 
toán đó để biến số 1 thành một giá trị nguyên dương X cho trước.
Dữ liệu: Vào từ văn bản BAI5.INP: Gồm một dòng duy nhất chứa số X (X≤1019).
Kết quả: Ghi ra file văn bản BAI5.OUT: Là kết quả tìm được của bài toán. 
Ví dụ: 
 BAI5.INP BAI5.OUT
 10 1*2*2*2*2div3*2
 ----------HẾT----------
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
 ĐÁP ÁN
Bài 1 (6 điểm): Cặp số Lucasa
Pascal
Const fi='BAI1.INP';
 fo='BAI1.OUT';
Var n,i,j:int64;
 d:Byte;
 s,s1: Ansistring;
 luu: Array[1..30] of int64;
BEGIN
 Assign(input,fi); Reset(input);
 Assign(output,fo); Rewrite(output);
 Readln(N);
 i:=0; d:=0;
 n:=round(sqrt(n));
 While (i <= N) do
 Begin
 i:=i + 1;
 str(i,s);
 j:=i*i;
 str(j,s1);
 if pos(s,s1) = length(s1) - length(s) +1 then
 Begin
 d:=d+1;
 luu[d]:=i;
 End;
 End;
 Writeln(d);
 i:=1;
 While i<= d do
 Begin
 Writeln(luu[i],' ',sqr(luu[i]));
 inc(i);
 End;
 Close(output);
END.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
Bài 2 (5 điểm): Số anh em 
Pascal
const fi = 'BAI2.INP';
 fo = 'BAI2.OUT';
 VAR i, j, m, n: word;
 f1, f2: text;
 FUNCTION KT(x,y:word):Boolean;
 var i,j:word;
 sx,sy:longint;
 ok:boolean;
 BEGIN
 Sx:=0; Sy:=0;
 For i:=2 to x div 2 do
 if x mod i = 0 then Sx:=Sx+i;
 For j:=2 to y div 2 do
 if y mod j = 0 then Sy:=Sy+j;
 If (Sx = Sy) and (sx>0) Then
 ok:=TRUE
 else ok:=FALSE;
 KT:=ok;
 END;
 procedure xuly;
 begin
 assign(f1, fi); reset(f1);
 assign(f2,fo);rewrite(f2);
 While not eof(f1) do
 Begin
 Readln(f1,m,n);
 If KT(m,n)=TRUE then
 writeln(f2, 'YES') else writeln(f2, 'NO');
 End;
 end;
 procedure dongtep;
 begin
 close(f1);
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 cấp Trường (Có giải chi tiết) - De-Thi.com
 close(f2);
 end;
 BEGIN
 xuly;
 dongtep;
 END.
Bài 3 (4 điểm): Hạt nhân
Pascal
Program Hat_nhan;
Const fi='BAI3.INP';
 fo='BAI3.OUT';
Var s, s1: Ansistring;
 i:longint;
Function KT(u:Ansistring): Boolean;
 Var i:longint;
 ss:Ansistring;
 Begin
 KT:=True;
 if length(s) mod length(u)=0 then
 Begin
 ss:='';
 For i:=1 to length(s) div length(u) do
 ss:=ss+u;
 if ss=s then exit
 End;
 KT:= False;
 End;
BEGIN
 Assign(input,fi); Reset(input);
 Assign(output,fo); Rewrite(output);
 Readln(s);
 i:=0;
 Repeat
 inc(i);
 s1:=copy(s,1,i);
 De-Thi.com