A package repository holds n package versions.
A package version is identified by its name and version number, and it has a few requirements that must be present before it can be used.
A requirement 'b lo hi' means a package named b with a version from lo to hi must be present.
The list of requirements the installer is first asked to install is given.
The installer solves the given requirements one by one, in order, by the rules below.
To solve a requirement (b, lo, hi):
1. If b is currently being solved (its requirements in step 3 below are not all solved yet), stop with 'CYCLE b'.
2. Otherwise, if a version of b has already been chosen, the requirement is done when the chosen version is between lo and hi; if not, stop with 'CONFLICT b'. A chosen version is never changed.
3. If b has not been chosen yet, choose the highest version of b in the repository that is between lo and hi. If there is none (even if the name b is not in the repository at all), stop with 'MISSING b'.
After solving all requirements of the chosen version, in the order written, by the same rules, append that package version to the end of the install order.
If all the first requirements are solved without stopping, print the install order one line each as 'name version'.
If it stops along the way, print only one line with the first reason it stopped.
Input
The first line has n, followed by n lines each with 'name version d' and then d requirements in the form 'b lo hi', all separated by spaces (package lines come in any order). The last line has the number of first requirements r and then r requirements in the same form. 1 ≤ n ≤ 3,000, 1 ≤ r, the sum of all d and r ≤ 10,000, 1 ≤ version, lo ≤ hi ≤ 1,000,000. Names are 1 to 10 lowercase English letters, at most 1,500 different names appear on the package lines, and no name and version appear on two package lines.
Output
The install order (one 'name version' per line), or a single line 'CYCLE name', 'CONFLICT name' or 'MISSING name'
Example 1 · stdin
6
app 2 2 web 1 3 db 2 5
app 1 0
web 3 1 db 1 4
web 2 1 db 1 9
db 4 0
db 6 0
1 app 1 9
stdout
db 4
web 3
app 2
Example 2 · stdin
6
app 2 2 web 1 3 db 2 5
app 1 0
web 3 1 db 1 4
web 2 1 db 1 9
db 4 0
db 6 0
2 app 1 9 db 5 9
stdout
CONFLICT db
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Packages and requirements form a directed graph, and the installer walks it with depth-first search (DFS). Each package has three states: not seen, being solved (on the current path), and finished. A package joins the install order only after its requirements are solved (post-order), so dependencies are always installed first. A cycle exists only when you meet a package that is 'being solved' again — treating every already-chosen name as a cycle would also flag the diamond shape where two packages require the same one. So always clear the on-path mark when done. Conversely, treating a chosen name as 'done' without checking the path misses cycles. Other traps: adding to the install order before the dependencies (pre-order) reverses the order, and choosing the lowest version in range changes the answer (in example 1 it picks app 1 instead of app 2 and installs nothing else). Depth is a trap too: with up to 1,500 names a chain can be 1,500 levels deep, which exceeds Python's default recursion limit (1,000) and raises RecursionError — raise it with sys.setrecursionlimit or switch to a stack. The default call stacks of Java, C#, C, C++ and JavaScript handle this depth, and Craykon can call a few thousand levels deep, so 1,500 is fine. Reporting an error outward also differs: Python escapes in one go with an exception (raise/except); Java, C#, JavaScript and TypeScript return either an error string or null (string? in C#, string | null in TypeScript); C++ returns std::optional<std::string>; C returns success (1/0) and writes the message into a global buffer. Craykon has no exceptions, so it uses the empty string "" for 'no problem' and checks the returned value every time. Tables: Python dict/set, Java HashMap/HashSet (computeIfAbsent to create a list), C# Dictionary with a tuple key (string, int), C++ std::unordered_map and std::map<std::pair<std::string, int>, …>, C a sorted array of names with bsearch, JavaScript and TypeScript Map/Set, and Craykon a Dict() keyed by the string name + " " + version, clearing the on-path mark with onPath.Remove(name).
Pythonmain.py · 56 lines
import syssys.setrecursionlimit(10000) # 의존 사슬이 1,500단계까지 깊어질 수 있다(기본 한도는 1,000)class ResolveError(Exception): passdef read_reqs(tokens, count, start): """tokens[start:]에서 (이름, lo, hi) count개를 읽는다.""" return [(tokens[start + 3 * i], int(tokens[start + 3 * i + 1]), int(tokens[start + 3 * i + 2])) for i in range(count)]lines = sys.stdin.read().split("\n")n = int(lines[0])versions = {} # 이름 → 있는 버전들deps = {} # (이름, 버전) → 그 버전이 요구하는 것들for line in lines[1:1 + n]: t = line.split() name, ver, d = t[0], int(t[1]), int(t[2]) versions.setdefault(name, []).append(ver) deps[(name, ver)] = read_reqs(t, d, 3)root = lines[1 + n].split()root_reqs = read_reqs(root, int(root[0]), 1)chosen = {} # 이름 → 고른 버전on_path = set() # 지금 의존을 풀고 있는 중인 이름(깊이 우선 탐색의 길 위)order = [] # 설치 차례: 의존이 모두 끝난 뒤에 넣는다(후위 순서)def resolve(name, lo, hi): if name in on_path: raise ResolveError(f"CYCLE {name}") if name in chosen: if not lo <= chosen[name] <= hi: raise ResolveError(f"CONFLICT {name}") return fits = [v for v in versions.get(name, []) if lo <= v <= hi] if not fits: raise ResolveError(f"MISSING {name}") ver = max(fits) chosen[name] = ver on_path.add(name) for dep, dlo, dhi in deps[(name, ver)]: resolve(dep, dlo, dhi) on_path.remove(name) order.append(f"{name} {ver}")try: for name, lo, hi in root_reqs: resolve(name, lo, hi) print("\n".join(order))except ResolveError as e: print(e)
JavaScriptmain.js · 54 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");// tokens[start..]에서 [이름, lo, hi] count개를 읽는다function readReqs(tokens, count, start) { const reqs = []; for (let i = 0; i < count; i++) reqs.push([tokens[start + 3 * i], Number(tokens[start + 3 * i + 1]), Number(tokens[start + 3 * i + 2])]); return reqs;}const n = Number(lines[0]);const versions = new Map(); // 이름 → 있는 버전들const deps = new Map(); // "이름 버전" → 그 버전이 요구하는 것들for (let i = 1; i <= n; i++) { const t = lines[i].trim().split(/\s+/); const name = t[0], ver = Number(t[1]); if (!versions.has(name)) versions.set(name, []); versions.get(name).push(ver); deps.set(`${name} ${ver}`, readReqs(t, Number(t[2]), 3));}const root = lines[n + 1].trim().split(/\s+/);const rootReqs = readReqs(root, Number(root[0]), 1);const chosen = new Map(); // 이름 → 고른 버전const onPath = new Set(); // 지금 의존을 풀고 있는 중인 이름(깊이 우선 탐색의 길 위)const order = []; // 설치 차례: 의존이 모두 끝난 뒤에 넣는다(후위 순서)// 문제가 없으면 null, 있으면 오류 줄을 돌려준다function resolve(name, lo, hi) { if (onPath.has(name)) return `CYCLE ${name}`; if (chosen.has(name)) { const v = chosen.get(name); return lo <= v && v <= hi ? null : `CONFLICT ${name}`; } const fits = (versions.get(name) ?? []).filter((v) => lo <= v && v <= hi); if (fits.length === 0) return `MISSING ${name}`; const ver = Math.max(...fits); chosen.set(name, ver); onPath.add(name); for (const [dep, dlo, dhi] of deps.get(`${name} ${ver}`)) { const err = resolve(dep, dlo, dhi); if (err !== null) return err; } onPath.delete(name); order.push(`${name} ${ver}`); return null;}let error = null;for (const [name, lo, hi] of rootReqs) { error = resolve(name, lo, hi); if (error !== null) break;}console.log(error ?? order.join("\n"));
TypeScriptmain.ts · 57 lines
import { readFileSync } from "node:fs";type Req = [string, number, number];const lines: string[] = readFileSync(0, "utf8").split("\n");// tokens[start..]에서 [이름, lo, hi] count개를 읽는다function readReqs(tokens: string[], count: number, start: number): Req[] { const reqs: Req[] = []; for (let i = 0; i < count; i++) reqs.push([tokens[start + 3 * i], Number(tokens[start + 3 * i + 1]), Number(tokens[start + 3 * i + 2])]); return reqs;}const n = Number(lines[0]);const versions = new Map<string, number[]>(); // 이름 → 있는 버전들const deps = new Map<string, Req[]>(); // "이름 버전" → 그 버전이 요구하는 것들for (let i = 1; i <= n; i++) { const t = lines[i].trim().split(/\s+/); const name = t[0], ver = Number(t[1]); if (!versions.has(name)) versions.set(name, []); versions.get(name)!.push(ver); deps.set(`${name} ${ver}`, readReqs(t, Number(t[2]), 3));}const root = lines[n + 1].trim().split(/\s+/);const rootReqs = readReqs(root, Number(root[0]), 1);const chosen = new Map<string, number>(); // 이름 → 고른 버전const onPath = new Set<string>(); // 지금 의존을 풀고 있는 중인 이름(깊이 우선 탐색의 길 위)const order: string[] = []; // 설치 차례: 의존이 모두 끝난 뒤에 넣는다(후위 순서)// 문제가 없으면 null, 있으면 오류 줄을 돌려준다function resolve(name: string, lo: number, hi: number): string | null { if (onPath.has(name)) return `CYCLE ${name}`; if (chosen.has(name)) { const v = chosen.get(name)!; return lo <= v && v <= hi ? null : `CONFLICT ${name}`; } const fits = (versions.get(name) ?? []).filter((v) => lo <= v && v <= hi); if (fits.length === 0) return `MISSING ${name}`; const ver = Math.max(...fits); chosen.set(name, ver); onPath.add(name); for (const [dep, dlo, dhi] of deps.get(`${name} ${ver}`)!) { const err = resolve(dep, dlo, dhi); if (err !== null) return err; } onPath.delete(name); order.push(`${name} ${ver}`); return null;}let error: string | null = null;for (const [name, lo, hi] of rootReqs) { error = resolve(name, lo, hi); if (error !== null) break;}console.log(error ?? order.join("\n"));
JavaMain.java · 65 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Set;public class Main { record Req(String name, int lo, int hi) {} static Map<String, List<Integer>> versions = new HashMap<>(); // 이름 → 있는 버전들 static Map<String, List<Req>> deps = new HashMap<>(); // "이름 버전" → 그 버전이 요구하는 것들 static Map<String, Integer> chosen = new HashMap<>(); // 이름 → 고른 버전 static Set<String> onPath = new HashSet<>(); // 지금 의존을 풀고 있는 중인 이름(깊이 우선 탐색의 길 위) static StringBuilder order = new StringBuilder(); // 설치 차례: 의존이 모두 끝난 뒤에 넣는다(후위 순서) static List<Req> readReqs(String[] t, int count, int start) { List<Req> reqs = new ArrayList<>(); for (int i = 0; i < count; i++) reqs.add(new Req(t[start + 3 * i], Integer.parseInt(t[start + 3 * i + 1]), Integer.parseInt(t[start + 3 * i + 2]))); return reqs; } // 문제가 없으면 null, 있으면 오류 줄을 돌려준다 static String resolve(Req req) { String name = req.name(); if (onPath.contains(name)) return "CYCLE " + name; Integer have = chosen.get(name); if (have != null) return req.lo() <= have && have <= req.hi() ? null : "CONFLICT " + name; int ver = -1; for (int v : versions.getOrDefault(name, List.of())) if (req.lo() <= v && v <= req.hi()) ver = Math.max(ver, v); if (ver == -1) return "MISSING " + name; chosen.put(name, ver); onPath.add(name); for (Req dep : deps.get(name + " " + ver)) { String err = resolve(dep); if (err != null) return err; } onPath.remove(name); order.append(name).append(' ').append(ver).append('\n'); return null; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); for (int i = 0; i < n; i++) { String[] t = in.readLine().trim().split("\\s+"); int ver = Integer.parseInt(t[1]); versions.computeIfAbsent(t[0], key -> new ArrayList<>()).add(ver); deps.put(t[0] + " " + ver, readReqs(t, Integer.parseInt(t[2]), 3)); } String[] root = in.readLine().trim().split("\\s+"); String error = null; for (Req req : readReqs(root, Integer.parseInt(root[0]), 1)) { error = resolve(req); if (error != null) break; } System.out.print(error != null ? error + "\n" : order); }}
C#Main.cs · 63 lines
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ record Req(string Name, int Lo, int Hi); static readonly Dictionary<string, List<int>> versions = new(); // 이름 → 있는 버전들 static readonly Dictionary<(string, int), List<Req>> deps = new(); // (이름, 버전) → 그 버전이 요구하는 것들 static readonly Dictionary<string, int> chosen = new(); // 이름 → 고른 버전 static readonly HashSet<string> onPath = new(); // 지금 의존을 풀고 있는 중인 이름(깊이 우선 탐색의 길 위) static readonly StringBuilder order = new(); // 설치 차례: 의존이 모두 끝난 뒤에 넣는다(후위 순서) static List<Req> ReadReqs(string[] t, int count, int start) => Enumerable.Range(0, count) .Select(i => new Req(t[start + 3 * i], int.Parse(t[start + 3 * i + 1]), int.Parse(t[start + 3 * i + 2]))) .ToList(); // 문제가 없으면 null, 있으면 오류 줄을 돌려준다 static string? Resolve(Req req) { string name = req.Name; if (onPath.Contains(name)) return "CYCLE " + name; if (chosen.TryGetValue(name, out int have)) return req.Lo <= have && have <= req.Hi ? null : "CONFLICT " + name; var fits = versions.GetValueOrDefault(name, new List<int>()).Where(v => req.Lo <= v && v <= req.Hi).ToList(); if (fits.Count == 0) return "MISSING " + name; int ver = fits.Max(); chosen[name] = ver; onPath.Add(name); foreach (var dep in deps[(name, ver)]) { string? err = Resolve(dep); if (err != null) return err; } onPath.Remove(name); order.Append(name).Append(' ').Append(ver).Append('\n'); return null; } static void Main() { int n = int.Parse(Console.ReadLine()!.Trim()); for (int i = 0; i < n; i++) { string[] t = Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries); int ver = int.Parse(t[1]); if (!versions.ContainsKey(t[0])) versions[t[0]] = new List<int>(); versions[t[0]].Add(ver); deps[(t[0], ver)] = ReadReqs(t, int.Parse(t[2]), 3); } string[] root = Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries); string? error = null; foreach (var req in ReadReqs(root, int.Parse(root[0]), 1)) { error = Resolve(req); if (error != null) break; } Console.Write(error != null ? error + "\n" : order.ToString()); }}
C++main.cpp · 73 lines
#include <iostream>#include <map>#include <optional>#include <set>#include <string>#include <unordered_map>#include <unordered_set>#include <vector>struct Req { std::string name; int lo, hi;};std::unordered_map<std::string, std::vector<int>> versions; // 이름 → 있는 버전들std::map<std::pair<std::string, int>, std::vector<Req>> deps; // (이름, 버전) → 그 버전이 요구하는 것들std::unordered_map<std::string, int> chosen; // 이름 → 고른 버전std::unordered_set<std::string> onPath; // 지금 의존을 풀고 있는 중인 이름(깊이 우선 탐색의 길 위)std::vector<std::pair<std::string, int>> order; // 설치 차례: 의존이 모두 끝난 뒤에 넣는다(후위 순서)std::vector<Req> readReqs(std::istream& in, int count) { std::vector<Req> reqs(count); for (auto& r : reqs) in >> r.name >> r.lo >> r.hi; return reqs;}// 문제가 없으면 빈 값, 있으면 오류 줄을 돌려준다std::optional<std::string> resolve(const Req& req) { const std::string& name = req.name; if (onPath.count(name)) return "CYCLE " + name; if (auto it = chosen.find(name); it != chosen.end()) { if (req.lo <= it->second && it->second <= req.hi) return std::nullopt; return "CONFLICT " + name; } int ver = -1; if (auto it = versions.find(name); it != versions.end()) for (int v : it->second) if (req.lo <= v && v <= req.hi && v > ver) ver = v; if (ver == -1) return "MISSING " + name; chosen[name] = ver; onPath.insert(name); for (const Req& dep : deps[{name, ver}]) if (auto err = resolve(dep)) return err; onPath.erase(name); order.emplace_back(name, ver); return std::nullopt;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; for (int i = 0; i < n; i++) { std::string name; int ver, d; std::cin >> name >> ver >> d; versions[name].push_back(ver); deps[{name, ver}] = readReqs(std::cin, d); } int r; std::cin >> r; std::optional<std::string> error; for (const Req& req : readReqs(std::cin, r)) { error = resolve(req); if (error) break; } if (error) { std::cout << *error << "\n"; } else { for (const auto& [name, ver] : order) std::cout << name << " " << ver << "\n"; }}
Cmain.c · 90 lines
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 3000#define MAXREQ 10000typedef struct { char name[11]; int ver; int first, count; /* 이 버전의 요구들: reqs[first .. first + count - 1] */} Pkg;typedef struct { char name[11]; int lo, hi;} Req;static Pkg pkgs[MAXN];static Req reqs[MAXREQ];static int n, nreq;/* 이름마다 하나: 고른 버전(없으면 0)과 길 위에 있는지 */static char names[MAXN][11];static int chosen[MAXN], onPath[MAXN], nnames;static int orderPkg[MAXN], norder; /* 설치 차례(후위 순서) */static char error[32];static int byName(const void *a, const void *b) { return strcmp((const char *)a, (const char *)b);}/* 이름 번호(없으면 -1): names는 정렬해 두었으니 이진 탐색 */static int nameId(const char *name) { char(*p)[11] = bsearch(name, names, nnames, sizeof names[0], byName); return p == NULL ? -1 : (int)(p - names);}/* 문제가 없으면 1, 있으면 error에 적고 0 */static int resolve(const Req *req) { int id = nameId(req->name); if (id >= 0 && onPath[id]) { sprintf(error, "CYCLE %s", req->name); return 0; } if (id >= 0 && chosen[id] != 0) { if (req->lo <= chosen[id] && chosen[id] <= req->hi) return 1; sprintf(error, "CONFLICT %s", req->name); return 0; } int best = -1; for (int i = 0; i < n; i++) if (strcmp(pkgs[i].name, req->name) == 0 && req->lo <= pkgs[i].ver && pkgs[i].ver <= req->hi && (best == -1 || pkgs[i].ver > pkgs[best].ver)) best = i; if (best == -1) { sprintf(error, "MISSING %s", req->name); return 0; } chosen[id] = pkgs[best].ver; onPath[id] = 1; for (int j = 0; j < pkgs[best].count; j++) if (!resolve(&reqs[pkgs[best].first + j])) return 0; onPath[id] = 0; orderPkg[norder++] = best; return 1;}int main(void) { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%10s %d %d", pkgs[i].name, &pkgs[i].ver, &pkgs[i].count); pkgs[i].first = nreq; for (int j = 0; j < pkgs[i].count; j++, nreq++) scanf("%10s %d %d", reqs[nreq].name, &reqs[nreq].lo, &reqs[nreq].hi); strcpy(names[i], pkgs[i].name); } /* 이름을 정렬하고 겹치는 것을 없앤다 */ qsort(names, n, sizeof names[0], byName); for (int i = 0; i < n; i++) if (nnames == 0 || strcmp(names[nnames - 1], names[i]) != 0) { if (nnames != i) strcpy(names[nnames], names[i]); /* 같은 칸끼리 strcpy하면 안 된다 */ nnames++; } int r, rootFirst = nreq; scanf("%d", &r); for (int j = 0; j < r; j++, nreq++) scanf("%10s %d %d", reqs[nreq].name, &reqs[nreq].lo, &reqs[nreq].hi); int ok = 1; for (int j = 0; j < r && ok; j++) ok = resolve(&reqs[rootFirst + j]); if (!ok) { puts(error); } else { for (int i = 0; i < norder; i++) printf("%s %d\n", pkgs[orderPkg[i]].name, pkgs[orderPkg[i]].ver); } return 0;}
Craykonmain.cray · 97 lines
// 요구 하나는 [이름, lo, hi]요구읽기(tokens, count, start){ reqs = []; for (i = 0; i < count; i++) { reqs.Add([tokens[start + 3 * i], tokens[start + 3 * i + 1].ToNumber(), tokens[start + 3 * i + 2].ToNumber()]); } return reqs;}versions = Dict(); // 이름 → 있는 버전들deps = Dict(); // "이름 버전" → 그 버전이 요구하는 것들n = Console.ReadLine().Trim().ToNumber();for (i = 0; i < n; i++){ t = Console.ReadLine().Trim().Split(" "); name = t[0]; ver = t[1].ToNumber(); if (!versions.Contains(name)) { versions[name] = []; } versions[name].Add(ver); deps[name + " " + ver] = 요구읽기(t, t[2].ToNumber(), 3);}root = Console.ReadLine().Trim().Split(" ");rootReqs = 요구읽기(root, root[0].ToNumber(), 1);chosen = Dict(); // 이름 → 고른 버전onPath = Dict(); // 지금 의존을 풀고 있는 중인 이름(깊이 우선 탐색의 길 위)order = []; // 설치 차례: 의존이 모두 끝난 뒤에 넣는다(후위 순서)// 문제가 없으면 "", 있으면 오류 줄을 돌려준다풀기(req){ 이름 = req[0]; lo = req[1]; hi = req[2]; if (onPath.Contains(이름)) { return "CYCLE " + 이름; } if (chosen.Contains(이름)) { if (lo <= chosen[이름] && chosen[이름] <= hi) { return ""; } return "CONFLICT " + 이름; } 고른 = -1; if (versions.Contains(이름)) { foreach (v in versions[이름]) { if (lo <= v && v <= hi && v > 고른) { 고른 = v; } } } if (고른 == -1) { return "MISSING " + 이름; } chosen[이름] = 고른; onPath[이름] = true; foreach (dep in deps[이름 + " " + 고른]) { err = 풀기(dep); if (err != "") { return err; } } onPath.Remove(이름); order.Add(이름 + " " + 고른); return "";}error = "";foreach (req in rootReqs){ if (error == "") { error = 풀기(req); }}if (error != ""){ Console.WriteLine(error);}else{ Console.WriteLine(order.Join("\n"));}