소프티어

런타임에러 원인 문의

import sys import math n, m = map(int, input().split()) graph = [[]*(n+5) for _ in range(n+5)] for _ in range(m) : a,b,c = map(int, input().split()) graph[a].append([b,c]) graph[b].append([a,c]) #print(graph) left, right = 2, 10000000000 def dfs(u) : global mid, flag check[u] = 1 #print(u, end = ' ') if u == n : #마지막 장소 도착 flag = 1 return for v, c in graph[u] : if check[v] or mid <= c: continue dfs(v) whil...

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

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

지우는 소수를 좋아해 자바스크립트 제 풀이입니다.

https://yeyeyechan.github.io/2023/08/26/softeer01/ 자바스크립트는 인접리스트로 풀어야 시간초과 안걸리고 해결 되더라구요.

지우는 소스를 좋아해 예제 출력 오류

https://softeer.ai/practice/info.do?idx=1&eid=582&sw_prbl_sbms_sn=253509 해당 문제 첫번째 예제 출력 값은 3인 것 같은데 5인 이유가 있을까요? (반례) 체육관번호 - (레벨) - 체육관번호 1 - (2) - 4 - (3) - 7 - (2) - 9 - (3) - 10 최소 레벨은 3인 것 같습니다

지우는 소수를 좋아해 - 시간초과...

3번 4번 히든 케이스에서 자꾸 시간초과가 발생하는데 뭐가 문제인지 모르겠어요 ㅠㅠ /* 지우는 소수를 좋아해 10 13 1 2 5 1 3 1 1 4 2 2 5 5 3 5 4 3 6 1 4 6 1 4 7 3 5 8 5 6 9 4 7 9 2 8 10 5 9 10 3 출력예제1 5 다익스트라 우선순위 큐로 구현 하지만, 거리에 상관없이 레벨만 낮으면 오케이 1번에서 시작해서 n번으로 가는 길 찾고, 최소 레벨을 구한다. 그 최소레벨보다 높은 소수 구한다. 지우는 항상 1번 체육관에서부터 출발하고 마지막 N번 체육관을 지나가야 마지막 포켓몬 리그로 갈 수 있다. (마지막 체육관까지 가는 길은 반드시 존재한다.) */ #include #include #include #include #define INF 1e9 #define MAX 1000000000 using namespace std; //globals...

지우는 소수를 좋아해 예외 케이스 좀 받을 수 있을까요?

다익스트라를 이용한 풀이가 정해라는 것은 알고 있습니다만 parametric search + bfs 로도 해결이 가능할 것 같아서 시도해 보았는데 5~6개의 케이스가 자꾸 통과가 안되네요.. 예외 케이스 좀 받아볼 수 있을까요? #include #include #include #include using namespace std; #define MAXN 1000000001 queue q; vector> v[10001]; bool bfs(int start, int end, int level) { bool vi[10001]; fill(vi, vi + 10001, false); q.push(start); vi[start] = true; while (!q.empty()) { int now = q.front(); q.pop(); if (now == end) return true; for (int i = 0; i < v[now].size(); i++) { int n...

지우는 소수를 좋아해 "미만" -> "이하"

그 관장들을 이기기 위해선 그 관장들이 갖고 있는 레벨(level)보다 높아야 한다.하지만 너무 자주 찾아오는 지원자들 때문에 지친 체육관 관장들은 체육관 오는 길에 레벨 제한을 두었다. ‘X레벨 미만 지원자는 오지 마시오’ X레벨의 지원자는 올 수 있는 것 아닌가요..? 그렇다면 첫 번쨰 테스트 케이스는 3이 정답 아닌가요..?

지우는 소수를 부탁해 반례부탁드립니다.

런타임에러/오답/시간초과 반례 하나씩만 부탁드립니다! n, m = map(int, input().split()) alpha = [] beta = [] graph = [[] for i in range(n+1)] for i in range(m): alpha.append(list(map(int, input().split()))) for i in range(m): if alpha[i][0] > alpha[i][1]: q = alpha[i][0] alpha[i][0] = alpha[i][1] alpha[i][1] = q for i in range(m): for j in range(m): if i != j and alpha[i][0] == alpha[j][0] and alpha[i][1] == alpha[j][1]: if alpha[...

지우는 소수를 좋아해 반례 부탁드립니다.

import java.util.*; import java.io.*; public class Main { static int N, M, totalMax=1000000000; public static void main(String args[]) { int from, to, weight; Map map = new HashMap<>(); Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); for(int i=0;ito){ int temp=from; from=to; to=temp; } if(map.containsKey(from)){ ...

지우는 소수를 좋아해 추가 테스트케이스 부탁드립니다.

2, 9, 10, 12 테스트 케이스 오답 나오는데 디버깅이 어렵네요. 그리고 아래 코드입력에서 #include 다 깨져서 안보이는 것 같습니다. #include #include #include #include #include #define INT_MAX 1000000001 using namespace std; int N, M; unordered_map cost; vector edges[10000+1]; int memo[10000+1]; bool visited[10000+1]; int traverse(int cur_i){ if(cur_i == N){ return 0; } int &ret = memo[cur_i]; if(ret != INT_MAX){ return ret; } for(auto node: edges[cur_i]){ if(!visited[node]){ visited[node] = true; int tmp_res = max(traverse(node), cos...