Đề thi Tin học , kì thi chọn hsg cấp Tỉnh Bà Rịa - Vũng Tàu lớp 12 THPT, năm 2009 - 2010

[quynhhoa]

Bài 1: ( 8 điểm )

Trên mộ mảnh đất hình cuông người ta chia làm n x n ô vuông nhỏ bằng nhau để trồng trọt.Người ta muốn đánh số ô vuông để chia cho các hộ gia đình theo thứ tự từ 1 đến n^2 , gia đình thứ i nhận ô thứ i . Vì chất lượng để trồng trọt trên các ô vuông là khác nhau nên có rất nhiều phương án đánh số thứ tự. Cuối cùng mọi người đồng ý đánh số thứ tự theo đường xoắn ốc ( Sprial ) theo đề nghị của một số nhà toán học. Ô đầu tiên là số 1, theo thứ tự tăng dần từ trái sang phải, từ trên xuống dưới, từ phải sang trái, từ dưới lên trên và từ ngoài vào trong. Nhưng theo sự mô tả của nhà toán học mọi người vẫn k biết cách đánh số ntn.
Yêu cầu: Viết chương trình đánh số thứ tự theo đường xoắn ốc như mô tả trên.

Dữ liệu vào: file “Spiral.inp”
Chứa 1 số nguyên dương n (2<= n <= 100)

Dữ liệu ra: file “Spiral.out”
Chứa một ma trận cấp n x n mô tả cách đánh số theo hình xoắn ốc.

Ví dụ :
Inp
5

Out
1 2 3 4 5
16 1 7 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Bài 2 ( 7 điểm)

Ngày xưa có anh nông dân hiền lành, khỏe mạnh đi cày thuê cho một người nhà giàu. Vì muốn cưới con gái của chủ, anh nông dân bèn lên rừng quyết tâm tìm cây tre trăm đốt, cây tre có chiều dài m. Sau khi đốn được cây tre, anh thất vọng ngồi khóc vì không thể nào vác cây tre ra khỏi rừng được. Bụt hiện lên nói: “Con hãy chia cây tre thành nhìu đoạn nhỏ, trong đó có n loại khác nhau, loaị thứ i có chiều dài ai và số lượng xi”. Nói xong bụt biến mất và để lại tờ giấy trong đó có 2 dòng, dòng thứ nhất mô tả ai, dòng thứ hai mô tả xi(i=1,2,..n). Nhưng không may nước mắt của anh nông dân rơi xuống tờ giấy làm nhòa đi các số liệu của xi . Vì không xác định được các giá trị xi để chia cây tre ra làm nhìu đoạn nhỏ, anh nông dân lại ngồi khóc tiếp. Một học sinh đi ngang qua, sau khi hỏi nguyên do, cậu học sinh liền mở máy tính ra viết chương trình để tìm các giái trị xi giúp a nông dân.

Yêu cầu: Hãy viết chương trình giúp a nông dân xác định các giá trị xi ( 1<= xi <= m)
Dự liệu vào : file “bamboo.inp” có chứa 2 dòng
-Dòng thứ nhất chứa 2 số nguyên dương m,n (1<=m <=65000; 1<=n<=100)
-Dòngthứ 2 chứ n số nguyên dương a1 ,…,an (1 <= ai <= 200)

Dữ liệu ra : file “bamboo.out”
Một dòng chứa n số nguyên dương x1,…,xn là bộ nghiệm đầu tiên được tìm thấy

Ví dụ :

Inp
30 3
7 4 5

Out
1 2 3

Bài 3 ( 5 điểm )
Để tổ chức Hội giảng cấp tỉnh Ban tổ chức Hội thi phải hoàn thành n công việc khác nhau, các công việc đượng đánh số thứ tự từ 1->n, thời gia để hoàn thành công việc thứ i là Ti (i=1,2,...,n). Có một số công việc phụ thuộc một hoặc nhìu công việc hoàn thành mới được thực hiện, biết rầng nếu i phụ thuộc vào j thì i>j. Sauk hi hoàn thành tất cả các công việc Ban tổ chức mới tiến hành khai mạc Hội thi.

Yêu cầu : Hãy viết chương trình giúp Ban tổ chức xác định thời gian sớm nhất để khai mạc Hội thi ( tính từ thời điểm bắt đầu tiến hành công việc).

Dự liệu vào: file “Modul.inp’
-Dòng thứ 1 chứa số nguyên dương n ( 1<= n <= 100)
-Dòng thứ i trong n dòng tiếp theo chứ số nguyên dương Ti và các số nguyên dương tiếp theo mô tả các công thức phải hoàn thành trước khi thực hiện công việc thứ i. Nếu công việc thứ i không phụ thuộc vào công việc nào thì trên dòng này chỉ chứ mỗi Ti.
Dữ liệu ra: file “Modul.out” chứa một số nguyên là thời gian sớm nhất để khai mạc Hội thi.

Ví dụ :
Inp
10
6
7
5
2 1 2 3
7
8
9
1 5 6 7
3 4 8
10 8

Out
20


p/s : tỉnh mình vẫn thi vik code trên giấy .
ngày thi : 24-11-2009

[dksupport]

Bài 1: ( 8 điểm )

Trên mộ mảnh đất hình cuông người ta chia làm n x n ô vuông nhỏ bằng nhau để trồng trọt.Người ta muốn đánh số ô vuông để chia cho các hộ gia đình theo thứ tự từ 1 đến n^2 , gia đình thứ i nhận ô thứ i . Vì chất lượng để trồng trọt trên các ô vuông là khác nhau nên có rất nhiều phương án đánh số thứ tự. Cuối cùng mọi người đồng ý đánh số thứ tự theo đường xoắn ốc ( Sprial ) theo đề nghị của một số nhà toán học. Ô đầu tiên là số 1, theo thứ tự tăng dần từ trái sang phải, từ trên xuống dưới, từ phải sang trái, từ dưới lên trên và từ ngoài vào trong. Nhưng theo sự mô tả của nhà toán học mọi người vẫn k biết cách đánh số ntn.
Yêu cầu: Viết chương trình đánh số thứ tự theo đường xoắn ốc như mô tả trên.

Dữ liệu vào: file “Spiral.inp”
Chứa 1 số nguyên dương n (2<= n <= 100)

Dữ liệu ra: file “Spiral.out”
Chứa một ma trận cấp n x n mô tả cách đánh số theo hình xoắn ốc.

Ví dụ :
Inp
5

Out
1 2 3 4 5
16 1 7 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Bài 2 ( 7 điểm)

Ngày xưa có anh nông dân hiền lành, khỏe mạnh đi cày thuê cho một người nhà giàu. Vì muốn cưới con gái của chủ, anh nông dân bèn lên rừng quyết tâm tìm cây tre trăm đốt, cây tre có chiều dài m. Sau khi đốn được cây tre, anh thất vọng ngồi khóc vì không thể nào vác cây tre ra khỏi rừng được. Bụt hiện lên nói: “Con hãy chia cây tre thành nhìu đoạn nhỏ, trong đó có n loại khác nhau, loaị thứ i có chiều dài ai và số lượng xi”. Nói xong bụt biến mất và để lại tờ giấy trong đó có 2 dòng, dòng thứ nhất mô tả ai, dòng thứ hai mô tả xi(i=1,2,..n). Nhưng không may nước mắt của anh nông dân rơi xuống tờ giấy làm nhòa đi các số liệu của xi . Vì không xác định được các giá trị xi để chia cây tre ra làm nhìu đoạn nhỏ, anh nông dân lại ngồi khóc tiếp. Một học sinh đi ngang qua, sau khi hỏi nguyên do, cậu học sinh liền mở máy tính ra viết chương trình để tìm các giái trị xi giúp a nông dân.

Yêu cầu: Hãy viết chương trình giúp a nông dân xác định các giá trị xi ( 1<= xi <= m)
Dự liệu vào : file “bamboo.inp” có chứa 2 dòng
-Dòng thứ nhất chứa 2 số nguyên dương m,n (1<=m <=65000; 1<=n<=100)
-Dòngthứ 2 chứ n số nguyên dương a1 ,…,an (1 <= ai <= 200)

Dữ liệu ra : file “bamboo.out”
Một dòng chứa n số nguyên dương x1,…,xn là bộ nghiệm đầu tiên được tìm thấy

Ví dụ :

Inp
30 3
7 4 5

Out
1 2 3

Bài 3 ( 5 điểm )
Để tổ chức Hội giảng cấp tỉnh Ban tổ chức Hội thi phải hoàn thành n công việc khác nhau, các công việc đượng đánh số thứ tự từ 1->n, thời gia để hoàn thành công việc thứ i là Ti (i=1,2,...,n). Có một số công việc phụ thuộc một hoặc nhìu công việc hoàn thành mới được thực hiện, biết rầng nếu i phụ thuộc vào j thì i>j. Sauk hi hoàn thành tất cả các công việc Ban tổ chức mới tiến hành khai mạc Hội thi.

Yêu cầu : Hãy viết chương trình giúp Ban tổ chức xác định thời gian sớm nhất để khai mạc Hội thi ( tính từ thời điểm bắt đầu tiến hành công việc).

Dự liệu vào: file “Modul.inp’
-Dòng thứ 1 chứa số nguyên dương n ( 1<= n <= 100)
-Dòng thứ i trong n dòng tiếp theo chứ số nguyên dương Ti và các số nguyên dương tiếp theo mô tả các công thức phải hoàn thành trước khi thực hiện công việc thứ i. Nếu công việc thứ i không phụ thuộc vào công việc nào thì trên dòng này chỉ chứ mỗi Ti.
Dữ liệu ra: file “Modul.out” chứa một số nguyên là thời gian sớm nhất để khai mạc Hội thi.

Ví dụ :
Inp
10
6
7
5
2 1 2 3
7
8
9
1 5 6 7
3 4 8
10 8

Out
20


p/s : tỉnh mình vẫn thi vik code trên giấy .
ngày thi : 24-11-2009

Bài 1./ Tỉnh chị cho bài cổ điển ghê: http://www.diendantinhoc.vn/showthread.php?t=7119&highlight=Sắp+xếp+trận +xoắn
Bài 2. / Quay lui phải không chị? Code đây, test thì đúng, nhưng không chắc chạy tốt:

program caytre;
uses crt;
const fi='bamboo.inp';
      fo='bamboo.out';
var a,x:array[1..200] of byte;m:longint;n,i:byte;kt:boolean;f:text;
procedure input;
begin
        assign(f,fi);
        reset(f);
        read(f,m);
        read(f,n);
        for i:=1 to n do read(f,a[i]);
        close(f);
end;
procedure print;
var i:byte;
begin
        assign(f,fo);
        rewrite(f);
        for i:=1 to n do write(f,x[i],' ');
        close(f);
end;
procedure cantsolve;
begin
        assign(f,fo);
        rewrite(f);
        write(f,'Khong tim duoc bo nghiem thich hop');
        close(f);
end;
function sum(n:byte):longint;
var i:byte;
begin
        sum:=0;
        for i:=1 to n do sum:=sum+a[i]*x[i];
end;
function max(n:byte):longint;
var i:byte;
begin
        max:=a[1];
        for i:=2 to n do
                if max<a[i] then max:=a[i];
end;
procedure find(k:byte);
var i:byte;
begin
        if kt then exit
        else
                begin
                        i:=1;
                        while i<m div max(n) do
                                begin
                                        x[k]:=i;
                                        if sum(n)=m then
                                                begin
                                                        print;
                                                        kt:=true;
                                                        exit;
                                                end
                                                else if k<n then find(k+1);
                                        inc(i);
                                end;
                end;
end;
BEGIN
        input;
        kt:=false;
        find(1);
        if not kt then cantsolve;
END.

Bài 3./ Em không hiểu lắm.

[muadongvinhcuu]

Bài 1 em viết code trong 1 topic khác rồi, nhưng ko nhớ nó ở topic nào, hình như thuật toán đại học thì phải.
Bài 2 chung ý tưởng với binhnguyen, nhưng thử cách chạy 3 vòng for xem sao. Nhưng nếu gặp test hiểm chắc thời gian trong mơ mất.
Bài 3 giống bài của mình kiểm tra xét học bổng lần trước, lần đó làm theo tham lam, chắc được 70% số test. Thi xong cô giáo bảo dùng hamilton - vì đi qua các đỉnh cũng tương tự như làm tất cả các công việc mà. Nhưng chưa hiểu lắm nên chưa cài đặt

[blogsechia1]

@ Nguyên :
- b2 : chưa tối ưu
dùng 2 mảng , tính tổng ngược và tổng xuôi thì tập đề cử ít hơn , ct chạy nhanh hơn
- b3 : suy nghĩ thêm ik . TG làm bài là 180min cơ
@ Long : chắc mình = tuổi bạn thôi , k phải xưng e thế [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) . Mình học 11
b3 : dùng qhđ mờ

[hoang_kisirong]

hix, cúp điện cả ngày này, bi chừ mới được on =))
3 bài này mình làm ngon lành lắm, mà ko biết được bao nhiêu điểm [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

[caole1992]

bài 2 này

const fi='BAMBOO.INP';
      fo='BAMBOO.OUT';
var f:text;
    n,m:longint;
    x,a:array[1..100] of longint;
    tn:array[1..101] of longint;
    tx:array[0..101] of longint;
procedure docfile;
var i:longint;
begin
   assign(f,fi);
   reset(f);
   readln(f,m,n);
   for i:=1 to n do read(f,a[i]);
   close(f);
end;

procedure ghi1kq;
var i:longint;
begin
   assign(f,fo);
   rewrite(f);
   for i:=1 to n do write(f,x[i],' ');
   close(f);
   halt;
end;

procedure try(i:longint);
var j,k,tg:longint;
begin
   tg:=m-tx[i-1]-tn[i+1];
   k:=tg div a[i];
   if (tg mod a[i])=0 then
      begin
         x[i]:=k;
         ghi1kq;
      end;
   if i<n then
      for j:=1 to k do
         begin
            x[i]:=j;
            tx[i]:=tx[i-1] + a[i]*j;
            try(i+1);
            x[i]:=1;
         end;
end;

procedure xuly;
var i:longint;
begin
   for i:=1 to n do x[i]:=1;
   for i:=n downto 1 do tn[i]:=tn[i+1]+a[i];
   try(1);
end;

begin
   docfile;
   xuly;
end.

[thethaotamchinh]

bài 3 đọc kĩ thì cần chi dùng đến đồ thị, tìm max Hằng nhỉ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

[giantapta]

@ Nguyên :
- b2 : chưa tối ưu
dùng 2 mảng , tính tổng ngược và tổng xuôi thì tập đề cử ít hơn , ct chạy nhanh hơn
- b3 : suy nghĩ thêm ik . TG làm bài là 180min cơ
@ Long : chắc mình = tuổi bạn thôi , k phải xưng e thế [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) . Mình học 11
b3 : dùng qhđ mờ

Ý chị là sử dụng bảng lưu trữ loại bỏ các tập đề cử hở chị?
Bài 3 em không hiểu cả cái đề ấy chứ, không hiểu yêu cầu và input lắm.

[hiennhan12]

bài 3 đọc kĩ thì cần chi dùng đến đồ thị, tìm max Hằng nhỉ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

b3 : hix , tui dùng đồ thị [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](
b2 : tui k xét dk của i . Đc max điểm k nhỉ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) . Vào vòng try là for j lun

Mong kq quá . Hiếu giải I chắc r`
---------------------------------Bài viết đã được trộn ---------------------------------

Ý chị là sử dụng bảng lưu trữ loại bỏ các tập đề cử hở chị?
Bài 3 em không hiểu cả cái đề ấy chứ, không hiểu yêu cầu và input lắm.

- thì e cứ suy nghĩ ik , có j` Hiếu post code lên , chứ c dùng đồ thị , k có tối ưu
- b2, c làm tựa tựa code của a Hiếu í

[vongocbao]

Bài 3 QHD như nào thế, bài này mình làm tham lam vì hum đó thi theo nghĩa vụ, không để ý nên xài tham lam cho nhanh. THi xong mới biết tối ưu là hamilton.
Thứ 3 tuần sau mình thi tỉnh nha, mọi người chúc thi tốt tí đi để có tinh thần làm bài. Thi xong về post bài mọi người ngâm cứu.