Hướng dẫn thi học sinh giỏi tin học THCS năm học 2012 - 2103

HƯỚNG DẪN THI HỌC SINH GIỎI TIN HỌC THCS
NĂM HỌC 2012-2103
Yờu cầu chung
- Đề thi được ra theo hỡnh thức lập trỡnh trờn máy với cỏc thuật toỏn cơ bản. 
- Chương trỡnh dịch: Turbo Pascal, Free Pascal.
- Đề thi gồm 3 đờ́n 5 cõu, thang điểm 20.
- Chấm thi: Bài thi được chấm trờn mỏy tớnh; Chấm theo cỏc test, đỳng test nào được điểm test đú. Điểm bài thi là tổng điểm cỏc test.(Chỉ đọc chương trỡnh khi cần phõn loại cỏc trường hợp đồng điểm).
- Học sinh phải tuõn thủ nghiờm ngặt cỏc quy định về đặt tờn file và qui cỏch xuất dữ liệu (định hướng chấm bằng mỏy).
Nội dung:
- Tổ chức rẽ nhỏnh ( Lệnh If  then  else; If  then )
- Tổ chức rẽ nhỏnh Case  of
- Tổ chức lặp While do
- Tổ chức lặp Repeat Until
- Tổ chức lặp For  Do
- Kiểu dữ liệu xõu (String)
- Kiểu dữ liệu mảng ARRAY: Mảng một chiều, hai chiều
- Kiểu dữ liệu file: File văn bản (cỏc cõu lệnh nhập xuất cơ bản)
- Chương trỡnh con: Thủ tục và hàm. 
- Đệ quy.
3. Các thuọ̃t toán cần lưu ý:
- Thuật toỏn tỡm kiếm, sắp xờ́p.
- Số học: Kiờ̉m tra sụ́ nguyờn tụ́, sụ́ chính phương, sụ́ hoàn hảo, phõn tích ra thừa sụ́ nguyờn tụ́, dãy Fibonacci, tính giai thừa của mụ̣t sụ́ nguyờn, tính lũy thừa, tính tụ̉ng các chữ sụ́ trong 1 sụ́ nguyờn, tính tụ̉ng các ước của 1 sụ́ nguyờn, tỡm số đảo của 1 số nguyờn, tớnh tổng của 1 dóy số, tạo số ngẫu nhiờn, tìm USCLN, BSCNN, chuyờ̉n đụ̉i cơ sụ́, sụ́ La mã. Nộn và giải nộn xõu kớ tự. Cụ̣ng, trừ, nhõn sụ́ lớn, chuyển đổi cơ số
- Cỏc thuật toỏn cơ bản về xử lý mảng 1 chiều: Tìm phõ̀n tử lớn nhṍt, nhỏ nhṍt (cõ̀n chỉ ra vị trí), đếm số phần tử thỏa điều kiện cho trước. Di chuyển cỏc phần tử trờn mảng. Sắp xếp mảng thỏa điều kiện cho trước. Trộn 2 mảng thành 1 mảng mới, tạo dóy số ngẫu nhiờn
- Xõu: Chuõ̉n hóa xõu (chuyển xõu sang chữ in hoa, chữ thường, xóa dṍu cách thừa, viờ́t hoa kí tự đõ̀u từ,...), kiờ̉m tra xõu đụ́i xứng, đờ́m kí tự, từ trong xõu, mó húa, giải mó xõu. Đếm cỏc phần tử của xõu thỏa điều kiện cho trước
- Hỡnh học: Cỏc thuật toỏn biểu diễn điểm, đường thẳng, đoạn thẳng, vị trớ tương đối (giữa điểm đường thẳng, điểm đường trũn, đường thẳng đường thẳng, đường thẳng đường trũn). Tớnh diện tớch chu vi đa giỏc
-Cỏc bài toỏn thực tế: Tiền gửi ngõn hàng, Dõn số, Sắp xếp lịch thi đấu,
Lưu ý: 
Dữ liệu nhập bao gồm: nhập từ bàn phớm và nhập từ file văn bản.
Chấm bài thi mụn Tin học theo Test, nờn cần ghi rừ cỏc phương ỏn làm Test ở đỏp ỏn. (đảm bảo phõn loại học sinh: test lớn, test nhỏ, độ khú, test dự phũng). 
Giám khảo chṍm trờn mụi trường Free Pascal trước, nờ́u có lụ̃i xảy ra thì chuyờ̉n sang chṍm trờn mụi trường Turbo Pascal đờ̉ đảm bảo quyờ̀n lợi thí sinh.
Đáp án cõ̀n ghi rõ qui cỏch dữ liợ̀u vào, dữ liợ̀u ra, điờ̉m của từng test và các khả năng và điờ̉m tương ứng (lưu ý cú kiểm soỏt lỗi dữ liệu nhập và quy cỏch dữ liệu xuất).
Phần chương trỡnh con và đệ quy được giới thiệu mang tớnh cụng cụ lập trỡnh giải quyết bài toỏn. Khụng yờu cầu bắt buộc phải giải quyết bằng chương trỡnh con và đệ quy.
ĐỀ THAM KHẢO
KỲ THI CHỌN HỌC SINH GIỎI CẤP 
Năm học .
Mụn: TIN HỌC
Thời gian: phỳt (khụng kể thời gian giao đề)
Ngày thi : ...//.
(Đề thi cú . trang, gồm  bài)
Hóy lập trỡnh giải cỏc bài toỏn sau:
Bài 1: Cộng hai số (5 điểm)	Tờn chương trỡnh: SUM.PAS
Cho trước hai số nguyờn A và B. Hóy tớnh tổng của chỳng.
Dữ liệu: Vào từ file văn bản SUM.INP chứa hai số nguyờn dương A và B, mỗi số 1 dũng (A, B < 10100).
Kết quả: Ghi ra file văn bản SUM.OUT chứa tổng cần tỡm (khụng chứa số 0 ở đầu).
SUM.INP
SUM.OUT
2
3
5
Bài 2: Số nguyờn tố (5 điểm)	Tờn chương trỡnh: PRIME.PAS
Biết rằng: “Mọi số tự nhiờn chẵn lớn hơn 2 đều viết được dưới dạng tổng của 2 số nguyờn tố”.
Viết chương trỡnh đọc vào một số chẵn N lớn hơn 2, hóy tỡm cặp số nguyờn tố cú tổng bằng N, nếu cú nhiều cặp như vậy thỡ hóy tỡm cặp cú chứa số nguyờn tố nhỏ nhất.
Dữ liệu: Vào từ file văn bản PRIME.INP gồm 1 dũng chứa số chẵn N(4 ≤ N ≤ 998)
Kết quả: Ghi ra file văn bản PRIME.OUT chứa hai số nguyờn tố cú tổng bằng N, số đầu tiờn là số nguyờn tố nhỏ nhất (hai số này cỏch nhau bởi dấu cỏch).
Vớ dụ: 
Test
PRIME.INP
PRIME.OUT
1
6
3 3
2
992
73 919
Bài 3: Text (5 điểm)	Tờn chương trỡnh: TEXT.PAS
Với một văn bản cho trước bao gồm cỏc từ, dấu chấm cõu và cỏc ký hiệu khỏc. Từ trong văn bản là một chuỗi liờn tiếp cỏc ký tự chữ hoa hoặc chữ thường trong bảng chữ cỏi. 
Yờu cầu: Hóy viết theo thứ tự ngược tất cả cỏc từ của văn bản, cỏc dấu cõu và ký tự khỏc khụng cần thay đổi.
Dữ liệu: Vào từ file văn bản TEXT.INP chứa văn bản ban đầu gồm một hay nhiều dũng, mỗi dũng cú khụng quỏ 255 ký tự, dũng trong file cú thể đến 1000.
Kết quả: Ghi ra file văn bản TEXT.OUT chứa văn bản mà cỏc kớ tự đó bị đảo ngược.
Vớ dụ: 
TEXT.INP
TEXT.OUT
This is an example.
sihT si na elpmaxe.
Bài 4: Dóy 0-1 (5 điểm)	Tờn chương trỡnh: DAYSO.PAS
Đọc vào một dóy chứa cỏc số 0 hoặc 1. Hóy kiểm tra dóy này cú chứa cỏc số 0 và 1 xen kẽ nhau khụng?
Dữ liệu: Vào từ file văn bản DAYSO.INP gồm dũng:
Dũng đầu chứa số nguyờn n (1≤ n ≤ 20)
Dũng thứ hai chứa dóy số 0 , 1. 
Cỏc số trờn cựng 1 dũng cỏch nhau bởi dấu cỏch.
Kết quả: Ghi ra file văn bản DAYSO.OUT chứa chữ ‘YES” nếu đú là dóy chứa cỏc số 0 và 1 xen kẽ nhau, ngược lại ghi “NO”.
DAYSO.INP
DAYSO.OUT
5
1 0 1 0 1
YES
6
0 1 0 1 1 1
NO
------------- HẾT -----------------
Thớ sinh khụng được sử dụng tài liệu.
Giỏm thị khụng giải thớch gỡ thờm.
HƯỚNG DẪN CHẤM
Bài 1: Cộng hai số (5 điểm)
Test
SUM.INP
SUM.OUT
1
2
3
5
2
1234
56
1290
3
9099
2012
11111
4
1234567890
2012 
1234569902
5
45454545454545454545454545454545454545454545454545
54545454545454545454545454545454545454545454545454
99.9( 50 số 9)
Lời giải tham khảo:
var s1,s2: string;
 m: array[1..120] of integer;
 i,c,l1,l2 : integer;
begin
 assign(input, 'input.txt'); reset(input);
 assign(output, 'output.txt'); rewrite(output);
 readln(s1); readln(s2);
 l1:=length(s1); l2:=length(s2);
 while(length(s1)<110) do s1:='0'+s1;
 while(length(s2)<110) do s2:='0'+s2;
 i:=1;c:=0;
 while (i<=l1)or(i<=l2) do begin
 c:=c+ord(s1[length(s1)-i+1])+ord(s2[length(s2)-i+1])-96;
 m[i]:=c mod 10;
 c:=c div 10;
 inc(i);
 end;
 if c>0 then begin m[i]:=c;inc(i) end;
 l1:=i;
 for i:=l1-1 downto 1 do write(m[i]);
end.
Bài 2: Số nguyờn tố (5 điểm)
Test
PRIME.INP
PRIME.OUT
1
6
3 3
2
992
73 919
3
50
3 47
4
4
2 2
5
66
5 61
var n,i : integer;
function IsPrime(x:integer):boolean;
var i:integer;
begin
 i:=2;
 while (i*i 0) do inc(i);
 IsPrime:= i*i > x;
end;
begin
 assign(input,'ONE.IN'); reset(input);
 assign(output,'ONE.OUT'); rewrite(output);
 read(n);
 for i:=2 to n div 2 do
 if IsPrime(i) and IsPrime(n-i) then
 begin write(i,' ',n-i); break end
 close(input);
 close(output);
end.
Bài 3: Text 	
Test
PRIME.INP
PRIME.OUT
1
This is an example.
sihT si na elpmaxe.
2
Thisisveryveryverylongword
drowgnolyrevyrevyrevsisihT
3
This test is very! easy and short.
But it's ,. mo:re difficult than first.
sihT tset si yrev! ysae dna trohs.
tuB ti's ,. om:er tluciffid naht tsrif.
4
This file for check your programm an
d ; to check whether your prog$ramm reverses "words" correctly
(or] nOt,!
 We hope that your~programm_ will:;^ &cope just +|perfectly/
:" ", . /\ -""::::: % &*&$ @` ó„€ỗă :-( [{|]
 2
 E = M * c
:-)
{no comments}
#Good$LuCk*
 "jury"
sihT elif rof kcehc ruoy mmargorp na
d ; ot kcehc rehtehw ruoy gorp$mmar sesrever "sdrow" yltcerroc
(ro] tOn,!
 eW epoh taht ruoy~mmargorp_ lliw:;^ &epoc tsuj +|yltcefrep/
:" ", . /\ -""::::: % &*&$ @` ó„€ỗă :-( [{|]
 2
 E = M * c
:-)
{on stnemmoc}
#dooG$kCuL*
 "yruj"
5
program word_order;
procedure solve;
 var i:integer;
 word,s:string;
 mn:Set of char;
begin
 mn:=['A'..'Z','a'..'z'];
 Assign(input,'input.txt');
 ReSet(input);
 Assign(output,'output.txt');
 ReWrite(output);
 While Not Eof do begin
 ReadLn(s);
 i:=1;
 While i<=length(s) do begin
 word:='';
 While (i<=length(s)) and (s[i] in mn) do begin
 word:=s[i]+word;
 inc(i);
 end;
 Write(word);
 While (i<=length(s)) and not(s[i] in mn) do begin
 Write(s[i]);
 Inc(i)
 end;
 end;
 WriteLn;
 end;
 Close(input);
 Close(output);
end;
begin
 solve;
end.
Bài 4 Dóy 0-1
Test
DAYSO.INP
DAYSO.OUT
1
5
1 0 1 0 1
YES
2
6
0 1 0 1 1 1
NO
3
8
1 1 0 1 0 1 0 1 
NO
4
10
0 1 0 1 0 1 0 1 0 1
YES
5
20
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
YES
program Day_0_1
var a:array[1..10]of integer;
 flag,i,k,n:integer;
begin
 Assign(input,'input.txt');
 ReSet(input);
 Assign(output,'output.txt');
 ReWrite(output);
 readln(n);
 for i:=1 to n do
 readln(a[i]);
 i:=1;
 while i<=n-1 do
 begin
 flag:=0;
 if ((a[i]=1)and(a[i+1]=0))or((a[i]=0)and(a[i+1]=1))
 then flag:=1
 else begin
 write('NO');flag:=0;
	 readln;halt;
 end;
 i:=i+2;
 end;
 if flag=1 then write('YES');
 close(input);
 close(output);
end.