# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Đề 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”
> ...


 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.

----------


## bao245

bạn ơi.mình ko hiểu vể cách sử dụng haminton cho lắm
bạn nói rõ hơn được ko!

----------


## phamvulinh

Bài 3 theo mình hamilton ở đây áp dụng được vì yêu cầu là làm hết tất cả các công việc, giống như tính chất của đồ thị có đường đi hamilton - đi qua tất cả các đỉnh. Đỉnh trong đồ thị là công việc phải làm, từ đó ta tìm đường đi hamilton trong các công việc với điều kiện để đi tới 1 đỉnh là các đỉnh yêu cầu trước của nó đã được đi tới. --> đúng như yêu cầu của đề bài: tất cả các việc đều được làm + việc nào được làm khi những việc khác cần làm trước việc đó đều đã được làm. Còn nếu không tìm được đường đi hamilton tức là không xếp được các công việc hợp lí.

----------


## seoer

> bạn ơi giúp mình với sao máy minh tắt ko được


Xin lỗi bạn nha, vì box này chỉ giúp đỡ về vấn đề liên quan tới Pascal nên vấn đề của bạn có thể đưa vào mục Support Center để hỏi. Mình sẽ chuyển bài viết của bạn tới đó cho phù hợp.
Đây là link bài viết của bạn trong Support Center.
http://diendantinhoc.vn/showthread.php?t=36532
Bạn vô box đó để đưa ra câu hỏi về máy tính nhé.

----------


## hongquang014

> Bài 3 theo mình hamilton ở đây áp dụng được vì yêu cầu là làm hết tất cả các công việc, giống như tính chất của đồ thị có đường đi hamilton - đi qua tất cả các đỉnh. Đỉnh trong đồ thị là công việc phải làm, từ đó ta tìm đường đi hamilton trong các công việc với điều kiện để đi tới 1 đỉnh là các đỉnh yêu cầu trước của nó đã được đi tới. --> đúng như yêu cầu của đề bài: tất cả các việc đều được làm + việc nào được làm khi những việc khác cần làm trước việc đó đều đã được làm. Còn nếu không tìm được đường đi hamilton tức là không xếp được các công việc hợp lí.


--> đao to búa lớn
xem đề kĩ dùm cái, dễ lắm chứ ko phải thế đâu bạn

----------


## bomhao

Dễ thì làm thế nào vậy? Đây là cách áp dụng hamilton vì tính chất yêu cầu của đề bài rất giống hamilton, ta có thể áp dụng nó, không cần nghĩ nhiều.

----------


## tienhuy111

chào các bác , sao các bác làm mà ko giải thích j cả vậy, mình đọc ko hiểu j cả, mong các bác giải thích giùm nhé, giái thích rõ ràng luôn nha
cám ơn các bác
Tại sao phải dùng 3 mảng và thủ tục try chạy như thế nào mình ko hỉu

----------

