Задача

”Дорогой дядя Фёдор!

После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики!

Я сначала обрадовался, так как помню, что из шахматной доски он не мог выпилить больше 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

Код

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);
		}
	}
}

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}$$

Задача на e-olymp
Код программы на ideone
Засчитанное решение

Условие

Дана конечная последовательность, состоящая из левых и правых скобок различных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

Код

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static class stack
	{
		char arr[] = new char[10];
		int current;
		stack(){current = 0;};
		void push(char x)
		{
			arr[current] = x;
			current++;
		}
		void pop()
		{
			current--;
		}
		char back()
		{
			return arr[current-1];
		}
		int size()
		{
			return current;
		}
	};
	public static void main (String[] args) throws java.lang.Exception
	{
		String brace;
		Scanner input = new Scanner(System.in);
		brace = input.nextLine();
		stack x = new stack();
		char a = brace.charAt(0);
		if(a == '(' || a == '{' || a== '[') 
		{
			for(int i=0;i<brace.length();i++)
			{
				a = brace.charAt(i);
				if(a == '(' || a == '{' || a== '[')
					x.push(a);
				else if(Math.abs(a - x.back()) < 3 && x.size() != 0)
				{
            				x.pop();
				} else
				{
					System.out.println("No");
					System.exit(0);
				}
			}
			if(x.size() == 0)
			{
				System.out.println("Yes");
			} else System.out.println("No");
		}
		else 
		{
			System.out.println("No");
			System.exit(0);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static class stack

{

char arr[] = new char[10];

int current;

stack(){current = 0;};

void push(char x)

{

arr[current] = x;

current++;

}

void pop()

{

current--;

}

char back()

{

return arr[current-1];

}

int size()

{

return current;

}

};

public static void main (String[] args) throws java.lang.Exception

{

String brace;

Scanner input = new Scanner(System.in);

brace = input.nextLine();

stack x = new stack();

char a = brace.charAt(0);

if(a == '(' || a == '{' || a== '[')

{

for(int i=0;i<brace.length();i++)

{

a = brace.charAt(i);

if(a == '(' || a == '{' || a== '[')

x.push(a);

else if(Math.abs(a - x.back()) < 3 && x.size() != 0)

{

x.pop();

} else

{

System.out.println("No");

System.exit(0);

}

if(x.size() == 0)

{

System.out.println("Yes");

} else System.out.println("No");

}

else

{

System.out.println("No");

System.exit(0);

}

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать класс $latex stack$, в который поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Пример работы программы можно увидеть на сайте ideone.
Условие задачи.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: скобки

e-olymp 399. Последствия гриппа в Простоквашино

Задача

Входные данные

Выходные данные

Тесты

Код

Решение

AL6

Условие

Входные данные

Выходные данные

Код

Решение