软件包仓库里有 n 个软件包版本。 一个软件包版本由名字和版本号确定，它有若干个使用前必须先具备的依赖要求。 一个要求 'b lo hi' 表示必须有名字为 b、版本在 lo 到 hi 之间的软件包。 给出安装器最初被要求安装的要求列表。 安装器按顺序逐个处理收到的要求，规则如下。 处理要求 (b, lo, hi) 时：
1. 如果 b 正在处理中（下面第 3 步中 b 的要求还没有全部处理完），以 'CYCLE b' 停止。 2. 否则，如果已经选定了 b 的版本：选定的版本在 lo 到 hi 之间则这个要求完成，否则以 'CONFLICT b' 停止。 选定的版本不会再改。 3. 如果还没有选定 b，就在仓库里 b 的版本中选出在 lo 到 hi 之间的最高版本。 如果没有这样的版本（即使仓库里根本没有名字 b），以 'MISSING b' 停止。 按所写顺序、用同样的规则处理完所选版本的全部要求后，把这个软件包版本接到安装顺序的末尾。 如果没有停止就处理完了全部最初的要求，按每行一个 '名字 版本' 输出安装顺序。 如果中途停止，只输出最先停止的原因这一行。
输入
第一行给出 n，接下来 n 行每行是 '名字 版本 d'，后面接着 d 个 'b lo hi' 形式的要求，都用空格分开（软件包行的顺序任意）。 最后一行给出最初要求的个数 r 和同样形式的 r 个要求。 1 ≤ n ≤ 3,000，1 ≤ r，所有 d 与 r 之和 ≤ 10,000，1 ≤ 版本，lo ≤ hi ≤ 1,000,000。 名字是 1~10 个英文小写字母，软件包行中出现的不同名字不超过 1,500 个，同一名字和版本的软件包行不会出现两次。
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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
// 요구 하나는 [이름, lo, hi]요구읽기(tokens, count, start){ reqs = []; 循环 (i = 0; i < count; i++) { reqs.添加([tokens[start + 3 * i], tokens[start + 3 * i + 1].转数字(), tokens[start + 3 * i + 2].转数字()]); } 返回 reqs;}versions = 字典(); // 이름 → 있는 버전들deps = 字典(); // "이름 버전" → 그 버전이 요구하는 것들n = 控制台.读行().去空白().转数字();循环 (i = 0; i < n; i++){ t = 控制台.读行().去空白().分割(" "); name = t[0]; ver = t[1].转数字(); 如果 (!versions.包含(name)) { versions[name] = []; } versions[name].添加(ver); deps[name + " " + ver] = 요구읽기(t, t[2].转数字(), 3);}root = 控制台.读行().去空白().分割(" ");rootReqs = 요구읽기(root, root[0].转数字(), 1);chosen = 字典(); // 이름 → 고른 버전onPath = 字典(); // 지금 의존을 풀고 있는 중인 이름(깊이 우선 탐색의 길 위)order = []; // 설치 차례: 의존이 모두 끝난 뒤에 넣는다(후위 순서)// 문제가 없으면 "", 있으면 오류 줄을 돌려준다풀기(req){ 이름 = req[0]; lo = req[1]; hi = req[2]; 如果 (onPath.包含(이름)) { 返回 "CYCLE " + 이름; } 如果 (chosen.包含(이름)) { 如果 (lo <= chosen[이름] && chosen[이름] <= hi) { 返回 ""; } 返回 "CONFLICT " + 이름; } 고른 = -1; 如果 (versions.包含(이름)) { 遍历 (v 在 versions[이름]) { 如果 (lo <= v && v <= hi && v > 고른) { 고른 = v; } } } 如果 (고른 == -1) { 返回 "MISSING " + 이름; } chosen[이름] = 고른; onPath[이름] = 真; 遍历 (dep 在 deps[이름 + " " + 고른]) { err = 풀기(dep); 如果 (err != "") { 返回 err; } } onPath.移除(이름); order.添加(이름 + " " + 고른); 返回 "";}error = "";遍历 (req 在 rootReqs){ 如果 (error == "") { error = 풀기(req); }}如果 (error != ""){ 控制台.输出(error);}否则{ 控制台.输出(order.连接("\n"));}