結果

問題 No.308 素数は通れません
ユーザー gew1fw
提出日時 2025-06-12 20:33:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,413 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 81,772 KB
実行使用メモリ 95,048 KB
最終ジャッジ日時 2025-06-12 20:34:30
合計ジャッジ時間 9,562 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 58 TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import isqrt

def is_prime(n):
    if n < 2:
        return False
    for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n % i == 0:
            return n == i
    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 get_position(i, W, H):
    if i <= W * H:
        x = (i - 1) // W
        y = (i - 1) % W
    else:
        x = H
        y = (i - 1) - (W * H) - 1
    return (x, y)

def is_connected(W, N):
    H = (N) // W
    A = N % W
    if A == 0:
        A = W
        H -= 1
        if H < 0:
            return False

    visited = set()
    queue = [(0, 0)]
    visited.add((0, 0))
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        x, y = queue.pop(0)
        current = get_current_number((x, y), W, H, N)
        if current == N:
            return True
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if (nx, ny) in visited:
                continue
            if nx < 0 or ny < 0:
                continue
            if nx < H and ny >= W:
                continue
            if nx == H:
                if ny >= A:
                    continue
            if nx >= H + 1:
                continue
            current_neighbor = get_current_number((nx, ny), W, H, N)
            if is_prime(current_neighbor):
                continue
            queue.append((nx, ny))
            visited.add((nx, ny))
    return False

def get_current_number(pos, W, H, N):
    x, y = pos
    if x < H:
        return x * W + y + 1
    else:
        return H * W + (y + 1)

def find_min_w(N_str):
    N = int(N_str)
    if N == 1:
        return 1
    max_w = 2 * 10**5
    for W in range(1, max_w + 1):
        if W == 0:
            continue
        H = (N) // W
        A = N % W
        if A == 0:
            A = W
            H -= 1
            if H < 0:
                continue
        if is_connected(W, N):
            return W
    return N

if __name__ == "__main__":
    N = sys.stdin.readline().strip()
    print(find_min_w(N))
0