DCEPC903 - Encryption
Once Saikat sir tried to open his safe, but later on he realised that he forgot his password (which is actually a binary string), so he calls Anuja ma’am for help. Anuja ma’am then sends an encrypted message as they both wanted to keep the password safe.
Lets say if the password is
01100111
She encrypted this string by adding the adjacent bits of each bit to it (Characters off the left and right edges of the string are treated as zeroes), hence the new string will be 12211232
But on decryption Saikat sir realized that the decrypted string will not be unique and will lead to more than 1 binary strings. Being too much tired he asks you for help.
Input
First line contains T (1 <= T <= 100) number of test cases.
Each test case consists of 2 lines, first line consists of N (1 <= N <= 1000) length of the string and second line contains the encrypted message.
Output
So for each test case first print “Test x:” where x is the test case number starting from 1. Then print all possible binary strings in lexicographic order.
If there is no string possible then print "Not Possible" without quotes.
Example
Input: 3 5 11111 3 122 7 2222222 Output: Test 1: 01001 10010 Test 2: 011 Test 3: Not Possible
Added by: | dce coders |
Date: | 2012-08-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C C++ 4.3.2 CPP JAVA |
Resource: | Own Problem |