| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13774 | Mom, don't do that 3.0 |
|
| 13782 | Super Idol (lab10) |
|
Description
Modified from 13752 - Mom, don't do that 2.0.
To further improve our security, we modify our encoding rule:
First, you'll be given a number n, and you'll use n to get a binary string Sn, following the representation:
S0 = "0"S1 = "1"Si = (Si-1) + ("1") + (reverse(invert(Si-1))) + ("0") + (invert(reverse(Si-2))) for i > 1
Reverse means that after such a function, the order of the binary string will be reversed(e.g., reverse(100) -> 001).
Invert means that after such a function, all the bits will become its inverse(e.g., invert(011)-> 100).
For example, S2 is "11001", and S3 is "1100110110000".
Next, there will be given T indexes k, indicating the position of choosing element in the decoded binary string Sn.
So, your job is to print all the Sn[k], which implies your final password.
Input
The first line is N(1 <= N <= 20) and T(1<= T <= 30), separated by white space.
The next T lines are the index of chosen element, k(1 < k < len(Sn)).
Output
For each test case, print "0" or "1' according to the decoded binary string and the index.
You have to print a '\n' in each line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
TWICE is a world-wise famous idol group.
One day, there is a special event for people with fans ID in the range [start, end].
Since you are a CS student, you want to check if there are any special relations between the numbers in this range.
The way you check these numbers is easy:
There will be T test cases.
For each test case, given the range [start, end], you must calculate the bitwise AND of all numbers in this range, inclusive.
For example, [5, 7] will be 5 & 6 & 7, which will be 101 & 110 & 111.
The calculated result is 4(100).
Note that for test case 1~3, there will be only 1 test case; for test case 4~5, there will be multiple test cases.
If you got TLE, please consider the bit relation in these numbers instead of using a brute-force algorithm.
Input
The first line is T(1 <= 50).
The next T lines are the test cases.
For each test case, are 2 unsigned integers start and end(1 <= start, end <=2147483647), separated by white space.
Output
For each test case, you have to print a '\n' in the end.