Задача

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

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

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

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

Задача

Для заданного целого $x$ найти количество таких $a$, удовлетворяющих условию:

$ a $ xor $x > x $

$ 0 < a < x $

где $a$ и $x$ — целые, xor — битовый XOR оператор.

Имеются $q$ запросов, каждый из которых содержит целое число $x$. Для каждого запроса выведите общее количество значений $a$, удовлетворяющих условиям выше.

Код

import java.util.*;

class Main{
	public static void main (String[] args){
		Scanner in = new Scanner(System.in);
		long q, x, res, two; 
		q = in.nextInt();
		for(long i = 0; i < q; ++ i){
			x = in.nextLong();
			res = 0;
			two = 1; // two = 2^0
			while(x > 0){
				if(x % 2 == 0) // check if the last bit is equal to zero
					res += two;
				x >>= 1;	// moving to the next bit
				two <<= 1; // same as two *= 2
			}
			System.out.println(res);
		}
	}
}

import java.util.*;

class Main{

public static void main (String[] args){

Scanner in = new Scanner(System.in);

long q, x, res, two;

q = in.nextInt();

for(long i = 0; i < q; ++ i){

x = in.nextLong();

res = 0;

two = 1; // two = 2^0

while(x > 0){

if(x % 2 == 0) // check if the last bit is equal to zero

res += two;

x >>= 1; // moving to the next bit

two <<= 1; // same as two *= 2

}

System.out.println(res);

}

Решение

XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.

Задача на e-olymp

Код программы на ideone

Засчитанное решение

№	Входные данные	Выходные данные
1	2 2 10	1 5
2	3 13 3 16	2 0 15
3	5 1 7 4294967295 42 451	0 0 0 21 60

java@Cat

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

Author Archives: Никита Репнин

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

Задача

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

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

Тесты

Код

Решение

e-olymp 4142. Большой XOR

Задача

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

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

Тесты

Код

Решение