Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Từ xâu nhị phân 𝑆0 = "1" người ta sinh ra các xâu 𝑆1, 𝑆2, … , 𝑆𝑛 trong đó 𝑆𝑖 = 𝑆𝑖1 + 𝑆𝑖1. Ở đây 𝑆𝑖1 là xâu nhị phân tạo thành từ xâu 𝑆𝑖−1 bằng cách đảo hết các bit (bit 1 thành bit 0 và bit 0 thành bit 1).

Ví dụ:

𝑆0 = "1"

𝑆1 = "10"

𝑆3 = "10010110"

𝑆4 = "1001011001101001"

Yêu cầu: Cho số nguyên dương 𝑛, hãy xác định trong xâu 𝑆𝑛 có bao nhiêu vị trí có 2 bit liên tiếp bằng nhau (tức là đếm số lần xuất hiện của xâu "00" và "11" trong 𝑆𝑛) Dữ liệu vào:

  • Dòng 1 chứa số nguyên dương T105 là số test
  • T dòng tiếp theo, mỗi dòng chứa một số nguyên dương 𝑛109 ứng với một test

Kết quả: Ghi ra T dòng, mỗi dòng ghi một số nguyên duy nhất là số dư của kết quả tìm được khi chia cho 123456789.

Ví dụ:
Input:
Copy
4
1
2
3
4
Output:
Copy
0
1
2
5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.