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 a1,a2,...,aN (10 < N < 100 000), ai <=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:=