Back to Category
d244: [12.06] E - Circular Codes
Keyword:

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 2 Times | Submit :11 Times | Clicks : 350
Accepted : 1 Users | Submit : 1 Users | Accepted rate : 100%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
Update : 2012-10-29 17:19

Content:

The Circular Intelligence Agency stores all secret information in the following circular codes. Each encrypted string is an N-bit binary string c = c0c1 ... cN-1. We say that binary string a = a0a1 ... aN-1 is a circular rotation of c if there exists an index k with 0 ≤ k ≤ N - 1 such that ci = a(i+k) mod N holds for each i =0, 1, ... , N - 1. The message d = d0d1 ... dN-1 to be decrypted is the bit-wise exclusive-OR of a = a0a1 ... aN-1 and b = b0b1 ... bN-1, where 
  •  a is the circular rotation of c such that the binary number represented by a (if treated as a nonnegative integer) is the maximum, and
  •  b is the circular rotation of c such that the binary number represented by b (if treated as a nonnegative integer) is the minimum.
 
 For instance, if c = 11001, then a = 11100, b = 00111, and d = 11011.
 

Technical Speci cation

  •  1 ≤ N ≤ 300000 

Input:

In the rst line of the input le there is an integer C, indicating the number
of distinct test cases to be followed. Each of the next C lines stands for a
test case. For each test case, there is an integer N, followed by an N-bit
binary string.

Output:

Output should be C lines. The binary string in the j-th line is the decrypted
message for the j-th test case.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5
5 10101
6 111111
7 0000000
6 110110
25 1101001011100100111010101

Sample Output :

10001
000000
0000000
101101
1100110110111110001110011

Hint :

click here to download the problem solving hint

Author :


  Solve it!   Status Forum

C
C++
JAVA
PASCAL
46206. rabbit125
(184ms, 1616KB, 851B)

Program running time may be affected by various factors. Check server system environment information here