#804. BITRANS - Biến đổi nhị phân

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

NGUỒN: TRẠI HÈ HÙNG VƯƠNG LẦN THỨ XII (BẮC GIANG 2016)

Với một dãy nhị phân bất kỳ, ta biến đổi dãy nhị phân như sau:

  • 1 → 01
  • 0 → 10

Như vậy, với dãy bắt đầu là 1 :

  • Sau bước biến đổi thứ nhất, ta sẽ thu được dãy 01 .
  • Sau phép biến đổi thứ 2 , ta thu được 1001 .
  • Sau phép biến đổi thứ 3 , ta thu được 01101001 . …

Người ta muốn tính xem, sau n bước biến đổi, sẽ thu được dãy gồm có bao nhiêu cặp 2 số 0 đứng liên tiếp.

Dữ liệu vào:

  • Gồm một số test, mỗi test được ghi trên một dòng, mỗi dòng ghi một số nguyên không âm n .

Dữ liệu ra:

  • Với mỗi test, ghi ra số cặp 2 số 0 đứng liên tiếp.

Ví dụ:

Dữ liệu vào:
2
3
Dữ liệu ra:
1
1

Ràng buộc:

  • 40\% số test ứng với 40\% số điểm của bài có n≤ 20 ;
  • 40\% số test khác ứng với 40\% số điểm của bài có n≤ 50 ;
  • 20\% số test còn lại ứng với 20\% số điểm còn lại của bài có n≤1000 .