Dạo này thấy box Pascal ỉu xìu quá!

[truongngocdai]

Một dãy dấu ngoặc hợp lệ là một dãy các ký tự "(" và ")" được định nghĩa như sau:

1. Dãy rỗng là một dãy dấu ngoặc hợp lệ độ sâu 0
2. Nếu A là dãy dấu ngoặc hợp lệ độ sâu k thì (A) là dãy dấu ngoặc hợp lệ độ sâu k+1
3. Nếu A và B là hai dãy dấu ngoặc hợp lệ với độ sâu lần lượt là p và q thì AB là dãy dấu ngoặc hợp lệ độ sâu là max(p,q)

Độ dài của một dãy ngoặc là tổng số ký tự "(" và ")"

Bài toán đặt ra là khi cho biết trước hai số nguyên dương n và k, hãy liệt kê các dãy ngoặc hợp lệ có độ dài n và độ sâu là k

INPUT: file BRACKET.INP
- Dòng đầu tiên viết n là độ dài dãy dấu ngoặc
- Dòng thứ hai viết k là độ sâu dãy dấu ngoặc

OUTPUT: file BRACKET.OUT
Gồm nhiều dòng, mỗi dòng là 1 dãy dấu ngoặc hợp lệ

Ví dụ:
INPUT:
8
3
OUTPUT
((()()))
((())())
((()))()
(()(()))
()((()))

Chú ý: Bài này không có giới hạn n và k. HÃY LÀM ĐƯỢC VỚI N CÀNG LỚN CÀNG TỐT (đây cũng chính là thang đo điểm cho bài làm)

Bài này được trích từ cuốn DSAPTextbook của thầy Lê Minh Hoàng và có được sửa đổi đi chút ít ở phần input/output

[trinick_13]

He he! Gần giống với bài đi thi của tui!

[Nemesis_II]

Mình đã làm dc ... nhưng chưa cải tiến chỉ chạy tạm thôi ! CHưa ngon lám !
Kết quả :
_Pascal : 100 - 4 : Max ! Do không lưu dc File
_Free Pascal : 200 - 4 : 7 giây Dung lượng File Out Lên 112,435 KB (100Mb) (quá shock)

bạn nào Test thử nhe :
10 - 4 -> 7 Cấu hình
10 - 2 -> 5 Cấu hình
100 - 4 -> 66750 Cấu hình
100 - 2 -> 77 Cấu hình

CODE :

Program Bra;

Const Fi = 'Bracket.Inp';
Fo = 'Bracket.Out';

Var n,k:Longint;
A:Array[0..10000] Of Longint;
WF:Text;

Procedure Input;
Var F:Text;
i:Longint;
Begin
Assign(F,Fi);Reset(F);
Readln(F,n);
Readln(F,k);
Close(F);
For i:=1 to 2*k do A[i]:=i;
A[2*k+1]:=N;
A[0]:=0;
End;

Procedure Output;
Var i,j:Longint;
Begin
For i:=1 to (A[1]-1) Div 2 do Write(wF,'()');
For i:=1 to 2*k do
Begin
If i > k Then Write(wF,')') Else Write(wF,'(');
For j:=1 to ((A[i+1]-A[i]) Div 2) Do Write(wF,'()');
End;
Writeln(Wf);
End;

Procedure Try(t:Longint);
Var i:Integer;
Begin
If t> 2*k Then
Begin Output; Exit; End;
If t = k+1 Then Begin A[t]:=A[t-1]+1;Try(t+1);Exit; End;
A[t]:=A[t-1]+1;Try(t+1);
For i:=1 to (N - 2*k)Div 2 do
If (A[t]+2*i <= A[t+1])and(T <> K) Then
Begin
A[t]:=A[t]+2*i;
Try(t+1);
End;
For i:=1 to (((N - 2*k)Div 2)) do
If (T=k)and(A[t]+2*i <= A[t+2])and(A[t+1]+2*i <= A[t+2]) Then
Begin
A[t]:=A[t]+2*i;{Try(t+1);}
End
End;

Procedure Solve;
Begin Try(1); End;

BEGIN
Input;
Assign(wF,Fo);Rewrite(wF);
Solve;
Close(wF);
END.

[truongngocdai]

Bạn có thể nêu thuật toán và ý tưởng của bạn không chứ viết code không thế này thì khó hiểu quá

[Nemesis_II]

ah !
Thuật toán là thế này :
Các bạn có thể xem một dấu ngoặt quyết định ( Tức " ( " hoặc " ) " ) là một dấu ngoặt mà nó sẽ quyết định độ sau của dãy !
Ví dụ như theo "ví dụ" trên của bạn nhé (8 - 3)

1 2 3 4 5 6 7 8
(_(_(_)_(_)_)_)
(_(_(_____)_)_)

1 2 3 4 5 6 7 8
(_(_(_)_)_)_(_)
(_(_(_)_)_)____

1 2 3 4 5 6 7 8
(_(_)_(_(_)_)_)
(_(___(___)_)_)

_Các dấu ngoặc dc đánh dấu (-) là dấu ngoặc quyết định đến độ sâu của dãy !
_Dể thấy rằng với độ sâu bằng 3 thì sẽ có 6 dấu ngoặc quyết định (Tức 3 mở ngoặt và 3 đống ngoặc)
_Độ sau của dãy sẽ không thay đổi nếu mình thêm vào giử các dấu ngoặc quyết định 2 dấu "()"

Ví dụ :
(_(_(_)_)_) -> Độ sâu bằng 3
(_(_)_(_(_)_)_) -> Độ sâu bằng 3
__o_o -> Vị trí thêm vào 2 dấu ngoặc mới mà độ sâu ko đổi
Tương tự :
(_(_(_)_)_)_(_) -> độ dâu vẫn bằng 3.

_Nói nôn na là nếu bạn thêm váo một cặp dấu "( _ )" vào giữa các dấu ngoặt quyết định thì độ sau sẽ ko thay đổi !
_Tuy nhiên bạn cần chú ý dấu ngoặc thứ k và k+1 (Tức nằm ở giữa và tạo nên độ sau tối đa) vì nếu bạn thêm vào đây thì độ sâu sẽ thay đổi

Ví dụ :
(_(_(_)_)_) -> Độ sau bằng 3
(_(_(_(_)_)_)_) -> Thêm vào giữa độ sâu tăng lên 4

Giải thích về chương trình :
A : là mảng lưu vị trí của các dấu ngoặc quyết định
ví dụ :
i = 0 1 2 3 4 5 6 7
A = 0 1 2 5 6 7 8 8
-> các bạn sẽ dc dãy các dấu như sau :
(_(_(_)_(_)_)_)
Thủ tục Try(t) - T là dấu ngoặc quyết định thứ T (0<=t<=2K)
-MỘi lần mình thử dịch các dấu ngoặt sang 2 ô để chèn "()" vào sau đó lại làm như thế với các dấu típ theo !

p/s : ah ! bài trên còn thiếu một trường hợp 2 ngoặt lồng nhau nhưng độ sâu vẫn ko thay đổi "(_(_)_)" , vì mình làm hơi nhanh - sorry ! Bạn viết thủ tục xuất thêm khu đó là dc ! vẫn dc tính theo độ sau quyết định đó !

[truongngocdai]

@trinick_13: lại spam rồi, bỏ cái tính đấy đi nhóc
@Có ai còn có cách nào khác không

[bete]

Tui nghĩ như vầy:

giả sử mình in ra TẤT CẢ các chuỗi tạo được từ '(' và )' => mình sẽ làm đại khái như sau:
Ở mỗi vị trí: thử xài '(' (lần 1) và thử xài ')' (lần 2 -- khi quay lui)

Nhưng sẽ có nhiều chuỗi không thỏa đề bài: không cân bằng, không đủ độ sâu hoặc quá sâu

Mình có thể sửa lại:

Ở mỗi vị trí:

Nếu phải xài '(' (thỏa điều kiện 1) => xài '(' (và sẽ không có lần 2 -- sẽ không quay lui)
Ngược lại, nếu phải xài ')' (thỏa điều kiện 2) => xài ')' (và sẽ không có lần 2 -- sẽ không quay lui)
Ngược lại => xài '(' nếu là lần 1; hoặc xài ')' nếu là lần 2 (đang quay lui)
...........
Nếu đã xài hết kí tự => in chuỗi đang có và quay lui

Điều kiện 1 (phải xài '('): số '(' cần cân bằng là 0 (không thể xài ')') hoặc [chưa đạt độ sâu và không còn dư kí tự]

Điều kiện 2 (phải xài ')': số ')' còn thiếu > 0 và không còn dư kí tự

Để lượng giá điều kiện 1 và điều kiện 2 tại mỗi vị trí thì mình cần có các thông số sau:

Số ')' còn thiếu (= số '(' cần cân bằng; = độ sâu hiện thời)
Độ sâu lớn nhứt đã đạt
Số kí tự chưa xài

Mỗi khi mình xài '(' hoặc ')' (khi quay lui) thì phải hiệu chỉnh các thông số trên một cách tương ứng . Cần thêm 2 mảng chứa độ sâu hiện thời và độ sâu lớn nhứt đã đạt tương ứng tại mỗi vị trí (để khi quay lui có thể hiệu chỉnh 2 thông số này)

(có gì sai sót mong được góp ý, xin cám ơn)

-thân

[Nemesis_II]

To TruongNgocDaiCa : Thực sự nếu bác dùng quay lui + nhánh cận và Thêm trường hợp biên thì chắc chắn đúng 100 % nhưng sẽ chạy dc ko lớn !
Ý bác thế nào ?

[1+1=2]

Châc đây là 1 bài trên spoj mà...
Mà bài này dùng đê quy quay lui thì chi có die...

[truongngocdai]

To TruongNgocDaiCa : Thực sự nếu bác dùng quay lui + nhánh cận và Thêm trường hợp biên thì chắc chắn đúng 100 % nhưng sẽ chạy dc ko lớn !
Ý bác thế nào ?

uh, mình cũng công nhận là như thế. Lúc trước mình cũng đã nghĩ ra 1 số ràng buộc như về các dấu ngoặc. Nghĩa là trong trường hợp này chỉ có duy nhất 1 trường hợp là mở ngoặc hay đóng ngoặc (1 trong 2). Còn nếu không thuộc ràng buộc đó thì sẽ quay lui tiếp, xét cả 2. Vì vẫn còn nhiều lỗi nên mình không dám post lên .