Đề thi HSG Tin học lớp 9 TP Bảo Lộc – Năm học 2013 – 2014

Đề thi HSG Tin học lớp 9 TP Bảo Lộc – Năm học 2013 – 2014

ĐỀ THI HSG TP BẢO LỘC 2013 – 2014

 Bài 2: DÃY SỐ

Cho một dãy số nguyên A: a1 … an với n £ 100, . Hãy tìm dãy con đơn điệu giảm dần liên tiếp dài nhất.

VD:

DAYSO.INP DAYSO.OUT
14

5 -1 17 8 6 5 12 5 -1 -2 6 9 0 13

17 8 6 5

 

Bài 3: XÂY NHÀ

Có n hạng mục (đánh số từ 1 đến n, n £ 100) cần được thi công đối với 2 đội thợ, đầu tiên đội thợ A thi công xong, sau đó đến đội thợ B thi công. Giả thiết biết thời gian thi công hạng mục i tương ứng đối với 2 đội thợ A, B là ai , bi (i=1,2,…,n). Hãy tìm một lịch thi công (thứ tự thi công) để thời gian hoàn thành các hạng mục là sớm nhất.

Dữ liệu vào: XAYNHA.INP

  • Dòng 1: ghi n
  • Dòng 2: ghi hạng mục
  • Dòng 3, 4, lần lượt thời gian thi công xong các hạng mục của đội A, B

Dữ liệu ra: XAYNHA.OUT

  • Dòng 1: ghi hạng mục
  • Dòng 2, 3:Tổng thời gian hoàn thành sau mỗi hạng mục của đội A, B
  • Dòng cuối: Ghi tổng thời gian thi công.
XAYNHA.INP XAYNHA.OUT
3

1 2 3

3 4 6

3 3 2

1 2 3

3 7 13

6 10 15

Tong: 15


Bài 2: DÃY SỐ

 

Ý TƯỞNG: (Phương pháp vét cạn)

– Duyệt qua tất cả các dãy con bất kỳ: ai … aj (i<j) của dãy a1 … an (dùng 2 vòng lặp for)

– Dùng biến (khoảng cách) để lưu độ dài dãy ai … aj (khởi động bằng 1)

– Kiểm tra dãy ai … aj có đơn điệu giảm dần không. Nếu có thì tính độ dài dãy (j – i +1) nếu dài hơn (khoảng cách) thì đặt lại (khoảng cách) bằng độ dài này.

– Dùng thêm biến (lưu) để lưu lại giá trị của biến i khi xác định được dãy ai … aj đơn điệu giảm dần để truy xuất lại.

CHƯƠNG TRÌNH VD:

program daycondondieu;

var i,l,j,k,luu,dem,max,n:integer;

kt:boolean;  a: array[1..100] of integer;

f:text;

begin

assign(f,’input.inp’);

reset(f);

readln(f,n);

for i:=1 to n do read(f,a[i]);

close(f);

{——————}

max:=1;luu:=1;

for i:=1 to n-1 do

for j:=i+1 to n do

begin

dem:=j-i+1; kt:=true;

for k:=i to j-1 do

if a[k]<=a[k+1] then kt:=false;

if kt and (max<dem) then

begin

max:=dem;

luu:=i;

end;

end;

{——————}

writeln;

{writeln(max,’ ‘,luu);}

for i:=luu to luu+max-1 do write(a[i],’ ‘);

readln;

end.

 

Bài 3

Ý TƯỞNG:

Cần phải đọc thật kĩ đề để hiểu đề: Đúng ra đề phải ghi thi công hạng mục nào trước cũng được nhưng nhớ đối với 1 hạng mục thì đội A làm xong thì đội B mới được làm.

 

– Dùng 3 mảng một chiều: hm, a, b để lưu hạng mục, thời gian thi công đội A, B. và hai mảng một chiều a1, b1 để lưu tổng thời gian thi công đội A, B.

XAYNHA.INP XAYNHA.OUT
3

1 2 3 (hm)

3 4 6 (a)

3 3 2 (b)

1 2 3           (hm)

3 7 13          (a1)

6 10 15        (b1)

Tong: 15

– Vì với một hạng mục đội A phải làm xong thì đội B mới được làm, nếu đội A làm chưa xong thì đội B phải “đợi” vì vậy để tiết kiệm thời gian thì đội A phải làm những hạng mục ít thời gian nhất để đội B khỏi phải đợi lâu (vì vậy ta sắp xếp mảng a theo chiều tăng dần và mảng hm, b cũng phải đổi theo cho tương ứng)

VD:

Hang mục: 1 2 3

TG đội A : 4 3 6

TG đội B  : 3 4 2

Sắp xếp thành Hang mục: 2 1 3

TG đội A : 3 4 6

TG đội B  : 4 3 2

– Vì đội A làm liên tục nên sinh mảng a1 đơn giản

– Đội B có thể phải đợi đội A làm xong hạng mục nào đó mới được làm vì vậy cần chú ý khi sinh mảng b1

– Tổng thời gian chính là: b1[n]

CHƯƠNG TRÌNH VD:

program xaynha;

var i,j,k,n,TG,sum,xp,doi:integer;

kt:boolean;  hm,a,b,a1,b1: array[1..100] of integer;

f:text;

begin

{——- doc file ————–}

assign(f,’xaynha.inp’);

reset(f);

readln(f,n);

for i:=1 to n do read(f,hm[i]);readln(f);

for i:=1 to n do read(f,a[i]);readln(f);

for i:=1 to n do read(f,b[i]);readln(f);

close(f);

{——-sap xep thoi gian———–}

for i:=1 to n-1 do

for j:=i+1 to n do

begin

if a[i] >a[j] then

begin

TG:=a[i];a[i]:=a[j]; a[j]:=TG;

TG:=hm[i]; hm[i]:=hm[j];hm[j]:=TG;

TG:=b[i];b[i]:=b[j]; b[j]:=TG;

end;

end;

{—tao mang a1—– }

sum:=0;

for i:=1 to n do begin

sum:=sum+a[i];

a1[i]:=sum;

end;

{—-tao mang b1——}

sum:=0;doi:=a[1];xp:=0;

for i:=1 to n do begin

b1[i]:= xp+doi+b[i];

xp:=b1[i];

if a1[i+1]>b1[i] then doi:=a1[i+1]-b1[i] else doi:=0;

end;

{———ghi file————}

assign(f,’xaynha.out’); rewrite(f);

for i:=1 to n do write(f,hm[i],’ ‘);writeln(f);

for i:=1 to n do write(f,a1[i],’ ‘);writeln(f);

for i:=1 to n do write(f,b1[i],’ ‘);writeln(f);

write(f,’Tong:’,b1[n]);

close(f);

end.

Trả lời

Email của bạn sẽ không được hiển thị công khai.

Back to top button