Confusion in Binary Number
All submissions for this problem are available.
John is learning binary numbers (base 2 numbers with only two symbols 0 and 1 only). He took the help of one of his friend Dave. Dave tried to confuse John. He told the John that there are eight magic numbers (1, 2, 4, 8, 16, 64, 128) in decimal for which there are special strings in binary (k/a magic strings) and told the following rules:
Magic string for Magic number 1 is 000.
Magic string for Magic number 2 is 001
Magic string for Magic number 4 is 010
Magic string for Magic number 8 is 011
Magic string for Magic number 16 is 100
Magic string for Magic number 32 is 101
Magic string for Magic number 64 is 110
Magic string for Magic number 128 is 111
Now he asks to play a game to John. He told him that he will give three things, a binary string ‘bs’ , a positive integer number n and no of passes ‘x’ ( also a positive integer) to john. First he need to break the number n such that it is represented as the sum of magic numbers and those magic numbers ( and their corresponding magic strings )are said to be contained in number n. Eg for n=142
142 = 128+8+4+2
Magic numbers 2,4,8 and 128 are said to be contained in 142 and their corresponding magic strings 001,010,011 and 111 are said to be contained in 142.
After that he need to process the given string ‘bs’ x times with the following rules:
For every kth character in string 'bs' we construct a magic string such that first character will be the left neighbour of kth character in given string ‘bs’. Middle character will be the the kth character and last character will be the right neighbour of kth character in the given string ‘bs’. [Note that if k is the first character then left neighbour will be the last character of the string and if k is the last character then right neighbour of k will be the first character of the string.]
Now if the formed magic string is contained in ‘n’ then kth character will be replaced by 1, otherwise 0. [Note that John needs to perform this operation for every character in the string ‘bs’ then one pass will be regarded as complete].
For n= 142 ,x=10 and string ‘bs ’
bs = 00000000000100000000000
the new strings created will be
00000000001100000000000 (Pass 1)
00000000011000000000000 (Pass 2)
00000000110000000000000 (Pass 3)
00000001100000000000000 (Pass 4)
00000011000000000000000 (Pass 5)
00000110000000000000000 (Pass 6)
00001100000000000000000 (Pass 7)
00011000000000000000000 (Pass 8)
00110000000000000000000 (Pass 9)
01100000000000000000000 (Pass 10) -> RESULT
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows :
For each test case next three lines will be string bs (Binary string) , n ( Number) and x (Number of passes).
For each test case, output a single line containing single string that results after x passes. So your program will total print T lines
- 1 ≤ T ≤ 100
- 0 ≤ n ≤ 255
- 0 < length(bs) < 100
- 0 ≤ k < 100
Input: 2 00000000000100000000000 142 10 010101010 17 2 Output: 01100000000000000000000 111111100
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.