結果

問題 No.308 素数は通れません
ユーザー gew1fw
提出日時 2025-06-12 20:34:00
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,688 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,972 KB
実行使用メモリ 119,184 KB
最終ジャッジ日時 2025-06-12 20:35:06
合計ジャッジ時間 9,781 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31 WA * 27 TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import isqrt

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def main():
    N = int(sys.stdin.readline().strip())
    if N == 1:
        print(1)
        return

    W = 1
    while True:
        blocked = set()
        for k in range(1, N+1):
            if is_prime(k):
                blocked.add(k)
        
        from collections import deque
        visited = set()
        q = deque()
        q.append(1)
        visited.add(1)
        found = False
        while q:
            current = q.popleft()
            if current == N:
                found = True
                break
            row = (current - 1) // W
            col = (current - 1) % W
            neighbors = []
            # Check up
            if row > 0:
                up = current - W
                if up >= 1 and up <= N:
                    neighbors.append(up)
            # Check down
            if current + W <= N:
                down = current + W
                neighbors.append(down)
            # Check left
            if col > 0:
                left = current - 1
                if left >= 1 and left <= N:
                    neighbors.append(left)
            # Check right
            if col < W - 1:
                right = current + 1
                if right <= N:
                    neighbors.append(right)
            # For the last row, handle the R columns
            H = N // W
            R = N % W
            if R != 0:
                if row == H:
                    if col >= R:
                        if current + 1 <= N:
                            neighbors.append(current + 1)
                        if current - 1 >= 1:
                            neighbors.append(current - 1)
                        if current - W >= 1:
                            neighbors.append(current - W)
                        if current + W <= N:
                            neighbors.append(current + W)
                    else:
                        if current + 1 <= N:
                            neighbors.append(current + 1)
                        if current - 1 >= 1:
                            neighbors.append(current - 1)
                        if current - W >= 1:
                            neighbors.append(current - W)
                        if current + W <= N:
                            neighbors.append(current + W)
                else:
                    if current + 1 <= N and (current + 1) // W == row:
                        neighbors.append(current + 1)
                    if current - 1 >= 1 and (current - 1) // W == row:
                        neighbors.append(current - 1)
                    if current - W >= 1:
                        neighbors.append(current - W)
                    if current + W <= N:
                        neighbors.append(current + W)
            # Check each neighbor
            for neighbor in neighbors:
                if neighbor not in blocked and neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)
        if found:
            print(W)
            return
        W += 1

if __name__ == '__main__':
    main()
0