Problem:


Score : 900 points

Problem Statement

You are developing frog-shaped robots, and decided to race them against each other.

First, you placed N robots onto a number line.
These robots are numbered 1 through N.
The current coordinate of robot i is x_i.
Here, all x_i are integers, and 0 < x_1 < x_2 < ... < x_N.

You will repeatedly perform the following operation:

Select a robot on the number line. Let the coordinate of the robot be x. Select the destination coordinate, either x-1 or x-2, that is not occupied by another robot. The robot now jumps to the selected coordinate.

When the coordinate of a robot becomes 0 or less, the robot is considered finished and will be removed from the number line immediately.
You will repeat the operation until all the robots finish the race.

Depending on your choice in the operation, the N robots can finish the race in different orders.
In how many different orders can the N robots finish the race?
Find the answer modulo 10^9+7.

Constraints

2 ≤ N ≤ 10^5

x_i is an integer.

0 < x_1 < x_2 < ... < x_N ≤ 10^9

Partial Score

In a test set worth 500 points, N ≤ 8.

Input

The input is given from Standard Input in the following format:

N
x_1 x_2 ... x_N

Output

Print the number of the different orders in which the N robots can finish the race, modulo 10^9+7.

Sample Input 1

3
1 2 3

Sample Output 1

4

There are four different orders in which the three robots can finish the race:

(Robot 1 → Robot 2 → Robot 3)

(Robot 1 → Robot 3 → Robot 2)

(Robot 2 → Robot 1 → Robot 3)

(Robot 2 → Robot 3 → Robot 1)

Sample Input 2

3
2 3 4

Sample Output 2

6

There are six different orders in which the three robots can finish the race:

(Robot 1 → Robot 2 → Robot 3)

(Robot 1 → Robot 3 → Robot 2)

(Robot 2 → Robot 1 → Robot 3)

(Robot 2 → Robot 3 → Robot 1)

(Robot 3 → Robot 1 → Robot 2)

(Robot 3 → Robot 2 → Robot 1)

For example, the order (Robot 3 → Robot 2 → Robot 1) can be achieved as shown in the figure below:

Sample Input 3

8
1 2 3 5 7 11 13 17

Sample Output 3

10080

Sample Input 4

13
4 6 8 9 10 12 14 15 16 18 20 21 22

Sample Output 4

311014372

Remember to print the answer modulo 10^9+7.
This case is not included in the test set for the partial score.



Sample input:
3
1 2 3


Sample output:
4

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    assert N <= 8

    X = [int(i) for i in input().split()]

    cnt = 0
    MOD = 10**9 + 7

    for pm in permutations(range(N)):
        Xc = X[:]
        flag = True

        for p in pm:
            for i in range(p-1, -1, -1):
                if Xc[i] < 2*i + 1:
                    flag = False
                    break
            if flag:
                break
            Xc[p] = float('inf')

        cnt += flag

    print(cnt % MOD)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    assert N <= 8

    X = [int(i) for i in input().split()]

    cnt = 0
    MOD = 10**9 + 7

    for pm in permutations(range(N)):
        Xc = X[:]
        flag = True

        for p in pm:
            for i in range(p-1, 0, -1):
                if Xc[i] < 2*i + 1:
                    flag = False
                    break
            if flag:
                break
            Xc[p] = float('inf')
            k += 1

        cnt += flag

    print(cnt % MOD)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
 
def sampling_row(mat, row):
    row_str = copy.deepcopy(mat[row, :])
    return row_str
 
def writing_col(mat, row_str, col):
 
    row = 0
    for s in row_str:
        mat[row, col] = s
        row+=1
 
def check(mat, N):
    max_val = 0
    max_row = 0
    max_col = 0
    is_ok = True
    is_fast = True
    for i in range(N):
        for j in range(N):
            row = mat[i, :]
            col = mat[:, j]
            val = 0
 
            no_change = True
            for k in range(N):
                if row[k] == "#" and col[k] == ".":  
                    val += 1
                elif row[k] == "." and col[k] == "#":
                    val -= 1
                elif row[k] == "." and col[k] == ".":
                    val -= 1
                elif row[k] == "#" and col[k] == "#":
                    val -= 1

                if row[k] == "#" and col[k] == "#" and is_ok: 
                    pass
                else:
                    is_ok = False

                if row[k] == col[k] and no_change:
                    pass
                else:
                    no_change = False
 
            if (max_val < val and not(no_change)) or is_fast:
                max_val = val
                max_row = i
                max_col = j
                is_fast = False
 
    return (max_val, max_row, max_col, is_ok)
 
 
if __name__ == "__main__":
    mat_str = []
 
    N = raw_input()
    N = int(N)
    mat = np.zeros((N, N), str)
    for i in range(N):
        s = raw_input()
        for j in range(N):
            mat[i][j] = s[j]
 
    # row = sampling(mat, 0)
    # writing(mat, row, 1)
 
    is_ok = -1
 
    for s in mat.reshape(N*N):
        if s == "#":
            is_ok = 0
            break
 
    if is_ok != -1:
        while True:
            max_val, max_row, max_col, c_ok = check(mat, N)
            if c_ok == True:
                break
            else:
                writing_col(mat, sampling_row(mat, max_row), max_col)
                is_ok += 1
                print mat
                
    print is_ok

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    assert N <= 8

    X = [int(i) for i in input().split()]

    for i in range(N - 1):
        if X[i] + 1 == X[i + 1] and X[i] > 1 and X[i-1] < X[i] - 1:
            X[i] -= 1
    cnt = 0
    MOD = 10**9 + 7
    k = 0

    for pm in permutations(range(N)):
        Xc = X[:]
        flag = True

        for p in pm:
            for i in range(p-1, 0, -1):
                if Xc[i] == Xc[i - 1] + 1 and Xc[i - 1] == 1:
                    flag = False
                    break
            if flag:
                break
            Xc[p] = -(1 + 2*k)
            k += 1

        cnt += flag

        # if flag:
            # print(list(pm))

    print(cnt % MOD)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    assert N <= 8

    X = [int(i) for i in input().split()]

    for i in range(N - 1):
        if X[i] + 1 == X[i + 1] and X[i] > 1 and X[i-1] < X[i] - 1:
            X[i] -= 1
    cnt = 0
    MOD = 10**9 + 7
    k = 0

    for pm in permutations(range(N)):
        Xc = X[:]
        flag = True

        for p in pm:
            for i in range(p-1, 0, -1):
                if Xc[i] == Xc[i - 1] + 1 and Xc[i - 1] == 1:
                    flag = False
                    break
            if flag:
                break
            Xc[p] = -(1 + 2*i)
            k += 1

        cnt += flag

        # if flag:
            # print(list(pm))

    print(cnt % MOD)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    assert N <= 8

    X = [int(i) for i in input().split()]

    for i in range(N - 1):
        if X[i] + 1 == X[i + 1] and X[i] > 1 and X[i-1] < X[i] - 1:
            X[i] -= 1
    cnt = 0
    MOD = 10**9 + 7
    i = 0

    for pm in permutations(range(N)):
        Xc = X[:]
        flag = True

        for p in pm:
            for i in range(p-1, 0, -1):
                if Xc[i] == Xc[i - 1] + 1 and Xc[i - 1] == 1:
                    flag = False
                    break
            if flag:
                break
            Xc[p] = -(1 + 2*i)
            i += 1

        cnt += flag

        # if flag:
            # print(list(pm))

    print(cnt % MOD)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    assert N <= 8

    X = [int(i) for i in input().split()]

    for i in range(N - 1):
        if X[i] + 1 == X[i + 1] and X[i] > 1 and X[i-1] < X[i] - 1:
            X[i] -= 1
    cnt = 0
    MOD = 10**9 + 7

    for pm in permutations(range(N)):
        Xc = X[:]
        flag = True

        for p in pm:
            for i in range(p-1, 0, -1):
                if Xc[i] == Xc[i - 1] + 1 and Xc[i - 1] == 1:
                    flag = False
                    break
            if flag:
                break
            Xc[p] = -1

        cnt += flag

        # if flag:
            # print(list(pm))

    print(cnt % MOD)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import numpy as np
 

def change(a,i,j,n):
    b = a
    imask = (2**n-1) << i*n
    jmask = 0
    for k in range(n):
        jmask |= (1<<k*n+n-1-j)
    buf = (a & imask) >> i*n
    chg = 0
    for k in range(n)[::-1]:
        #print(bin(((buf&(1<<k))>>k)))
        #print(bin(((buf&(1<<k))>>k)<<k*n+n-1-j))
        chg |= (((buf&(1<<k))>>k)<<k*n+n-1-j)
    b = (b-(b&jmask)+chg)
    return b
                
          
n = int(input())
a = ''
for i in range(n):
    a += input()
a = a.replace('#','1')
a = a.replace('.','0')
a = '0b'+a
a = int(a, 2)
#print(a)

#n = 3
max = 2**(n**2)
#a = 0b000010000

dp = [2*n+1 for _ in range(max)]
dp[a] = 0
for _ in range(2*n-1):
    for dpi in range(max):
        for i in range(n):
            for j in range(n):
                b = change(dpi,i,j,n)
                dp[b] = min(dp[dpi]+1,dp[b])
if dp[-1] > 2*n:
    print(-1)
else:
    print(dp[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
A = [[0 if x == "." else 1 for x in input()] for i in range(N)]

if sum([sum(x) for x in A]) == 0:
    print(-1)
else:
    sum_list = [0] * N
    for i in range(N):
        s = 0
        for j in range(N):
            s += A[j][i]
        sum_list[i] = s

    count = N
    index = []
    flag2 = True
    for i in range(N):
        tmp = 0
        id = []
        flag1 = True
        for j in range(N):
            if A[i][j] == 1:
                continue
            elif sum_list[i] > 0:
                tmp += 1
                id.append(j)
            else:
                flag1 = False
                break

        if flag1:
            flag2 = False
            if tmp <= count:
                count = tmp
                index = id

        if count == 0:
            break

    if flag2:
        print(-1)
    else:
        result = 2 * count
        print(count, index)
        for i in range(N):
            if i not in index and sum_list[i] != N:
                result += 1

        print(result)

Submission status: Runtime Error

Solution code:
from math import factorial
N=int(input())
x_list=input().split()
x_list=[int(x) for x in x_list]
mod=10e9+7
ans=1
j=0
for n in range(N-1):
	for i, x in enumerate(x_list[n+j:-1]):
		if x<2*(i+j)+1:
			ans=(ans*(i+j+1))%(mod)
			j+=i
			break
	else:
		ans=(ans*factorial(N-n))%mod
		break
print(ans)

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_x = len(x) - xofs
    if num_of_x == 1:
        return 1
    elif num_of_x == 2:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return (num_of_x - 2 + 1) * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_x - 1 + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, x[xofs] - 2)

n = int(input())
x = list(map(int, input().split()))

print(rec(x, 0, 0) % (1000000000 + 7))

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_x = len(x) - xofs
    if num_of_x == 1:
        return 1
    elif num_of_x == 2:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return (num_of_x - 2 + 1) * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_x - 1 + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, min(x[xofs:]))

n = int(input())
x = list(map(int, input().split()))

if n <= 8:
    print(rec(x, 0, 0) % (1000000000 + 7))
else:
    print(1)

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_x = len(x) - xofs
    if num_of_x == 1:
        return 1
    elif num_of_x == 2:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return (num_of_x - 2 + 1) * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_x - 1 + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

if n <= 8:
    print(rec(x, 0, 0) % (1000000000 + 7))
else:
    print(1)

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_x = len(x) - xofs
    if num_of_x == 1:
        return 1
    elif num_of_x == 2:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return (num_of_x - 2) * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_x - 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

if n <= 8:
    print(rec(x, 0, 0) % (1000000000 + 7))
else:
    print(1)

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_rest_x = len(x) - (xofs + 1)
    if num_of_rest_x == 0:
        return 1
    elif num_of_rest_x == 1:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return num_of_rest_x * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_rest_x + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

if n <= 8:
    print(rec(x, 0, 0) % (1000000000 + 7))
else:
    print(1)

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_rest_x = len(x) - (xofs + 1)
    if num_of_rest_x == 0:
        return 1
    elif num_of_rest_x == 1:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return num_of_rest_x * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_rest_x + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

if n =< 8:
    print(rec(x, 0, 0) % (1000000000 + 7))
else:
    print(1)

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_rest_x = len(x) - (xofs + 1)
    if num_of_rest_x == 0:
        return 1
    elif num_of_rest_x == 1:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return num_of_rest_x * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_rest_x + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

print(rec(x, 0, 0) % (1000000000 + 7))

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_rest_x = len(x) - (xofs + 1)
    if num_of_rest_x == 0:
        return 1
    elif num_of_rest_x == 1:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return num_of_rest_x * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_rest_x + 1) * rec(x, xofs + 1, goal + 2)
    else:
        return rec(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

print(rec(x, 0, 0))

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_rest_x = len(x) - (xofs + 1)
    if num_of_rest_x == 0:
        return 1
    elif num_of_rest_x == 1:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return num_of_rest_x * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs] == goal + 2:
        return (num_of_rest_x + 1) * rec(x, xofs + 1, goal + 1)
    else:
        return rec(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

print(rec(x, 0, 0))

Submission status: Runtime Error

Solution code:
n = input()
X = map(int, raw_input().split())

if n > 10:
    exit(1)

cur = 1
for i in xrange(n):
    if cur <= X[i]:
        X[i] = cur
        cur += 2
    else:
        cur = X[i]+2

ALL = 2**n-1
memo = {}
def dfs(state):
    if state in memo:
        return memo[state]
    if state == ALL:
        return 1
    Y = X[:]
    cur = 1
    for i in xrange(n):
        if (state >> i) & 1:
            continue
        if cur <= Y[i]:
            Y[i] = cur
            cur += 2
        else:
            cur = Y[i]+2
    res = 0
    prev = -100
    for i in xrange(n):
        if (state >> i) & 1:
            continue
        res = (res + dfs(state | (1 << i))) % (10**9 + 7)
        if prev+1 == Y[i]:
            break
        prev = Y[i]
    memo[state] = res
    return res
print dfs(0)

Submission status: Runtime Error

Solution code:
def solve_loop(s):
    count = 0
    while len(s) > 1 and count < 100:
        s = solve(s)
        count += 1
    return s

def solve(s):
    for i in range(0, len(s)-1):
        if s[i] == s[i+1]:
            if s[i] == 'z':
                s = s.replace(s[i:i+2], '')
            else:
                next_chr = chr(ord(s[i])+1)
                s = s.replace(s[i:i+2], next_chr)
            return s
    return s



s = input()
q = int(input())

start = []
end = []
for i in range(0, q):
    _input = input()
    start.append(int(_input.split(' ')[0]))
    end.append(int(_input.split(' ')[1]))

for i in range(0, q):
    test_st = s[start[i]-1:end[i]]
    opt_str = solve_loop(test_st)
    if len(opt_str) == 0:
        print('YES')
    else:
        print('NO')

Submission status: Runtime Error

Solution code:
def rec(x, xofs, goal):
    num_of_rest_x = len(x) - (xofs + 1)
    if num_of_rest_x == 0:
        return 1
    elif num_of_rest_x == 1:
        return 2
    elif x[xofs] == goal + 1 and x[xofs + 1] == goal + 2:
        return num_of_rest_x * rec(x, xofs + 2, goal + 2) * 2
    elif x[xofs] == goal + 1 or x[xofs + 1] == goal + 2:
        return (num_of_rest_x + 1) * rec(x, xofs + 1, goal + 1)
    else:
        return(x, xofs, goal + 1)

n = int(input())
x = list(map(int, input().split()))

print(rec(x, 0, 0))