De va dap an thi chon HSG truong - tin hoc
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (128.6 KB, 5 trang )
TRƯỜNG THPT ĐỨC THỌ
ĐỀ THI CHỌN HSG TRƯỜNG KHỐI 11 NĂM HỌC 2010-2011
Môn: Tin học
Thời gian làm bài: 180 phút
Viết chương trình bằng NNLT Pascal giải các bài toán sau:
Bài 1: Cho trước dãy số. Hãy tìm một dãy con liền nhau cực đại có các phần tử bằng nhau.
Dữ liệu vào: File DAYSO.INP chứa một dãy số
Dữ liệu ra: Ghi vào file DAYCON.OUT dãy con lớn nhất thỏa mãn bài toán.
Bài 2: Dãy con
Cho một dãy số nguyên dương a
1
,a
2
, ,a
N
(10 < N < 100 000), a
i
<=10000 với mọi i=1 N và
một số nguyên dương S (S < 100 000 000).
Yêu cầu : Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có tổng
các phần tử lớn hơn hoặc bằng S.
Dữ liệu vào: Đọc từ file SUB.INP gồm nhiều test, mỗi test chứa N và S ở dòng đầu. Dòng 2
chứa các phần tử của dãy.
Dữ liệu ra: Kết quả ghi vào file SUB.OUT, mỗi test đưa một dòng chứa độ dài của dãy con
tìm được.
Ví dụ :
SUB.INP SUB.OUT
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
2
3
Bài 3: Cho trước một xâu nhị phân độ dài bất kỳ được đưa vào từ file văn bản INPUT.TXT. Cần
biến đổi xâu nhị phân này về dạng toàn số 0. Các phép biến đổi có thể chỉ là một trong các loại sau:
- Biến đổi xâu con 11 thành 00.
- Biến đổi xâu con 010 thành 000.
Hãy chỉ một cách biển đổi xâu đã cho thành xâu có toàn 0. Kết quả thể hiện trong file
OUTPUT.TXT như sau:
Dòng đầu tiên của OUTPUT.TXT chứa xâu ban đầu, sau đó mỗi dòng là một xâu tiếp theo sau một
phép biến đổi, xâu cuối cùng là xâu toàn 0.
Ví dụ 1:
INPUT.TXT OUTPUT.OUT
11010011 11010011
11010000
00010000
00000000
Ví dụ 2:
INPUT.TXT OUTPUT.OUT
10101101 Khong the bien doi duoc
HẾT
Lưu ý: Giám thị coi thi không giải thích gì thêm
ĐÁP ÁN
Bài 1: (7 điểm)
- Viết được thủ tục đọc và ghi tệp được 1 điểm
- Chương trình chạy đúng 1 bộ Test đưa ra được 1 điểm
Chương trình cụ thể như sau.
Program DaysobangnhauMax;
Var a:array[1 1000] of integer;
n:integer;
f1,f2:text;
Procedure Doctep;
begin
assign(f1,'c:\dayso.inp');reset(f1);
assign(f2,'c:\dayso.out');rewrite(f2);
n:=0;
while not eof(f1) do
begin
n:=n+1;
read(f1,a[n]);
end;
end;
procedure xuli;
Var dem,max,i,j:integer;
Begin
dem:=1;
max:=0;
for i:=2 to n+1 do
if (a[i]=a[i-1]) and (i<=n) then dem:=dem+1
else
begin
if dem>max then max:=dem;
dem:=1;
end;
dem:=1;
for i:=2 to n+1 do
if (a[i]=a[i-1]) and (i<=n) then dem:=dem+1
else
begin
if dem=max then
begin
for j:=i-max to i-1 do write(f2, a[j],' ');
writeln(f2);
end;
dem:=1;
end;
close(f1);close(f2);
end;
BEGIN
doctep;
xuli;
END.
Bài 2: (7 điểm).
- Viết được thủ tục đọc và ghi tệp được 1 điểm
- Chương trình chạy đúng 1 bộ Test đưa ra được 1 điểm
Chương trình cụ thể như sau.
Program Bai2;
Type Ma=array[1 1000] of integer;
Var a:ma;
f1,f2:text;
Procedure xuli(b:ma; n,s:integer);
Var ok:boolean;
m,i,j,tong:integer;
Begin
ok:=true;
for m:=1 to n do
if not ok then break else
for i:=1 to n+1-m do
if not ok then break else
begin
tong:=0;
for j:=i to i+m-1 do tong:=tong+b[j];
if tong>=s then
begin
writeln(f2,m);
ok:=false;
end;
end;
end;
Procedure Doctep;
var dem,t,i:integer;
Begin
assign(f1,'c:\sub.inp');reset(f1);
assign(f2,'c:\sub.out');rewrite(f2);
while not eof(f1) do
begin
readln(f1,dem,t);
for i:=1 to dem do read(f1,a[i]);
readln(f1);
xuli(a,dem,t);
end;
close(f1);close(f2);
end;
BEGIN
doctep;
END.
BÀI 3 (6 điểm)
- Viết được thủ tục đọc và ghi tệp được 1 điểm
- Chương trình chạy đúng 1 bộ Test đưa ra được 1 điểm
Chương trình cụ thể như sau.
Program bai3hsg11nam2010_2011;
Uses Crt;
Const st1='11';
st2='010';
Var fin, fou: text;
l, p: integer;
st: string;
(*==================================*)
Procedure ghi1(i: integer);
Begin
st[i]:='0';
st[i+1]:='0';
Writeln(fou, st);
End;
(*=================================*)
Procedure ghi2(i: integer);
Begin
st[i+1]:='0';
Writeln(fou, st);
End;
(*=================================*)
Begin
Clrscr;
assign(fin, 'c:\input.txt');
reset(fin);
Readln(fin, st);
close(fin);
l:=length(st);
If ((st[l]='1') and (st[l-1]='0')) or ((st[1]='1') and (st[2]='0')) then Writeln('Khong the bien doi
duoc!')
Else
Begin
assign(fou,'c:\output.txt');
rewrite(fou);
Writeln(fou,st);
If (st[l]='1') and (st[l-1]='1') then ghi1(l-1);
Repeat { bien doi xau con '11' }
p:=pos(st1,st);
If (p<>0) then ghi1(p);
Until (p=0);
Repeat {bien doi xau con '010' }
p:=pos(st2,st);
If (p<>0) then ghi2(p);
Until (p=0);
close(fou);
{kiÓm tra}
assign(fou,'c:\output.txt');
reset(fou);
While not(seekeof(fou)) do
Begin
Readln(fou,st); Writeln(st);
End;
close(fou);
End;
Readln;
End.
