소프티어

1e9이하에서 소수 사이 간격이 충분히 작다는 것이 증명 가능한지 궁금합니다

우선 제 풀이는 다음과 같습니다. 데이크스트라를 변형해서 1에서 n까지 가는 경로에 속한 간선들 중 가중치가 가장 큰 간선의 가중치가 가장 작은 경로를 찾습니다. 그 경로에서 가중치가 가장 큰 간선의 가중치보다 큰 가장 작은 소수를 구합니다. 2의 과정을 하는데 있어서 소수들 사이의 간격이 작다는 가정을 세우고 단순 반복문과 루트 시간 소수 판정을 사용해서 데이크스트라 $O((N + M) log N)$ 에 두 소수 사이의 간격의 크기를 $p$ 라고 했을때 총 시간 복잡도 $O((N + M) log N + p \sqrt{10^{9}})$ 정도?되는 풀이를 짠거 같은데 46ms정도로 굉장히 빠르게 통과하더군요. $p$에 비례하는 시간이 걸리는 풀이를 짜도 될 정도로 $p$가 $10^{9}$이하의 소수들에 대해 충분히 작다는게 증명 가능한지 또는 작다라는 정보를 참고할수 있는 출처가 있는지 아니면 틀려야 하는 코드고 데이터가 약한건지 알려주시면 감사하겠습니다. 아래는 제 코드입니다 ...

시간 초과 관련 문의

import sys sys.setrecursionlimit(10000) n, m = map(int, sys.stdin.readline().split()) s = sys.stdin.readline() h = [[""]*(n+1) for _ in range(n+1)] graph = [ [] for _ in range(n+1)] for i in range(n-1) : u, v, c = map(str, sys.stdin.readline().split()) u, v = int(u), int(v) h[u][v] = str(c) h[v][u] = str(c) graph[u].append(v) graph[v].append(u) #print(graph) visited = [0] * (n+1) visited[1] = 1 ans = -1 def LCS(b) : global ans a_len = l...

dfs 풀이 오류좀 찾아봐 주실 수 있을까요

n,T = map(int,input().split()) signals = [list(map(int,input().split())) for _ in range(n**2)] # print(signals) L = [0,-1] R = [0,1] U = [-1,0] D = [1,0] ## 1번 리스트 [R U R D] 에서 제일 앞의 R은 해당 신호에 통과하기 위한 올바른 방향입니다. R U L D 가 순서대로 순환하며 들어 가 있습니다 signal_dict = [[],[R,U,R,D],[U,L,U,R],[L,U,L,D],[D,L,D,R], [R,U,R],[U,L,U],[L,L,D],[D,D,R], [R,R,D],[U,U,R],[L,L,U],[D,L,D]] # dir = signal_dict[1] # print(dir[0]) # print(dir[1]) answer = [[0,0]] import sys n,T = map(int,sys.stdin.readline().split()) sig...

회의실 예약 반례 찾아주시면 감사드리겠습니다

#include <stdio.h> #include <string.h> #define maxtime 100 typedef struct{ char name[10]; }room_name; typedef struct{ char name[10]; int start_time; int end_time; }room_reserve; int compare_checktime(const void* a, const void* b) { int arg1 = *(const int*)a; int arg2 = *(const int*)b; if (arg1 < arg2) return -1; if (arg1 > arg2) return 1; return 0; } int main(void) { int N,M; int temp; scanf("%d %d", &N,&M); int check_time[N][maxtime]; int avail; int str_num; char *str_temp; room_name x[N]; r...

런타임에러 뜨는데 도움 주시면 정말 감사하겠습니다.

import java.io.*; import java.util.*; public class Main { static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); StringTokenizer st1 = new StringTokenizer(br.readLine()); StringTokenizer st2 = new StringTokenizer(br.readLine()); StringTokenizer st3 = new StringTokenizer(br.readLine()); Student[] test1 = new Student[N]...

Phi Squared TC 1 ~ 10 오답 도와주세요.

TC 1 ~ 10 통과 못하고 있는데, 도통 어디가 문제인지 모르겠습니다. 도와주시면 감사하겠습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); Deque<Node> nextDayQueue = new LinkedList<>(); Deque<Node> todayQueue = new LinkedList<>(); for(int i = 1 ; i < N + 1 ; i++) { int size = sc.nextInt(); todayQueue.addLast(new Node(i, size)); ...

반례 알려주시면 정말 감사하겠습니다. 소프티어 유튜브 풀이 영상 보고 구현 해봤는데 통과가 안되서요 ㅠㅠ

import java.io.*; import java.util.*; public class Main {     static int N; // 정점의 갯수 static int M; // 간선의 갯수 static ArrayList<Integer>[] graph1; // 정순 static ArrayList<Integer>[] graph2; // 정순 static boolean[] visited1; // 정순 S출발 static boolean[] visited2; // 정순 T출발 static boolean[] visitedR1; // 역순 S출발 static boolean[] visitedR2; // 역순 T출발 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu...

11개 테스트케이스 오답으로 나와요.. 예제 부탁드려요 ㅠㅠ

제목대로 테스트케이스 11개가 오답으로 처리됩니다.. 시간초과는 아니구요! 아래코드는 간단한 주석을 달고 올립니다. 고수님들 부탁 드립니다.. 개발자톡에서 몇몇분이 올려주신 엣지케이스들은 통과가 되고 있어요.. ! 제 코드에 해당될 것 같은 반례나, 개선점 제안 부탁 드립니다! import sys #초기 n,m값 받기 n, m = map(int, sys.stdin.readline().split()) def solution(n,m):     #염기서열 입력값 저장     initial = []     for _ in range(n):         line = sys.stdin.readline().rstrip()         if len(line) == m:             initial.append(line)     #복잡한 아이들 찾기 (알파벳 많이 들어갈 수록 복잡하다) --> 알파벳 포함된 갯수가 dict의 key, 해당 문자...

총체적 난국 파이썬 코드

n, m = map(int, input().split()) maze = [list(input()) for _ in range(n)] def dfs(x, y): stack = [(x, y, [])] # 좌표와 경로를 함께 저장 while stack: x, y, path = stack.pop(0) if 0 <= x < n and 0 <= y < m and maze[x][y] != "#" and maze[x][y] != "G": if maze[x][y] == "D": path.append((x,y)) short_path = path[1:] #path.append((x, y)) return short_path # 최단 경로 반환 if maze[x][y] != "N": maze[x][y] = "#" stack.append((x, y + 1, path + [(x, y)])) # 오른쪽 이동 stack.append((x, y - 1, path + [(x, y)])) # 왼쪽 이동 stack...