To solve this problem, we need to determine the number of valid parentheses sequences of length (2n). This is a classic problem that can be efficiently solved using the concept of Catalan numbers.

Approach

The number of valid parentheses sequences of length (2n) is given by the (n)-th Catalan number. Catalan numbers can be computed using either dynamic programming or a combinatorial formula. Here, we use the combinatorial formula for its simplicity and efficiency:

The (n)-th Catalan number (C_n) is calculated as: [ C_n = \frac{1}{n+1} \binom{2n}{n} ] where (\binom{2n}{n}) is the binomial coefficient (number of ways to choose (n) elements from (2n) elements).

Solution Code

import math

n = int(input())
result = math.comb(2 * n, n) // (n + 1)
print(result)

Explanation

1. Combinatorial Formula: The formula (\frac{1}{n+1} \binom{2n}{n}) directly gives the number of valid parentheses sequences. This is because each valid sequence can be represented as a path in a grid that does not cross above the diagonal (Dyck path), which is exactly what Catalan numbers count.
2. Efficiency: Using the built-in math.comb function (available in Python 3.10+) allows us to compute the binomial coefficient efficiently. The integer division by (n+1) ensures we get an integer result (since Catalan numbers are integers).

For example, when (n = 3):

• (\binom{6}{3} = 20)
• (20 // (3+1) = 5), which matches the given output.

This approach is optimal for the problem constraints and provides the correct result in constant time for practical values of (n).

Answer: The code reads the input (n), computes the (n)-th Catalan number, and prints it. For input 3, the output is 5.

(\boxed{5})

作者声明:本文包含人工智能生成内容。