Problem:


すごろくを作る

太郎君は、子供会の催しでみんなで遊べるようにすごろくを作りました。ゲームをおもしろくするために、「ふりだし」と「あがり」以外のすごろくのマスのいくつかに「６つ進む」、「５つ戻る」のように指示を書き込んでいきました。ルーレットを回して出た数だけ進み、止まったマスに指示が書き込んであれば、その指示に従って移動します。ただし、指示に従って進んだ先のマスの指示には従いません。

ルーレットは１からある数までの間の数を等確率で出すことができるものとします。また、「あがり」に達するより大きな数が出たときや、指示に従うと「あがり」より先に進んでしまうときは「あがり」に移動します。指示に従って戻るときに「ふりだし」より前に戻ってしまうときは「ふりだし」に戻ることにします。

ところが、ルーレットとマスの指示によっては「あがり」にたどりつけない場合が出てきてしまいます。たとえば、図のようなすごろくを作ったとしましょう。１と２しか出ないルーレットを使うと、１，２の順に出れば「あがり」に行けますが、はじめに２が出たらその後は何が出ても永久に「あがり」にはたどり着けません。太郎君は、そうとは知らずに調子に乗ってあちこちのマスに指示を書き込んでしまいました。

そこで、太郎君に代わって、ルーレットとマスの指示によっては、「あがり」にたどり着けない場合が生じるかどうか判定するプログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。

max
n
d1
d2
.
.
.
dn

１行目にルーレットが出す数の最大値 max (2 ≤ max ≤ 250) が与えられ、２行目に「ふりだし」と「あがり」以外のマスの数 n (2 ≤ n ≤ 250) が与えられる。続く n 行に各マスの指示を表す数 di(-n ≤ di ≤ n) が与えられる。di がゼロのときは指示が書いていないことを、正の数のときは |di| 進む指示を、負の数のときは |di| 戻る指示を表す（ここで、|x| は x の絶対値を表す）。入力される値はすべて整数である。

データセットの数は 100 を超えない。

出力

各データセットごとに判定結果を１行に出力する。ルーレットとマスの指示によっては、「あがり」にたどり着けない場合が生じるときは「NG」、そうでなければ「OK」を出力する。

入力例

3
3
-2
1
0
2
4
2
0
-1
-2
2
2
-2
-2
0

出力例

OK
NG
NG



Sample input:
3
3
-2
1
0
2
4
2
0
-1
-2
2
2
-2
-2
0


Sample output:
OK
NG
NG

Submission status: Wrong Answer

Solution code:
def reachable(graph, init):
    if init not in graph or graph[init] is None:
        return set()
    
    tmp,  graph[init] = graph[init], None

    return tmp.union(* [reachable(graph, i) for i in tmp])

def sugoroku(m, d):
    d = [0] + d + [0]
    start, goal = 0, len(d) - 1

    graph_to = {goal:{goal}}
    graph_from = {start:{start}}
    
    for init in range(len(d) - 1):
        for xi in range(1, 1 + m):
            pos = min(init + xi, goal)
            to = max(start, pos + d[pos])
            try:
                graph_to[to].add(init)
            except KeyError:
                graph_to[to] = {init}
            try:
                graph_from[init].add(to)
            except KeyError:
                graph_from[init] = {to}                
    
    unreachable_node = reachable(graph_from, start).difference(reachable(graph_to, goal))
    
    return 0 == len(unreachable_node)

import sys
f = sys.stdin

while True:
    m = int(f.readline())
    if m == 0:
        break
    d = [int(f.readline()) for _ in range(int(f.readline()))]
    print('OK' if sugoroku(m, d) else 'NG')

Submission status: Wrong Answer

Solution code:
def sugoroku(m, d):
    d = [0] + d + [0]
    start, goal = 0, len(d) - 1

    g = [[0 for j in range(len(d))] for i in range(len(d))]
    for i in range(len(d) - 1):
        for mi in range(m + 1):
            pos = min(goal, i + mi)
            pos = max(start, pos + d[pos])
            g[i][pos] = 1

    for i in range(len(d)):
        for j in range(len(d)):
            for k in range(len(d)):
                if g[i][j] and g[j][k]:
                    g[i][k]
    
    for i in range(len(d)):
        if g[start][i] and not g[i][goal]:
            return False
    return True

import sys
f = sys.stdin

while True:
    m = int(f.readline())
    if m == 0:
        break
    d = [int(f.readline()) for _ in range(int(f.readline()))]
    print('OK' if sugoroku(m, d) else 'NG')

Submission status: Wrong Answer

Solution code:
while 1:
    m = int(input())
    if m == 0:break
    n = int(input())
    d = [int(input()) for _ in range(n)]
    if n < m:print("OK")
    for i in range(m):
        if d[- i - 1] > - m + i:break
    else:
        print("NG")
        continue
    print("OK")

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000

def solve(dmax, arr):
    arr.insert(0, 0)
    arr.append(0)
    n = len(arr)
    graph = [[inf for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        graph[i][i] = 0

    for s in range(n):
        for d in range(1, dmax + 1):
            next = min(max(0, s + d), n - 1)
            next += arr[next]
            next = min(max(0, next), n - 1)
            graph[s][next] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] < inf and graph[k][j] < inf:
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    for i in range(0, n - 1):
        if graph[0][i] < inf and graph[i][n - 1] == inf:
            print("NG")
            return
    print("OK")

def main():
    while True:
        dmax = int(input())
        if dmax == 0:
            return
        n = int(input())
        arr = [int(input()) for _ in range(n)]
        solve(dmax, arr)
        

main()

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000

def solve(dmax, arr):
    arr.insert(0, 0)
    arr.append(0)
    n = len(arr)
    graph = [[False for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        graph[i][i] = True

    for s in range(n):
        for d in range(1, dmax + 1):
            next = min(max(0, s + d), n - 1)
            next += arr[next]
            next = min(max(0, next), n - 1)
            graph[s][next] = True

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] < inf and graph[k][j] < inf:
                    graph[i][j] |= graph[i][k] and graph[k][j]
                    
    for i in range(0, n - 1):
        if graph[0][i] and (not graph[i][n - 1]):
            print("NG")
            return
    print("OK")

def main():
    while True:
        dmax = int(input())
        if dmax == 0:
            return
        n = int(input())
        arr = [int(input()) for _ in range(n)]
        solve(dmax, arr)
        

main()

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000

def graph_set(g, i, j, v):
    g[i][j >> 5] |= v << (j & 31)

def graph_set1(g, i, j):
    graph_set(g, i, j, 1)

def graph_get(g, i, j):
    return (g[i][j >> 5] >> (j & 31)) & 1

def solve(dmax, arr):
    arr.insert(0, 0)
    arr.append(0)
    n = len(arr)
    g = [[0 for _ in range(int((n + 31) / 32))] for _ in range(n)]
    
    for i in range(n):
        graph_set1(g, i, i)

    for s in range(n):
        for d in range(1, dmax + 1):
            next = min(max(0, s + d), n - 1)
            next += arr[next]
            next = min(max(0, next), n - 1)
            graph_set1(g, s, next)

    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph_set(g, i, j, 
                          graph_get(g, i, j) | graph_get(g, i, k) & graph_get(g, k, j))
                    
    for i in range(0, n - 1):
        if graph_get(g, 0, i) and (not graph_get(g, i, n - 1)):
            print("NG")
            return
    print("OK")

def main():
    while True:
        dmax = int(input())
        if dmax == 0:
            return
        n = int(input())
        arr = [int(input()) for _ in range(n)]
        solve(dmax, arr)
        

main()

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000

def graph_set(g, i, j, v):
    g[i][j >> 5] |= v << (j & 31)

def graph_set1(g, i, j):
    graph_set(g, i, j, 1)

def graph_get(g, i, j):
    return (g[i][j >> 5] >> (j & 31)) & 1

def solve(dmax, arr):
    arr.insert(0, 0)
    arr.append(0)
    n = len(arr)
    g = [[False for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        g[i][i] = True

    for s in range(n):
        for d in range(1, dmax + 1):
            next = min(max(0, s + d), n - 1)
            next += arr[next]
            next = min(max(0, next), n - 1)
            g[s][next] = True

    visited = [[False for _ in range(n)] for _ in range(n)]
    def dfs(i, t):
        if i == t:
            return True
        elif visited[i][t]:
            return g[i][t]
        visited[i][t] = True
        for j in range(n):
            if g[i][j] and dfs(j, t):
                g[i][t] = True
                return True
        return False
                    
    for i in range(n):
        for j in range(n):
            dfs(i, j)


    for i in range(0, n - 1):
        if g[0][i] and (not g[i][n - 1]):
            print("NG")
            return
    print("OK")

def main():
    while True:
        dmax = int(input())
        if dmax == 0:
            return
        n = int(input())
        arr = [int(input()) for _ in range(n)]
        solve(dmax, arr)
        

main()

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000

def graph_set(g, i, j, v):
    g[i][j >> 5] |= v << (j & 31)

def graph_set1(g, i, j):
    graph_set(g, i, j, 1)

def graph_get(g, i, j):
    return (g[i][j >> 5] >> (j & 31)) & 1

def solve(dmax, arr):
    arr.insert(0, 0)
    arr.append(0)
    n = len(arr)
    g = [[False for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        g[i][i] = True

    for s in range(n):
        for d in range(1, dmax + 1):
            next = min(max(0, s + d), n - 1)
            next += arr[next]
            next = min(max(0, next), n - 1)
            g[s][next] = True

    visited = [[False for _ in range(n)] for _ in range(n)]
    def dfs(i, t):
        if i == t:
            return True
        elif visited[i][t]:
            return g[i][t]
        visited[i][t] = True
        for j in range(n):
            if g[i][j] and not visited[j][t] and dfs(j, t):
                g[i][t] = True
                return True
        return False
                    
    for i in range(n):
        for j in range(n):
            dfs(i, j)

    for i in range(0, n - 1):
        if g[0][i] and (not g[i][n - 1]):
            print("NG")
            return
    print("OK")

def main():
    while True:
        dmax = int(input())
        if dmax == 0:
            return
        n = int(input())
        arr = [int(input()) for _ in range(n)]
        solve(dmax, arr)
        

main()

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000

def graph_set(g, i, j, v):
    g[i][j >> 5] |= v << (j & 31)

def graph_set1(g, i, j):
    graph_set(g, i, j, 1)

def graph_get(g, i, j):
    return (g[i][j >> 5] >> (j & 31)) & 1

def solve(dmax, arr):
    arr.insert(0, 0)
    arr.append(0)
    n = len(arr)
    g = [[False for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        g[i][i] = True

    for s in range(n):
        for d in range(1, dmax + 1):
            next = min(max(0, s + d), n - 1)
            next += arr[next]
            next = min(max(0, next), n - 1)
            g[s][next] = True

    visited = [[False for _ in range(n)] for _ in range(n)]
    memo = [[None for _ in range(n)] for _ in range(n)]

    def dfs(s, i, t):
        if i == t:
            return True
        if visited[i][t]:
            return False
        if memo[i][t] != None:
            return memo[i][t]
        visited[i][t] = True
        memo[s][i] = True

        for j in range(n):
            if g[i][j] and not visited[j][t] and dfs(s, j, t):
                g[i][t] = True
                return True
        memo[i][t] = False
        g[i][t] = False
        return False
                    
    for i in range(n):
        for j in range(n):
            if dfs(i, i, j):
                g[i][j] = True
        
    for i in range(0, n - 1):
        if g[0][i] and (not g[i][n - 1]):
            print("NG")
            return
    print("OK")

def main():
    while True:
        dmax = int(input())
        if dmax == 0:
            return
        n = int(input())
        arr = [int(input()) for _ in range(n)]
        solve(dmax, arr)
        

main()

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000

def graph_set(g, i, j, v):
    g[i][j >> 5] |= v << (j & 31)

def graph_set1(g, i, j):
    graph_set(g, i, j, 1)

def graph_get(g, i, j):
    return (g[i][j >> 5] >> (j & 31)) & 1

def solve(dmax, arr):
    arr.insert(0, 0)
    arr.append(0)
    n = len(arr)
    g = [[False for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        g[i][i] = True

    for s in range(n):
        for d in range(1, dmax + 1):
            next = min(max(0, s + d), n - 1)
            next += arr[next]
            next = min(max(0, next), n - 1)
            g[s][next] = True

    visited = [[False for _ in range(n)] for _ in range(n)]
    memo = [[None for _ in range(n)] for _ in range(n)]

    def dfs(s, i, t):
        if i == t:
            return True
        if visited[i][t]:
            return False
        if memo[i][t] != None:
            return memo[i][t]
        visited[i][t] = True
        memo[s][i] = True

        for j in range(n):
            if g[i][j] and not visited[j][t] and dfs(i, j, t):
                g[i][t] = True
                g[s][t] = True
                memo[s][t] = True
                return True
        memo[i][t] = False
        g[i][t] = False
        return False
                    
    for i in range(n):
        for j in range(n):
            if dfs(i, i, j):
                g[i][j] = True
        
    for i in range(0, n - 1):
        if g[0][i] and (not g[i][n - 1]):
            print("NG")
            return
    print("OK")

def main():
    while True:
        dmax = int(input())
        if dmax == 0:
            return
        n = int(input())
        arr = [int(input()) for _ in range(n)]
        solve(dmax, arr)
        

main()

Submission status: Accepted

Solution code:
def reachable(graph, init):
    if init not in graph or graph[init] is None:
        return set()
    
    tmp,  graph[init] = graph[init], None

    return tmp.union(* [reachable(graph, i) for i in tmp])

def sugoroku(m, d):
    d = [0] + d + [0]
    start, goal = 0, len(d) - 1

    graph_to = {goal:{goal}}
    graph_from = {start:{start}}
    
    for init in range(len(d) - 1):
        for xi in range(1, 1 + m):
            pos = min(init + xi, goal)
            to = max(start, min(pos + d[pos],goal))
            try:
                graph_to[to].add(init)
            except KeyError:
                graph_to[to] = {init}
            try:
                graph_from[init].add(to)
            except KeyError:
                graph_from[init] = {to}
    
    unreachable_node = reachable(graph_from, start).difference(reachable(graph_to, goal))
    
    return 0 == len(unreachable_node)

import sys
f = sys.stdin

while True:
    m = int(f.readline())
    if m == 0:
        break
    d = [int(f.readline()) for _ in range(int(f.readline()))]
    print('OK' if sugoroku(m, d) else 'NG')

Submission status: Accepted

Solution code:
while True:
    m = int(input())
    if not m:
        break
    n = int(input())
    ds = [0] + [int(input()) for _ in range(n)] + [0]

    g = [[] for _ in range(n+2)]
    rg = [[] for _ in range(n+2)]
    for i in range(n+2):
        for j in range(min(n+1,i+1),min(n+1,i+m)+1):
            j = max(0,min(n+1,j+ds[j]))
            g[i].append(j)
            rg[j].append(i)
    
    def go(g,bs,i):
        bs[i] = True
        for j in g[i]:
            if not bs[j]:
                go(g,bs,j)
    
    bs = [False]*(n+2)
    rbs = [False]*(n+2)
    go(g,bs,0)
    go(rg,rbs,n+1)

    if any((b and (not rb)) for b,rb in zip(bs,rbs)):
        print('NG')
    else:
        print('OK')

Submission status: Accepted

Solution code:
from collections import deque
while 1:
    M = int(input())
    if M == 0:
        break
    N = int(input())
    D = [0] + [int(input()) for i in range(N)] + [0]
    G = [[] for i in range(N+2)]

    u = [0]*(N+2)
    que = deque([0])
    u[0] = 1
    while que:
        v = que.popleft()
        for j in range(1, M+1):
            if D[min(v+j, N+1)] != 0:
                to = max(min(v+j+D[v+j], N+1), 0)
            else:
                to = min(v+j, N+1)
            if not u[to]:
                que.append(to)
                u[to] = 1
            G[to].append(v)

    z = [0]*(N+2)
    que = deque([N+1])
    z[N+1] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            if z[w]:
                continue
            z[w] = 1
            que.append(w)
    print("OK" if u == z else "NG")

Submission status: Accepted

Solution code:
import queue

while True:
    m = int(input())
    if m == 0:
        break
    n = int(input())
    d = [0]*(n+2)
    for i in range(1,n+1):
        d[i] = int(input())
    visited = [False]*(n+2)
    visited[0] = True
    ok = [False]*(n+2)
    ok[n+1] = True
    rev = [[] for _ in range(n+2)]
    
    que = queue.LifoQueue()
    que.put(0)
    while not que.empty():
        i = que.get()
        for j in range(1,m+1):
            if i+j > n+1:
                break
            k = min(max(i+j+d[i+j], 0), n+1)
            rev[k].append(i)
            if not visited[k]:
                que.put(k)
                visited[k] = True

    que.put(n+1)
    while not que.empty():
        i = que.get()
        for j in rev[i]:
            if not ok[j]:
                ok[j] = True
                que.put(j)

    ans = 'OK'
    if not visited[n+1]:
        ans = 'NG'
    for i in range(n+1):
        if visited[i] and (not ok[i]):
            ans = 'NG'
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

def bfs(adj_list, s):
    q = deque([s])
    visited = [False]*(n+2)
    visited[s] = True
    
    while q:
        v = q.popleft()
        
        for nv in adj_list[v]:
            if not visited[nv]:
                visited[nv] = True
                q.append(nv)

    return visited

while True:
    m = int(input())
    
    if m==0:
        break
    
    n = int(input())
    d = [int(input()) for _ in range(n)]
    adj_list = [[] for _ in range(n+2)]
    rev_adj_list = [[] for _ in range(n+2)]
    
    for i in range(n+1):
        for j in range(1, m+1):
            if i+j>n:
                adj_list[i].append(n+1)
                rev_adj_list[n+1].append(i)
            else:
                t = min(n+1, max(i+j+d[i+j-1], 0))
                adj_list[i].append(t)
                rev_adj_list[t].append(i)
    
    visited_1 = bfs(adj_list, 0)
    visited_2 = bfs(rev_adj_list, n+1)
    
    for i in range(n+2):
        if visited_1[i] and not visited_2[i]:
            print('NG')
            break
    else:
        print('OK')

Submission status: Accepted

Solution code:
def search(x, visited, edges):
  if visited[x]:
    return

  visited[x] = True
  for to in edges[x]:
    search(to, visited, edges)

def main():
  while True:
    m = int(input())
    if m == 0:
      break
    n = int(input())
    mp = [0] + [int(input()) for _ in range(n)] + [0]
    visited = [False] * (n + 2)
    rev_visited = [False] * (n + 2)
    edges = [[] for _ in range(n + 2)]
    rev_edges = [[] for _ in range(n + 2)]
    for i in range(n + 2):
      for j in range(1, m + 1):
        nex = i + j
        nex = min(nex, n + 1)
        nex += mp[nex]
        nex = min(nex, n + 1)
        nex = max(nex, 0)
        edges[i].append(nex)
        rev_edges[nex].append(i)
  
    search(0, visited, edges)
    search(n + 1, rev_visited, rev_edges)
    for node in range(n + 1):
      if visited[node] and not rev_visited[node]:
        print("NG")
        break
    else:
      print("OK")

main()

Submission status: Runtime Error

Solution code:
def sugoroku(m, d):
    d = [0] + d + [0]
    start, goal = 0, len(d) - 1

    g = [[0 for j in range(len(d))] for i in range(len(d))]
    for i in range(len(d) - 1):
        for mi in range(1, m + 1):
            pos = min(goal, i + mi)
            pos = max(start, pos + d[pos])
            g[i][pos] = 1

    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                if g[i][k] and g[k][j]:
                    g[i][j] = 1
    
    for i in range(len(d) - 1):
        if g[start][i] and not g[i][goal]:
            return False
    return True

import sys
f = sys.stdin


while True:
    m = int(f.readline())
    if m == 0:
        break
    d = [int(f.readline()) for _ in range(int(f.readline()))]
    print('OK' if sugoroku(m, d) else 'NG')