Dãy Catalan Xếp Hạng Và Truy Ngược · canuc80k4008

Dãy Catalan cấp $n$ là dãy $C_{1}, \dots, C_{2 n + 1}$ số nguyên không âm, bắt đầu và kết thúc bằng $0$ , hai phần tử kề nhau chênh đúng $1$ . Sắp mọi dãy như vậy theo thứ tự từ điển và đánh số từ $1$ ; hãy tìm thứ hạng của dãy truy vấn và dãy đứng ở vị trí $k$ .

Input

Dòng đầu chứa cấp $n$ .
Dòng thứ hai chứa $2 n + 1$ giá trị của một dãy Catalan hợp lệ.
Dòng thứ ba chứa thứ hạng $k$ .

Output

Dòng đầu in thứ hạng của dãy đã cho.
Dòng thứ hai in dãy Catalan đứng ở vị trí $k$ .

Constraints

$1 \leq n \leq 15$ .
Dãy truy vấn là một dãy Catalan cấp $n$ hợp lệ.
$k$ là thứ hạng hợp lệ.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 10$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
0 1 2 1 2 1 0
3

Output

4
0 1 2 1 0 1 0

Giải thích: Năm dãy Catalan cấp $3$ theo thứ tự bắt đầu bằng $0$ $1$ $0$ $1$ $0$ $1$ $0, 0$ $1$ $0$ $1$ $2$ $1$ $0, 0$ $1$ $2$ $1$ $0$ $1$ $0, 0$ $1$ $2$ $1$ $2$ $1$ $0, 0$ $1$ $2$ $3$ $2$ $1$ $0$ . Dãy truy vấn đứng thứ tư, còn dãy cần khôi phục ở vị trí $3$ là $0$ $1$ $2$ $1$ $0$ $1$ $0$ .

Phân tích: Gọi ways[len][h] là số đường đi gồm len bước, bắt đầu ở độ cao h, kết thúc ở 0 và không xuống âm. Cơ sở ways[0][0]=1; chuyển: ways[len][h]=ways[len-1][h-1]+ways[len-1][h+1], bỏ trạng thái âm/không thể.
Phân tích: Rank: bắt đầu 1. Nếu bước thật là đi lên, và hiện tại có thể đi xuống, thì mọi dãy chọn bước xuống đứng trước; cộng ways[remaining][h-1]. Sau đó đi theo bước thật.
Phân tích: Unrank: thử đi xuống trước. Nếu k nằm trong downBlock, chốt xuống; nếu không, trừ block và đi lên.
Tính đúng đắn: Tại mọi tiền tố hợp lệ, các dãy hoàn tất được phân hoạch theo bước kế tiếp. Vì độ cao xuống h-1 nhỏ hơn độ cao lên h+1, toàn bộ block đi xuống đứng trước block đi lên. DP đếm chính xác số hậu tố của từng block theo nguyên lý phân hoạch bước đầu. Do đó rank cộng đúng các block nhỏ hơn và unrank chọn đúng block chứa k tại mọi bước.
Độ phức tạp: O(n²) thời gian và O(n²) bộ nhớ với n là cấp Catalan.