Đề thi HSG tỉnh Tây Ninh !

[mini_bestboy]

BT1:Dãy giảm (6đ)
Một dãy A1,A2...An được gọi là dãy giảm nếu A1>A2...>An ( VD dãy 7 6 5 là dãy giảm, 9 8 7 7 không là dãy giảm). Cho số N, tìm tất cả các dãy giảm có tổng các số trong dãy bằng N
Dữ liệu vào : file BT1.INP gồm 1 dòng chứ số N
Dữ liệu ra : file BT1.OUT gồm nhiều dòng, mỗi dòng chứ 1 kết quả, dòng cuối dùng ghi số các kết quả.
VD
BT1.INP
7

BT1.OUT
7
6 1
5 2
4 3
4 2 1
5
Câu 2: Dụng cụ học tập (8 đ)
Một nhóm học sinh A cần làm N bài tập hình học. Mỗi bài tập cần có Ki dụng cụ học tập để giải như : thước kẻ, bút chì, gôm ..., có tất cả P dụng cụ. Để hiệu suất làm bài đạt cao nhất người ta quy định : mỗi bài tập chỉ được giải xong khi có đầy đủ dụng cụ học tập. Mỗi dụng cụ học tập không được dùng cùng lúc cho 2 bài tập. Mỗi bài tập đều được giải trong T thời gian. Tìm thời gian ngắn nhất học sinh có thể giải xong N bài tập.
Dữ liệu vào : file BT2.INP
- Dòng đầu gồm 3 số N,P,T
- N dòng tiếp theo, mỗi dòng : số đầu tiên ghi số dụng cụ cần để làm bài tập, các số tiếp theo ghi chỉ số của các dụng cụ
Dữ liệu ra : file BT2.OUT
Gồm 1 dòng ghi thời gian tối thiểu để làm N bài tập
VD:
BT2.INP
4 5 1
2 1 3
1 1
2 2 4
2 1 2
BT2.OUT
3

VD2:
BT2.INP
5 6 2
3 1 2 3
2 1 3
2 1 2
2 2 3
1 2
BT2.OUT
8

Câu 3: Nhặt bi (6 đ)
Cho số N (N<=50)và một mảng hình vuông NxN, mỗi ô của mảng chứa một số bi khác nhau( -30000<=số bi<=30000), Một cậu bé cần đi từ góc trên bên trái (ô 1,1) đến góc dưới bên phải ( ô N,N) để nhặt bi trong mỗi ô đi qua, biết cậu bé chỉ có thể đi qua ô bên phải, cùng dòng hoặc ô phía dưới cùng cột với ô đang đứng. Tìm đường đi để cậu bé có thể lấy được nhiều bi nhất
Dữ liệu vào : file BT3.INP Dòng đầu chứa số N
N dòng sau, dòng thứ i gồm N số số là số bi của mỗi ô
Dữ liệu ra: file BT3.OUT là mảng (NxN) thể hiện đường đi của cậu bé :ô cậu bé đi qua đánh số 1, nếu không đánh số 0
VD:
BT3.INP
4
7 5 8 -16
2 5 9 12
1 7 5 4
2 3 4 8
BT3.OUT
1 0 0 0
1 0 0 0
1 0 0 0
1 1 1 1
Đề như vậy các bạn giải thử xem. Các bạn thấy như vậy là dễ hay khó đối với HSG vòng tỉnh ?

[bld]

bài 1 QHd theo kiểu F[i] là tổng dãy con giảm kết thúc ở i
(số phần tử là n)
F[1]=a[1]
for i:=2 to n do
if a[i]<a[i-1] then F[i]:=F[i-1]+a[i] else F[i]:=a[i];
, xong rồi, duyệt ngược bảng F từ vị trí cuối để in kq, dùng thêm biến đếm .i]


i:=n
while i>0 do
begin
if F[i]=N then inc(dem);
while F[i]<>a[i] do dec(i);
dec(i);
end;


[=========> Bổ sung bài viết <=========]

bài 3 : QHD
bài 2 : chưa nghĩ ra cách nào ngoài tham lam

[lehang_gb1]

Sao bài 1 không phải nhập A1,A2,...,An ah
Mà test lại cho N=7 và chỉ tính dãy gồm các chữ số từ 1 đến 7 thôi ư. Đề bài cho không rõ ràng

[bld]

uhm , đề lạ thật
có lẽ phát biểu lại theo kiểu tìm dãy giảm tổng N , thế thôi . chứ dãy ban đầu ko nhập vào ..... nói bậy đừng trách nhé %^^
.. hay là dãy này giảm liên tiếp ? :p

[lehang_gb1]

bld viết phần đưa ra màn hình các dãy con tìm đựoc có tổng bằng n đi. Đoan viết này khó. Bài này cũng tương tự bài mình đã đưa lên.Cứ làm theo đề nhập vào các số A1, A2,..An xem sao mà cũng tương tự như với dãy các số từ 1 đến N thôi.

[mini_bestboy]

A, bài 1 nó dễ cái là không cần nhập vào các số A1,A2,...An, ta chỉ cần nhập N, các phần tử của dãy sẽ là các số <=N (VD: N=7 thì các phần tử có thể là :1,2,3,4,5,6,7).Đừng suy nghĩ quá rắc rối ^^
BLD pro QHĐ thật, còn tui thấy bài 1 dùng quay lui là chuẩn nhất, dạng cơ bản của quay lui mà, zí lại đề cũng không có yêu cầu thời gian ^^

[=========> Bổ sung bài viết <=========]

Mà đề này là của năm 2008-2009 năm trước mình có được, mấy bạn từng đi thi xem với đề vòng tỉnh như vầy,nó thuộc loại dễ hay khó nào ?

[quangtq]

Bài 1 mình quay lui. QHĐ gà nên bài nào thấy đúng dạng mới dùng :D.
Không giới hạn time, sao TLE được :D

[bld]

bạn làm quay lui à ^^
nếu như đề bài 1 phát biểu giống như bạn mini best bboy nói thì code trên của mình sai rồi , chỉ đúng nếu dãy là dãy giảm liên tiếp
nếu làm tổng n cũng có thể giải = QHD

gọi F[i,j]= true nếu có dãy giảm trong đó giới hạn phần tử lớn nhất là i , tổng là j , =false nếu ko có dãy nào như vậy tổng bằng j

F[i,j]=true nếu F[i-1,j-i] = true hoặc F[i-1,j]= true
tính xong bảng phương án thì xét cột n của bảng , gặp ô nào trong cột = true thì truy vết ra , 1 điều trùng hợp là khi truy vết thì nó sẽ in ra dãy giảm luôn ^^

[=========> Bổ sung bài viết <=========]

chú ý chỗ truy vết , ko thì có mấy dãy trùng nhau thì toi ^^.
có thắc mắc gì các bạn cứ ý kiến ^^