Problem:

Trampoline

  A plurality of trampolines are arranged in a line at 10 m intervals. Each trampoline has its own maximum horizontal distance within which the jumper can jump safely. Starting from the left-most trampoline, the jumper jumps to another trampoline within the allowed jumping range. The jumper wants to repeat jumping until he/she reaches the right-most trampoline, and then tries to return to the left-most trampoline only through jumping. Can the jumper complete the roundtrip without a single stepping-down from a trampoline?

  Write a program to report if the jumper can complete the journey using the list of maximum horizontal reaches of these trampolines. Assume that the trampolines are points without spatial extent.

Input

  The input is given in the following format.

N
d_1
d_2
:
d_N

The first line provides the number of trampolines N (2 ≤ N ≤ 3 &times; 105). Each of the subsequent N lines gives the maximum allowable jumping distance in integer meters for the i-th trampoline d_i (1 ≤ d_i ≤ 106).

Output

  Output "yes" if the jumper can complete the roundtrip, or "no" if he/she cannot.

Sample Input 1

4
20
5
10
1

Sample Output 1

no

Sample Input 2

3
10
5
10

Sample Output 2

no

Sample Input 3

4
20
30
1
20

Sample Output 3

yes



Sample input:
4
20
5
10
1


Sample output:
no

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
trs = [int(input()) for _ in range(n)]
cannot = False

visited = [False] * n
visited[0] = True
for i in range(n):
  if not visited[i]:
    cannot = True
  else:
    x = min(i + trs[i] // 10, n - 1)
    if not visited[x]:
      for j in range(i + 1, x + 1):
        visited[j] = True

visited = [False] * n
visited[n - 1] = True
for i in range(n - 1, -1, -1):
  if not visited[i]:
    cannot = True
  else:
    x = max(i - trs[i] // 10, 0)
    if not visited[x]:
      for j in range(i - 1, x - 1, -1):
        visited[j] = True

if cannot:
  print("no")
else:
  print("yes")

Submission status: Accepted

Solution code:
n = int(input())
d = [int(input()) for i in range(n)]
pos = 0
ans = "yes"
for i in range(n):
      if pos>=i*10:
            pos = max(pos,i*10+d[i])
      else:
            ans = "no"
            break
      if pos >= (n-1)*10:
            break
pos = 0
for i in range(n):
      if pos>=i*10:
            pos = max(pos,i*10+d[n-1-i])
      else:
            ans = "no"
            break
      if pos >= (n-1)*10:
            break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
j = 0
t = 10
for i in range(n):
    if j < i:
        print("no")
        break
    d = int(input())
    j += d // 10
    if d < t:
        t += 10
    elif d >= t:
        t = 10
else:
    if t == 10:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
trs = [int(input()) for _ in range(n)]
cum = []
cannot = False

acc = 0
for i in range(n):
  acc = max(acc, i + trs[i] // 10)
  acc = min(acc, n -  1)
  cum.append(acc)

rev = []
acc = 0
for i in range(n):
  acc = max(acc, i + trs[n - 1 - i] // 10)
  acc = min(acc, n - 1)
  rev.append(acc)

ind = 0
tmp = 0
while True:
  ind = cum[ind]
  if ind == n - 1:
    break
  if ind == tmp:
    cannot = True
    break
  tmp = ind

ind = 0
tmp = 0
while True:
  ind = rev[ind]
  if ind == n - 1:
    break
  if ind == tmp:
    cannot = True
    break
  tmp = ind

if cannot:
  print("no")
else:
  print("yes")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def judge():
    l = [10*i+d[i] for i in range(N)]
    
    for i in range(1, N):
        l[i] = max(l[i], l[i-1])
    
    now = 0
    
    for _ in range(N-1):
        now = l[now//10]
        
        if now>=10*(N-1):
            return True
    
    return False

N = int(input())
d = [int(input()) for _ in range(N)]

if judge():
    d.reverse()
    
    if judge():
        print('yes')
        exit()

print('no')

Submission status: Accepted

Solution code:
N = int(input())
a = []
for i in range(N):
    a.append(int(input())//10)
    
max_dist = 0

for i in range(N):
    if max_dist >= i:
        max_dist = max(max_dist, i + a[i])

if max_dist >= N-1:
    max_dist = 0
    for i in range(N):
        if max_dist >= i:
            max_dist = max(max_dist, i + a[N-1-i])

    if max_dist >= N-1:
        print("yes")
    else:
        print("no")

else:
    print("no")

Submission status: Accepted

Solution code:
n = int(input())
d = [int(input())for i in range(n)]
ok1 = True
nowmx = 0
for i in range(n-1):
    if i > nowmx:
        ok1 = False
        break
    x = i+d[i]//10#いける右端のトランポリ
    if x >= nowmx:
        nowmx = x
   
if nowmx < n-1:ok1 = False
d = d[::-1]
ok2 = True
nowmx = 0
for i in range(n-1):
    if i > nowmx:        
        ok2 = False
        break
    x = i+d[i]//10#いける右端のトランポリン
    if x >= nowmx:
        nowmx = x
  
if nowmx < n-1:ok2 = False
if ok1 and ok2:print('yes')
else:print('no')

Submission status: Accepted

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

ok = True
rg = range(n)
l = 0
for i,d in zip(rg,a):
    if i*10 > l:
        ok = False
        break
    if l >= (n-1)*10:
        break
    if i*10+d > l:
        l = i*10+d

a.reverse()
l = 0
for i,d in zip(rg,a):
    if i*10 > l:
        ok = False
        break
    if l >= (n-1)*10:
        break
    if i*10+d > l:
        l = i*10+d

if ok:
    print('yes')
else:
    print('no')

Submission status: Accepted

Solution code:
N, *D = map(int, open(0).read().split())
ok = 1
e = 0
for i in range(N):
    if e < i:
        ok = 0
    e = max(e, i+D[i]//10)
e = N-1
for i in range(N-1, -1, -1):
    if e > i:
        ok = 0
    e = min(e, i-D[i]//10)
print("yes" if ok else "no")

Submission status: Accepted

Solution code:
n = 0
bounce = []

def IsReachable() :
    current = 0
    for i in range(n) :
        if current < 10*i : return False
        current = max( current, 10*i + bounce[i] )
        if current >= 10*n : return True
    return False

n = int(input())
for i in range(n) :
    bounce.append( int(input()) )

if not IsReachable() : print("no")
else :
    bounce.reverse()
    if IsReachable() : print("yes")
    else : print("no")

Submission status: Runtime Error

Solution code:
fi = int(input())
tramp = [int(input()) for i in range(fi)]
is_reachable = [0 for i in range(fi)]


def jump(n):
    is_reachable[n] = 1
    if n == fi:
        return
    for j in range(min(tramp[n] // 10, fi-n-1)):
        if not is_reachable[n+j+1]:
            jump(n+j+1)


jump(0)
if not is_reachable[-1]:
    print("no")
    exit()

tramp = tramp[::-1]
is_reachable = [0 for i in range(fi)]
jump(0)

if not is_reachable[-1]:
    print("no")
    exit()

print("yes")