Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
3. Nhân của biểu thức In E-mail
(3 votes)
Người viết: Ngô Minh Đức   
20/06/2008

Bài 3. Nhân của biểu thức

Biểu thức ngoặc là xâu chỉ gồm các ký tự ‘(’ và ‘)’. Biểu thức ngoặc đúng được định nghĩa một cách đệ qui như sau:

B         Biểu thức rỗng là biểu thức ngoặc đúng,

·         Nếu A là biểu thức ngoặc đúng thì (A) cũng là một biểu thức ngoặc đúng,

·         Nếu A và B là hai biểu thức ngoặc đúng thì AB cũng là một biểu thức ngoặc đúng.

Số lượng ký tự trong biểu thức ngoặc đúng gọi là độ dài của biểu thức.

Cho S là một biểu thức ngoặc đúng độ dài 2n (n > 0).  Nhân của S ký hiệu là Ker(S) và được xác định như sau. Gọi U là xâu thu được từ S bằng cách bỏ đi m ký tự cuối và m ký tự đầu của S, trong đó m = n div 2. Khi đó:

  • Ker(S) = U, nếu U là biểu thức ngoặc đúng và US,
  • Ker(S) = Æ (biểu thức rỗng), trong trường hợp ngược lại,

Qui ước Ker(Æ) = Æ.

Ví dụ, S = ‘()(())()’, ta có Ker(S) = ‘(())’. Nếu S = ‘()(())’, có Ker(S) = Æ, U = ‘)(()’ – không phải là biểu thức ngoặc đúng. Dễ dàng nhận thấy, với n = 1, Ker(S) = Æ.

Với biểu thức ngoặc đúng S cho trước ta có thể thực hiện đệ qui nhiều lần phép xác định nhân Ker(Ker((Ker(S))…)) cho đến khi nhận được biểu thức rỗng. Ta gọi bậc của biểu thức S là số lần thực hiện đệ qui việc xác định nhân của S cho đến khi nhận được biểu thức rỗng.

Ví dụ, biểu thức S = ‘()(())()’ có bậc 3 vì:

()(())() ® (()) ® ()® Æ.

Biểu thức S = ‘()(())’ có bậc 1 vì nhân của nó Ker(S) = Æ.

Yêu cầu: Xét các biểu thức ngoặc đúng độ dài 2n và có bậc p. Các biểu thức này được sắp xếp theo thứ tự từ điển (‘(‘ < ‘)’) và đánh số bắt đầu từ 1 trở đi. Hãy tìm biểu thức thứ k.

Dữ liệu: Vào từ file văn bản EKERNEL.INP gồm một dòng chứa 3 số nguyên n, pk, các số cách nhau một dấu cách (1 ≤ n ≤ 40, 1 ≤ p ≤ 6, 1 ≤ k ≤ 3×1018). Dữ liệu đảm bảo tồn tại biểu thức cần tìm.

Kết quả: Ghi ra file văn bản EKERNEL.OUT xâu ký tự xác định biểu thức tìm được.

Ví dụ:

EKERNEL.INP

EKERNEL.OUT

3 1 2

()(())

 
< Trước   Tiếp >