Problem:
 Score : 1000 points    Problem Statement We will host a rock-paper-scissors tournament with N people. The participants are called Person 1 , Person 2 , \ldots , Person N .
For any two participants, the result of the match between them is determined in advance.
This information is represented by positive integers A_{i,j} ( 1 \leq j < i \leq N ) as follows:   If A_{i,j} = 0 , Person j defeats Person i .  If A_{i,j} = 1 , Person i defeats Person j .   The tournament proceeds as follows:   We will arrange the N participants in a row, in the order Person 1 , Person 2 , \ldots , Person N from left to right.  We will randomly choose two consecutive persons in the row. They will play a match against each other, and we will remove the loser from the row.
We will repeat this process N-1 times, and the last person remaining will be declared the champion.   Find the number of persons with the possibility of becoming the champion.      Constraints  1 \leq N \leq 2000  A_{i,j} is 0 or 1 .         Input Input is given from Standard Input in the following format:  N  A_{2,1}  A_{3,1} A_{3,2}  :  A_{N,1} \ldots A_{N,N-1}       Output Print the number of persons with the possibility of becoming the champion.        Sample Input 1 3
0
10      Sample Output 1 2  Person 1 defeats Person 2 , Person 2 defeats Person 3 and Person 3 defeats Person 1 .
If Person 1 and Person 2 play the first match, Person 3 will become the champion.
If Person 2 and Person 3 play the first match, Person 1 will become the champion.       Sample Input 2 6
0
11
111
1111
11001      Sample Output 2 3

Solution (Python):
import sys

p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def pbit(aa,L):
    for a in aa:print(format(a,"b").zfill(L))
    print()

def main():
    n=II()
    aa=[[int(c) for c in SI()] for _ in range(n-1)]
    

    
    win=[0]*n
    for i,row in enumerate(aa,1):
        for j,a in enumerate(row):
            if a:win[i]|=1<<j
            else:win[j]|=1<<i
    

    
    
    dpl=[1<<i for i in range(n)]
    dpr=[1<<i for i in range(n)]
    for d in range(1,n):
        for i in range(n-d):
            j=i+d
            if dpl[j] & dpr[i+1] & win[i]:dpl[j]|=1<<i
        for i in range(d,n):
            j=i-d
            if dpl[i-1] & dpr[j] & win[i]:dpr[j]|=1<<i
    
    
    
    print(bin(dpl[n-1]&dpr[0]).count("1"))

main()

Solution (Python):
import sys

p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def pbit(aa,L):
    for a in aa:print(format(a,"b").zfill(L))
    print()

def main():
    n=II()
    aa=[[int(c) for c in SI()] for _ in range(n-1)]
    
    
    
    win=[0]*n
    for i,row in enumerate(aa,1):
        for j,a in enumerate(row):
            if a:win[i]|=1<<j
            else:win[j]|=1<<i
    

    
    
    dpl=[1<<i for i in range(n)]
    dpr=[1<<i for i in range(n)]
    for d in range(1,n):
        for i in range(n):
            j=i+d
            if j<n and dpl[j] & dpr[i+1] & win[i]:dpl[j]|=1<<i
            j=i-d
            if j>=0 and dpl[i-1] & dpr[j] & win[i]:dpr[j]|=1<<i
    
    
    
    print(bin(dpl[n-1]&dpr[0]).count("1"))

main()

Solution (Python):
N = int(input())
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1

A = [1<<i for i in range(N)]
B = [1<<i for i in range(N)]
for i in range(N):
    for j in range(i):
        if i and B[i-1] >> j & 1 and X[i][j]: A[i] |= A[j]
    for j in range(i):
        if A[i] >> j+1 & 1 and X[j][i]: B[i] |= B[j]

print(sum([(A[i] & 1) * (B[N-1]>>i & 1) for i in range(N)]))