Đề thi chọn HSG Tin học 12 năm 2012-2013

Chia sẻ: Trần Văn được | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST

Báo xấu

608
lượt xem 40
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề thi chọn học sinh giỏi Tin học 12 năm 2012-2013 dành cho học sinh và giáo viên tham khảo, giúp các em phát triển và tư duy năng khiếu của mình, nhằm giúp bạn củng cố kiến thức luyện thi học sinh giỏi đạt kết quả cao.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi chọn HSG Tin học 12 năm 2012-2013

SỞ GD&ĐT NINH BÌNH ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT Kỳ thi thứ nhất - Năm học 2012 – 2013 ĐỀ THI CHÍNH THỨC MÔN: TIN HỌC Ngày thi: 09/10/2012 (Thời gian làm bài:180 phút ) Đề thi gồm 04 câu, trong 02 trang Tổng quan đề thi: Câu Tên file bài làm Tên file Input Tên file Otput Thời gian chạy 1 NUMBER.PAS NUMBER.INP NUMBER.OUT 1 giây/test 2 GOMBI.PAS GOMBI.INP GOMBI.OUT 1 giây/test 3 TRIANGLE.PAS TRIANGLE.INP TRIANGLE.OUT 2 giây/test 4 PASCAL.PAS PASCAL.INP PASCAL.OUT 1 giây/test Ghi chú: Thí sinh phải đặt tên file bài làm, file Input, file Output theo quy định như trên. Câu 1: Chữ số thứ N. Khi viết các số tự nhiên tăng dần từ 1, 2, 3,… liên tiếp nhau, ta nhận được một dãy các chữ số thập phân vô hạn, đoạn đầu tiên của dãy sẽ là: 1234567891011121314151617181920... Yêu cầu: Hãy tìm chữ số thứ N của dãy số vô hạn trên. Dữ liệu: Cho trong file NUMBER.INP gồm một nguyên dương N (N < 106). Kết quả: Ghi kết quả ra file NUMBER.OUT. Ví dụ: NUMBER.OUT NUMBER.OUT Giải thích kết quả 21 5 Chữ số thứ 21 trong dãy là chữ số 5 Câu 2: Gom bi. Có N cái hộp đánh số từ 1 tới N và N viên bi cũng đánh số từ 1 tới N. Ban đầu bi số i đặt trong hộp đánh số i (i = 1..N). Với một cặp số nguyên (u, v) cho trước, bạn phải thực hiện thao tác chuyển tất cả các bi cùng hộp với bi có số u vào hộp chứa bi số v. Yêu cầu: Cho số N và danh sách M thao tác cần phải thực hiện. Hãy xác định số lượng bi lớn nhất trong một hộp sau khi đã thực hiện đủ M thao tác chuyển bi. Dữ liệu: Cho trong file GOMBI.INP  Dòng 1 là hai số N, M (2 ≤ N ≤ 500; 1 ≤ M ≤ 1000).  M dòng tiếp theo, mỗi dòng chứa hai số nguyên u v thể hiện một thao tác cần thực hiện Kết quả: Ghi ra file GOMBI.OUT một số nguyên là số lượng bi trong hộp có nhiều bi nhất sau khi thực hiện các thao tác. Ví dụ: GOMBI.INP GOMBI.OUT Giải thích: Các hộp có bi sau mỗi lần chuyển. 74 4 Ban đầu: (1) (2) (3) (4) (5) (6) (7) 13 Chuyển 1 3: (2) (1 3) (4) (5) (6) (7) 26 Chuyển 2 6: (1 3) (4) (5) (2 6) (7) 16 Chuyển 1 6: (4) (5) (1 2 3 6) (7) 12 Chuyển 1 2: (4) (5) (1 2 3 6) (7) Câu 3: Tam giác cân. Cho hệ trục tọa độ Oxy, trên đó có đánh dấu n điểm (3 ≤ n ≤ 1500). Điểm thứ i có tọa độ (xi, yi) (i = 1 ÷ n), các tọa độ là số nguyên có giá trị tuyệt đối không vượt quá 10 9. Yêu cầu: Xác định số tam giác cân có ba đỉnh là ba điểm trong số n điểm đã cho. Dữ liệu: Cho trong file TRIANGLE.INP:  Dòng đầu tiên chứa số nguyên n.  Dòng thứ i trong n dòng sau chứa 2 số nguyên x i và yi.
Kết quả: Ghi ra file TRIANGLE.OUT số tam giác cân tìm được. Ví dụ: TRIANGLE.INP TRIANGLE.OUT 4 4 00 11 10 01 Chú ý: Trong 60% số test có n < 200. Câu 3(6 điểm): Tam giác PASCAL. Tam giác Pascal là một cách sắp xếp các hệ số khi khai triển nhị thức Newton vào một hình có dạng tam giác theo từng hàng, các hàng được đánh số bắt đầu từ 0, hàng thứ n (n ≥ 0) của tam giác bao gồm các hệ số trong khai triển của (x + y)n viết lần lượt từ trái sang phải. Dòng 0: (x + y)0 = 1 Dòng 1: (x + y)1 = 1.x + 1.y Dòng 2: (x + y)2 = 1.x2 + 2.xy + 1.y2 Dòng 3: (x + y)3 = 1.x3 + 3.x2y + 3.xy2 + 1.y3 … Dưới đây các hàng từ 0 đến 16 của Tam giác Pascal: Yêu cầu: Cho số tự nhiên n. Hãy tính số lượng số hạng là số lẻ trên dòng thứ n của tam giác Pascal. Dữ liệu: Cho trong file PASCAL.INP cấu trúc như sau: dòng đầu là số nguyên k < 10 là số lượng số n, k dòng tiếp theo mỗi dòng ghi một số n (1< n < 2.109) Kết quả: Ghi ra file PASCAL.OUT k dòng, mỗi dòng một số nguyên là kết quả bài toán tương ứng với một số n trong file dữ liệu theo đúng thứ tự. Ví dụ: PASCAL.INP PASCAL.OUT 3 4 3 2 8 8 11 Chú ý: Trong 40 % số test có n < 30; trong 70% số test có n < 5000. -----------------------------Hết-------------------------- Họ và tên thí sinh :....................................................... ……………..Số báo danh ............................. Họ và tên, chữ ký: Giám thị 1:...................................................................................................... Giám thị 2:.......................................................................................................
HƯỚNG DẪN CHẤM THI CHỌN HỌC SINH GIỎI LỚP 12 THPT Kỳ thi thứ nhất - Năm học 2012 – 2013 MÔN: TIN HỌC Chấm bằng chương trình tự động AMM2: Câu 1: 10 test, mỗi test đúng cho 0,5 điểm. Câu2: 10 test, mỗi test đúng cho 0,5 điểm. Câu3: 10 test đầu, mỗi test đúng cho 0,3 điểm. 10 test sau, mỗi test đúng cho 0,2 điểm. Câu 4: 10 test, mỗi test đúng cho 0,5 điểm. Bài 1: Const fi ='number.inp'; fo ='number.out'; cs:array[1..8] of longint = (9, 180, 2700, 36000, 450000, 5400000, 63000000, 720000000); Var n : longint; f,g :text; Function num(n:longint):char; var k, so, mu : longint; s : string; Begin k:=1; mu:=1; while (k
readln(f,n,m); for i:=1 to m do readln(f,u[i],v[i]); close(f); for i:=1 to n do cha[i]:=-1; end; procedure Join(u,v:longint); begin While cha[u]>0 do u:=cha[u]; While cha[v]>0 do v:=cha[v]; if u = v then exit; if cha[u]
assign(f,fi); reset(f); readln(f,n); for i:=1 to n do readln(f,a[i].x,a[i].y); close(f); end; function truoc(t1,t2:td):boolean; begin truoc:=true; if t1.y
if dau0 then begin inc(d); kc[d]:=m; end; end; if d>1 then begin qsort(1,d); tinh(kc); end; end; end; procedure loaitru; var i,j,l,r,m,d,c,u:integer; look:td; nb:boolean; begin for i:=1 to n do for j:=i+1 to n do begin
if ((a[i].x+a[j].x) mod 2=0) and ((a[i].y+a[j].y) mod 2=0) then begin look.x:=(a[i].x+a[j].x) div 2; look.y:=(a[i].y+a[j].y) div 2; l:=1; r:=n; while llook.y) or ((a[m].y=look.y) and (a[m].x>look.x)) then r:=m-1 else if (a[m].y
SỞ GD&ĐT NINH BÌNH ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT Kỳ thi thứ nhất - Năm học 2012 – 2013 ĐỀ THI CHÍNH THỨC MÔN: TIN HỌC Ngày thi: 10/10/2012 (Thời gian làm bài: 180 phút) Đề thi gồm 04 câu, trong 02 trang Tổng quan đề thi: Câu Tên file bài làm Tên file Input Tên file Otput Thời gian chạy 1 TOUR.PAS TOUR.INP TOUR.OUT 1 giây/test 2 HAIVAN.PAS HAIVAN.INP HAIVAN.OUT 1 giây/test 3 FROG.PAS FROG.INP FROG.OUT 1 giây/test 4 EC.PAS EC.INP EC.OUT 1 giây/test Câu 1: Thăm quan. Có N đoàn khách du lịch được đánh số từ 1 đến N đang chờ Công ty du lịch Ninh Bình đưa đi thăm quan theo hợp đồng. Đoàn thứ i sẽ đi tới thăm quan ở địa điểm cách trụ sở Công ty di km. Công ty có M xe khách (N≤ M) đánh số từ 1 tới M, xe thứ j có mức tiêu thụ xăng là vj lít/km. Yêu cầu: Hãy chọn N xe và bố trí để đưa các đoàn đến địa điểm thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng lượng xăng cần phải sử dụng là ít nhất. Dữ liệu: Cho trong file TOUR.INP  Dòng 1 chứa hai số nguyên N, M ( N≤ M ≤ 500).  Dòng 2 chứa N số nguyên dương d 1, d 2,..., d N (di < 10 4).  Dòng 3 chứa M số nguyên dương v1, v2, ..., vM (vi < 104). Kết quả: Ghi ra file TOUR.OUT một số nguyên là lượng xăng ít nhất cần cung cấp cho các xe. Ví dụ: TOUR.INP TOUR.OUT 34 256 759 17 13 15 10 Câu 2: An toàn đường hầm Hải Vân. Hầm đèo Hải Vân nối liền hai địa danh nổi tiếng miền trung Việt Nam là Huế và Đà Nẵng. Theo quy định, xe ô tô đi trong đường hầm không được vượt nhau. Đầu năm 2012 (là năm an toàn giao thông), ban quản lý đã đặt camera theo dõi xe ô tô vào và ra đường hầm. Có N xe ô tô đánh số từ 1 tới N được camera ghi nhận đi vào đường hầm (bên địa phận Huế) và ra khỏi đường hầm (bên địa phận Đà Nẵng). Yêu cầu: Dựa vào thứ tự các xe vào và ra khỏi đường hầm, xác định số lượng xe ra đường hầm không đúng thứ tự như khi đi vào và số lượng những xe chắc chắn đã vượt xe khác trong đường hầm. Dữ liệu: Cho trong file HAIVAN.INP:  Dòng 1 chứa số nguyên N ( N ≤ 10 5).  Dòng 2 chứa N số lần lượt là chỉ số các xe theo thứ tự đi vào đường hầm.  Dòng 3 chứa N số lần lượt là chỉ số các xe theo thứ tự đi ra khỏi đường hầm. Kết quả:Ghi ra file HAIVAN.OUT trên 02 dòng:  Dòng 1 chứa số nguyên K - số xe đi ra không đúng thứ tự như khi vào đường hầm.  Dòng 2 chứa số nguyên M - số xe đã vượt xe khác trong hầm. Nếu không có xe nào phạm luật thì mỗi dòng ghi một số 0. Ví dụ: HAIVAN.INP HAIVAN.OUT Giải thích
5 4 Xe 2, 3, 4, 5 ra không đúng thứ tự 12345 3 Xe 3, 4, 5 đã vượt xe 2 14532 Chú ý: Trong 60% số test có n < 200; Trong mỗi test, chỉ làm đúng 1phần vẫn được cho điểm phần đó. Câu 3: Chú ếch. Chú ếch con phải giải quyết một chuyện phức tạp: có một hàng N lá bông súng trên mặt nước đánh số từ 1 đến N từ trái qua phải (2 ≤ N ≤ 105), khi chú ếch đang ngồi ở lá thứ m mỗi bước chú có thể nhảy sang một trong k lá bông súng khác có thứ tự là m + pi (i = 1, 2,..,k; k ≤ 1000). Chú ếch của chúng ta ban đầu ở lá a và cần di chuyển trên các lá bông súng để đến bắt con ruồi ở lá b (1 ≤ a, b ≤ N, a ≠ b). Yêu cầu: Cho n, a, b và các bước nhảy ếch có thể thực hiện. Hãy chỉ ra số bước nhảy ít nhất để ếch đến bắt được ruồi tại lá b. Dữ liệu: Cho trong file FROG.INP:  Dòng 1 chứa 4 số nguyên N, k, a và b.  Trên k dòng sau mỗi dòng là một số nguyên pi (|pi| < N). Kết quả: Ghi ra file FROG.OUT số bước nhảy ít nhất tìm được. Nếu không có cách nhảy ghi -1. Ví dụ: FROG.INP FROG.OUT 5223 2 2 -1 Chú ý: Trong 60% số test có n < 30. Bài 4: Ép cọc. Một công trình xây dựng đang cần thi công việc ép N chiếc cọc. Người ta sử dụng một chiếc máy ép cọc. Mỗi lần sử dụng, máy có thể ép được những cọc thuộc hình tròn bán kính R, tâm là vị trí máy. Giả thiết rằng khu vực thi công nằm trong hệ trục Oxy và máy chỉ được đặt trên trục Ox tại các điểm có tọa độ nguyên. Do mỗi lần vận hành máy rất vất vả tốn kém nên các thợ máy muốn xác định số lần ép cọc ít nhất có thể. Yêu cầu: Cho biết tọa độ của N chiếc cọc, hãy xác định số lần sử dụng máy ít nhất có thể ép được tất cả N cọc. Dữ liệu: Cho trong file EC.INP:  Dòng 1 chứa 2 số nguyên dương N và R. (N≤105, R ≤103).  Trong N dòng tiếp theo, mỗi dòng chứa 2 số nguyên xi và yi thể hiện tọa độ cọc thứ i ( 0 ≤xi ≤10 9 ; | yi| ≤ R). Kết quả: Ghi ra file EC.OUT một số nguyên là số lần ép cọc ít nhất tìm được. Ví dụ: EC.INP EC.OUT 4 3 2 2 2 4 -2
7 2 8 1 Chú ý: Trong 60% số test tất cả các cọc thẳng hàng và đều nằm trên trục Ox với n ≤ 1000, R ≤ 100, các tọa độ nhỏ hơn 104. -----------------------------Hết-------------------------- Họ và tên thí sinh :....................................................... ……………..Số báo danh ............................. Họ và tên, chữ ký: Giám thị 1:...................................................................................................... Giám thị 2:.......................................................................................................
HƯỚNG DẪN CHẤM THI CHỌN HỌC SINH GIỎI LỚP 12 THPT Kỳ thi thứ nhất - Năm học 2012 – 2013 MÔN: TIN HỌC Chấm bằng chương trình tự động AMM2: Câu 1: 10 test, mỗi test đúng cho 0,5 điểm. Câu2: 10 test, mỗi test đúng cho 0,5 điểm. Câu3: 10 test, mỗi test đúng cho 0,5 điểm. Câu 4: 10 test, mỗi test đúng cho 0,5 điểm. Bài 1 const finp = 'TOUR.INP'; fout = 'TOUR.OUT'; var n, m: Integer; Val, Pos: array[1..2, 1..8000] of Integer; {=================================================} procedure ReadInput; var i: Integer; hf: Text; begin Assign(hf, finp); Reset(hf); Readln(hf, n, m); for i := 1 to n do Read(hf, Val[1, i]); Readln(hf); for i := 1 to m do Read(hf, Val[2, i]); Close(hf); for i := 1 to m do begin Pos[1, i] := i; Pos[2, i] := i; end; end; {=================================================} procedure QuickSort(t, l, r: Integer); var x, tg, i, j: Integer; begin x := Val[t, (l + r) div 2]; i := l; j := r; repeat while Val[t, i] < x do Inc(i); while Val[t, j] > x do Dec(j); if i
until i > j; if i < r then QuickSort(t, i, r); if j > l then QuickSort(t, l, j); end; {=================================================} procedure WriteOutput; var i: Integer; Sum: LongInt; hf: Text; begin Sum := 0; for i := 1 to n do Inc(Sum, Val[1, n - i + 1] * Val[2, i]); for i := 1 to n do Val[1, Pos[1, n - i + 1]] := Pos[2, i]; Assign(hf, fout); Rewrite(hf); Writeln(hf, Sum); for i := 1 to n do Writeln(hf, Val[1, i]); Close(hf); end; begin ReadInput; QuickSort(1, 1, n); QuickSort(2, 1, m); WriteOutput; end. Bài 2: const fi = 'HAIVAN.INP'; fo = 'HAIVAN.OUT'; nmax = 100005; Var v,r:array[1..nmax] of longint; vipham:array[1..nmax]of boolean; n,k,m:longint; procedure nhap; var f:text; i,j:longint; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do read(f,v[i]); readln(f); for j:=1 to n do read(f,r[j]); close(f); end; procedure xuly; Var i,j:longint; f:text; begin k:=0;
for i:=1 to n do if v[i]r[i] then inc(k); fillchar(vipham,sizeof(vipham),false); m:=0; j:=0; for i:=1 to n do if vipham[v[i]]=false then Repeat inc(j); if r[j]v[i] then begin inc(m); vipham[r[j]]:=true; end; Until r[j] = v[i]; assign(f,fo); rewrite(f); writeln(f,k); writeln(f,m); close(f); end; Begin nhap; xuly; end. Bài 3: const fi='frog.inp'; fo='frog.out'; var f:text; n,k,a,b:longint; p:array[1..100000]of longint; hd,truoc,d:array[1..100000]of longint; dau:array[1..100000]of boolean; procedure nhap; var i:longint; begin assign(f,fi); reset(f); readln(f,n,k,a,b); for i:=1 to k do readln(f,p[i]); close(f); end; procedure chuanbi; begin fillchar(truoc,sizeof(truoc),0); fillchar(dau,sizeof(dau),false); dau[a]:=true; end; procedure xuli; var i,d,c,u,s:longint;
begin d:=1; c:=1; hd[1]:=a; d[a]:=0; while d0) and (u+p[i]
i,j:longint; begin assign(f,fi); reset(f); readln(f,n,r); for i:=1 to n do readln(f,a[i].x,a[i].y); close(f); end; procedure chuanbi; var i:longint; le,ri:real; begin for i:=1 to n do begin le:=a[i].x - sqrt(sqr(r)-sqr(a[i].y)); ri:=a[i].x + sqrt(sqr(r)-sqr(a[i].y)); if le =r then exit; i:=l; j:=r; k:=d[l+random(r-l+1)].y; Repeat while d[i].yk do dec(j); if ij; Sort(l,j); Sort(i,r); end; procedure xuly; var diemcuoi,i:longint; f:text; begin diemcuoi:=-1; kq:=0; For i:=1 to n do if d[i].x>diemcuoi then begin inc(kq); diemcuoi:= d[i].y;
end; assign(f,fo); rewrite(f); write(f,kq); close(f); end; begin nhap; chuanbi; Sort(1,n); Xuly; end.
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HÀ TĨNH HỌC SINH GIỎI QUỐC GIA LỚP 12 THPT NĂM HỌC 2012-2013 ĐỀ THI CHÍNH THỨC MÔN THI: TIN HỌC - Vòng 2 (Đề thi có 02 trang, gồm 03 bài) Thời gian: 180 phút (không kể thời gian giao đề) Ngày thi thứ hai: 22/09/2012 TỔNG QUAN NGÀY THI THỨ HAI Tên bài File chương trình File dữ liệu vào File kết quả Bài 1 Từ chuẩn TUCHUAN.PAS TUCHUAN.INP TUCHUAN.OUT Bài 2 Tìm mật khẩu PASSWROD.PAS PASSWROD.INP PASSWROD.OUT Bài 3 Quà Tết Trung thu TIMQUA.PAS TIMQUA.INP TIMQUA.OUT Hãy sử dụng ngôn ngữ lập trình pascal hoặc free pascal lập trình giải các bái toán sau: Bài 1. (6 điểm) Từ chuẩn Một từ loại M là một dãy các chữ số, mỗi chữ số nằm trong khoảng từ 1 đến M. Số lượng các chữ số có mặt trong một từ được gọi là chiều dài của từ đó. Từ loại M được gọi là từ chuẩn nếu nó không chứa hai khúc (từ con) liền nhau mà giống nhau. Ví dụ: 12131231 là từ chuẩn loại 3, chiều dài 8. 12132131 không phải là từ chuẩn vì nó chứa liên tiếp hai từ con giống nhau là 213. Tương tự, 12332 không phải là từ chuẩn vì chứa liên tiếp hai từ con giống nhau là 3. Yêu cầu: Với mỗi giá trị N và M cho trước, tìm và ghi vào tệp văn bản tên TUCHUAN.OUT một từ chuẩn loại M có chiều dài N. Dữ liệu: Vào từ file văn bản TUCHUAN.INP gồm 2 số nguyên dương N và M (M < N, 1 ≤ N ≤ 10000) được ghi trên một dòng, mỗi số cách nhau ít nhất là một ký tự trống. Kết quả: Ghi ra file văn bản TUCHUAN.OUT một dòng chứa một từ chuẩn. Ví dụ: TUCHUAN.INP TUCHUAN.OUT 15 3 121312313231232 Bài 2. (7 điểm) Tìm mật khẩu Việc bảo vệ máy tính của mình để hạn chế người khác thâm nhập vào là một vấn đề đặt ra cho mọi nguời sử dụng máy tính. Để tăng tính an toàn trong lưu trữ, một nguời đã quyết định dấu mật khẩu truy cập máy tính của mình vào một xâu T với một quy ước sao cho khi cần anh ta có thể lấy lại đuợc mật khẩu từ T như sau: Là một người yêu thích số học anh ta thường chọn mật khẩu P là một số nguyên tố và đem dấu vào một xâu ký tự T sao cho P chính là số nguyên tố có giá trị lớn nhất trong số các số nguyên Trang 1 /3
tố tạo được từ các xâu con của T (xâu con của một xâu ký tự T là một chuỗi liên tiếp các ký tự trong T). Ví dụ: xâu T= “timpassword232432fsdgd45435dsfdsf” chứa mật khẩu là 43 vì T chứa các xâu con ứng với các số nguyên tố 2, 3, 23, 43, và 5. Yêu cầu: Cho một xâu ký tự T chiều dài không quá 250 ký tự. Tìm mật khẩu P đã dấu trong xâu T biết P có giá trị nhỏ hơn 105. Dữ liệu cho đảm bảo T chứa ít nhất 1 số nguyên tố. Dữ liệu: Vào từ file văn bản PASSWORD.INP gồm 1 dòng duy nhất là xâu T. Kết quả: Ghi ra file văn bản PASSWORD.OUT chứa số P tìm được. Ví dụ: PASSWORD.INP PASSWORD.OUT timpassword232432fsdgd45435dsfdsf 43 Bài 3. (7 điểm) Quà Tết Trung thu Để vui Tết Trung thu cho các cháu ban tổ chức thành phố X quyết định phát quà cho mỗi cháu bằng cách tổ chức một trò chơi trên lưới ô vuông như sau: Vẽ một hình chữ nhật kích thước M x N ô vuông, Các dòng được đánh số từ 1 đến M, các cột được đánh số từ 1 đến N (các số được đánh từ trên xuống dưới và từ trái sang phải). mỗi ô nằm trên giao của dòng i và cột j được gọi là ô (i,j) ghi một số nguyên dương A[i,j], (1 ≤ i ≤ M, 1 ≤ j ≤ N) chính là số món quà trên ô đó. Có thể di chuyển từ một ô sang ô thuộc cột bên phải cùng dòng hoặc chênh lệch một dòng. Yêu cầu: Tìm cách giúp các cháu di chuyển từ một ô nào đó của cột bên trái (cột xuất phát) đến một ô nào đó thuộc cột N (cột đích) sao cho tổng các số của ô đi qua là lớn nhất vì đó chính là tổng số món quà mà các cháu được nhận. Dữ liệu: Vào từ file văn bản TIMQUA.INP dòng đầu tiên là 2 số nguyên dương M, N (M, N ≤ 100). M dòng tiếp theo mỗi dòng N số nguyên A[i,j] (0 ≤ A[i,j] ≤ 50) của hình chữ nhật. Kết quả: Ghi ra file văn bản TIMQUA.OUT gồm 2 dòng: - Dòng thứ nhất ghi tổng các số của các ô đi qua. - Dòng thứ hai ghi N số là chỉ số dòng các ô đi qua từ cột 1 đến cột N. Ví dụ: TIMQUA.INP TIMQUA.OUT 35 50 7 3 8 1 5 23321 8 8 3 12 1 6 15 10 5 2 --------------------------- 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. Trang 2 /3
Họ và tên thí sinh……………………………………………..Số báo danh…………………….. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HÀ TĨNH HỌC SINH GIỎI QUỐC GIA LỚP 12 THPT NĂM HỌC 2012-2013 MÔN THI: TIN HỌC - Vòng 2 HƯỚNG DẪN CHẤM VÒNG 2 Tên bài File chương trình File dữ liệu vào File kết quả Bài 1 Từ chuẩn TUCHUAN.PAS TUCHUAN.INP TUCHUAN.OUT Bài 2 Tìm mật khẩu PASSWROD.PA PASSWROD.IN PASSWROD.OU Bài 3 Quà Tết Trung thu TIMQUA.PAS TIMQUA.INP TIMQUA.OUT Tất cả các bài đều chấm bằng bộ test, mỗi bộ test đúng được một điểm. Nếu không chạy được chương trình thì căn cứ vào bài làm của học sinh để cho điểm nhưng tối đa không quá 2 điểm trên bài. - Bài 1: 6 test 6 điểm. - Bài 2: 7 test 7 điểm. - Bài 3: 7 test 7 điểm. Hướng dẫn chương trình tham khảo Bài 1. (6 điểm) Từ chuẩn Ta dùng mảng v[1..n] để lưu từ cần tìm. Tại mỗi bước i ta xác định giá trị v[i] trong khoảng 1..m sao cho v[1..i] là từ chuẩn. Điều kiện P: v[1..i] là từ chuẩn. Điều kiện Q: Dừng thuật toán theo một trong hai tình huống sau đây:  nếu i = n thì bài toán có nghiệm v[1..n].  nếu i = 0 thì bài toán vô nghiệm. TimTu1: Tìm một nghiệm. Hàm Tim hoạt động như sau: duyệt các giá trị tại vị trí v[i] của từ v[1..i] kể từ v[i] + 1 đến m sao cho v[1..i] là từ chuẩn. Tim = true nếu tồn tại một giá trị v[i] như vậy. Ngược lại, nếu với mọi v[i] = v[i] + 1..m từ v[1..i] đều không chuẩn thì Tim = false. Để kiểm tra tính chuẩn của từ v[1..i], ta lưu ý rằng từ v[1..i-1] đã chuẩn (tính chất P), do đó chỉ cần khảo sát các cặp từ có chứa v[i], cụ thể là khảo sát các cặp từ có chiều dài k đứng cuối từ v. Đó là các cặp từ v[(i–k–k+1)..(i–k)] và v[i–k+1..i] với k = 1..(i div 2). Nếu với mọi k như vậy hai từ đều khác nhau thì Chuan=true. Ngược lại, Chuan = false. Hàm Bang(i,k) kiểm tra xem hai từ kề nhau chiều dài k tính từ i trở về trước có bằng nhau hay không. Hai từ được xem là khác nhau nếu chúng khác nhau tại một vị trí nào đó. Bài 2. (7 điểm) Tìm mật khẩu Ta duyệt qua tất cả các xâu con của xâu T mà có thể tạo thành một số và kiểm tra số đó có phải số nguyên tố hay không. Để duyệt qua các xâu con, ta duyệt qua vị trí đầu: for i:=1 to length(t) do {i là vị trí đầu của xâu con} Trang 3 /3