SPOJ.com - Problem BCBIT

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCBIT - Đếm bít liền kề

Cho một chuỗi nhị phân có n phần từ: x₁, x₂, x₃, …, x_n. Giá trị đếm bít liền kề được định nghĩa theo công thức:

AdjBC(x) = x₁*x₂ + x₂*x₃ + … + x_n-1*x_n.

tức là đếm các bít 1 mà bít liền kề cũng là bít 1.

Ví dụ:

AdjBC(011101101) = 3

AdjBC(111101101) = 4

AdjBC(010101010) = 0

Viết chương trình nhận vào hai số nguyên n và k và trả về số các xâu nhị phân x có n phần tử mà AdjBC(x) = k.

Ví dụ với n=5, k=2, ta có 6 xâu nhị phân độ dài 5 có AdjBC(x) = 2 là: 11100, 01110, 00111, 10111, 11101, 11011.

Dữ liệu vào:

Dòng đầu tiên ghi số 1<= n <=1000 là số bộ Test.

Mỗi bộ Test ghi trên một dòng bắt đầu là số thứ tự bộ test, sau đó là hai số nguyên dương n và k với n không lớn hơn 100, k<n.

Dữ liệu ra:

Với mỗi bộ test, ghi trên một dòng: số thứ tự bộ test, tiếp theo là số xâu nhị phân độ dài n có AdjBC(x) = k.

Ví dụ cho Input và Output:

INPUT

OUTPUT

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 6

2 63426

3 1861225

4 168212501

5 44874764

6 160916

7 22937308

8 99167

9 15476

10 23076518

ID	RESULT	TIME

code...

Submit solution!

Được gửi lên bởi:	adm
Ngày:	2011-10-20
Thời gian chạy:	1s-2.727s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

BCBIT - Đếm bít liền kề