結果

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

ソースコード

diff # 

import sys
import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def get_grid_positions(n, w):
    h = n // w
    r = n % w
    positions = {}
    for i in range(1, n+1):
        if i <= h * w:
            row = (i-1) // w
            col = (i-1) % w
            positions[i] = (row, col)
        else:
            row = h
            col = (i - h*w -1)
            positions[i] = (row, col)
    return positions

def bfs(start, end, grid, is_not_prime):
    from collections import deque
    visited = set()
    queue = deque()
    queue.append((start, 0))
    visited.add(start)
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    while queue:
        current, steps = queue.popleft()
        if current == end:
            return True
        row, col = grid[current]
        for dr, dc in directions:
            nr = row + dr
            nc = col + dc
            neighbor = None
            for num in grid:
                if grid[num] == (nr, nc):
                    neighbor = num
                    break
            if neighbor and neighbor not in visited and is_not_prime(neighbor):
                visited.add(neighbor)
                queue.append((neighbor, steps+1))
    return False

def find_min_w(n):
    if n == 1:
        return 1
    for w in range(1, n):
        if w == 0:
            continue
        positions = get_grid_positions(n, w)
        is_not_prime = lambda x: not is_prime(x) if x != 1 else True
        if bfs(1, n, positions, is_not_prime):
            return w
    return n-1

def main():
    n = int(sys.stdin.readline())
    print(find_min_w(n))

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