Problem:


Score : 2400 points

Problem Statement

Takahashi and Aoki love calculating things, so they will play with numbers now.

First, they came up with one positive integer each. Takahashi came up with X, and Aoki came up with Y.
Then, they will enjoy themselves by repeating the following operation K times:

Compute the bitwise AND of the number currently kept by Takahashi and the number currently kept by Aoki. Let Z be the result.

Then, add Z to both of the numbers kept by Takahashi and Aoki.

However, it turns out that even for the two math maniacs this is just too much work.
Could you find the number that would be kept by Takahashi and the one that would be kept by Aoki eventually?

Note that input and output are done in binary.
Especially, X and Y are given as strings S and T of length N and M consisting of 0 and 1, respectively, whose initial characters are guaranteed to be 1.

Constraints

1 ≤ K ≤ 10^6

1 ≤ N,M ≤ 10^6

The initial characters of S and T are 1.

Input

Input is given from Standard Input in the following format:

N M K
S
T

Output

In the first line, print the number that would be kept by Takahashi eventually; in the second line, print the number that would be kept by Aoki eventually.
Those numbers should be represented in binary and printed as strings consisting of 0 and 1 that begin with 1.

Sample Input 1

2 3 3
11
101

Sample Output 1

10000
10010

The values of X and Y after each operation are as follows:

After the first operation: (X,Y)=(4,6).

After the second operation: (X,Y)=(8,10).

After the third operation: (X,Y)=(16,18).

Sample Input 2

5 8 3
10101
10101001

Sample Output 2

100000
10110100

Sample Input 3

10 10 10
1100110011
1011001101

Sample Output 3

10000100000010001000
10000100000000100010



Sample input:
2 3 3
11
101


Sample output:
10000
10010

Submission status: Wrong Answer

Solution code:
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")
print("hello")

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
s=int(input())
t=int(input())
def bitwise(n,m):
    c=0
    i=0
    while n>=1 and m>=1:
        an=n%(10**1)
        am=m%(10**1)
        if an==1 and am==1:
            c+=10**i
        n=(n-an)/10
        m=(m-am)/10
        i+=1
    return(c)
def two_ten(n):
    z=0
    c=0
    while n>=1:
        if n%10==1:
            z+=2**c
            n-=1
        n/=10
        c+=1
    return(z)
def ten_two(n):
    z=0
    c=0
    while n>=1:
        if n%2==1:
            z+=10**c
            n-=1
        n/=2
        c+=1
    return(z)  

while k >0:
    z=bitwise(s,t)
    s10=two_ten(s)+two_ten(z)
    t10=two_ten(t)+two_ten(z)
    s=ten_two(s10)
    t=ten_two(t10)
    k-=1
print(s)
print(t)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
s=int(input(),2)
t=int(input(),2)
for i in range(k):
    z=s&t
    s+=z
    t+=z
print(format(s,'b'))
print(format(t,'b'))

Submission status: Time Limit Exceeded

Solution code:
m=-1;I=input;N,M,K=map(int,I().split());W=2000000;s=[0]*W;t=[0]*W;L=max(N,M)-1;R=range;p=lambda x:print(*reversed(x),sep='')
for i,c in zip(R(N-1,m,m),I()):s[i]=int(c)
for i,c in zip(R(M-1,m,m),I()):t[i]=int(c)
for i in R(L,m,m):
 j=i;z=K
 while s[j]and t[j]and z:
  s[j]=t[j]=0;s[j+1]+=1;t[j+1]+=1;j+=1;z-=1;x=y=j
  while s[x]==2:s[x]=0;s[x+1]+=1;x+=1
  while t[y]==2:t[y]=0;t[y+1]+=1;y+=1
  j=max(x,y)
 L=max(L,j)
s=s[:L+1];t=t[:L+1]
while s[m]==0:s.pop()
while t[m]==0:t.pop()
p(s);p(t)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M, K = map(int, input().split())

    MAX_N = 2000000

    s = [int(c) for c in input()][::-1] + [0] * (MAX_N - N)
    t = [int(c) for c in input()][::-1] + [0] * (MAX_N - M)

    len_max = max(N, M) - 1
    st = []
    for i in range(len_max, -1, -1):
        m = []
        if s[i] and t[i]:
            s[i] = t[i] = 0
            xs = xt = 1
            z = K - 1
            j = i + 1

            while xs or xt:
                if not s[j] and not t[j]:
                    if xs and not xt:
                        s[j] = 1
                        st.append(j)
                        len_max = max(len_max, j)
                        break
                    elif not xs and xt:
                        t[j] = 1
                        st.append(j)
                        len_max = max(len_max, j)
                        break

                if not st or st[-1] - j > z:
                    s[j + z] = t[j + z] = 1
                    len_max = max(len_max, j + z)
                    break

                p = st.pop()
                z -= p - j
                j = p

                if s[j] == xs and t[j] == xt:
                    s[j] = t[j] = 0
                    j += 1
                    continue

                if xs and xt:
                    xs = s[j]
                    xt = t[j]
                    s[j] ^= 1
                    t[j] ^= 1
                    m.append(j)
                    j += 1
                    continue

                if s[j] != xs and t[j] != xt:
                    if not z:
                        s[j] = t[j] = 1
                        break
                    else:
                        s[j] = t[j] = 0
                        j += 1
                        z -= 1
                        xs = xt = 1
                        continue

            st += reversed(m)

        elif s[i] or t[i]:
            st.append(i)
    
    js = jt = 0
    while not s[len_max - js]:
        js += 1
    while not t[len_max - jt]:
        jt += 1

    print(*s[len_max - js:: -1], sep='')
    print(*t[len_max - jt:: -1], sep='')


main()

Submission status: Time Limit Exceeded

Solution code:
(n, m, k) = list(map(int, input().split()))
s = int(input(), 2)
t = int(input(), 2)

for _ in range(k):
    an = s & t
    s += an
    t += an

print(bin(s)[2:])
print(bin(t)[2:])

Submission status: Time Limit Exceeded

Solution code:
N, M, K = (int(i) for i in input().split())
S = int(input(), 2)
T = int(input(), 2)

for i in range(K):
    Z = S & T
    S += Z
    T += Z
print(format(S, "b"))
print(format(T, "b"))

Submission status: Time Limit Exceeded

Solution code:
N,M,K = input().split(' ')
S = int(input(),2)
T = int(input(),2)
for i in range(0,int(K)):
    Z = S & T
    S,T = Z+S, Z+T
print(bin(S)[2:])
print(bin(T)[2:])

Submission status: Time Limit Exceeded

Solution code:
def tenTotwo(x):
    ret =""
    while x >0:
        if x%2==1:
            ret += '1'
        else:
            ret += '0'
        x //= 2

    return ret[::-1]
N,M,K = [int(i) for i in input().split(' ')]
a = input()
b = input()
a_=0
b_=0
for i in range(len(a)):
    a_ += int(a[i])*(2**(len(a)-i-1))
for i in range(len(b)):
    b_ += int(b[i])*(2**(len(b)-i-1))
#print(type(a))
for i in range(K):
    z = a_&b_
    a_ += z
    b_ += z
    #print(z)

print(tenTotwo(a_))
print(tenTotwo(b_))

Submission status: Time Limit Exceeded

Solution code:
def w_z(a,b):
    return a&b

def tenTotwo(x):
    ret =""
    while x >0:
        if x%2==1:
            ret += '1'
        else:
            ret += '0'
        x //= 2

    return ret[::-1]
N,M,K = [int(i) for i in input().split(' ')]
a = input()
b = input()
a_=0
b_=0
for i in range(len(a)):
    a_ += int(a[i])*(2**(len(a)-i-1))
for i in range(len(b)):
    b_ += int(b[i])*(2**(len(b)-i-1))
#print(type(a))
for i in range(K):
    z = w_z(a_,b_)
    a_ += z
    b_ += z
    #print(z)

print(tenTotwo(a_))
print(tenTotwo(b_))

Submission status: Time Limit Exceeded

Solution code:
N,M,k = map(int,input().split())
s = input()
t = input()

#print (s,t)

def two_bit_sum(a,b,c):
    if int(a) + int(b) + int(c) == 3:
        return ('1','1')
    elif int(a) + int(b) + int(c) == 2:
        return ('0','1')
    elif int(a) + int(b) + int(c) == 1:
        return ('1','0')
    elif int(a) + int(b) + int(c) == 0:
        return ('0','0')

def bitwiseAnd(s,t):
    m = len(s)
    n = len(t)
    min_mn = min(m,n)
    strin = ''
    for i in range(min_mn):
        if (s[-i - 1] == '1' and  t[-i - 1] == '1'):
            strin = '1' + strin
        else:
            strin = '0' + strin
    return strin

def sum(s,t):
    c = '0'
    u = '0'
    ans = ''
    n = len(s)
    m = len(t)
    length = max(n,m)
    for i in range(length):
        if i < min(n,m):
        #    print (i, 'A')
            u,c = two_bit_sum(s[- i - 1],t[- i - 1],c)
            ans = u + ans
        elif n == max(n,m):
        #    print (i, 'B')
            u,c = two_bit_sum(s[- i - 1],'0',c)
            ans = u + ans
        elif m == max(n,m):
        #    print (i, 'C')
            u,c = two_bit_sum(t[- i - 1],'0',c)
            ans = u + ans

    if c == '1':
        ans = '1' + ans
    return (ans)

for i in range(k):
    z = bitwiseAnd(s,t)
    #print (s,t,z)
    s = sum(s,z)
    t = sum(t,z)

print (s)
print (t)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

n,m,k=map(int, input().split())
s=int(input(),2)
t=int(input(),2)

for i in range(k):
  z = s & t
  s += z
  t += z

out="{}\n{}".format(bin(s),bin(t))
out=out.replace("0b","")
print(out)

Submission status: Time Limit Exceeded

Solution code:
line1 = input().split()
N = int(line1[0])
M = int(line1[1])
K = int(line1[2])
S = int(input(), 2)
T = int(input(), 2)
 
for i in range(K):
    Z = S & T
    S += Z
    T += Z
 
print(format(S, 'b'))
print(format(T, 'b'))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
 
n, m, k = map(int, input().split(" "))
x = int(input(), 2)
y = int(input(), 2)

b2i = (lambda n: reduce((lambda x, y: (x << 1) | y), map(int, list(n))))

for _ in range(k):
	z = x & y

	x, y = x + z, y + z

print(bin(x)[2:])
print(bin(y)[2:])

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int,input().split())
S = int(input(),2)
T = int(input(), 2)

for i in range(K):
    Z = S&T
    S+=Z
    T+=Z
print(bin(S)[2:])
print(bin(T)[2:])

Submission status: Time Limit Exceeded

Solution code:
l = map(int, raw_input().split())
n = l[0]
m = l[1]
k = l[2]
s = int(raw_input(), 2)
t = int(raw_input(), 2)

for i in xrange(0, k):
	z = s & t
	s += z
	t += z

print format(s, "b")
print format(t, "b")

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
S = int(input(),2)
T = int(input(),2)
p = N if N > M else M
for i in range(K):
    Z = S & T
    if Z == 0:
        break
    S += Z
    T += Z

print(format(S,'b'))
print(format(T,'b'))

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
S = int(input(),2)
T = int(input(),2)
p = N if N > M else M
for i in range(K):
    Z = S & T
    if Z == 0:
        break
    S += Z
    T += Z
    #print(format(Z,'b').zfill(p+i))
    #print(format(S,'b').zfill(p+i))
    #print(format(T,'b').zfill(p+i))
    #print()

print(format(S,'b'))
print(format(T,'b'))

Submission status: Time Limit Exceeded

Solution code:
n1,m1,k1 = input().split()
n,m,k=int(n1),int(m1),int(k1)
s1 = input()
t1 = input()
s = int(s1,2)
t = int(t1,2)
for i in range(k):
    u = s & t
    s = s + u
    t = t + u
print(format(s,"b"))
print(format(t,"b"))

Submission status: Time Limit Exceeded

Solution code:
N,M,K=(int(i) for i in input().split())
X=int(input(),2)
Y=int(input(),2)

for i in range(K):
	Z=X&Y
	X+=Z
	Y+=Z

print(format(X,'b'))
print(format(Y,'b'))

Submission status: Time Limit Exceeded

Solution code:
N,M,K=(int(i) for i in input().split())
X=int(input(),2)
Y=int(input(),2)

for i in range(K):
	Z=X&Y
	X+=Z
	Y+=Z

print(format(X,'b'))
print(format(Y,'b'))

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
S = int(input(),2)
T = int(input(),2)
for _ in [None]*K:
    Z = S & T
    S += Z
    T += Z
print(format(S,'b'))
print(format(T,'b'))

Submission status: Time Limit Exceeded

Solution code:
def dec_to_bin(x):
    return int(bin(x)[2:])
def bit_wise_and(a,b):
    return (a&b)

n,m,k=map(int,input().strip().split())
s=input()
t=input()
s1=int(s,2)
t1=int(t,2)
for _ in range(k):
    bit=bit_wise_and(s1,t1)
    s1=s1+bit 
    t1=t1+bit
x=dec_to_bin(s1)
y=dec_to_bin(t1)
print(x)
print(y)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int,input().split())	
s = int(input(), 2)
t = int(input(), 2)

for i in range(k):
  u = s & t
  s = s + u
  t = t + u

print(format(s,'b'))
print(format(t,'b'))

Submission status: Time Limit Exceeded

Solution code:
l = map(int, raw_input().split())
n = l[0]
m = l[1]
k = l[2]
s = int(raw_input(), 2)
t = int(raw_input(), 2)

for i in range(0, k):
	z = s & t
	s += z
	t += z

print format(s, "b")
print format(t, "b")

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
s = int(input(), 2)
t = int(input(), 2)
for i in range(k):
    z = s & t
    s += z
    t += z
print('{0:b}'.format(s))
print('{0:b}'.format(t))

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M, K, S, T = sys.stdin.read().split()
k = int(K)
s = int(S, 2)
t = int(T, 2)

for i in range(k):
    a = s & t
    s = s + a
    t = t + a
print(format(s, 'b'))
print(format(t, 'b'))

Submission status: Time Limit Exceeded

Solution code:
line1 = input().split()
N = int(line1[0])
M = int(line1[1])
K = int(line1[2])
S = int(input(), 2)
T = int(input(), 2)

for i in range(K):
    Z = S & T
    S += Z
    T += Z

print(format(S, 'b'))
print(format(T, 'b'))

Submission status: Accepted

Solution code:
def Z():
 m=-1;I=input;N,M,K=map(int,I().split());W=2000000;s=[0]*W;t=[0]*W;L=max(N,M)-1;R=range;p=lambda x:print(*reversed(x),sep='')
 for i,c in zip(R(N-1,m,m),I()):s[i]=int(c)
 for i,c in zip(R(M-1,m,m),I()):t[i]=int(c)
 for i in R(L,m,m):
  j=i;z=K
  while s[j]and t[j]and z:
   s[j]=t[j]=0;s[j+1]+=1;t[j+1]+=1;j+=1;z-=1;x=y=j
   while s[x]==2:s[x]=0;s[x+1]+=1;x+=1
   while t[y]==2:t[y]=0;t[y+1]+=1;y+=1
   j=max(x,y)
  L=max(L,j)
 s=s[:L+1];t=t[:L+1]
 while s[m]==0:s.pop()
 while t[m]==0:t.pop()
 p(s);p(t)
Z()

Submission status: Accepted

Solution code:
def main():
    N, M, K = map(int, input().split())

    MAX_N = 2000000

    s = [0] * MAX_N
    t = [0] * MAX_N
    for i, c in zip(range(N - 1, -1, -1), input()):
        s[i] = int(c)
    for i, c in zip(range(M - 1, -1, -1), input()):
        t[i] = int(c)

    len_max = max(N, M) - 1

    for i in range(len_max, -1, -1):
        j = i
        z = K
        while s[j] and t[j] and z:
            s[j] = t[j] = 0
            s[j + 1] += 1
            t[j + 1] += 1
            j += 1
            z -= 1
            js = jt = j

            while s[js] == 2:
                s[js] = 0
                s[js + 1] += 1
                js += 1

            while t[jt] == 2:
                t[jt] = 0
                t[jt + 1] += 1
                jt += 1

            j = max(js, jt)
            
        len_max = max(len_max, j)

    s = s[:len_max + 1]
    t = t[:len_max + 1]

    while not s[-1]:
        s.pop()
    while not t[-1]:
        t.pop()

    print(*reversed(s), sep='')
    print(*reversed(t), sep='')
    
main()

Submission status: Accepted

Solution code:
def main():
    N, M, K = map(int, input().split())

    MAX_N = 2000000

    s = [0] * MAX_N
    t = [0] * MAX_N
    for i, c in zip(range(N - 1, -1, -1), input()):
        s[i] = int(c)
    for i, c in zip(range(M - 1, -1, -1), input()):
        t[i] = int(c)

    len_max = max(N, M) - 1
    st = []
    for i in range(len_max, -1, -1):
        m = []
        if s[i] and t[i]:
            s[i] = t[i] = 0
            xs = xt = 1
            z = K - 1
            j = i + 1

            while xs or xt:
                if not s[j] and not t[j]:
                    if xs and not xt:
                        s[j] = 1
                        st.append(j)
                        len_max = max(len_max, j)
                        break
                    elif not xs and xt:
                        t[j] = 1
                        st.append(j)
                        len_max = max(len_max, j)
                        break

                if not st or st[-1] - j > z:
                    s[j + z] = t[j + z] = 1
                    len_max = max(len_max, j + z)
                    break

                p = st.pop()
                z -= p - j
                j = p

                if s[j] == xs and t[j] == xt:
                    s[j] = t[j] = 0
                    j += 1
                    continue

                if xs and xt:
                    xs = s[j]
                    xt = t[j]
                    s[j] ^= 1
                    t[j] ^= 1
                    m.append(j)
                    j += 1
                    continue

                if s[j] != xs and t[j] != xt:
                    if not z:
                        s[j] = t[j] = 1
                        break
                    else:
                        s[j] = t[j] = 0
                        j += 1
                        z -= 1
                        xs = xt = 1
                        continue

            st += reversed(m)

        elif s[i] or t[i]:
            st.append(i)

    s = s[:len_max + 1]
    t = t[:len_max + 1]

    while not s[-1]:
        s.pop()
    while not t[-1]:
        t.pop()

    print(*reversed(s), sep='')
    print(*reversed(t), sep='')


main()

Submission status: Runtime Error

Solution code:
# Meet


n, m, k = input().split()
n = int(n)
m = int(m)
k = int(k)

def bitwise_and(a, b):
	temp = [0 for i in range(32)]
	for i in range(32):
		if a[i]==0 or b[i]==0:
			temp[i] = 0
		else:
			temp[i] = 1

	return temp

def bitwise_sum(a, b):
	temp = [0 for i in range(32)]
	carry = 0
	for i in range(31, -1, -1):
		if a[i]+b[i]+carry == 2:
			temp[i] = 0
			carry = 1
		elif a[i]+b[i]+carry == 3:
			temp[i] = 1
			carry = 1
		elif a[i]+b[i]+carry == 1:
			temp[i] = 1
			carry = 0
		elif a[i]+b[i]+carry == 0:
			temp[i] = 0
			carry = 0

	return temp

s = list(input())
t = list(input())

a = [0 for i in range(32)]
b = [0 for i in range(32)]

for i in range(n):
	a[31-i] = int(s[n-1-i])

for i in range(m):
	b[31-i] = int(t[m-1-i])

# print(a)
# print(b)

for i in range(k):
	temp = bitwise_and(a, b)
	a = bitwise_sum(a, temp)
	b = bitwise_sum(b, temp)

	# print(a)
	# print(b)

s_a = ''
s_b = ''

flag = 0
for i in a:
	if i==1:
		flag = 1
	if flag:
		s_a+=str(i)

flag = 0
for i in b:
	if i==1:
		flag = 1
	if flag:
		s_b+=str(i)

# print(a)
# print(b)
print(s_a)
print(s_b)