Problem:


Score : 700 points

Problem Statement

Aoki is playing with a sequence of numbers a_{1}, a_{2}, ..., a_{N}. Every second, he performs the following operation :

Choose a positive integer k. For each element of the sequence v, Aoki may choose to replace v with its remainder when divided by k, or do nothing with v. The cost of this operation is 2^{k} (regardless of how many elements he changes).

Aoki wants to turn the sequence into b_{1}, b_{2}, ..., b_{N} (the order of the elements is important). Determine if it is possible for Aoki to perform this task and if yes, find the minimum cost required.

Constraints

1 \leq N \leq 50

0 \leq a_{i}, b_{i} \leq 50

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N
a_{1} a_{2} ... a_{N}
b_{1} b_{2} ... b_{N}

Output

Print the minimum cost required to turn the original sequence into b_{1}, b_{2}, ..., b_{N}. If the task is impossible, output -1 instead.

Sample Input 1

3
19 10 14
0 3 4

Sample Output 1

160

Here's a possible sequence of operations :

Choose k = 7. Replace 19 with 5, 10 with 3 and do nothing to 14. The sequence is now 5, 3, 14.

Choose k = 5. Replace 5 with 0, do nothing to 3 and replace 14 with 4. The sequence is now 0, 3, 4.

The total cost is 2^{7} + 2^{5} = 160.

Sample Input 2

3
19 15 14
0 0 0

Sample Output 2

2

Aoki can just choose k = 1 and turn everything into 0. The cost is 2^{1} = 2.

Sample Input 3

2
8 13
5 13

Sample Output 3

-1

The task is impossible because we can never turn 8 into 5 using the given operation.

Sample Input 4

4
2 0 1 8
2 0 1 8

Sample Output 4

0

Aoki doesn't need to do anything here. The cost is 0.

Sample Input 5

1
50
13

Sample Output 5

137438953472

Beware of overflow issues.



Sample input:
3
19 10 14
0 3 4


Sample output:
160

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    N = len(S)
    if N<26:
        d = defaultdict(bool)
        for s in S:
            d[s] = True
        for a in alphabet:
            if not d[a]:
                ans = S + a
                print(ans)
                return
    keep = []
    for i in range(N-1)[::-1]:
        keep.append(S[i+1])
        if S[i]<S[i+1]:
            break
    #print(keep)
    n = len(keep)
    c = "zz"
    for s in keep:
        if s>S[(N-n-1)]:
            c = min(c,s)
    if c=="zz":
        print(-1)
        return
    ans = S[:(N-n-1)] + c
    print(ans)
    return

def examB():
    N = I()
    if N==3:
        print("2 5 63")
        return
    if N%2==0:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    else:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-2)
        cur += 6; now += 2
    cur = 21
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-6)
        cur += 12; now += 2
    for i in range(N-now):
        cur = (i+1)*6
        ans.append(cur)
    print(" ".join(map(str,ans)))
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    C = max(A)
    ans = 0
    for _ in range(10**4):
        cur = 0
        for a, b in zip(A, B):
            if a==b:
                continue
            flag = False
            for i in range(1, C + 1):
                if a%i==b or a%i>b*2:
                    cur = max(cur, i)
                    flag = True
                    break
            if not flag:
                print(-1)
                return
        if cur==0:
            break
        #print(A,cur)
        #input()
        for i in range(N):
            if A[i]%cur==B[i] or A[i]%cur>B[i]*2:
                A[i] %= cur
        ans += pow(2,cur)
    for i in range(N):
        if A[i]!=B[i]:
            while(True):
                pass
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    N = len(S)
    if N<26:
        d = defaultdict(bool)
        for s in S:
            d[s] = True
        for a in alphabet:
            if not d[a]:
                ans = S + a
                print(ans)
                return
    keep = []
    for i in range(N-1)[::-1]:
        keep.append(S[i+1])
        if S[i]<S[i+1]:
            break
    #print(keep)
    n = len(keep)
    c = "zz"
    for s in keep:
        if s>S[(N-n-1)]:
            c = min(c,s)
    if c=="zz":
        print(-1)
        return
    ans = S[:(N-n-1)] + c
    print(ans)
    return

def examB():
    N = I()
    if N==3:
        print("2 5 63")
        return
    if N%2==0:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    else:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-2)
        cur += 6; now += 2
    cur = 21
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-6)
        cur += 12; now += 2
    for i in range(N-now):
        cur = (i+1)*6
        ans.append(cur)
    print(" ".join(map(str,ans)))
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    C = max(A)
    ans = 0
    for _ in range(10**4):
        cur = 0
        for a, b in zip(A, B):
            if a==b:
                continue
            flag = False
            for i in range(1, C + 1):
                if a%i==b or a%i>b*2:
                    cur = max(cur, i)
                    flag = True
                    break
            if not flag:
                print(-1)
                return
        if cur==0:
            break
        #print(A,cur)
        #input()
        for i in range(N):
            if A[i]%cur==B[i] or A[i]%cur>B[i]*2:
                A[i] %= cur
        ans += pow(2,cur)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    N = len(S)
    if N<26:
        d = defaultdict(bool)
        for s in S:
            d[s] = True
        for a in alphabet:
            if not d[a]:
                ans = S + a
                print(ans)
                return
    keep = []
    for i in range(N-1)[::-1]:
        keep.append(S[i+1])
        if S[i]<S[i+1]:
            break
    #print(keep)
    n = len(keep)
    c = "zz"
    for s in keep:
        if s>S[(N-n-1)]:
            c = min(c,s)
    if c=="zz":
        print(-1)
        return
    ans = S[:(N-n-1)] + c
    print(ans)
    return

def examB():
    N = I()
    if N==3:
        print("2 5 63")
        return
    if N%2==0:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    else:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-2)
        cur += 6; now += 2
    cur = 21
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-6)
        cur += 12; now += 2
    for i in range(N-now):
        cur = (i+1)*6
        ans.append(cur)
    print(" ".join(map(str,ans)))
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    C = max(A)
    ans = 0
    for _ in range(10**4):
        cur = 0
        for a, b in zip(A, B):
            if a==b:
                continue
            flag = False
            for i in range(1, C + 1):
                if a%i==b or a%i>b*2:
                    cur = max(cur, i)
                    flag = True
                    break
            if not flag:
                print(-1)
                return
        if cur==0:
            break
        #print(A,cur)
        #input()
        for i in range(N):
            if A[i]%cur==B[i] or A[i]%cur>=B[i]*2:
                A[i] %= cur
        ans += pow(2,cur)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    N = len(S)
    if N<26:
        d = defaultdict(bool)
        for s in S:
            d[s] = True
        for a in alphabet:
            if not d[a]:
                ans = S + a
                print(ans)
                return
    keep = []
    for i in range(N-1)[::-1]:
        keep.append(S[i+1])
        if S[i]<S[i+1]:
            break
    #print(keep)
    n = len(keep)
    c = "zz"
    for s in keep:
        if s>S[(N-n-1)]:
            c = min(c,s)
    if c=="zz":
        print(-1)
        return
    ans = S[:(N-n-1)] + c
    print(ans)
    return

def examB():
    N = I()
    if N==3:
        print("2 5 63")
        return
    if N%2==0:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    else:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-2)
        cur += 6; now += 2
    cur = 21
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-6)
        cur += 12; now += 2
    for i in range(N-now):
        cur = (i+1)*6
        ans.append(cur)
    print(" ".join(map(str,ans)))
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    C = max(A)
    ans = 0
    for _ in range(3*10**4):
        cur = 0
        for a, b in zip(A, B):
            if a==b:
                continue
            flag = False
            for i in range(1, C + 1):
                if a%i==b or a%i>=b*2:
                    cur = max(cur, i)
                    flag = True
                    break
            if not flag:
                print(-1)
                return
        if cur==0:
            break
        #print(A,cur)
        #input()
        for i in range(N):
            if A[i]%cur==B[i] or A[i]%cur>=B[i]*2:
                A[i] %= cur
        ans += pow(2,cur)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    N = len(S)
    if N<26:
        d = defaultdict(bool)
        for s in S:
            d[s] = True
        for a in alphabet:
            if not d[a]:
                ans = S + a
                print(ans)
                return
    keep = []
    for i in range(N-1)[::-1]:
        keep.append(S[i+1])
        if S[i]<S[i+1]:
            break
    #print(keep)
    n = len(keep)
    c = "zz"
    for s in keep:
        if s>S[(N-n-1)]:
            c = min(c,s)
    if c=="zz":
        print(-1)
        return
    ans = S[:(N-n-1)] + c
    print(ans)
    return

def examB():
    N = I()
    if N==3:
        print("2 5 63")
        return
    if N%2==0:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    else:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-2)
        cur += 6; now += 2
    cur = 21
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-6)
        cur += 12; now += 2
    for i in range(N-now):
        cur = (i+1)*6
        ans.append(cur)
    print(" ".join(map(str,ans)))
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    C = max(A)
    ans = 0
    for _ in range(10**4):
        cur = 0
        for a, b in zip(A, B):
            if a==b:
                continue
            flag = False
            for i in range(1, C + 1):
                if a%i==b or a%i>=b*2:
                    cur = max(cur, i)
                    flag = True
                    break
            if not flag:
                print(-1)
                return
        if cur==0:
            break
        #print(A,cur)
        #input()
        for i in range(N):
            if A[i]%cur==B[i] or A[i]%cur>=B[i]*2:
                A[i] %= cur
        ans += pow(2,cur)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    N = len(S)
    if N<26:
        d = defaultdict(bool)
        for s in S:
            d[s] = True
        for a in alphabet:
            if not d[a]:
                ans = S + a
                print(ans)
                return
    keep = []
    for i in range(N-1)[::-1]:
        keep.append(S[i+1])
        if S[i]<S[i+1]:
            break
    #print(keep)
    n = len(keep)
    c = "zz"
    for s in keep:
        if s>S[(N-n-1)]:
            c = min(c,s)
    if c=="zz":
        print(-1)
        return
    ans = S[:(N-n-1)] + c
    print(ans)
    return

def examB():
    N = I()
    if N==3:
        print("2 5 63")
        return
    if N%2==0:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    else:
        ans = [2, 4, 3, 9]
        now = 4
        cur = 10
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-2)
        cur += 6; now += 2
    cur = 21
    while(cur<=30000):
        if N-1<=now:
            break
        ans.append(cur)
        ans.append(cur-6)
        cur += 12; now += 2
    for i in range(N-now):
        cur = (i+1)*6
        ans.append(cur)
    print(" ".join(map(str,ans)))
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    C = max(A)
    ans = 0
    while(True):
        cur = 0
        for a, b in zip(A, B):
            if a==b:
                continue
            flag = False
            for i in range(1, C + 1):
                if a%i==b or a%i>=b*2:
                    cur = max(cur, i)
                    flag = True
                    break
            if not flag:
                print(-1)
                return
        if cur==0:
            break
        #print(A,cur)
        #input()
        for i in range(N):
            if A[i]%cur==B[i] or A[i]%cur>=B[i]*2:
                A[i] %= cur
        ans += pow(2,cur)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
e = dd(list)
for x in range(51):
  for k in range(1, 51):
    e[x].append((x % k, 1 << k))

import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]

dij = dijkstra(50, e)
res = 0
for i in range(N):
  t = dij.path(a[i], b[i])
  if t == float("inf"):
    print(-1)
    exit(0)
  res |= t

tt = []
for i in range(51):
  if res & (1 << i): tt.append(i)
for t in range(1, len(tt) + 1):
  for c in combi(tt, t):
    #print(c)
    for i in range(N):
      for j in range(1 << t):
        x = a[i] + 0
        for k in range(t - 1, -1, -1):
          if j & (1 << k): x %= c[k]
        #print(a[i], x)
        if x == b[i]: break
      else: break

    else:
      y = 0
      for i in range(t - 1, -1, -1): y += 1 << c[i]
      res = min(res, y)
print(res)

Submission status: Wrong Answer

Solution code:
def rem(x,r):
  if (x,r) == (1,0):
    return [[1]]
  if x <= 2*r:
    return -1
  ret = []
  for i in range(1,x+1):
    if x%i == r:
      ret.append([i])
    else:
      s = rem(x%i,r)
      if s == -1:
        continue
      else:
        for j in s:
          if j == -1:
            continue
          elif j[-1] < i:
            ret.append([i]+j)
          else:
            ret.append([i]+j)
  return ret
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
for xx,yy in zip(x,y):
  if xx != yy and rem(xx,yy) == -1:
    print(-1)
    exit()
ls = [rem(xx,yy) if xx != yy else 0 for xx,yy in zip(x,y)]
flg = [0]*n
def findmx(lsi,ansst,mx):
  ret = 100
  if lsi == 0:
    return 0
  for lsls in lsi:
    for j in lsls:
      if j > mx:
        return min(j,ret)
      elif j in ansst:
        continue
      else:
        ret = min(j,ret)
        break
    else:
      return 0
  else:
    return 0
mxls = [ls[i][0][0] if type(ls[i]) == list else 0 for i in range(n)]
mx = max(mxls)
ansst = set((mx,))
mxcand = mx
while mxcand:
  for i in range(n):
    t = findmx(ls[i],ansst,mx)
    mxls[i] = t
    if t == 0:
      flg[i] = 1
  mxcand = max(mxls)
  ansst.add(mxcand)
  if flg.count(1) == n:
    break
ans = 0
for b in ansst:
  if b:
    ans += 2**b
print(ans)

Submission status: Wrong Answer

Solution code:
def rem(x,r):
  if (x,r) == (1,0):
    return [[1]]
  if x <= 2*r:
    return -1
  ret = []
  for i in range(1,x):
    if x%i == r:
      ret.append([i])
    else:
      s = rem(x%i,r)
      if s == -1:
        continue
      else:
        for j in s:
          if j == -1:
            continue
          elif j[-1] < i:
            ret.append([i]+j)
          else:
            ret.append([i]+j)
  return ret
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
for xx,yy in zip(x,y):
  if xx != yy and rem(xx,yy) == -1:
    print(-1)
    exit()
ls = [rem(xx,yy) if xx != yy else 0 for xx,yy in zip(x,y)]
mxls = [ls[i][0][0] if type(ls[i]) == list else 0 for i in range(n)]
mx = max(mxls)
ansst = set()
ansst.add(mx)
flg = [0]*n
while mx:
  for i in range(n):
    if x[i]%mx == y[i]:
      flg[i] = 1
      mxls[i] = 0
      continue
    r = rem(x[i]%mx,y[i])
    if r != -1 and r[0][0] <= mxls[i]:
      mxls[i] = r[0][0]
      x[i] %= mx
  mx = max(mxls)
  ansst.add(mx)
  if flg.count(1) == n:
    break
ans = 0
for b in ansst:
  if b:
    ans += 2**b
print(ans)

Submission status: Wrong Answer

Solution code:
def rem(x,r):
  if (x,r) == (1,0):
    return [[1]]
  if x <= 2*r:
    return -1
  ret = []
  for i in range(1,x):
    if x%i == r:
      ret.append([i])
    else:
      s = rem(x%i,r)
      if s == -1:
        continue
      else:
        for j in s:
          if j == -1:
            continue
          elif j[-1] < i:
            ret.append([i]+j)
          else:
            ret.append([i]+j)
  return ret
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
for xx,yy in zip(x,y):
  if xx != yy and rem(xx,yy) == -1:
    print(-1)
    exit()
ls = [rem(xx,yy) if xx != yy else 0 for xx,yy in zip(x,y)]
mxls = [ls[i][0][0] if type(ls[i]) == list else 0 for i in range(n)]
mx = max(mxls)
ansst = set()
ansst.add(mx)
flg = [0]*n
while mx:
  for i in range(n):
    if x[i]%mx == y[i]:
      flg[i] = 1
      mxls[i] = 0
      continue
    r = rem(x[i]%mx,y[i])
    if r != -1 and r[0][0] <= mxls[i]:
      mxls[i] = r[0][0]
      x[i] %= mx
  mx = max(mxls)
  ansst.add(mx)
  if flg.count(1) == n:
    break
ans = -1
for b in ansst:
  ans += 2**b
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(bit_state, num, mod):
    for div in range(1, num + 1):
        if num % div == mod:
            cand[i].append(bit_state | (1 << div))
        if num % div > mod:
            solve(bit_state | (1 << div), num % div, mod)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cand = [[] for i in range(n)]
for i in range(n):
    solve(0, a[i], b[i])

ans = 0
while True:
    max_ = 0
    for j in range(n):
        min_ = 10 ** 5
        for num in cand[j]:
            min_ = min(min_, num.bit_length() - 1)
        max_ = max(max_, min_)

    if max_ == 0:
        print(ans)
        break
    if max_ == 10 ** 5:
        print(-1)
        break
    ans += 2 ** max_
    
    tmp = [[] for i in range(n)]
    for j in range(n):
        for num in cand[j]:
            if num & (1 << max_):
                tmp[j].append(num - (1 << max_))
            else:
                tmp[j].append(num)
    cand = tmp[0:]

Submission status: Wrong Answer

Solution code:
def solve(bit_state, num, mod):
    for div in range(1, num + 1):
        if num % div == mod:
            cand[i].append(bit_state | (1 << div))
        if num % div > mod:
            solve(bit_state | (1 << div), num % div, mod)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cand = [[] for i in range(n)]
for i in range(n):
    solve(0, a[i], b[i])

ans = 0
for i in range(50):
    max_ = 0
    for j in range(n):
        min_ = 10 ** 5
        for num in cand[j]:
            min_ = min(min_, num.bit_length() - 1)
        max_ = max(max_, min_)

    if max_ == 0:
        print(ans)
        break
    if max_ == 10 ** 5:
        print(-1)
        break
    ans += 2 ** max_
    
    tmp = [[] for i in range(n)]
    for j in range(n):
        for num in cand[j]:
            if num & (1 << max_):
                tmp[j].append(num - (1 << max_))
            else:
                tmp[j].append(num)
    cand = tmp[0:]

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


def main():
    border = 12

    graph = [[] for _ in range(51)]
    for start in range(51):
        for cost in range(1,51):
            if start%cost == 0:
                graph[0].append((cost, start))
    for end in range(1, 51):
        for cost in range(end+1, 51):
            start = end + cost
            while start <= 50:
                graph[end].append((cost, start))
                start += cost

    mustconsider = [True]*N
    basebit = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if b >= border:
            mustconsider[i] = False
            if a >= 2*b+1:
                basebit |= 1<<(a-b)
            elif a != b:
                return -1
    
    # 立ってるbitのcostを使う
    ans = 10**60
    for bit in range(1<<(border-1)):
        bit <<= 1
        ok = True
        using = [0 for _ in range(N)]
        lowest = []
        for i, (a, b) in enumerate(zip(A, B)):
            if mustconsider[i]:
                canreach = False
                q = [b]
                checked = [False]*51
                checked[b] = True
                while q:
                    qq = []
                    for p in q:
                        if p == a:
                            canreach = True
                            break
                        if 2*p+1 <= a:
                            n = 1
                            while (a-p)//n > p:
                                if (a-p)%n == 0:
                                    using[i] |= 1<<((a-p)//n)
                                n += 1
                        for cost, np in graph[p]:
                            if (1<<cost)&bit and not checked[np]:
                                checked[np] = True
                                qq.append(np)
                    if canreach: break
                    q = qq
                if not canreach:
                    if using[i] == 0:
                        ok = False
                        break
                    l = using[i] & -using[i]
                    lowest.append((l, i))
        if ok:
            now = bit|basebit
            lowest.sort(reverse=True)
            for l, i in lowest:
                if using[i]&now: continue
                now |= l
            ans = min(ans, now)

    if ans == 10**60:
        return -1
    return ans



if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


def main():
    border = 12

    graph = [[] for _ in range(51)]
    for start in range(51):
        for cost in range(1,51):
            if start%cost == 0:
                graph[0].append((cost, start))
    for end in range(1, 51):
        for cost in range(end+1, 51):
            start = end + cost
            while start <= 50:
                graph[end].append((cost, start))
                start += cost

    mustconsider = [True]*N
    basebit = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if b >= border:
            mustconsider[i] = False
            if a >= 2*b+1:
                basebit |= 1<<(a-b)
            elif a != b:
                return -1
    
    # 立ってるbitのcostを使う
    ans = 10**60
    for bit in range(1<<(border-1)):
        bit <<= 1
        ok = True
        using = [0 for _ in range(N)]
        lowest = []
        for i, (a, b) in enumerate(zip(A, B)):
            if mustconsider[i]:
                canreach = False
                q = [b]
                checked = [False]*51
                checked[b] = True
                while q:
                    qq = []
                    for p in q:
                        if p == a:
                            canreach = True
                            break
                        if 2*p+1 <= a:
                            using[i] |= 1<<(a-p)
                        for cost, np in graph[p]:
                            if (1<<cost)&bit and not checked[np]:
                                checked[np] = True
                                qq.append(np)
                    if canreach: break
                    q = qq
                if not canreach:
                    if using[i] == 0:
                        ok = False
                        break
                    l = using[i] & -using[i]
                    lowest.append((l, i))
        if ok:
            now = bit|basebit
            lowest.sort(reverse=True)
            for l, i in lowest:
                if using[i]&now: continue
                now |= l
            ans = min(ans, now)

    if ans == 10**60:
        return -1
    return ans



if __name__ == "__main__":
    print(main())