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 itertools import starmap
from operator import mul


def test(a):
    print(*a)
    for i in range(len(a) - 1):
        a = [abs(a1 - a0) for a0, a1 in zip(a, a[1:])]
        print(' ' * i, *a)


def first(aaa):
    aaa = list(map(int, aaa))
    aaa = [abs(a1 - a0) for a0, a1 in zip(aaa, aaa[1:])]
    return aaa


def last(aaa):
    for i in range(len(aaa) - 1):
        aaa = [abs(a1 - a0) for a0, a1 in zip(aaa, aaa[1:])]
    return aaa[0]


def prepare():
    # for v in product([0, 1, 2], repeat=10):
    ret = [0] * (3 ** 10)
    for i in range(3 ** 10):
        v = i
        v, m1 = divmod(v, 3)
        tmp = []
        for _ in range(9):
            v, m2 = divmod(v, 3)
            tmp.append(abs(m1 - m2))
            m1 = m2
        tmp.reverse()
        for _ in range(8):
            tmp = [abs(a1 - a0) for a0, a1 in zip(tmp, tmp[1:])]
        ret[i] = tmp[0]
    return ret


# test([2, 3, 1, 1, 3, 1, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 2, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 3, 2, 3, 1, 2])
# test([1, 3, 1, 3, 1, 3, 1, 3, 1, 3])

n = int(input())
aaa = input()
aaa = first(aaa)
ppp = prepare()
pow3 = [3 ** (9 - i) for i in range(10)]
while len(aaa) >= 10:
    aaa = [ppp[sum(starmap(mul, zip(aaa[i:i + 10], pow3)))] for i in range(len(aaa) - 9)]
ans = last(aaa)
print(ans)

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):
    #print(b)
    for i in range(n-j):
        if i+1<len(b):
            #print(abs(b[i]-b[i+1]))
            ans.append(abs(b[i]-b[i+1]))
    b=ans
    #print(ans)
    if len(ans)>1:
        ans=[]

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input(''))
m=input('')
s=[]
for a in range(n):
    s.append(int(m[a]))

m=[]
m.append(s)

b=1
for a in range(n-1):
    ender=0
    c=0
    kara=[]
    while ender==0:
        if c<len(m[b-1])-1:
            z=(m[b-1][c]-m[b-1][c+1])
            if z<0:
                z=z*(-1)
            kara.append(z)
        else:
            ender=1
        c=c+1
    m.append(kara)
    b=b+1

print(m[n-1][0])

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import stdin
  N=int(stdin.readline().rstrip())
  A = list(stdin.readline().rstrip())
  An=[int(x) for x in A]
  for i in range(N-1):
    An = [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:
n = int(input())
 
numlist = []
numstr = input()
 
for a in range(0, n):
    numlist.append(numstr[a])
 
l_numlist = len(numlist)

for b in range(1, n):
 
    for a in range(0, l_numlist-1):
        d = int(numlist[a]) - int(numlist[a+1])
        numlist.append(abs(d))
 
    numlist = numlist[l_numlist:]
    l_numlist = len(numlist)
 
print(numlist[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
an = str(input())

before = an;
for i in range(2,n+1):
    now = ""
    for j in range(1,n+2-i):
        if before[j-1:j] == before[j:j+1]:
            now += "0"
        else:
            now += str(abs(int(before[j-1:j]) - int(before[j:j+1])))
    before = now

print(now)

Submission status: Time Limit Exceeded

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

for j in range(1,N):
    for i in range(N-j):
        min = abs(int(l[i]) - int(l[i+1]))
        k.append(min)
    l = k
    k = []

ans = l[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.array(list(input())).astype(np.int)

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

print(*A)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = input()
ans = a
while len(ans) != 1 and len(ans) != 0:
    a = ans
    ans = ""
    for i in range(len(a)-1):
        if abs(int(a[i+1])-int(a[i])) != 0:
            ans += str(abs(int(a[i+1])-int(a[i])))
if ans == "":
    print(0)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(str(input()))
a = [int(y) for y in a]

x = [[0]*(n+1)]*(n+1)
#x=[0][0]

for j in range(n):
    x[1][j+1] = a[j]


for i in range(n-2):
    for j in range(n-1-i):
        x[i+2][j+1] = abs(x[i+1][j+1] - x[i+1][j+2])
        #print('x[',i+2,'][',j+1,']: ' ,x[i+2][j+1])

print(abs(x[n-1][1] - x[n-1][2]))

#print(x[n][1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x1 = input()
x1ar = []
for i in range(len(x1)):
    x1ar.append(int(x1[i]))
xar = []
xar.append(x1ar)
for i in range(N-1):
    xar.append([])
    for j in range(N-i-1):
        xar[i+1].append(abs(xar[i][j] - xar[i][j+1]))
print(xar[len(xar)-1][0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = input()
A=[None]
x = [None]
for n in range(len(a)):
    A.append(int(a[n]))
x.append(A)
b = [None, None]
for i in range(2,N+1):
    b.append([None])
    for j in range(1,N+2-i):
        y = int(x[i-1][j])
        z = int(x[i-1][j+1])
        if y <= z:
            b[i].append(z-y)
        else:
            b[i].append(y-z)
    x.append(b[i])

print(x[N][1])

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])
  else:
    m = len(L)
    B=[]
    for i in range(m-1):
      B.append(abs(L[i+1]-L[i]))
    list(B)
list(A)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    import sys
    sys.setrecursionlimit(4100000)
    input = sys.stdin.readline

    N = int(input())
    a = input()[:-1]
    la = np.array([int(c) for c in a])

    na, nd = np.abs, np.diff
    def f(l1):
        if len(l1) ==1:
            print(l1[0])
        else:
            return f(na(nd(l1)))
    f(la)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())

L = [int(s) for s in input()]

a = np.array(L)
for i in range(N-1):
  a = abs(a[1:]-a[:-1])
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
def f(X):
  j=len(X)
  if j<2: return X
  R=[0]*(j-1)
  for i in range(1,j):
    R[i-1]=abs(X[i]-X[i-1])
  return R
N=int(input())
A=[int(x) for x in list(input())]
for i in range(N-1):
  A=f(A)
print(A[0])

Submission status: Time Limit Exceeded

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

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

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 = list(map(int, list(input())))


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):
    A = diff(A)

print(A[0])

Submission status: Time Limit Exceeded

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()

def main():
    N = I(); a = IS()
    x = [int(a[i]) for i in range(N)]
    while len(x) > 1:
        x = [abs(x[i]-x[i+1]) if x[i]!=x[i+1] else 0 for i in range(len(x)-1)]
    print(x[0])

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
a = input()
for i in range(N):
  A.append(int(a[i]))
for j in range(N):
  for i in range(N-j-1):
    A[i] = abs(A[i] - A[i+1])
print(A[0])

Submission status: Time Limit Exceeded

Solution code:
def test(a):
    print(*a)
    for i in range(len(a) - 1):
        a = [abs(a1 - a0) for a0, a1 in zip(a, a[1:])]
        print(' ' * i, *a)


def first(aaa):
    aaa = list(map(int, aaa))
    aaa = [abs(a1 - a0) for a0, a1 in zip(aaa, aaa[1:])]
    return ''.join(map(str, aaa))


def last(aaa):
    aaa = list(map(int, aaa))
    for i in range(len(aaa) - 1):
        aaa = [abs(a1 - a0) for a0, a1 in zip(aaa, aaa[1:])]
    return aaa[0]


def prepare():
    # for v in product([0, 1, 2], repeat=10):
    ret = [0] * (3 ** 10)
    for i in range(3 ** 10):
        v = i
        v, m1 = divmod(v, 3)
        tmp = []
        for _ in range(9):
            v, m2 = divmod(v, 3)
            tmp.append(abs(m1 - m2))
            m1 = m2
        tmp.reverse()
        for _ in range(8):
            tmp = [abs(a1 - a0) for a0, a1 in zip(tmp, tmp[1:])]
        ret[i] = str(tmp[0])
    return ret


# test([2, 3, 1, 1, 3, 1, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 2, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 3, 2, 3, 1, 2])
# test([1, 3, 1, 3, 1, 3, 1, 3, 1, 3])

n = int(input())
aaa = input()
aaa = first(aaa)
ppp = prepare()
while len(aaa) >= 10:
    aaa = ''.join(ppp[int(aaa[i:i + 10], 3)] for i in range(len(aaa) - 9))
ans = last(aaa)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
 
numlist = []
numstr = input()
 
for a in range(0, n):
    numlist.append(numstr[a])
 
l_numlist = len(numlist)

for b in range(1, n):
 
    for a in range(0, l_numlist-1):
        d = int(numlist[a]) - int(numlist[a+1])
        if d < 0:
            d = -d
        numlist.append(d)
 
    numlist = numlist[l_numlist:]
    l_numlist = len(numlist)
 
print(numlist[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
an = str(input())

before = an;
for i in range(2,n+1):
    now = ""
    for j in range(1,n+2-i):
        now += str(abs(int(before[j-1:j]) - int(before[j:j+1])))
    before = now

print(now)

Submission status: Time Limit Exceeded

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

tmp1 = [a[i] for i in range(N)]	# 初期値
if sum(tmp1) == 0:
  print(0)
tmp2 = []
for i in range(1,N):
  tmp2 = []
  for j in range(0,N-i):
    tmp2.append(abs(tmp1[j]-tmp1[j+1]))
  tmp1 = tmp2
  if sum(tmp1) == 0:
    tmp2[0] = 0
    break
print(tmp2[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, list(input())))
C = A[:]
while len(C) > 1:
  B = [abs(i-j) for i, j in zip(C, C[1:])]
  C = B[:]
if C:
  print(C[0])
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_list = list(map(int, list(input())))
diff = a_list.copy()
for i in range(N - 1) :
    temp = list()
    for j in range(len(diff) - 1) :
        temp.append(abs(diff[j] - diff[j + 1]))
    diff = temp
print(diff[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)

hiku(a_list)

Submission status: Time Limit Exceeded

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

x=[]

for i in range(N):
    i_list =[]
    for j in range(N+1-i):
        i_list.append(0)
    x.append(i_list)


for j,a_j in enumerate(a):
    x[0][j] = (int)(a_j)

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
count = 0
a = []
for i in range(n-1):
	a.append(abs(int(s[i])-int(s[i+1])))
while(len(a)!=1):
	b = [abs(a[j]-a[j+1]) for j in range(len(a)-1)]
	a = b[:]
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, list(input()))))
for _ in range(n-1):
    a = np.absolute(np.diff(a))
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
a = list(input())
for i in range(len(a)):
    a[i] = int(a[i])
a = np.array(a)

while a.size > 1:
    b = a
    c = a
    b = np.append(b,0)
    c = np.insert(c, 0, 0)
    d = np.abs(c - b)
    d = np.delete(d, 0)
    d = np.delete(d, d.size-1)
    a = d

print(a[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import math
import fractions

import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
import numpy as np
from decimal import *
sys.setrecursionlimit(10 ** 6)

def CalcList(list):
    bfnum = -1
    afterList =[]
    for i in list:
        if bfnum == -1:
            bfnum = i
        else:
            now = abs(i -bfnum)
            afterList.append(now)
            bfnum = i
    return afterList

def CheckList(list):
    bfnum = -1
    count = 0
    afterList =[]
    for i in list:
        if bfnum == -1:
            bfnum = i
            afterList.append(i)
        else:
            if i == bfnum:
                count = count +1
                if count < 3:
                    afterList.append(i)
            else:
                afterList.append(i)
    return afterList


if __name__ == '__main__':
    n = int(input())
    s = input()
    list =list(map(lambda x: int(x), s))

    while(len(list) >1):
        list = CalcList(list)

    if len(list) ==0:
        print(0)
    else:
        print(list[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
b = input()
ans = []
a = [int(x) for x in list(str(b))]

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