Задача
”Дорогой дядя Фёдор!
После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.
Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики!
Я сначала обрадовался, так как помню, что из шахматной доски он не мог выпилить больше 64-х квадратиков. Но скоро понял, что я глубоко ошибался.
Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.
Всегда твой верный друг – кот Матроскин.”
Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.
Входные данные
В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.
Выходные данные
Вывести в $n$ строках по одному числу – ответ на соответствующее задание Шарика.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 3 2 3 4 |
1 0 2 |
| 2 | 5 3 11 7 43 27 |
0 0 0 0 0 |
| 3 | 6 2 28 42 14 64 0 |
1 2674440 24466267020 429 55534064877048198 1 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
import java.util.Scanner; class Main{ public static void main (String[] args) throws java.lang.Exception{ Scanner in = new Scanner(System.in); int n, k; long[] brackets = new long[33]; brackets[0] = 1; for(int i = 1; i <= 32; ++ i){ brackets[i] = 0; for(int j = 0; j < i; ++ j){ brackets[i] += brackets[j] * brackets[i - 1 - j]; } } n = in.nextInt(); for (int i = 0; i < n; i ++) { k = in.nextInt(); System.out.println(k % 2 == 0 ? brackets[k / 2] : 0); } } } |
Решение
Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$