eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Adjacent Bit Counts

Adjacent Bit Counts

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Для строки из n битов x_1, x_2, x_3, …, x_n, будем считать смежные биты строки функцией (AdjBC(x)) имеющей вид

x_1·x_2 + x_2·x_3 + x_3·x_4 + … + x_{n-1}·x_n

которая считает, сколько раз 1 бит примыкает к другому 1 биту. Например:

AdjBC(011101101) = 3 AdjBC(111101101) = 4 AdjBC(010101010) = 0

Напишите программу, которая принимает в качестве входных числа n и k и возвращает количество x n-битных строк (из 2^n), которые удовлетворяют AdjBC(x) = k. Например, для 5-битовых строк есть шесть способов получения AdjBC(x) = 2:

11100, 01110, 00111, 10111, 11101, 11011

Вхідні дані

Первая строка входного файла содержит одно целое число P (1P1000), которое указывает количество последующих наборов данных. Каждый набор данных представляет собой одну строку, содержащую номер набора данных, затем пробел, а далее заданное десятичное целое число (n) бит в n -битной строки, за которым следует опять один пробел и далее следует десятичное число (k) для выполнения подсчета прилегающих битов. Количество бит (n) не будет больше, чем 100 и значения n и k будут подобраны так, что ответ будет помещаться в 32-х разрядное число.

Вихідні дані

Для каждого набора входных данных вывести одну строку. Она должна содержать номер тестового набора данных, за которым следует один пробел, а далее количество n-битных строк, для которых количество смежных единичных битов равно k.

Приклад

Вхідні дані #1
10
1 5 2
2 20 8
3 30 17
4 40 24
5 50 37
6 60 52
7 70 59
8 80 73
9 90 84
10 100 90
Вихідні дані #1
1 6
2 63426
3 1861225
4 168212501
5 44874764
6 160916
7 22937308
8 99167
9 15476
10 23076518
Джерело Greater New York Regional 2009