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



Sample input:
-9


Sample output:
1011

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import logging
import time


class Solver:
    def __init__(self):
        self.n = 0

    # 入力
    def input_value(self):
        # self.n = int(input())
        # self.A, self.B = map(int, input().split())
        # self.A = list(map(int, input().split()))
        # self.a, self.b, self.c = map(int, [input() for i in range(4)])
        # self.t = [None] * self.n
        self.n = int(input())

    @staticmethod
    def sigma(n):
        x = 0
        if n % 2 == 0:
            for i in range(0, n + 1, 2):
                x += (-2) ** i
        else:
            for i in range(1, n + 1, 2):
                x += (-2) ** i
        return x

    @staticmethod
    def to_base_m2(n):
        # logging.debug(input_str)
        if n == 0:
            return '0'

        MAX_BIT = 30
        s = ''
        i = MAX_BIT
        while i >= 0:
            if i % 2 == 0:
                if Solver.sigma(i - 2) < n <= Solver.sigma(i):
                    s = s + '1'
                    n -= (-2) ** i
                else:
                    s = s + '0'
            elif i % 2 == 1:
                if Solver.sigma(i) <= n < Solver.sigma(i - 2):
                    s = s + '1'
                    n -= (-2) ** i
                else:
                    s = s + '0'
            i -= 1
        while s[0] == '0':
            s = s[1:]
        return s

        # logging.debug(input_str)



    # def run(self):
    #     if self.n % self.k == 0:
    #         return 0
    #     return 1

    @staticmethod
    def test():
        start_time = time.time()

        assert Solver.sigma(2) == 5, 'Error.'
        assert Solver.sigma(3) == -10, 'Error.'
        assert Solver.to_base_m2(9) == '11001', 'Error.'
        assert Solver.to_base_m2(-9) == '1011', 'Error.'
        assert Solver.to_base_m2(123456789) == '11000101011001101110100010101', 'Error.'
        assert Solver.to_base_m2(0) == '0', 'Error.'
        assert Solver.to_base_m2(1) == '1', 'Error.'
        assert Solver.to_base_m2(2) == '110', 'Error.'
        assert Solver.to_base_m2(-1) == '11', 'Error.'
        assert Solver.to_base_m2(-2) == '10', 'Error.'

        elapsed_time = time.time() - start_time
        logging.debug('elapsed_time: {0}'.format(elapsed_time) + '[sec]')


if __name__ == '__main__':
    logging.basicConfig(level=logging.DEBUG)

    solver = Solver()

    # Solver.test()

    solver.input_value()
    ans = solver.to_base_m2(solver.n)
    # print(str(ans))
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())+2
a=""
for i in range(n):
    if n%2==0:
        a+=0
    else:
        a +=1
    n /= 2
    if n <= 1:
        a += n
        print(a)
        exit()

Submission status: Runtime Error

Solution code:
n = int(input())
ps = [0] * (1 << 16)
for i in range(1 << 16):
    temp = 0
    for j in range(16):
        if (i >> j) & 1:
                temp += (-2) ** (2 *j)
    ps[i] = temp

"""
for index, value in enumerate(ps):
    print(bin(index)[2:].zfill(16), value)
"""

pattern1 = None
pattern2 = None

for i in range(1 << 16):
    temp2 = 0
    for j in range(16):
        if (i >> j) & 1:
                temp2 += (-2) ** (2 *j + 1)
    n2 = n - temp2
    pattern1 = bisect.bisect_left(ps, n2)
    if pattern1 != (1 << 16) and ps[pattern1] == n2:
        pattern2 = bin(i)[2:].zfill(16)
        pattern1 = bin(pattern1)[2:].zfill(16)
        break

ans = ""
for i in range(16):
    ans += pattern2[i]
    ans += pattern1[i]
    
true_ans = ""
flag = False
for i in range(len(ans)):
    if ans[i]=="1":
        true_ans += "1"
        flag = True
    elif flag:
        true_ans += "0"

if true_ans == "":
    true_ans = "0"
        
print(true_ans)

Submission status: Runtime Error

Solution code:
import bisect
def put(a,b):
    l=max(len(a),len(b))
    a="0"*l+a
    b="0"*l+b
	s=""
    for i in range(-1,-l-1,-1):
      s+=a[i]+b[i]
    print(s[-1::-1])

def quad(i):
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18):
    l+=[4**i+j for j in l]

n=int(input())
for i in range(len(l)):
    if (n-l[i])%2==0:
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break

Submission status: Runtime Error

Solution code:
import bisect
def put(a,b):
    l=max(len(a),len(b))
    a="0"*l+a
    b="0"*l+a
	s=""
    for i in range(-1,-l-1,-1):
      s+=a[i]+b[i]
    print(s[-1::-1])

def quad(i):
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18):
    l+=[4**i+j for j in l]

n=int(input())
for i in range(len(l)):
    if (n-l[i])%2==0:
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break

Submission status: Runtime Error

Solution code:
import bisect
def put(a,b):
 	l=max(len(a),len(b))
    a="0"*l+a
    b="0"*l+a
	s=""
    for i in range(-1,-l-1,-1):
      s+=a[i]+b[i]
    print(s[-1::-1])

def quad(i):
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18):
    l+=[4**i+j for j in l]

n=int(input())
for i in range(len(l)):
    if (n-l[i])%2==0:
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break

Submission status: Runtime Error

Solution code:
import numpy as np

def SolveNegBinary(N):
    r = N
    # ansTrue allocates the "True" index for -2nary expression
    ansTrue = []
    
    while r != 0:
        ind = (- np.sign(r) + 1)/2
        s = (-2)**ind
        while np.abs(s) < np.abs(r):
            ind +=2
            s += (-2)**ind

        ansTrue.insert(0,ind)
        r = r - (-2)**ind

    displayAnswer = ""
    for k in range(ansTrue[-1] + 1)[::-1]:
        if k in ansTrue:
            displayAnswer += "1"
        else:
            displayAnswer += "0"
        
    
    print displayAnswer
    

n = input()
SolveNegBinary(n)

Submission status: Runtime Error

Solution code:
a=int(input())
b=''
while a:
  s=str(a&1)+s
  n=-(n//2)
print(b if b else 0)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
stack<int> stk;
int main(){
  int x;
  cin>>x;
  do {
    int r = x > 0 ? x % 2 : -(x%2);
    stk.push(r);
    x-=r;
    x/=-2;
  } while(x);
  while(!stk.empty()){
    cout<<(stk.top()!=0);
    stk.pop();
  }
  cout<<'\n';
  return 0;
}

Submission status: Runtime Error

Solution code:
a=int(input())
b=[]
if a==0:
  print(0)
else:
  while a:
	b.append(a&1)
	a=int((a-(a&1))/(-2))
  print(''.join(map(str,b)))

Submission status: Runtime Error

Solution code:
a=int(input())
b=[]
if(a==0)print(0)
else:
  while a:
	b.append(a&1)
	a=int((a-(a&1))/(-2))
  print(''.join(map(str,b)))

Submission status: Runtime Error

Solution code:
a=int(input())
b=[]
if(a==0)print(0)
while a:
	b.append(a&1)
	a=int((a-(a&1))/(-2))
print(''.join(map(str,b)))

Submission status: Runtime Error

Solution code:
N = int(input())
def n_aray_notation(N, n):
  if N == 0:
    return '0'
  else:
    s = ''
    while N:
      s = str(N % abs(n)) + s
      N -= N % abs(n)
      N //= n
    return s
print(n_array_notation(N, -2))

Submission status: Runtime Error

Solution code:
n=int(input())
s=''
while n!=0:
  s=str(n%2)+s
  n=-(n//2)
print(s*(s!='')else 0)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
i = int(raw_input())
print(bin(i).split('b')[1])

Submission status: Runtime Error

Solution code:
N = float(input())

if N==0:
  print(0)
else:
q = N
r_s = []

while q!=1:
  hoge = (q-1) / (-2)
  if hoge.is_integer():
    r = int(1)
    q = float(hoge)
  else:
    r = int(0)
    q = float(q/(-2))
  
  r_s.append(r)
r_s.append(1)
r_s = r_s[::-1]

for i in range(len(r_s)):
  print(r_s[i], end="")

Submission status: Runtime Error

Solution code:
N = int(input())
import math
import itertools
f = []
max_len = int(math.log(abs(N), 2) // 1)
for i in range(max_len+1):
    f.append((-2) ** i)
for m in range(1,max_len+1):
    l = list(itertools.combinations(f,m))
    ans = [0] * len(l)
    for k in range(len(l)):
        if sum(l[k]) == N:
            for j in range(len(l[0])):
                a = [i for i, x in enumerate(f) if x == l[k][j]][0]
                ans[a] = 1
print(''.join(list(map(str,ans[::-1]))))

Submission status: Runtime Error

Solution code:
N = int(input())
import math
import itertools
f = []
max_len = int(math.log(abs(N), 2) // 1)
for i in range(max_len+1):
    f.append((-2) ** i)
for m in range(1,max_len+1):
    l = list(itertools.combinations(f,m))
    ans = [0] * len(l)
    for k in range(len(l)):
        if sum(l[k]) == N:
            for j in range(3):
                a = [i for i, x in enumerate(f) if x == l[k][j]][0]
                ans[a] = 1
print(''.join(list(map(str,ans[::-1]))))

Submission status: Runtime Error

Solution code:
N=-int(input())
if N=0:
    print(0)
else:
    tmp=[]
    while N!=0:
        tmp.insert(0,N%(2))
        N=-N//2
    s=''.join([str(_) for _ in tmp])
    print(s)

Submission status: Runtime Error

Solution code:
N = int(input())
ts = fetch_Hosu(N)

le = len(ts)
numl = [0]* 15

for i in range(15):
    tmp = int(ts[2*i+1:2*i+3])
    
    if tmp ==1:
        numl[i]  += 11
    elif tmp ==11:
        if i>1:
            numl[i-1]  += 11
        numl[i]  += 1
    else:
        numl[i]  += tmp
    
#     print(numl)

# print(numl)

for j in range(len(numl)):
    if numl[14-j]==21:
        numl[13-j]  += 11
        numl[14-j]  = 1

    if numl[14-j]==12:
        numl[14-j]  = 0
    
    if numl[14-j]==22:
        numl[14-j]  = 10
    
# print(numl)
outttt = ["{0:02d}".format(i) for i in numl]
# print(outttt)
ttt=""
for k in range(len(outttt)):
    ttt += outttt[k]

ttt += ts[-1]

if int(ttt)==0:
    print(0)
else:
    tetee = str(ttt)
    tpl = tetee[2:].find("1")
    print(tetee[tpl+2:])

Submission status: Runtime Error

Solution code:
N = int(input())
ts = fetch_Hosu(N)

le = len(ts)
numl = [0]* 15

for i in range(15):
    tmp = int(ts[2*i+1:2*i+3])
    
    if tmp ==1:
        numl[i]  += 11
    elif tmp ==11:
        if i>1:
            numl[i-1]  += 11
        numl[i]  += 1
    else:
        numl[i]  += tmp
    
#     print(numl)

# print(numl)

for j in range(len(numl)):
    if numl[14-j]==21:
        numl[13-j]  += 11
        numl[14-j]  = 1

    if numl[14-j]==12:
        numl[14-j]  = 0
    
    if numl[14-j]==22:
        numl[14-j]  = 10
    
# print(numl)
outttt = ["{0:02d}".format(i) for i in numl]
# print(outttt)
ttt=""
for k in range(len(outttt)):
    ttt += outttt[k]

ttt += ts[-1]

# print(ttt)
tetee = str(ttt)
tpl = tetee[2:].find("1")
print(tetee[tpl+2:])

Submission status: Runtime Error

Solution code:
N = int(input())
import numpy as np
#何桁か
dign = 0
if N > 0:
    n = 0
    while (4**n-1)/3<N:
        n=n+1
        N = N-4**n
    dign = 2*n+1
    
elif N == 0:
    answer = [0]
else:
    n = 0
    absN = abs(N)
    while 2*(4**n-1)/3<absN:
        n = n+1
    dign = 2*n
    N = N + 4**n
answer = np.zeros(dign)

def ans(N):
    if N > 0:
        n = 0
        while (4**n-1)/3<N:
            n=n+1
        N = N-4**n
        dign = 2*n+1
        answer[dign]=1
        ans(N)
        
    elif N == 0:
        answer=[0]
    else:
        n = 0
        absN = abs(N)
        while 2*(4**n-1)/3<absN:
            n = n+1
        dign = 2*n
        N = N + 4**n
        answer[dign]=1
        ans(N)
ans(N)
print(answer)

Submission status: Runtime Error

Solution code:
N = int(input())

def ans(ans_list, value):
    if value > 0:
        for i in range(16):
            if 4**(i+1) == 3*value+1:
                ans_list[2*i+1] = 1
                return ans_list
            elif 4**(i+1) > 3*value+1:
                ans_list[2*i+1] = 1
                print(value)
                return ans(ans_list, value-4**i)
    elif value < 0:
        for i in range(15):
            if 4**i == 3*abs(value)/2+1:
                ans_list[2*i] = 1
                return ans_list
            elif 4**i > 3*abs(value)/2+1:
                ans_list[2*i] = 1
                print(value)
                return ans(ans_list, value+2*4**(i-1))

if N == 0:
    print(0)
else:
    ans_list = [0]*16
    ans_list = ans(ans_list, N)
    answer = int("".join(map(str, ans_list[::-1]))[:-1])
    print(answer)

Submission status: Runtime Error

Solution code:
a=int(input())
sum=0
s=''
'''if a<0:
    b = abs(a)
    if b%2==1:
        b=b+1
        print(str(bin(b))[2:-1]+'1')
    else:
        print(str(bin(b))[2:-1])''
if a!=0:
    while(a!=1):
        if a%(-2)==-1:
            s=s+'1'
            a=a-1
            a=a/-2
        else:
            s = s + '0'
            a=a/-2
    s=s+'1'
    for i in range(len(s)):
        print(s[len(s)-1-i],end='')
    print()
else:
    print(0)

Submission status: Runtime Error

Solution code:
N = float(input())

q = N
r_s = []
while q!=1:
  hoge = (q-1) / (-2)
  if hoge.is_integer():
    r = int(1)
    q = float(hoge)
  else:
    r = int(0)
    q = float(q/(-2))
  
  r_s.append(r)
r_s = r_s.append(1)
r_s = r_s[::-1]

for i in range(len(r_s)):
  print(r_s[i], end="")

Submission status: Runtime Error

Solution code:
N = float(input())

q = N
r_s = []
while q!=1:
  hoge = (q-1) / (-2)
  if hoge.is_integer():
    r = int(1)
    q = float(hoge)
  else:
    r = int(0)
    q = float(q/(-2))
  
  r_s = r_s.append(r)
r_s = r_s[::-1]
for i in range(r_s):
  print(i, end="")

Submission status: Runtime Error

Solution code:
n=int(input())
#正答が出るプログラムではないです
base = [(-2)** i for i in range(32)]
num = 0
for i0 in range(2):
  num += base[0]*i0
  for i1 in range(2):
    num += base[1]*i1
    for i2 in range(2):
      num += base[2]*i2
      for i3 in range(2):
        num += base[3]*i3
        for i4 in range(2):
          num += base[4]*i4
          for i5 in range(2):
            num += base[5]*i5
            for i6 in range(2):
              num += base[6]*i6
              for i7 in range(2):
                num += base[7]*i7
                for i8 in range(2):
                  num += base[8]*i8
                  for i9 in range(2):
                    num += base[9]*i9
                    for i10 in range(2):
                      num += base[10]*i10
                      for i11 in range(2):
                        num += base[11]*i11
                        for i12 in range(2):
                          num += base[12]*i12
                          for i13 in range(2):
                            num += base[13]*i13
                            for i14 in range(2):
                              num += base[14]*i14
                              for i15 in range(2):
                                num += base[15]*i15
                                for i16 in range(2):
                                  num += base[16]*i16
                                  for i17 in range(2):
                                    num += base[17]*i17
                                    for i18 in range(2):
                                      num += base[18]*i18
                                      for i19 in range(2):
                                        num += base[19]*i19
                                        for i20 in range(2):
                                          num += base[20]*i20
                                          for i21 in range(2):
                                            num += base[21]*i21
                                            for i22 in range(2):
                                              num += base[22]*i22
                                              for i23 in range(2):
                                                num += base[23]*i23
                                                for i24 in range(2):
                                                  num += base[24]*i24
                                                  for i25 in range(2):
                                                    num += base[25]*i25
                                                    for i26 in range(2):
                                                      num += base[26]*i26
                                                      for i27 in range(2):
                                                        num += base[27]*i27
                                                        for i28 in range(2):
                                                          num += base[28]*i28
                                                          for i29 in range(2):
                                                            num += base[29]*i29
                                                            for i30 in range(2):
                                                              num += base[30]*i30
                                                              for i31 in range(2):
                                                                num += base[31]*i31
                                                                if num == n: 
                                                                  ans = str(i0)+str(i1)+str(i2)+str(i3)+str(i4)+str(i5)+str(i6)+str(i7)+str(i8)+str(i9)+str(i10)+str(i11)+str(i12)+str(i13)+str(i14)+str(i15)+str(i16)+str(i17)+str(i18)+str(i19)+str(i20)+str(i21)+str(i22)+str(i23)+str(i24)+str(i25)+str(i26)+str(i27)+str(i28)+str(i29)+str(i30)+str(i31)

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

a = []
s = 0
while (-2)**s<1000000000:
    a.append((-2)**s)
    s += 1


def judge(n):
    sum = 0
    count = 0
    dig = 0
    if n >0:
        for num in a:
            count += 1
            if num >0:
                sum += num
            if sum >= n:
                dig = count
                break
    else:
        for num in a:
            count += 1
            if num <0:
                sum += num
            if sum <= n:
                dig = count
                break
            
    return dig
    
ans = ["0" for i in range(judge(n))]

while n!=0:
    ans[judge(n)-1] = "1"
    n -= a[judge(n)-1]

    
answer = ""
for i in range(len(ans)-1,-1,-1):
    answer += ans[i]
    
print(answer)

Submission status: Runtime Error

Solution code:
from sys import stdin
stdin = open('sample.txt')


def main():
    N = int(stdin.readline().rstrip())

    if N == 0:
        print('0')
        return

    ans = ''
    base = 2
    while N != 1:
        ans = str(abs(N % base)) + ans
        N = N // base
        N = -1 * N
    print('1' + ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
inp = input()
if inp > -1:
  print('{0:b}'.format(int(inp)))
else:
  s = ""
  maximum = math.floor(math.log(abs(inp), 2))
  for i in range(maximum,0):
    if inp - math.pow(2,i) < 0:
      s += '1'
      inp -= math.pow(2,i)
    else:
      s += '0'
  print(s)

Submission status: Runtime Error

Solution code:
import math
inp = input()
if inp > -1:
  print('{0:b}'.format(int(inp)))
else:
  s = ""
  maximum = math.floor(math.log(abs(inp), 2))
  for i in range(maximum,0):
    if inp - math.pow(2,i) < 0:
      s += '1'
      inp -= math.pow(2,i)
    else
      s += '0'
  print(s)

Submission status: Runtime Error

Solution code:
N = int(input())
ans = [0]*36

def bit(inp,ans):
    if inp == 0:
        ans[0] = 0
        inp2 = 0
    
    if inp > 0:
        b = [1,5,21,85,341,1365,5461,21845,87381,349525,1398101,5592405,22369621,89478485,357913941,1431655765]
        pcount = 0
        for ii in range(len(b)):
            if inp <= b[ii]:
                inp2 = inp - 4**ii
                break
            pcount = pcount + 1
        ans[pcount*2] = 1
        
    if inp < 0:
        b2 = [-2,-10,-42,-170,-682,-2730,-10922,-43690,-174762,-699050,-2796202,-11184810,-44739242,-178956970,-715827882]
        pcount = 0
        for ii in range(len(b2)):
            if inp >= b2[ii]:
                inp2 = inp + 2 * (4**ii)
                break
            pcount = pcount + 1
        ans[pcount*2+1] = 1
        
    return inp2,ans

    
while N != 0:
    N,ans = bit(N,ans)

fi = ans[::-1]
fistr = [str(n) for n in fi]
m = ''.join(fistr)
mm = int(m)

print(mm)

Submission status: Runtime Error

Solution code:
N=int(input())
L=[]
M=""
while N!=0:
  M=int((-1)*(N%(-2)))
  if N<0:
    N=int((N-1)/(-2))
  else:
    N=int(N/(-2))
  L.insert(0,str(M))
if N=0:
  print(0)
else:
  print("".join(L))

Submission status: Runtime Error

Solution code:
N = int(input())
ans = [0]*32

def bit(inp,ans):
    if inp == 0:
        ans[0] = 0
        inp2 = 0
    
    if inp > 0:
        b = [1,5,21,85,341,1365,5461,21845,87381,349525,1398101,5592405,22369621,89478485,357913941]
        pcount = 0
        for ii in range(len(b)):
            if inp <= b[ii]:
                inp2 = inp - 4**ii
                break
            pcount = pcount + 1
        ans[pcount*2] = 1
        
    if inp < 0:
        b2 = [-2,-10,-42,-170,-682,-2730,-10922,-43690,-174762,-699050,-2796202,-11184810,-44739242,-178956970]
        pcount = 0
        for ii in range(len(b2)):
            if inp >= b2[ii]:
                inp2 = inp + 2 * (4**ii)
                break
            pcount = pcount + 1
        ans[pcount*2+1] = 1
        
    return inp2,ans


while N != 0:
    N,ans = bit(N,ans)

fi = ans[::-1]
fistr = [str(n) for n in fi]
m = ''.join(fistr)
mm = int(m)

print(mm)

Submission status: Runtime Error

Solution code:
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])))