Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

環状すごろく

  ユキさんは、子供会の催しでみんなで遊べるようにすごろくを作りました。このすごろくでは、環状にマスが並んでいて、それぞれのマスには１以上の整数が書いてあります。

  プレイヤーは出発点としてどこかのマスを選んで自分の駒を置きます。そのマスに書いてある数だけ、時計回りに駒を進めます。止まったマスに書いてある数だけ、再び時計回りに駒を進めます。これを繰り返して、出発点に選んだマスの上で駒が止まったら「あがり」です。

  実際には、マスの選び方によっては絶対に「あがり」にならない場合もあります。ユキさんは、このすごろくで「あがり」にたどり着けるマスの個数を数えようとしています。

すごろくの情報を入力とし、「あがり」にたどり着けるマスの個数を報告するプログラムを作成せよ。

Input

  入力は以下の形式で与えられる。

N
a1 a2 ... aN

１行目にすごろくに含まれるすべてのマスの個数 N (1 ≤ N ≤ 100000) が与えられる。２行目に、それぞれのマスに書かれた数 ai (1 ≤ ai ≤ 109) が、時計回りに順番に与えられる。

Output

「あがり」にたどり着けるマスの個数を１行に出力する。

Sample Input 1

3
1 1 1

Sample Output 1

3

Sample Input 2

3
1 1 2

Sample Output 2

2

Sample Input 3

8
2 3 7 3 3 3 4 4

Sample Output 3

6



Sample input:
3
1 1 1


Sample output:
3

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
edges = [[] for _ in range(n)]
rev_edges = [[] for _ in range(n)]
for i in range(n):
  edges[i].append((i + alst[i]) % n)
  rev_edges[(i + alst[i]) % n].append(i)

def dfs(x, ret, edges, visited):
  visited[x] = True
  for e in edges[x]:
    if not visited[e]:
      dfs(e, ret, edges, visited)
  ret.append(x)

def dfs_rev(x, cycles, rev_edges, visited):
  visited[x] = True
  flag = False
  for e in rev_edges[x]:
    if not visited[e]:
      cycles.add(e)
      dfs_rev(e, cycles, rev_edges, visited)
      flag = True
  if flag:
    cycles.add(x)

order = []
visited = [False] * n
for i in range(n):
  if not visited[i]:
    dfs(i, order, edges, visited)

order.reverse()

visited = [False] * n
cycles = set()
for i in order:
  if not visited[i]:
    dfs_rev(i, cycles, rev_edges, visited)
print(len(cycles))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(x, order, edges, visited):
  visited[x] = True
  for e in edges[x]:
    if not visited[e]:
      dfs(e, order, edges, visited)
  order.append(x)

def dfs_rev(x, rev_edges, visited):
  visited[x] = True
  ret = 0
  for e in rev_edges[x]:
    if not visited[e]:
      ret += 1
      ret += dfs_rev(e, rev_edges, visited)
    elif e == x:
      ret += 1
  return ret


n = int(input())
alst = list(map(int, input().split()))
edges = [[] for _ in range(n)]
rev_edges = [[] for _ in range(n)]
for i in range(n):
  edges[i].append((i + alst[i]) % n)
  rev_edges[(i + alst[i]) % n].append(i)

order = []
visited = [False] * n
for i in range(n):
  if not visited[i]:
    dfs(i, order, edges, visited)
order.reverse()

visited = [False] * n
cycles = 0
for i in order:
  if not visited[i]:
    a = dfs_rev(i, rev_edges, visited)
    if a > 0 or i in rev_edges[i]:
      a += 1
    cycles += a
print(cycles)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = list(map(int,input().split()))

c = [False for _ in range(n)]

for i in range(n):
    t = [False for _ in range(n)]

    if c[i]:
        continue

    j = i
    while True:
        if t[j]:
            break
        t[j] = True
        j = (j + d[j]) % n

    if i == j:
        for j in range(n):
            c[j] = c[j] | t[j]


sum = 0
for i in range(n):
    if c[i]:
        sum += 1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = list(map(int,input().split()))
c = [False for _ in range(n)]

for i in range(n):

    if c[i]:
        continue

    j = i
    t = [False for _ in range(n)]
    while True:
        if t[j]:
            break
        else:
            t[j] = True
            j = (j + d[j]) % n

    if i == j:
        for j in range(n):
            c[j] = c[j] | t[j]


sum = 0
for i in range(n):
    if c[i]:
        sum += 1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = list(map(int,input().split()))
c = [False for _ in range(n)]

for i in range(n):

    if c[i]:
        continue

    j = i
    t = [False for _ in range(n)]
    while True:
        if t[j]:
            break
        else:
            t[j] = True
            j = (j + d[j]) % n

    if i == j:
        for j in range(n):
            c[j] = c[j] | t[j]
    else:
        c[j] = True

sum = 0
for i in range(n):
    if c[i]:
        sum += 1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import dropwhile

n = int(input())
d = list(map(int,input().split()))
c = set([])

for i in range(n):

    if i in c:
        continue

    j = i
    t = []
    while True:
        if j in t:
            break
        else:
            t.append(j)
            j = (j + d[j]) % n

#    print("i={0},j={1}".format(i,j))
    if i == j:
        c = c.union(t)
    else:
#        print("t={0}".format(t))
        tt = dropwhile(lambda x: x != j, t)
        c = c.union(tt)

print( len(c) )

Submission status: Time Limit Exceeded

Solution code:
#from itertools import dropwhile

n = int(input())
d = list(map(int,input().split()))
c = set()

for i in range(n):

    if i in c:
        continue

    j = i
    t = []
    while True:
        if j in c:
            break
        elif j in t:
            #    print("i={0},j={1}".format(i,j))
            if i == j:
                c = c.union(t)
#            else:
#                #        print("t={0}".format(t))
#                tt = dropwhile(lambda x: x != j, t)
#                c = c.union(tt)
            break
        else:
            t.append(j)
            j = (j + d[j]) % n
print( len(c) )

Submission status: Time Limit Exceeded

Solution code:
from itertools import dropwhile

n = int(input())
d = list(map(int,input().split()))
c = set()

for i in range(n):

    if i in c:
        continue

    j = i
    t = []
    while True:
        if j in c:
            break
        elif j in t:
            #    print("i={0},j={1}".format(i,j))
            if i == j:
                c = c.union(t)
            else:
                #        print("t={0}".format(t))
                tt = dropwhile(lambda x: x != j, t)
                c = c.union(tt)
            break
        else:
            t.append(j)
            j = (j + d[j]) % n
print( len(c) )

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())

l = [0]*n
for i in range(n):
    if l[i] == 0:
        s = set()
        p = i
        can = 1
        while p not in s:
            if l[p] == 1:
                can = 0
                break
            s.add(p)
            l[p] = 1
            p = (p + A[p]) % n
        if can:
            while l[p] == 1:
                l[p] = 2
                p = (p + A[p]) % n
print(sum(e == 2 for e in l))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
alst = list(map(int, input().split()))
edges = [[] for _ in range(n)]
rev_edges = [[] for _ in range(n)]
for i in range(n):
  edges[i].append((i + alst[i]) % n)
  rev_edges[(i + alst[i]) % n].append(i)

def dfs(x, ret, edges, visited):
  visited[x] = True
  for e in edges[x]:
    if not visited[e]:
      dfs(e, ret, edges, visited)
  ret.append(x)

def dfs_rev(x, cycles, rev_edges, visited):
  visited[x] = True
  flag = False
  for e in rev_edges[x]:
    if not visited[e]:
      cycles.add(e)
      dfs_rev(e, cycles, rev_edges, visited)
      flag = True
    elif x == e:
      flag = True
  if flag:
    cycles.add(x)

order = []
visited = [False] * n
for i in range(n):
  if not visited[i]:
    dfs(i, order, edges, visited)
order.reverse()

visited = [False] * n
cycles = set()
for i in order:
  if not visited[i]:
    dfs_rev(i, cycles, rev_edges, visited)
print(len(cycles))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(x, order, edges, visited):
  visited[x] = True
  for e in edges[x]:
    if not visited[e]:
      dfs(e, order, edges, visited)
  order.append(x)

def dfs_rev(x, rev_edges, visited):
  visited[x] = True
  ret = 0
  for e in rev_edges[x]:
    if not visited[e]:
      ret += 1
      ret += dfs_rev(e, rev_edges, visited)
  return ret


n = int(input())
alst = list(map(int, input().split()))
edges = [[] for _ in range(n)]
rev_edges = [[] for _ in range(n)]
for i in range(n):
  edges[i].append((i + alst[i]) % n)
  rev_edges[(i + alst[i]) % n].append(i)

order = []
visited = [False] * n
for i in range(n):
  if not visited[i]:
    dfs(i, order, edges, visited)
order.reverse()

visited = [False] * n
cycles = 0
for i in order:
  if not visited[i]:
    a = dfs_rev(i, rev_edges, visited)
    if a > 0 or i in rev_edges[i]:
      a += 1
    cycles += a
print(cycles)

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

Submission status: Runtime Error

Solution code:
n = int(input())
alst = list(map(int, input().split()))
edges = [[] for _ in range(n)]
rev_edges = [[] for _ in range(n)]
for i in range(n):
  edges[i].append((i + alst[i]) % n)
  rev_edges[(i + alst[i]) % n].append(i)

def dfs(x, ret, edges, visited):
  visited[x] = True
  for e in edges[x]:
    if not visited[e]:
      dfs(e, ret, edges, visited)
  ret.append(x)

def dfs_rev(x, cycles, rev_edges, visited):
  visited[x] = True
  flag = False
  for e in rev_edges[x]:
    if not visited[e]:
      cycles.add(e)
      dfs_rev(e, cycles, rev_edges, visited)
      flag = True
    elif x == e:
      flag = True
  if flag:
    cycles.add(x)

order = []
visited = [False] * n
for i in range(n):
  if not visited[i]:
    dfs(i, order, edges, visited)

order.reverse()

visited = [False] * n
cycles = set()
for i in order:
  if not visited[i]:
    dfs_rev(i, cycles, rev_edges, visited)
print(len(cycles))