Problem:


Score : 700 points

Problem Statement

Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2, or 3.
Let x_{i,j} defined as follows:

x_{1,j} := a_j \quad (1 \leq j \leq N)

x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)

Find x_{N,1}.

Constraints

2 \leq N \leq 10^6

a_i = 1,2,3 (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
a_1a_2\ldotsa_N

Output

Print x_{N,1}.

Sample Input 1

4
1231

Sample Output 1

1

x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1.

x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2.

x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1.

Finally, x_{4,1} = |0-1| = 1, so the answer is 1.

Sample Input 2

10
2311312312

Sample Output 2

0



Sample input:
4
1231


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict


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

# Do one step to reduce to make the list only 0, 1 or 2
# All subsequent steps will only contain 0, 1, or 2
A = [abs(x - y) for x, y in zip(A, A[1:])]
N -= 1


def solve(A):
    N = len(A)

    fact = [1]
    for i in range(1, N + 1):
        fact.append(fact[-1] * i)

    def nCr(n, r):
        return fact[n] // (fact[n - r] * fact[r])

    if False:
        import numpy as np

        # Absolute difference and mod 4 sum is almost the same:
        #         abs(x - y)   (x + y) % 4
        # 0, 0    0            0
        # 0, 2    2            2
        # 2, 2    0            0
        #
        # 0, 1    1            1
        # 1, 2    1            3
        #
        # 1, 1    0            2
        #
        # When the list only contains 0 and 2, can just use mod 4 sum exactly
        # When the mod 4 sum answer is odd, know the real answer is 1?

        # nextVec[i] = (vec[i] + vec[i + 1]) % 4
        mat = np.zeros((N, N), dtype=np.int64)
        for i in range(N - 1):
            mat[i][i] = 1
            mat[i][i + 1] = 1

        vec = np.array(A, dtype=np.int64)

        for t in range(N):
            M = np.linalg.matrix_power(mat, t)
            print("t", t)
            print("M^t", M)
            print("v_t", np.matmul(M, vec)[: N - t] % 4)
            print()
        # By inspection, it turns out the M^(N - 1) * v is just the corresponding row of the pascal triangle
        for i in range(N):
            assert np.linalg.matrix_power(mat, N - 1)[0][i] == nCr(N - 1, i)

    total = 0
    for i in range(N):
        total = (total + nCr(N - 1, i) * A[i]) % 4

    if Counter(A)[1] == 0:
        # If there are no ones, total is the exact answer (either 0 or 2)
        return total
    else:
        # Answer has to be 0 or 1
        if total % 2:
            return 1
        else:
            return 0
    return total


print(solve(A))

if False:
    from itertools import product

    for N in range(2, 7):
        print("")
        print("N", N)

        groups = defaultdict(list)
        for A in product([0, 1, 2], repeat=N):
            temp = list(A)
            for i in range(N - 1):
                temp = [abs(x - y) for x, y in zip(temp, temp[1:])]
            assert len(temp) == 1
            groups[temp[0]].append(A)

        for k, v in groups.items():
            print("ans", k)
            for A in v:
                ans = solve(A)
                assert k == ans
                print("\t", A, "\t", ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = input()
a1 = ''
for i in range(N-1):
    a1 += str(abs(int(a[i]) - int(a[i+1])))

if N == 2:
    print(a1)
    quit()

if a1[0] == '2':
    if int(a1[1:]) == 0:
        print(2)
        quit()

b = ''
c = ''
for _a1 in a1:
    if _a1 == '2':
        b += '0'
        c += '1'
    else:
        b += _a1
        c += _a1

b = int(b, 2)
c = int(c, 2)
for i in range(N-2):
    b = (b<<1 ^ b) >> 1
    c = (c<<1 ^ c) >> 1
    c |= b


b = int(bin(b)[-1])
c = int(bin(c)[-1])
if c and not b:
    print(2)
else:
    print(b)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input()))
k=0
for j in range(n):
  for i in range(n-j-1):
    #print(i,j)
    #print(i+k)
    a.append(abs(a[i+k]-a[i+1+k]))
  #print(a)
  k+=n-j
print(a[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
readline = sys.stdin.buffer.readline

n = int(readline())
s = readline().rstrip().decode('utf-8')
l = len(s)
zerone = [] #or
two = [] #and
#最初の1回は手動
for i in range(1,n):
    res = abs(int(s[i-1])-int(s[i]))
    if res == 0:
        zerone.append(0)
        two.append(0)
    elif res == 1:
        zerone.append(1)
        two.append(0)
    else:
        zerone.append(1)
        two.append(1)
"""print(two)
print(zerone)"""
for i in range(n-2): #1回目は上の操作なので、あとn-1回
    zerone = np.logical_xor(zerone[1:],zerone[:-1])
    two = np.logical_xor(two[1:],two[:-1])
    #print(two)
    #print(zerone)
    res = np.logical_or(zerone,two)
    two = np.logical_and(zerone,two)
    zerone = res

if zerone[0]&two[0]:
    print(2)
elif zerone[0]|two[0]:
    print(1)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n = int(input())
  a = list(map(int,input()))
  k=0
  for j in range(n):
    for i in range(n-j-1):
      #print(i,j)
      #print(i+k)
      a.append(abs(a[i+k]-a[i+1+k]))
    #print(a)
    k+=n-j
  print(a[-1])    
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    a = np.array(list(input().rstrip()))
    a = a.astype(np.int)

    for i in range(N-1):
        temp = np.diff(a)
        a = np.abs(temp)

    print(a[0])



main()

Submission status: Time Limit Exceeded

Solution code:
def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret
N = int(input())
a_ = list(map(int, list(str(input()))))
a = []
if N == 2:
  print(abs(a_[0]-a_[1]))
else:
  for i in range(1, len(a_)):
    a.append(abs(a_[i]-a_[i-1])%2)
  ans = 0
  for i in range(len(a)):
    ans += a[i]*com(len(a)-1, i)
    ans %= 2
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def calc(l, j, N):
    tmp = []
    for index in range(len(l)-1):
        tmp.append(abs(l[index] - l[index+1]))
    if len(tmp) == 1:
        print(tmp[0])
    else:
        calc(tmp, j+1, N)

N = int(sys.stdin.readline())
a = [int(x) for x in list(sys.stdin.readline())[:N]]
calc(a, 0, N)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def func(array):
    ret = np.copy(array)
    while len(ret) != 1:
        ret = np.abs(np.delete(ret,len(ret)-1,0) - np.delete(ret,0,0))
        #print(ret)
    return ret[0]


if __name__ == '__main__':
    N = int(input())
    num = []
    s = input()
    for elem in s:
        num.append(int(elem))

    array = np.array(num)
    print(func(array))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product
from math import log2

N = int(input())
A = ''.join(str(int(c) - 1) for c in input())

memo = defaultdict(dict)
for x in product('012', repeat = 3):
  memo[3][''.join(x)] = str(abs(abs(int(x[1])-int(x[0]))-abs(int(x[2])-int(x[1]))))

def f(T):
  if T not in memo[len(T)]:
    l = (len(T)-1) // 2 + 1
    memo[len(T)][T] = f(''.join(f(T[i:i+l]) for i in range(l)))
  return memo[len(T)][T]

def g(T):
  if len(T) == 1:
    return T[0]
  elif len(T) == 2:
    return str(abs(int(T[1])-int(T[0])))
  else:
    n = 2**int(log2(len(T)-1)) + 1
    return g(''.join(f(T[i:i+n]) for i in range(len(T) - n + 1)))

print(g(A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = input()
a1 = ''
for i in range(N-1):
    a1 += str(abs(int(a[i]) - int(a[i+1])))

if N == 2:
    print(a1)
    quit()

if a1[0] == '2':
    if int(a1[1:]) == 0:
        print(2)
        quit()

b = ''
c = ''
for _a1 in a1:
    if _a1 == '2':
        b += '0'
        c += '1'
    else:
        b += _a1
        c += _a1

b = int(b, 2)
c = int(c, 2)
for i in range(N-2):
    b = (b<<1 ^ b) >> 1
    c = (c<<1 ^ c) >> 1
    c |= b


b = int(bin(b)[-1])
c = int(bin(c)[-1])
if c and not b:
    print(2)
else:
    print(b)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_str = list(input())
a = [int(s) for s in a_str]

for i  in range(N - 1):
    for j in range(N - 1 - i):
        a[j] = abs(a[j] - a[j + 1])

print(a[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())

s=np.array(list(map(int,input())))

while True:
    a=s[:len(s)-1]
    b=s[1:len(s)+1]
    s=np.abs(a-b)
    
    if len(s)==1:
        print(s[0])
        break

Submission status: Time Limit Exceeded

Solution code:
num = map(int, list(input()))
input_list = list(map(int, list(input())))


def check(check_list):
    #print(check_list)
    if len(check_list) == 2:
        print(abs(check_list[0]-check_list[1]))
        #return(abs(check_list[0]-check_list[1]))
    else:
        '''
        next_check_list = []
        count = 0
        for l in check_list:
            if count == 0:
                pass
            else:
                next_check_list.append(abs(check_list[count - 1] - check_list[count]))
            count += 1
        check(next_check_list)
        '''
        check([abs(check_list[i]-check_list[i+1]) for i in range(len(check_list)-1)])

check(input_list)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = input()
a1 = ''
for i in range(N-1):
    a1 += str(abs(int(a[i]) - int(a[i+1])))

if N == 2:
    print(a1)
    quit()

if a1[0] == '2':
    if int(a1[1:]) == 0:
        print(2)
        quit()

b = ''
c = ''
for _a1 in a1:
    if _a1 == '2':
        b += '0'
        c += '1'
    else:
        b += _a1
        c += _a1

b = int(b, 2)
c = int(c, 2)
for i in range(N-2):
    b = (b<<1 ^ b) >> 1
    c = (c<<1 ^ c) >> 1
    if b >> (N-i-2):
        b -= 1<<(N-i-2)
    if c >> (N-i-2):
        c -= 1<<(N-i-2)
    c |= b


if c and not b:
    print(2)
else:
    print(b)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np

N = int(input())
# print(N)
a = list(input())

b = np.array([int(a[i]) for i in range(N)])
# a = np.array(a)
# print(a)
# print(b)

for i in range(N - 1):
    # b = np.abs(np.diff(b, n = 1))
    b = np.abs(b[0:-1] - b[1:])
    N -= 1
    # print(b)
print(b[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, list(input())))


def diff_2(A):
    new_A = []
    for i in range(1, len(A)-1):
        new_A.append(abs(abs(A[i]-A[i+1]) - abs(A[i]-A[i-1])))
    return new_A


def diff(A):
    new_A = []
    for i in range(len(A)-1):
        new_A.append(abs(A[i]-A[i+1]))
    return new_A



for i in range((N-1)//2):
    A = diff_2(A)

while len(A) > 1:
    A = diff(A)

print(A[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
a.append(int(input()))
# a = int(input())
def F(n,a,j,t):
    if n == 0:
        return t
    else:
        b = a%(pow(10,n))
        k = b//pow(10,n-1)
        t += abs(j-k)*pow(10,n-1)
        return F(n-1,b,k,t)
for i in range(n-1):
    a.append(F(n-1,a[i],a[i]//(pow(10,n-1)),0))
    n-=1
print(a[-1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())


a=input()

def calc(ary):
    if len(ary)==2:
        return abs(int(ary[1])-int(ary[0]))
    else:
        temp=[]
        for i in range(1,len(ary)):
            temp.append(abs(int(ary[i])-int(ary[i-1])))
        return calc(temp)

if n<100:
    b= [int(s) for s in list(a)]
    print(calc(b))
    exit()

adic = {}

for a1 in range(4):
    for a2 in range(4):
        for a3 in range(4):
            for a4 in range(4):
                for a5 in range(4):
                    for a6 in range(4):
                        for a7 in range(4):
                            for a8 in range(4):
                                for a9 in range(4):
                                    for a10 in range(4):
                                        adic[str(a1)+str(a2)+str(a3)+str(a4)+str(a5)+str(a6)+str(a7)+str(a8)+str(a9)+str(a10)]=int(calc([a1,a2,a3,a4,a5,a6,a7,a8,a9,a10]))
#print(adic)
a= list(a)
while len(a)>10:
    temp=[]
    for i in range(9,len(a)):
        #print(a[i-9]+a[i-8]+a[i-7]+a[i-6]+a[i-5]+a[i-4]+a[i-3]+a[i-2]+a[i-1]+a[i])
        temp.append(adic[a[i-9]+a[i-8]+a[i-7]+a[i-6]+a[i-5]+a[i-4]+a[i-3]+a[i-2]+a[i-1]+a[i]])
    a=temp
#print("hoge")
print(calc(a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, list(input())))
ans = 0
prev = [A[0]]
for a in A[1:]:
    loop = len(prev)
    for i in range(loop):
        x = prev[i]
        prev[i] = a
        a = abs(x-a)
        if i == loop-1:
            prev.append(a)
print(prev[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
a_ = list(map(int, list(str(input()))))
a = []
if N == 2:
  print(abs(a_[0]-a_[1]))
else:
  for i in range(1, len(a_)):
    a.append(abs(a_[i]-a_[i-1])%2)
  a = np.array(a)
  while len(a)>1:
    a = (a[1:] + a[:len(a)-1])%2
  print(a[0])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
imput = stdin.readline
N=int(input())
A = list(input())
An=tuple(int(x) for x in A)
for i in range(N-1):   
  An = tuple(abs(An[x]-An[x+1]) for x in range(N-i-1))
print(An[0])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = input().rstrip()
    b = a[0]
    for i in range(1, n):
        #print(b)
        c = a[i]
        b += c
        for j in reversed(range(len(b)-1)):
            b = b[:j] + str(abs(int(b[j]) - int(b[j+1]))) + b[j+1:]
        l = 1
        f = False
        r = 1
        while r < len(b):
            if f and b[r] != "0":
                if r - l > 1:
                    b = b[:l] + b[r:]
                f = False
            elif not f and b[r] == "0":
                l = r
                f = True
            r += 1
        l = 1
        f = False
        r = 1
        while r < len(b):
            if f and b[r] != "2":
                if r - l > 1:
                    b = b[:l] + b[r:]
                f = False
            elif not f and b[r] == "2":
                l = r
                f = True
            r += 1
    #print(b)
    print(b[0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product
from math import log2

N = int(input())
A = tuple(int(c) - 1 for c in input())

memo = defaultdict(dict)
for x in product([0, 1, 2], repeat = 3):
  memo[3][x] = abs(abs(x[1]-x[0])-abs(x[2]-x[1]))

def f(T):
  min_t = min(T)
  if min_t > 0:
    T = tuple(t - min_t for t in T)
  if T not in memo[len(T)]:
    l = (len(T)-1) // 2 + 1
    memo[len(T)][T] = f(tuple(f(T[i:i+l]) for i in range(l)))
  return memo[len(T)][T]

def g(T):
  if len(T) == 1:
    return T[0]
  elif len(T) == 2:
    return abs(T[1]-T[0])
  else:
    n = 2**int(log2(len(T)-1)) + 1
    return g(tuple(f(T[i:i+n]) for i in range(len(T) - n + 1)))

print(g(A))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)

n = int(input())
a = input()
ans = ""

for k in range(n-1):
    for v in range(n-1-k):
        x1 = int(a[v]) - int(a[v+1])
        if x1 <= 0:
            x1 = -x1
        ans += str(x1)
    a = ans
    ans = ""
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = input()
a = [int(i) for i in a]

while N > 1:
    for i in range(N-1):
        a[i] = abs(a[i]-a[i+1])
    N-=1
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
A=[]
for i in range(n):
  A.append(int(a[i]))

def list(L):
  if len(L)==1:
    print(L[0])
  elif len(set(L))==1:
      print(0)
  else:
    m = len(L)
    B=[]
    for i in range(m-1):
      B.append(abs(L[i+1]-L[i]))
    else:
      list(B)
list(A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

num = int(input())
base = np.array(list(map(int,list(input()))))

for i in range(num-1):
  base_1 = base[:num-1-i]
  base_2 = base[1:]
  
  base = np.abs(base_1 - base_2)
  
  if np.all(base == 0):
    break
  
print(int(base[0]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = input()

before_list = [a_list[:-1], a_list[1:]]
for y in range(1, n):
    next_list = ''
    for a, b in zip(before_list[0], before_list[1]):
        next_list += str(abs(int(a)-int(b)))

    before_list[0] = next_list[:-1] if len(next_list) > 1 else next_list[0]
    before_list[1] = next_list[1:] if len(next_list) > 1 else next_list[0]
    next_list = ''

print(before_list[0])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = input()
a = deque(list(int(i) for i in input()))

def func(a):
        ls = deque()
        cnt = 0
        while len(a) > 0:
                p = a.popleft()
                if cnt == 0:
                        pre = p
                else:
                        ls.append(abs(pre - p))
                        pre = p
                cnt = cnt + 1

        return ls

while len(a) > 1:
        a = func(a)
print(a.pop())

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
a = input()

u = int(math.sqrt(N))
dic = {}

# DEBUG
#print('u: ', u)

def calc(s: str) -> int:
    dp = [[0] * len(s) for i in range(len(s))]
    for i in range(len(s)):
        for j in range(len(s)-i):
            if i == 0:
                dp[i][j] = int(s[j])
            else:
                dp[i][j] = abs(dp[i-1][j] - dp[i-1][j+1])
    #print('dp: ', dp)
    return dp[len(s)-1][0]

preva = a
for i in range(1, N//u):
    preva_list = []
    for j in range(N - (u-1)):
        s = preva[j:j+u]
        ans = 0

        #print(s)
        #print(dic)

        if s in dic:
            ans = dic[s]
        else:
            ans = calc(s)
            # DEBUG
            #print('s: ', s)
            #print('calc(s): ', calc(s))
            dic[s] = ans
        preva_list.append(str(ans))
    preva = ''.join(preva_list)
    # DEBUG
    #print('preva: ', preva)

ans = calc(preva)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
s = str(s)
s = list(s)
S = list(map(int, s))

a =[]
b =[]
c =[]
 
for j in range(0, N-1, 1):
    a.append(abs(S[j]-S[j+1]))

b = a
import sys
for i in range(1, N, 1):
  if i==N:
    sys.exit()
  if i!=1:
    b = c
    c = []
  
  for j in range(0, len(b)-1):
    c.append(abs(b[j]-b[j+1]))
    if i==N-1:
      sys.exit()
      
print(b[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
queue = list(input())
num_queue = [int(i) for i in queue]
ans_queue = []
for i in range(N - 1):
	for j in range(len(num_queue) - 1):
		ans_queue.append(abs(num_queue[j] - num_queue[j + 1]))
	num_queue = ans_queue
	ans_queue = []
print(num_queue[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
array = [int(c) for c in s]
for i in range(N-1):
    array = [abs(x-y) for x, y in zip(array[:-1], array[1:])]
print(array[0])

Submission status: Time Limit Exceeded

Solution code:
N = input()
a = input()
a_list = list(a)

def hiku(tmp):
  kari = []
  for i in range(len(tmp) - 1):
     x = abs(int(tmp[i]) - int(tmp[i+1]))
     kari.append(x)
    #  print("----",kari)
  if len(kari) == 1:
      print(x)
  else:
    #   print("next") 
      hiku(kari)

def w_hiku(tmp):
  kari = []
  for i in range(len(tmp) - 2):
     x = abs(abs(int(tmp[i]) - int(tmp[i+1])) - abs(int(tmp[i+1]) - int(tmp[i+2])))
     kari.append(x)
    #  print("----",kari)
  if len(kari) == 2:
      hiku(kari)
  elif len(kari) == 1:
      print(x)
  else:
    #   print("next") 
      w_hiku(kari)

if len(a_list) == 2:
    hiku(a_list)
else:
    w_hiku(a_list)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())

s=list(map(int,input()))

s=np.array(s)
b=[]

while True:
    a=s[:len(s)-1]
    b=s[1:len(s)+1]
    s=np.abs(a-b)
    
    if len(s)==1:
        s=list(s)
        print(s[0])
        break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,list(input())))
a2 = list()
flag = True
while len(a)>1:
    if flag:
        flag = False
        for i in range(len(a)-1):
            ap = abs(a[i]-a[i+1])
            a2.append(ap)
            if ap == 2:
                flag = True
        a=a2
        a2=list()
    else:
        break
else:
    sn=a[0]

if flag==False:
    s=''.join(map(str,a))
    lens = len(s)
    sn=int(s,2)
    while sn>1:
        snn=sn<<1&~(1<<lens)
        snext=sn^snn
        sn=snext>>1
        lens-=1

print(sn)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
an = [int(x) for x in list(input())]

arr = np.array(an)

for i in range(N-1,0,-1):
    arr2 = abs(arr[0:-1] - arr[1:])
    arr = arr2

print(arr[0])

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    x=list(readline().rstrip())

    d={}
    for i in range(1,4):
        for j in range(1,4):
            for k in range(1,4):
                for l in range(1,4):
                    a1=abs(i-j)+1
                    a2=abs(j-k)+1
                    a3=abs(k-l)+1
                    b1=abs(a1-a2)+1
                    b2=abs(a2-a3)+1
                    d[str(i)+str(j)+str(k)+str(l)]=abs(b1-b2)+1

    i=1
    while i < n:
    #for i in range(1,n):
        # boost
        if (n-i)>=4:
            for j in range(n-i-4):
                key=str(x[j])+str(x[j+1])+str(x[j+2])+str(x[j+3])
                x[j]=d[key]
            i+=3
        else:
            for j in range(n-i):
                x[j]=str(abs(int(x[j])-int(x[j+1])))
        i+=1

    print(x[0])
    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Submission status: Time Limit Exceeded

Solution code:
def cal(x):
    y=[]
    for i in range(len(x)-1):
        y.append(abs(x[i]-x[i+1]))
    if len(y)>1:
        return cal(y)
    else:
        return y[0]

N=int(input())
A=input()
x=[int(A[j]) for j in range(N)]
print(cal(x))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, a: str):
    # a = "11002102121200"
    # a = "210211"
    a = list(map(int,a))
    # new = []
    # for i in range(len(a)-1):
    #     new.append(abs(a[i]-a[i+1]))
    # a = new
    # print(a)
    while len(a) > 1:
        new = []
        for i in range(len(a)-1):
            new.append(abs(a[i]-a[i+1]))
        a = new
    print(a[0])

    return


def main():
    N = int(input())  # type: int
    a = input() 
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input()))

#B = np.array(A)
#print(A)

for i in range(N-1):
    A = abs(np.diff(A))

print(int(A[0]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
a=[int(c) for c in s]
b=a
ans=[]
for j in range(n):
    for i in range(len(b)):
        if i+1<len(b):
            if b[i]==0 or b[i+1]==0:
                ans.append(max(b[i],b[i+1]))
            else:
                ans.append(abs(b[i]-b[i+1]))
    b=ans
    if len(ans)>1:
        ans=[]

print(ans[0])
#print(a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = input()
a = [0]*N
for k in range(N):
    a[k] = int(A[k])
# print(a[1:])
# print(a[:-1])
a = np.array(a)
for i in range(N-1):
    a = abs(a[1:] - a[:-1])
    # print(a)
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
a2 = [int(a[i]) for i in range(n)]
n2 = bin(n)
b = [0] * n
c = [1] * (2 ** (len(n2) - 3))
for i in range(len(c)):
    b[i] += c[i]
temp = len(n2) - 4
count = len(c)
while temp>= 0:
    if n2[-1-temp] == "1":
        c = [b[i] for i in range(count)]
        for i in range(count):
            b[i + 2 ** temp] += c[i]
        count += 2 ** temp
    temp -= 1
e = [b[i] % 2 for i in range(len(b))]
d = 0
for i in range(n):
    if e[i] % 2 == 1:
        d += a2[i]
if d % 2 == 1:
    print(1)
else:
    a3 = [abs(a2[i] - a2[i + 1]) for i in range(n - 1)]
    if 1 in a3:
        print(0)
    else:
        n3 = bin(n - 1)
        b = [0] * (n - 1)
        c = [1] * (2 ** (len(n3) - 3))
        for i in range(len(c)):
            b[i] += c[i]
        temp = len(n3) - 4
        count = len(c)
        while temp>= 0:
            if n3[-1-temp] == "1":
                c = [b[i] for i in range(count)]
                for i in range(count):
                    b[i + 2 ** temp] += c[i]
                count += 2 ** temp
            temp -= 1
        e = [b[i] % 2 for i in range(len(b))]
        d = 0
        for i in range(n - 1):
            if e[i] % 2 == 1:
                d += a3[i]
        if d % 4 == 0:
            print(0)
        else:
            print(2)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())


a=input()

def calc(ary):
    if len(ary)==2:
        return abs(ary[1]-ary[0])
    else:
        temp=[]
        for i in range(1,len(ary)):
            temp.append(abs(ary[i]-ary[i-1]))
        return calc(temp)


b= [int(s) for s in list(a)]
print(calc(b))

Submission status: Time Limit Exceeded

Solution code:
import sys

def calc(l, j, N):
    tmp = []
    for index in range(len(l)-1):
        tmp.append(abs(int(l[index]) - int(l[index+1])))
    if len(tmp) == 1:
        print(tmp[0])
    else:
        calc(tmp, j+1, N)

N = int(sys.stdin.readline())
a = list(sys.stdin.readline())
calc(a[:N], 0, N)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    s = input()
    array = [int(c) for c in s]
    for i in range(N-1):
        array = [abs(x-y) for x, y in zip(array[:-1], array[1:])]
    print(array[0])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import itertools

N = int(input())
lines = [int(n) for n in list(input())]

for i in range(N-1):
  next_lines = []
  for j in range(N-i-1):
    x = np.abs(lines[j] - lines[j+1])
    next_lines.append(x)
  lines = next_lines

print(lines[0])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    num = [int(x) for x in list(str(int(input())))]
    length= len(num)
    count_stopper = length
    cnt = 1
    big_count = 0
    while big_count != length-1:
        new = []
        while cnt != count_stopper:
            a = 0
            a = num[cnt - 1] - num[cnt]
            new.append(abs(a))
            cnt += 1
        cnt = 1
        num = new
        big_count += 1
        count_stopper -= 1
    print(num[0])

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

num = int(input())
base = np.array(list(map(int,list(input()))))

for i in range(num-1):
  base_1 = base[:num-1-i]
  base_2 = base[1:]
  
  base = np.abs(base_1 - base_2)
  
print(int(base[0]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input()
X = []

for a in A:
    X.append(int(a))

Y =[]
while len(X) > 1:
    Y =[]
    for i in range(len(X)):
        if i != 0:
            Y.append(abs(X[i] - X[i - 1]))
    X = Y

print(X[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

x_ar = [[0 for ii in range(N)] for jj in range(N)]

a_ar = list(map(int,list(str(input()))))

x_ar[0] = a_ar

for ii in range(N-1):
  for jj in range(N-ii-1):
    x_ar[ii+1][jj] = abs(x_ar[ii][jj] - x_ar[ii][jj+1])


print(x_ar[N-1][0])

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import stdin
  imput = stdin.readline
  N=int(input())
  A = list(input())
  An=tuple(int(x) for x in A)
  for i in range(N-1):
    An = tuple(abs(An[x]-An[x+1]) for x in range(N-i-1))
  print(An[0])
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    *a, = map(int, input())

    while len(a) > 2:
        na = []
        for a1, a2 in zip(a, a[2:]):
            if a1 % 2 == a2 % 2:
                na.append(0)
            else:
                na.append(1)
        a = na

    if len(a) == 1:
        print(a[0])
    else:
        print(abs(a[0] - a[1]))


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
a = [int(i) for i in S]

x = [[0 for j in range(N)] for i in range(N)]
x[0] = a

for i in range(1,N):
  for j in range(N-i):
    x[i][j] = abs(x[i-1][j] - x[i-1][j+1])

print(x[N-1][0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())

s=list(map(int,input()))

s=np.array(s)
b=[]

while True:
    if len(s)>1:
        a=s[:len(s)-1]
        b=s[1:len(s)+1]
        s=np.abs(a-b)
        continue
    elif len(s)==1:
        s=list(s)
        print(s[0])
        break

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    x=list(readline().rstrip())

    d={}
    for i in range(1,4):
        for j in range(1,4):
            for k in range(1,4):
                for l in range(1,4):
                    a1=abs(i-j)+1
                    a2=abs(j-k)+1
                    a3=abs(k-l)+1
                    b1=abs(a1-a2)+1
                    b2=abs(a2-a3)+1
                    d[str(i)+str(j)+str(k)+str(l)]=abs(b1-b2)+1


    for i in range(1,n):
        # boost
        if (n-i)>=4:
            for j in range(n-i-4):
                key=str(x[j])+str(x[j+1])+str(x[j+2])+str(x[j+3])
                x[j]=d[key]
            i+=2
        else:
            for j in range(n-i):
                x[j]=str(abs(int(x[j])-int(x[j+1])))

    print(x[0])
    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input()))
z = []

for i in range (N-1):
    if i % 2 == 0:
        for j in range(N-i-1):
            x = a[j] - a[j+1]
            z.append(abs(x))
        a.clear()
    else:
        for j in range(N-i-1):
            x = z[j] - z[j+1]
            a.append(abs(x))
        z.clear()
ans = a + z
print(ans[0])