パッケージの保管庫にパッケージのバージョンが 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"));}