SP5295 GNYR09F - Adjacent Bit Counts

For a string of n bits x1,x2,x3,...,Xn the adjacent bit count of the string (AdjBC(x)) is given by X1\*X2 + X2\*X3 + X3\*X4 + ... + Xn-1 \* Xn which counts the number of times a 1 bit is adjacent to another 1 bit. For example: AdjBC(011101101) = 3 AdjBC(111101101) = 4 AdjBC(010101010) = 0 Write a program which takes as input integers n and k and returns the number of bit strings x of n bits (out of 2ⁿ) that satisfy AdjBC(x) = k. For example, for 5 bit strings, there are 6 ways of getting AdjBC(x) = 2: 11100, 01110, 00111, 10111, 11101, 11011

The first line of input contains a single integer P, (1

For each data set there is one line of output. It contains the data set number followed by a single space, followed by the number of n-bit strings with adjacent bit count equal to k.