Dãy số Catalan

Xem dạng PDF

Gửi bài giải


Điểm: 0,15 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho số nguyên dương ~N~, dãy Catalan cấp ~n~ là dãy ~C(1), C(2) ... C(2n+1)~ gồm các số nguyên không âm thoả mãn: ~C(1) = C(2n+1) = 0~ với ~i~ bất kì ~1 \le i \le 2n~ thì ~C(i), C(i+1)~ hơn kém nhau 1 đơn vị.

Với mỗi ~n~ ta sắp xếp các dãy Catalan theo thứ tự từ điển, đánh số từ 1 trở đi. Yêu cầu:

1. Cho một dãy Catalan, hãy tìm thứ tự của dãy.

2. Cho số nguyên dương ~k~ hãy tìm dãy có thứ tự ~k~.

Input

  • Dòng đầu ghi ~n~ ~(n \le 15)~.
  • Dòng hai ghi một dãy Catalan cấp ~n~.
  • Dòng 3 ghi một số nguyên dương ~k~ (~k~ có thể rất lớn nhưng đảm bảo luôn có nghiệm).

Output

  • Dòng 1 ghi số thứ tự dãy ở dòng 2 của input.
  • Dòng 2 ghi dãy ứng với số thứ tự.

Sample Input

4
0 1 2 3 2 1 2 1 0
12

Sample Output

12
0 1 2 3 2 1 2 1 0

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.