Problem Link : https://codeforces.com/gym/102133/problem/G
Suppose, the answer for N is X. Now, to find the answer for N+1 there could be two cases :
If X is not divided by 2^(N+1) : As X is divided by 2^N and X is not divided by 2^(N+1) , the value of X % 2^(N+1) is equal to 2^N. We can prove this :
X = y * 2^N (where y = 0, 1, 2, ......)
Now, if y is even then X then X = y * 2^(N+1). So, X will be divided by 2^(N+1)
If y is odd then X then
X = (2z + 1) * 2^N
X = z * 2^(N+1) + 2^N
So, remainder when divided by 2^(N+1) is 2^N
Now, I have to add a multiple of 2^N with X to make it divisible by 2^(N+1). While adding multiple of 2^N I have to be careful of the digits (Only 1 and 2 can be used). So, I will add 10^Y (where Y >= N) with X and this will add a digit 1 in the front. But, if the number of digits in X is less than N then there will be some zero in between 1 and the most significant digit of X. This is because the answer for N should always have N number of digits.
If X is divided by 2^(N+1) : In this case, I have to add a digit so that the answer of N+1 has N+1 number of digits. Digit 1 can't be used as 10^N is not divisible by 2^(N+1). But digit 2 can be used as (2 * 10^N) is divisible by 2^(N+1).
2 x 10^N = 2 ^ (N + 1) x 5 ^ N
So, the final solution is if the previous answer is divisible by 2^i then add digit 2 in the front of that answer. Otherwise add digit 1.
Code : https://ideone.com/ffEATj