Problem:
 Score : 300 points    Problem Statement Given an integer N , find the base -2 representation of N .  Here, S is the base -2 representation of N when the following are all satisfied:   S is a string consisting of 0 and 1 .  Unless S =  0 , the initial character of S is 1 .  Let S = S_k S_{k-1} ... S_0 , then S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N .   It can be proved that, for any integer M , the base -2 representation of M is uniquely determined.      Constraints  Every value in input is integer.  -10^9 \leq N \leq 10^9         Input Input is given from Standard Input in the following format:  N       Output Print the base -2 representation of N .        Sample Input 1 -9      Sample Output 1 1011  As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9 , 1011 is the base -2 representation of -9 .       Sample Input 2 123456789      Sample Output 2 11000101011001101110100010101       Sample Input 3 0      Sample Output 3 0

Solution (Python):
N=int(input())
left,right=0,1
parity=1
interval=[]
ansList=[]
digit = -1
for i in range(40):
    if parity == 1:
        interval.append((right-2**i+1,right))
    else:
        interval.append((left,left+2**i-1))
    if left <= N and N <= right:
        digit = i
        break
    else:
        if parity==1:
            left -= 2**(i+1)
            parity=-1
        else:
            right += 2**(i+1)
            parity=1


while digit >= 0:
    left,right = interval[digit]
    
    if left <= N and N<= right:
        ansList.append('1')
        N -= parity*(2**digit)
    else:
        ansList.append('0')
    digit -= 1
    parity = -parity
ans = "".join(ansList)
print(ans)

Solution (Python):
import math


N = int(input())

if N == 0:
    print(0)
else:
    S = ""
    while N != 0:
        S = str(N + 2 * math.ceil(N / -2)) + S
        N = math.ceil(N / -2)

    print(S)

Solution (Python):
def convert_base(n):
    temp = n
    out = ''
    if n == 0:
        return '0'
    while temp != 0:
        q, r = divmod(temp, -2)
        if r == -1:
            q += 1
            r = 1
        out = str(r) + out
        temp = q
    return out

N = int(input())

print(convert_base(N))

Solution (Python):
import sys
N = int(sys.stdin.readline())

def div(a):
    return -(a // 2), a % 2


res = []
while N < 0 or 2 <= N:
    N, a = div(N)
    res.append(a)
res.append(N)

print(''.join(map(str, reversed(res))))

Solution (Python):
N = int(input())

if N == 0:
  print("0")
  exit()

res = ""
while N != 1:
  if N % 2 == 0:
    res += "0"
    N = N / (-2)
  else:
    res += "1"
    N = (N -1) / (-2)
res += "1"
print(res[::-1])

Solution (Python):
import math
N = int(input())

def retPlace(num):
    retVal = str(num % 2)
    num = math.ceil(num / (-2))
    if num != 0:
        retVal += retPlace(num)
    return retVal

ans = retPlace(N)
print(ans[::-1])

Solution (Python):
from collections import deque

def solve(n):
    queue = deque()
    while n != 0:
        r = -(n % (-2))
        
        n = (n - 1) // (-2)
        queue.appendleft(str(r))
    return 0 if len(queue) == 0 else "".join(queue)

if __name__ == "__main__":
    n = int(input())
    print(solve(n))

Solution (Python):
N = int(input())

res = ""

if N==0:print(0);exit()

while N!=0:
    tmp = N % -2
    N = N//-2 -tmp
    res = str(abs(tmp))+res

print(res)

Solution (Python):
def f(n):
    if n == 0:
        return "0"
    if n == 1:
        return "1"
    a = n // -2
    b = n % -2
    if b == -1:
        a += 1
        b += 2
    return f(a) + str(b)


def main():
    N = int(input())
    print(f(N))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())

ans = []

if N == 0:
    print("0")
else:
    while N != 1:
        if N%2 == 0:
            ans.append("0")
            N = N//(-2)
        else:
            ans.append("1")
            N = (N-1)//(-2)
    else:
        ans.append("1")

print("".join(ans[::-1]))

Solution (Python):
import sys
import math
import collections
import itertools
import array
import inspect


sys.setrecursionlimit(10000)



def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))



def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]




dp = None
c = []


def f(B):
    ans = 0
    for idx in range(len(B)):
        if B[len(B) - idx - 1] == "1":
            ans += ((-2)**idx)

    return ans


def is_lower(idx, c_value, N):
    add_value = 0
    for i in range(idx, -1, -1):
        if c[i] > 0:
            add_value += c[i]

    return c_value + add_value < N




def is_over(idx, c_value, N):
    sub_value = 0
    for i in range(idx, -1, -1):
        if c[i] < 0:
            sub_value += c[i]

    return c_value + sub_value > N


def main():
    N = int(input())
    c_value = None

    if N == 0:
        print(0)
        return

    for i in range(50):
        c.append((-2)**i)

    if N > 0:
        tmpsum = 0
        for i in range(50):
            if c[i] > 0:
                tmpsum += c[i]

            if tmpsum >= N:
                idx = i
                c_value = c[i]
                break

        ans = "1"

        for c_idx in range(idx - 1, -1, -1):
            if c[c_idx] < 0:
                if is_over(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"
            else:
                if is_lower(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"

    else:
        tmpsub = 0
        for i in range(50):
            if c[i] < 0:
                tmpsub += c[i]

            if tmpsub <= N:
                idx = i
                c_value = c[i]
                break

        ans = "1"

        for c_idx in range(idx - 1, -1, -1):
            if c[c_idx] < 0:
                if is_over(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"
            else:
                if is_lower(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"

    print(ans)


main()

Solution (Python):
N=int(input())
ans=[]

def calc(N):
    if N==0: return
    elif N>0:
        n=N
        power=-2
        while n>0:
            power+=2
            n-=2**power
    else:
        n=-N
        power=-1
        while n>0:
            power+=2
            n-=2**power
            
    ans.append(power)
   
    calc(N-(-2)**power)

if N==0:print('0')
else:
    calc(N)
    answer=''
    for a in range(ans[0],-1,-1):
        if a in ans: answer=answer+'1'
        else: answer=answer+'0'
    print(answer)

Solution (Python):
round = lambda x: (x*2+1)//2

def rec(num):
    ans = round(num / (-2))
    remain = num - (-2)*ans
    if ans == 0:
        print(int(remain), end='')
        return
    rec(ans)
    print(int(remain), end='')
    return

def p_ans(num):
    rec(num)
    print()

if __name__ == '__main__':
    N = int(input())
    p_ans(N)

Solution (Python):
n = int(input())

if n == 0:
    print('0')
else:
    s = ''
    i = 0
    while n != 0:
        q = n % 2
        s = str(q) + s
        n = (n - q*((-1)**i)) // 2
        i += 1
    print(s)

Solution (Python):
n = int(input())
str = ''
if n == 0:
  str = '0'
else:
  while n != 0:
    if n % 2 == 0:
      str = '0' + str
      n /= (-2)
    else:
      str = '1' + str
      n -= 1
      n /= (-2)
print(str)

Solution (Python):

N = int(input())
if N == 0:
  print('0')
  exit()

N_ = N
S = ''
b = 1

for i in range(100):
  N__ = abs(N_)
  if N__ % (b*2) == 0:
    S = '0' + S
  else:
    N_ = N_ - b
    S = '1' + S
  if N_ == 0:
    break
  b = b * (-2)

print(S)

Solution (Python):
def f(n):
    return (4 ** n - 1) // 3


n = int(raw_input())

if n < 0:
    m = 0
    while -2 * f(m) > n:
        m += 1
else:
    m = 0
    while f(m) < n:
        m += 1

if m == 0:
    print '0'
else:
    mask = sum(2 * 4 ** j for j in xrange(m))
    print bin((n + 2 * f(m)) ^ mask)[2:]

Solution (Python):
import numpy as np
import math

N = int(input())



k = 0

ret = ''

rest = N

while True:
    
    
    
    if rest % 2 == 1:
        ret += '1'
        if k % 2 == 0:
            rest -= 1
        else:
            rest += 1
    else:
        ret += '0'
    k += 1

    if rest == 0:
        break
    rest = int(rest / (2))
    

print(ret[::-1])

Solution (Python):

from bisect import bisect_left
def inpl(): return list(map(int, input().split()))

N = int(input())
A = []
B = []
for i in range(2**16):
    A.append(int(("0{}"*16).format(*list(bin(i)[2:].zfill(16))), 2))
for i in range(2**16):
    B.append(-int(("{}0"*16).format(*list(bin(i)[2:].zfill(16))), 2))

for j, b in enumerate(B):
    i = bisect_left(A, N-b)
    if i == len(A):
        continue
    a = A[i]
    if a+b == N:
        ans = [""]*32
        ans[::2] = list(bin(j)[2:].zfill(16))
        ans[1::2] = list(bin(i)[2:].zfill(16))
        print(int("".join(ans)))
        break

Solution (Python):
n = int(input())

if n != 0:
    ans = ''
    while n != 0:
        while n%2 == 0:
            n = n//(-2)
            ans = '0'+ans
        n = n-1
        ans ='1'+ans
        n = n/(-2)
else:
    ans = '0'
    
print(ans)

Solution (Python):
n = int(input())
i = 0
s = ''
for _ in range(100):
    
    d = n % 2**(i+1)
    
    if d:
        n -= (-2)**i
        s = '1' + s
    else:
        s = '0' + s
    if n == 0:
        break
    i += 1
    
print(s)

Solution (Python):
def c_base_minus2_number(N):
    def negaternary(i):
        if i == 0:
            digits = ['0']
        else:
            digits = []
            while i != 0:
                i, remainder = divmod(i, -2)
                if remainder < 0:
                    i, remainder = i + 1, remainder + 2
                digits.append(str(remainder))
        return ''.join(digits[::-1])

    ans = negaternary(N)
    return ans

N = int(input())
print(c_base_minus2_number(N))

Solution (Python):
n=int(input())

s=""
index=1

while n!=0:
    if n%2!=0:
        s+="1"
        n+=(-1)**index
    else:
        s+="0"
    n//=2
    index+=1

if len(s)==0:
    s="0"

print(s[::-1])

Solution (Python):
def negabinary(i):
    if i == 0:
        digits = ['0']
    else:
        digits = []
        while i != 0:
            i, remainder = divmod(i, -2)
            if remainder < 0:
                i, remainder = i + 1, remainder + 2
            digits.append(str(remainder))
    return ''.join(digits[::-1])


print(negabinary(int(input())))

Solution (Python):
N = int(input())
def solve(n):
	if n == 0:
		return "0"
	out = []
	while n != 0:
		n, rem = divmod(n, -2)
		if rem < 0:
			n += 1
			rem -= -2
		out.append(rem)
	return "".join(map(str, out[::-1]))
print(solve(N))

Solution (Python):


N = int(input())

S = ''
for i in range(50):
    if N % -2 == 0:
        S = '0' + S
    else:
        S = '1' + S
        N -= 1

    N = N // -2

print(int(S))

Solution (Python):





n=int(input())
a=[]

if n==0:
    a=["0"]

while n != 0:
        a.append(str(n%2))
        n=-(n-n%2)//2

print("".join(list(reversed(a))))

Solution (Python):
n = int(input())

a = ""

if n == 0:
    print(0)
else:
    while n != 0:
        if n % (-2) == 0:
            a += "0"
            n = n // -2
        else:
            a += "1"
            n = n // -2 + 1
    b = a[::-1]
    print(b)

Solution (Python):
n = int(input())
ans = []

if n == 0:
	print(0)
else:

	i = 0
	
	while n != 0:
		if n % (2 ** (i + 1)) != 0:
			ans.append("1")
			n -= (-2) ** i
		else:
			ans.append("0")

		i += 1

	print("".join(ans[::-1]))

Solution (Python):
N = int(input())
fugou = 1
ans = ''
if N == 0:
    ans = '0'
else:
    q = N
    while q!= 0:
        if q > 0:
            r = q%2
            q = (-1)*(q//2)
        else:
            q = -q
            r = q%2
            if r == 0:
                q = q//2
            else:
                q = q//2+1
        ans += str(r)
print(ans[::-1])

Solution (Python):
n = int(input())
answer = ''
while n <= -1 or 2 <= n:
    if n % 2 == 0:
        answer = '0' + answer
        n //= -2
    else:
        answer = '1' + answer
        n = n // -2 + 1
print(str(n) + answer)

Solution (Python):

N = int(input())

res_list = []
k = 0

while N != 0:
    if N % (2**(k+1)) != 0:
        N -= (-2)**k
        res_list.append("1")
    else:
        res_list.append("0")
    k += 1
if len(res_list) == 0:
    res_list.append("0")
    
print("".join(reversed(res_list)))

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

n = input()
if n == 0:
    print '0'
    exit()
num = 1
sig = 1
ans = ''
while n != 0:
    if n % (num * 2) != 0:
        n -= num * sig
        ans += "1"
    else:
        ans += "0"
    num *= 2
    sig *= -1
print ans[::-1]

Solution (Python):
A = int(input());
answer = str();
i=0;

if(A==0):
    print("0");
else:
    while(A!=0):
        if(A%abs(pow(-2,i+1))!=0):
            A-=pow(-2,i);
            answer = str(1) + answer;
        else:
            answer = str(0) + answer;
        i+=1;
    print(answer);

Solution (Python):
N = int(input())

if N == 0:
    print(0)
    exit()

a = ''
b = -2

while N != 1:
    if N % b == 0:
        a += '0'
        N = N // b
    else:
        a += '1'
        if N > 0:
            N = N // b + 1
        else:
            N = N // b + 1
if N == 1:
    a += '1'
print(a[::-1])

Solution (Python):
def foo(n):
    if n == 0:
        return "0"
    else:
        res = ""
        while n != 0:
            r = n % (-2)
            n = n // (-2)
            if r < 0:
                n += 1
                r += 2
            res += str(r)
    return "".join(reversed(res))


n = int(input())
print(foo(n))

Solution (Python):
N = int(input())
S = ""
if N == 0:
    print(0)
    exit(0)
    
while N != 0:
    r = N%(-2)
    N = N//(-2)
    if r < 0:
        r += 2
        N += 1
    S += str(r)
print(S[::-1])

Solution (Python):
def solve(N):
    if N == 0: return '0'
    s = []
    b = 1
    while N != 0:
        s.append('0' if N % 2 == 0 else '1')
        if N % 2 != 0:
            N -= b
        N //= 2
        b = -b
    s.reverse()
    return ''.join(s)

N = int(input())
print(solve(N))

Solution (Python):
N = input()

i = 1
s = ""

while abs(i) <= abs(N):
	if (abs(N) & abs(i)) != 0:
		s += '1'
		N -= i
	else:
		s += '0'

	i *= -2

if s == "":
	s = "0"
s = s[::-1]
print s

Solution (Python):
n = int(input())
if n == 0:
	 print ("0")
out = []
while n != 0:
	 n, rem = divmod(n, -2)
	 if rem < 0:
	 	 n += 1
	 	 rem -= -2
	 out.append(rem)
print ("".join(map(str, out[::-1])))

Solution (Python):
n=int(input())
b=2
c=0
ans=0
while n!=0:
    if n%b!=0:
        ans+=10**c
        n-=(-2)**c
    c+=1
    b*=2
print(ans)

Solution (Python):
n = int(input())
a = ''
for i in range(100):
    if n==0:
        break
    if (n % (2**(i+1)) != 0):
        a = '1'+a
        if i%2 == 0:
            n -= 2**i
        else:
            n += 2**i
    else:
        a = '0'+a
if a=='':
    a = '0'
print(a)

Solution (Python):
n = int(input())
l=[]
tmp=1
if n%abs(tmp*2)!=0:
    n-=tmp
    l.append('1')
else:
    l.append('0')

while n!=0:
    tmp *= (-2)
    if n%abs(tmp*2)!=0:
        n-=tmp
        l.append('1')
    else:
        l.append('0')
print(''.join(reversed(l)))

Solution (Python):
n=int(input())

s=''
while n!=0:
	s=str(n%2)+s
	n=-(n//2)
if s=='':
	print('0')
else:
	print(s)

Solution (Python):
def f(x):
 if x==0:return "0"
 if x==1:return "1"
 return f((x%2-x)/2)+str(x%2)
n=input()
print f(n)

Solution (Python):
N = input()
a = ""
while N!=0:
  d = int(N%2!=0)
  a += str(d)
  N -= d
  N /= -2
print "0" if a=="" else a[::-1]

Solution (Python):
N = int(input())
bit = []
for i in range(32):
    b = (N >> i) & 1
    if i % 2 == 0:
        bit.append(b)
        if b:
            N -= 1 << i
    else:
        bit.append(((N >> i) & 1))
        if b:
            N += 1 << i
while bit and bit[-1] == 0:
    bit = bit[:-1]
if not bit:
    bit = [0]
print(*bit[::-1], sep='')

Solution (Python):
N=int(input())
S=""
if N==0:
    print(0)
    exit()
while(True):
    if N==1:
        S="1"+S
        break
    if N%2==1:
        S="1"+S
    else:
        S="0"+S
    N-=N%2
    N=N//(-2)
print(S)

Solution (Python):
n=int(input())
s=''
while True:
    r=n%(-2)
    n //= -2
    if r<0:
        r+=2
        n+=1
    s+=str(r)
    if n == 0: break
print(s[::-1])

Solution (Python):
N = int(input())

answer = ''

for i in range(40):
    if N % (2**(i + 1)) != 0:
        N -= (-2)**i
        answer = '1' + answer
    else:
        answer = '0' + answer
while len(answer) > 1 and answer[0] == '0':
    answer = answer[1:]

print(answer)

Solution (Python):
N=int(input())
S=""

while N!=0:
    if N%(-2)==0:
        S="0"+S
    else:
        S="1"+S
        N-=1
    N=N/(-2)

if S=="":
    S="0"

print(S)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()

if n == 0:
    print(0)
else:
    s = ""
    while n != 0:
        if n % 2 != 0:
            n -= 1
            s = "1" + s
        else:
            s = "0" + s
        n //= -2
    print(s)

Solution (Python):
n = input()
x = 1
ret = ""
while n != 0:
    if n % abs(2*x) != 0:
        n -= x
        ret = "1" + ret
    else:
        ret = "0" + ret
    x *= -2
if len(ret) == 0:
    ret = "0"
print ret