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:
data = [input() for i in range(2)]
X = int(data[0]) - 1 #Ｎひく１
L = list(data[1])
#print(reallist)
answer = []
for i in range(int(data[0]) - 1):#たて
  data2 = [] 
  for l in range(int(data[0])-1-i):#よこ
      data2.append(abs(int(L[l]) - int(L[l+1])))
  answer.append(data2)
  L = data2
lastone = answer[X - 1]
finalanswer = lastone[0]
print(finalanswer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=input()
L=[]
L.append(a)
for i in range(N-1):
    s=L[i]
    for j in range(N-1-i):
        if(j==0):
            l=str(abs(int(s[j])-int(s[j+1])))
        #l=""
        #print(abs(int(s[j])-int(s[j+1])))
        else:
            l=l+str(abs(int(s[j])-int(s[j+1])))
        #print(l)
    L.append(l)
    #print(L)
ans=L[N-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
i=int(input())
s=input()
a=[]
while len(s)>1:
  a=[]
  for k in range(len(s)-1):
    a.append(str(abs((int(s[k])-int(s[k+1])))))
    #str(abs(int(s[k])-int(s[k+1])))
    #print(a[k])
  #print("".join(a))
  s="".join(a)
  #s="".join(a)
  #s="1"
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
numstr = input()
l = [int(i) for i in list(str(numstr))]
k = n-1
for _ in range(n-1):
    for i, x in enumerate(range(k)):
        l[i] = abs(l[i] - l[i+1])
    k = k-1
print(l[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def main():
    n =int(input())
    a = list(map(int,input()))
    new = a.copy()
    for i in range(n-1):
        new1 = new.copy()
        for j in range(1,n-i):
            new[j] = abs(new1[j]-new1[j-1])
        # print(new)
        new.pop(0)
        # print(new)
    print(new[0])





# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#B
import math
n = int(input())
a = list(map(int,input()))
for _ in range(len(a)-1):
    b=[]
    for i in range(len(a) - 1):
        b.append(abs(a[i] - a[i + 1]))
    a = b
print(*a)

Submission status: Time Limit Exceeded

Solution code:
i=int(input())
s=input()
a=[]
while len(s)>1:
  a=[]
  for k in range(len(s)-1):
    a.append(str(abs((int(s[k])-int(s[k+1])))))
  s="".join(a)
print(s)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def cal(b, N):
    c = []
    for i in range(N - 1):
        c.append(abs(b[i] - b[i + 1]))

    return c

N = int(input())
# print(N)
a = list(map(str, input().split()))
b = []
for i in range(N):
    b.append(int(a[0][i:i + 1]))
# print(a)
# print(b)

c = []
for i in range(N - 1):
    c = cal(b, N)
    b = c
    N -= 1
    # print(c)
print(c[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def array_subtraction(arr):
    arr = np.abs(arr)
    while len(arr) !=1:
        arr = np.abs(arr[1:]-arr[:-1])
        yield arr
    yield arr


input()
z = np.array([int(i) for i in input()])
for num in array_subtraction(z):
    pass
else:
    print(*num)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input()))
S=A[:];j=0
while j!=(N-1):
  for i in range(1,N-j):
    S[i-1]=abs(S[i-1]-S[i])
  j=j+1
  #print(S)
print(S[0])

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 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)

while l_numlist > 1:
 
    for a in range(0, l_numlist-1):
        d = numlist[a] - 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:
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 = np.abs(np.diff(a))
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3 ## -*- python -*-

def main():
    n = int(input())
    t = input()
    a = []
    a.append(-1)    # index 0は使わない
    for i in range(n):
        a.append(int(t[i]))

    x = [[0]*(n+1)]*(n+1)  #index 0は使わない
    for i,c in enumerate(a):
        x[1][i] = c

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N=int(stdin.readline().rstrip())
A = int(stdin.readline().rstrip())
An=[0]*N
for i in range(N):
  An[i]=A%10
  A=A//10
for i in range(N-1):
  for x in range(N-i-1):
    An[x] = abs(An[x]-An[x+1])
print(An[0])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
moji = input()

a = [[0]*N]*N

for j in range(N):
    a[0][j] = int(moji[j])

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
st = input()
a = []
for i in range(N):
  a.append(int(st[i]))

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

print(int(a[0]))

Submission status: Time Limit Exceeded

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

def minus(x,y):
    B = []
    for i in range(y-1):
        B.append(abs(x[i]-x[i+1]))
    #print(B)
    return B

for n in range(N-1):
    A = minus(A,N-n)

ans = int(A[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
data = [input() for i in range(2)]
X = int(data[0]) - 1 #Ｎひく１
L = list(data[1])
#print(reallist)
answer = []
for i in range(int(data[0]) - 1):#たて
  data2 = []
  if i==0:  
    for l in range(int(data[0])-1-i):#よこ
        data2.append(abs(int(L[l]) - int(L[l+1])))
  else:
    for l in range(int(data[0])-1-i):#よこ
        data2.append(abs(int(L[l]) - int(L[l+1])))
  answer.append(data2)
  L = data2
lastone = answer[X - 1]
finalanswer = lastone[0]
print(finalanswer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
j=int(input())

i=[]
while j > 0:
    i.append(j%10)
    j //= 10 
i.reverse()

n=N-1

while n!=0:
  for l in range(n):
    i[l]=abs(i[l]-i[l+1])
  n-=1
  
print(i[0])

Submission status: Time Limit Exceeded

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

    now = [a[-1]]

    for i in range(1, N):
        nxt = [a[-(i+1)]]
        for j in range(len(now)):
            x = abs(nxt[j] - now[j])
            nxt.append(x)

        now = nxt

    print(now[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
num = [int(c) for c in s]

temp = num

def sumlist(x1,x2):
  return abs(x1-x2)

I = N-1
for i in range(I):
  list1 = temp[1:]
  list2 = temp[:-1]
  result = map(sumlist, list1, list2)
  temp = list(result)

print(temp[0])

Submission status: Time Limit Exceeded

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

while len(a) > 1 :
    a = a.replace("11", "1")
    a = a.replace("22", "2")
    a = a.replace("33", "3")
    b = ""
    for i in range(len(a)-1) :
        if abs(int(a[i]) - int(a[i+1])) == 1 :
            b += "1"
        elif abs(int(a[i]) - int(a[i+1])) == 2 :
            b += "2"
    a = b

if a :
    print(a)
else :
    print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
x = [""] * n
x[0] = a
for i in range(1, len(x)):
    for j in range(len(x[i - 1]) - 1):
        x[i] = x[i] + str(abs(int(x[i - 1][j]) - int(x[i - 1][j + 1])))
print(x[-1][0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())

input_string = input()
a = [0] * N
for i in range(N):
  a[i] = int(input_string[i])

x = copy.copy(a)
x_temp = [0] * N

for i in range(N-1):#0~N-2
  for j in range(N - i - 1):#0~N-i-2
    x_temp[j] = abs(x[j] - x[j + 1])
    
  x = copy.copy(x_temp)

print(x[0])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    import sys
    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):
        return na(nd(l1))

    for _ in range(N-1):
       la =  f(la)

    print(*la)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)

n = int(input())
b = input()
a = []
ans = []
for v in range(n):
    a.append(int(b[v]))

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]))

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(N-1-i):
        seq.append(abs(seq[int(1+j+i*N-i*(i-1)*0.5)] -
                       seq[int(j+i*N-i*(i-1)*0.5)]))
if N < 5:
    print(seq[int(N*(N+1)*0.5-1)])
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
def calc(x, y):
  if x-y == 0:
    return 0
  elif (((x-y)==1) or(x-y)==-1):
    return 1
  else:
    return 2

N = int(input())
a =str(input())
alist = [0] * N
for i, a in enumerate(a):
  alist[i] = int(a)

for j in range(N-1):
  for i in range(N-j-1):
    alist[i] = calc(alist[i],alist[i+1])
print(alist[0])

Submission status: Time Limit Exceeded

Solution code:
def triangle(l):
    for i in range(len(l) - 1):
        l[i] = str(abs(int(l[i]) - int(l[i + 1])))
    l.pop(-1)
    if len(l) == 1:
        print(l[0])
    else:
        triangle(l)
n = int(input())
a = list(input())
triangle(a)

Submission status: Time Limit Exceeded

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

#print(N)
#print(A[1])

#print(A[0])
##xij
#B = []
#print(B)
'''
for i in range(N-1):
    B.append(A[i]-A[i+1])

print(B)
'''
def minus(x,y):
    B = []
    for i in range(y-1):
        B.append(abs(x[i]-x[i+1]))
    #print(B)
    return B

for n in range(N-1):
    A = minus(A,N-n)

ans = int(A[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
x = [int(a[i]) for i in range(n)]
for i in range(n - 1, 0, -1):
    for j in range(i):
        x[j] = abs(x[j] - x[j + 1])

print(x[0])

Submission status: Time Limit Exceeded

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

x = [int(_) for _ in a]

def x_n(x):
    if len(x) == 1:
        return x[0]
    else:
        for _ in range(len(x) - 1):
            x[_] = abs(x[_] - x[_ + 1])
        x = x[0:len(x) - 1]
        return x_n(x)

print(x_n(x))

Submission status: Time Limit Exceeded

Solution code:
size = int(input())
values = list(map(int, input()))
temp_values = []
pre_value = -1
for exec_count in range(size - 1):
    check_values = values
    if len(list(set(check_values))) == 1:
        temp_values.append(0)
        values = temp_values
        break
    for value_string in list(values):
        value = int(value_string)
        if pre_value != -1:
            temp_values.append(abs(value - pre_value))
        pre_value = value
    values = temp_values
    temp_values = []
    pre_value = -1
print(values[0])

Submission status: Time Limit Exceeded

Solution code:
i=int(input())
s=input()
a=""
while len(s)>1:
  a=""
  for k in range(len(s)-1):
    a += str(abs((int(s[k])-int(s[k+1]))))
    #str(abs(int(s[k])-int(s[k+1])))
    #print(str(abs((int(s[k])-int(s[k+1])))))
  s=a
print(s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
numbers = input()
input_arr = np.array([int(i) for i in numbers])
arr = np.array(input_arr)
for i in range(N-1):
    arr = np.abs(arr[1:] - arr[:-1])
print(arr[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
data = [int(s) for s in input()]


while len(data) > 1:
    temp = []
    for i in range(len(data) - 1):
        temp.append(abs(data[i] - data[i + 1]))

    data = temp

print(data[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
a=[0]
b=list(map(int, input()))
a[1:1]=b
a=np.array(a)
b.append(0)
b=np.array(b)
for i in range(N-1):
    x=abs(a-b)
    a=x
    b=np.insert(x[1:],N,0)
print(a[1])

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(N-1-i):
        seq.append(abs(seq[int(1+j+i*N-i*(i-1)*0.5)] -
                       seq[int(j+i*N-i*(i-1)*0.5)]))
print(seq[int(N*(N+1)*0.5-1)])

Submission status: Time Limit Exceeded

Solution code:
given = [input() for i in range(2)]
N = int(given[0])

result = [[0] * N] * N
result[0] = [int(c) for c in given[1]]

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys

s = int(input())
N1 = list(map(int,input()))
N2 = []

def recursion(N):
    for i in range(len(N) - 1):
        if i == 0:
            N2.clear()
        N2.append(abs(N[i]-N[i+1]))
    
    N1 = copy.copy(N2)
    if len(N1) == 1:
        print(N1[0])
        sys.exit()
    else:
        recursion(N1)

recursion(N1)

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)

while l_numlist > 1:

    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())
s=str(input())
while len(s) > 1:
    t=0
    for i in range(len(s)-1):
        element=abs(int(s[i])-int(s[i+1]))
        if element==0:
            continue
        else:
            t=t*10+element
    s=str(t)
print(s)

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)]
    for i in range(1, N):
        x = [abs(x[i]-x[i+1]) for i in range(N-i)]
    print(x[0])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def func(l):
    if len(l)==1:
        return l[0]
    else:
        l1=[]
        for i in range(len(l)-1):
            l1.append(abs(l[i]-l[i+1]))
        return func(l1)
n=int(input())
n1=int(input())
l=[]
while n1>0:
    l.append(n1%10)
    n1//=10
print(func(l[::-1]))