A sheet has n cells, and each cell has a name and a formula.
A line has the form "name = term + term + … + term", with words separated by single spaces.
A term is a non-negative integer or the name of a cell (possibly the cell itself).
The value of a cell is the sum of the values of the terms in its formula; if the same name appears several times, it is added that many times.
A cell that leads back to itself when its formula is followed, that is, a cell in a loop, has no value.
A cell whose formula uses a cell in a loop has no value either, nor does a cell that uses such a cell (through any number of steps).
For each cell, in the order of the input, print "name value" on its own line.
For a cell with no value, print ERR in place of the value.
Input
The first line has n, and each of the next n lines has one cell. 1 ≤ n ≤ 5,000. Names are distinct, 1 to 8 characters of lowercase letters and digits, starting with a lowercase letter. A formula has 1 to 8 terms, numbers are from 0 to 1,000,000, and every name in a formula is the name of some cell. All formulas together contain at most 10,000 name terms. The value of every cell that has a value is at most 10^15.
Output
n lines, each "name value" or "name ERR"
Example 1 · stdin
8
a = 3 + b + c
b = 10
c = b + b + 1
d = d + 1
e = a + f
f = e
g = d
h = a + 2
stdout
a 34
b 10
c 21
d ERR
e ERR
f ERR
g ERR
h 36
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
Draw an arrow j → i whenever cell i uses cell j in its formula; the cells that have a value are exactly the cells that topological sorting can put in order. Kahn's method is neat: for each cell count 'name terms whose value is not known yet' (waiting), put the cells with 0 in a queue, and add each cell taken out to the cells that use it while lowering their waiting by one. The cells that never get into the queue are exactly those in a loop or hanging off one — no need to look for the loops separately. Trap one: marking only the cells in a loop as ERR is wrong. In the example g uses the loop d, so it is ERR. If a recursive search marks only the 'in progress' cell it runs into and counts it as 0, the cells using the loop get bogus numbers. Trap two: b + b adds b twice (c = 21 in the example). Collecting names in a set adds it only once — put every occurrence into both the waiting count and the 'users' list. Trap three: following formulas recursively goes 5,000 levels deep on a 5,000-cell chain. That is past Python's default recursion limit of 1,000, and Craykon stops at a few thousand levels too. Kahn's method with a queue has no recursion, so this cannot happen. Trap four: values reach 10^15, past a 32-bit int (about 2.1 billion) (a 5,000-cell chain × a million = 5 billion, and a doubling chain reaches 2^49). C and C++ need long long, Java and C# long (a C# or Java int silently wraps around to a negative number); Python integers have no limit, and JavaScript, TypeScript and Craykon numbers are doubles, exact up to 2^53 (about 9×10^15), so they work as they are. Look up name → cell number in a dictionary: Python dict, JavaScript and TypeScript Map, Java HashMap<String, Integer>, C# Dictionary<string, int>, C++ std::unordered_map<std::string, int>. C has no dictionary, so it sorts the cell numbers by name with qsort and binary searches with strcmp. Splitting a line differs too: the words are [name, "=", term, "+", term, …], so stepping by two as in Python w[2::2] leaves only the terms. C reads a line with fgets and cuts it with strtok; C++ reads the words with std::istringstream. Whether a term is a number or a name is decided by whether its first character is a digit (names start with a letter). Craykon keeps name → number in a Dict() and tells the first character apart by whether Str.Code(w[k][0]) is 48 to 57 ("0" to "9"). The queue only ever adds to a list and moves a read position (head) forward from the front.
Pythonmain.py · 44 lines
import sysfrom collections import dequelines = sys.stdin.read().split("\n")n = int(lines[0])names = []const = [] # const[i] = i번 칸 식에 적힌 수들의 합refs = [] # refs[i] = i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번)for line in lines[1 : 1 + n]: w = line.split() names.append(w[0]) c = 0 r = [] for term in w[2::2]: # w = [이름, "=", 항, "+", 항, "+", ...] if term[0].isdigit(): c += int(term) else: r.append(term) const.append(c) refs.append(r)index = {name: i for i, name in enumerate(names)}users = [[] for _ in range(n)] # users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼)waiting = [0] * n # 아직 값을 모르는, 식에 쓴 이름의 수for i in range(n): for name in refs[i]: users[index[name]].append(i) waiting[i] += 1# 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다value = const[:]known = [False] * nqueue = deque(i for i in range(n) if waiting[i] == 0)while queue: j = queue.popleft() known[j] = True for i in users[j]: value[i] += value[j] waiting[i] -= 1 if waiting[i] == 0: queue.append(i)# 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다print("\n".join(f"{names[i]} {value[i] if known[i] else 'ERR'}" for i in range(n)))
JavaScriptmain.js · 43 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const names = [];const value = []; // 처음엔 식에 적힌 수들의 합, 이름 칸의 값을 알게 될 때마다 더한다const refs = []; // refs[i] = i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번)for (let i = 1; i <= n; i++) { const w = lines[i].trim().split(" "); // [이름, "=", 항, "+", 항, ...] names.push(w[0]); let c = 0; const r = []; for (let k = 2; k < w.length; k += 2) { if (/^[0-9]/.test(w[k])) c += Number(w[k]); else r.push(w[k]); } value.push(c); refs.push(r);}const index = new Map(names.map((name, i) => [name, i]));const users = Array.from({ length: n }, () => []); // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼)const waiting = new Array(n).fill(0); // 아직 값을 모르는, 식에 쓴 이름의 수refs.forEach((r, i) => { for (const name of r) { users[index.get(name)].push(i); waiting[i]++; }});// 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다const known = new Array(n).fill(false);const queue = [];for (let i = 0; i < n; i++) if (waiting[i] === 0) queue.push(i);for (let head = 0; head < queue.length; head++) { const j = queue[head]; known[j] = true; for (const i of users[j]) { value[i] += value[j]; // 10^15까지라 배정밀도 수로도 정확하다 if (--waiting[i] === 0) queue.push(i); }}// 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다console.log(names.map((name, i) => `${name} ${known[i] ? value[i] : "ERR"}`).join("\n"));
TypeScriptmain.ts · 45 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const names: string[] = [];const value: number[] = []; // 처음엔 식에 적힌 수들의 합, 이름 칸의 값을 알게 될 때마다 더한다const refs: string[][] = []; // refs[i] = i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번)for (let i = 1; i <= n; i++) { const w: string[] = lines[i].trim().split(" "); // [이름, "=", 항, "+", 항, ...] names.push(w[0]); let c = 0; const r: string[] = []; for (let k = 2; k < w.length; k += 2) { if (/^[0-9]/.test(w[k])) c += Number(w[k]); else r.push(w[k]); } value.push(c); refs.push(r);}const index = new Map<string, number>(names.map((name, i): [string, number] => [name, i]));const users: number[][] = Array.from({ length: n }, (): number[] => []); // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼)const waiting: number[] = new Array<number>(n).fill(0); // 아직 값을 모르는, 식에 쓴 이름의 수refs.forEach((r, i) => { for (const name of r) { users[index.get(name)!].push(i); // 식에 쓴 이름은 모두 어느 줄에선가 정해진다 waiting[i]++; }});// 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다const known: boolean[] = new Array<boolean>(n).fill(false);const queue: number[] = [];for (let i = 0; i < n; i++) if (waiting[i] === 0) queue.push(i);for (let head = 0; head < queue.length; head++) { const j = queue[head]; known[j] = true; for (const i of users[j]) { value[i] += value[j]; // 10^15까지라 number로도 정확하다 if (--waiting[i] === 0) queue.push(i); }}// 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다console.log(names.map((name, i) => `${name} ${known[i] ? value[i] : "ERR"}`).join("\n"));
JavaMain.java · 63 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); String[] names = new String[n]; long[] value = new long[n]; // 처음엔 식에 적힌 수들의 합. 10^15까지라 long List<List<String>> refs = new ArrayList<>(); // i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번) Map<String, Integer> index = new HashMap<>(); for (int i = 0; i < n; i++) { String[] w = in.readLine().trim().split(" "); // [이름, "=", 항, "+", 항, ...] names[i] = w[0]; index.put(w[0], i); List<String> r = new ArrayList<>(); for (int k = 2; k < w.length; k += 2) { if (Character.isDigit(w[k].charAt(0))) value[i] += Long.parseLong(w[k]); else r.add(w[k]); } refs.add(r); } List<List<Integer>> users = new ArrayList<>(); // users.get(j) = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼) for (int i = 0; i < n; i++) users.add(new ArrayList<>()); int[] waiting = new int[n]; // 아직 값을 모르는, 식에 쓴 이름의 수 for (int i = 0; i < n; i++) { for (String name : refs.get(i)) { users.get(index.get(name)).add(i); waiting[i]++; } } // 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다 boolean[] known = new boolean[n]; ArrayDeque<Integer> queue = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (waiting[i] == 0) queue.add(i); while (!queue.isEmpty()) { int j = queue.poll(); known[j] = true; for (int i : users.get(j)) { value[i] += value[j]; if (--waiting[i] == 0) queue.add(i); } } // 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다 StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { out.append(names[i]).append(' '); if (known[i]) out.append(value[i]); else out.append("ERR"); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 65 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); var names = new string[n]; var value = new long[n]; // 처음엔 식에 적힌 수들의 합. 10^15까지라 long var refs = new List<string>[n]; // i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번) var index = new Dictionary<string, int>(); for (int i = 0; i < n; i++) { string[] w = Console.ReadLine().Trim().Split(' '); // [이름, "=", 항, "+", 항, ...] names[i] = w[0]; index[w[0]] = i; refs[i] = new List<string>(); for (int k = 2; k < w.Length; k += 2) { if (char.IsDigit(w[k][0])) value[i] += long.Parse(w[k]); else refs[i].Add(w[k]); } } var users = new List<int>[n]; // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼) for (int i = 0; i < n; i++) users[i] = new List<int>(); var waiting = new int[n]; // 아직 값을 모르는, 식에 쓴 이름의 수 for (int i = 0; i < n; i++) { foreach (string name in refs[i]) { users[index[name]].Add(i); waiting[i]++; } } // 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다 var known = new bool[n]; var queue = new Queue<int>(); for (int i = 0; i < n; i++) if (waiting[i] == 0) queue.Enqueue(i); while (queue.Count > 0) { int j = queue.Dequeue(); known[j] = true; foreach (int i in users[j]) { value[i] += value[j]; if (--waiting[i] == 0) queue.Enqueue(i); } } // 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다 var sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.Append(names[i]).Append(' '); if (known[i]) sb.Append(value[i]); else sb.Append("ERR"); sb.Append('\n'); } Console.Write(sb.ToString()); }}
C++main.cpp · 61 lines
#include <cctype>#include <iostream>#include <queue>#include <sstream>#include <string>#include <unordered_map>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::string line; std::getline(std::cin, line); int n = std::stoi(line); std::vector<std::string> names(n); std::vector<long long> value(n, 0); // 처음엔 식에 적힌 수들의 합. 10^15까지라 long long std::vector<std::vector<std::string>> refs(n); // i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번) std::unordered_map<std::string, int> index; for (int i = 0; i < n; i++) { std::getline(std::cin, line); std::istringstream words(line); std::string term, sign; words >> names[i] >> sign; // 이름, "=" index[names[i]] = i; while (words >> term) { if (std::isdigit(static_cast<unsigned char>(term[0]))) value[i] += std::stoll(term); else refs[i].push_back(term); words >> sign; // "+" (줄 끝이면 읽지 못하고 끝난다) } } std::vector<std::vector<int>> users(n); // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼) std::vector<int> waiting(n, 0); // 아직 값을 모르는, 식에 쓴 이름의 수 for (int i = 0; i < n; i++) { for (const auto& name : refs[i]) { users[index[name]].push_back(i); waiting[i]++; } } // 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다 std::vector<bool> known(n, false); std::queue<int> queue; for (int i = 0; i < n; i++) if (waiting[i] == 0) queue.push(i); while (!queue.empty()) { int j = queue.front(); queue.pop(); known[j] = true; for (int i : users[j]) { value[i] += value[j]; if (--waiting[i] == 0) queue.push(i); } } // 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다 std::string out; for (int i = 0; i < n; i++) out += names[i] + " " + (known[i] ? std::to_string(value[i]) : "ERR") + "\n"; std::cout << out; return 0;}
Cmain.c · 90 lines
#include <ctype.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 5000#define MAXREF 10000static char names[MAXN][9];static long long value[MAXN]; /* 처음엔 식에 적힌 수들의 합. 10^15까지라 long long */static char refName[MAXREF][9]; /* 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번) */static int refOwner[MAXREF]; /* 그 이름을 쓴 칸 */static int nref;static int sorted[MAXN]; /* 칸 번호를 이름 차례로 늘어놓은 것: 이름 → 번호를 이진 탐색으로 찾는다 */static int byName(const void* a, const void* b) { return strcmp(names[*(const int*)a], names[*(const int*)b]);}static int findCell(const char* name, int n) { int lo = 0, hi = n - 1; while (lo <= hi) { int mid = (lo + hi) / 2; int c = strcmp(names[sorted[mid]], name); if (c == 0) return sorted[mid]; if (c < 0) lo = mid + 1; else hi = mid - 1; } return -1;}/* 같은 칸을 쓰는 칸들을 배열로 엮는다: head[j]에서 시작해 next[e]로 이어지고, user[e]가 쓰는 칸 */static int head[MAXN], next[MAXREF], user[MAXREF];static int waiting[MAXN]; /* 아직 값을 모르는, 식에 쓴 이름의 수 */static int known[MAXN];static int queue[MAXN];int main(void) { char line[256]; if (!fgets(line, sizeof line, stdin)) return 0; int n = atoi(line); for (int i = 0; i < n; i++) { fgets(line, sizeof line, stdin); char* word = strtok(line, " \r\n"); /* 이름 */ strcpy(names[i], word); strtok(NULL, " \r\n"); /* "=" */ while ((word = strtok(NULL, " \r\n")) != NULL) { if (strcmp(word, "+") == 0) continue; if (isdigit((unsigned char)word[0])) { value[i] += atoll(word); } else { strcpy(refName[nref], word); refOwner[nref++] = i; } } } for (int i = 0; i < n; i++) { sorted[i] = i; head[i] = -1; } qsort(sorted, n, sizeof sorted[0], byName); for (int e = 0; e < nref; e++) { int j = findCell(refName[e], n); user[e] = refOwner[e]; next[e] = head[j]; head[j] = e; waiting[refOwner[e]]++; } /* 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다 */ int qhead = 0, qtail = 0; for (int i = 0; i < n; i++) if (waiting[i] == 0) queue[qtail++] = i; while (qhead < qtail) { int j = queue[qhead++]; known[j] = 1; for (int e = head[j]; e != -1; e = next[e]) { int i = user[e]; value[i] += value[j]; if (--waiting[i] == 0) queue[qtail++] = i; } } /* 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다 */ for (int i = 0; i < n; i++) { if (known[i]) printf("%s %lld\n", names[i], value[i]); else printf("%s ERR\n", names[i]); } return 0;}
Craykonmain.cray · 80 lines
n = Console.ReadLine().Trim().ToNumber();names = [];value = []; // 처음엔 식에 적힌 수들의 합, 이름 칸의 값을 알게 될 때마다 더한다refs = []; // refs[i] = i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번)index = Dict(); // 이름 → 칸 번호for (i = 0; i < n; i++){ w = Console.ReadLine().Trim().Split(" "); // [이름, "=", 항, "+", 항, ...] names.Add(w[0]); index[w[0]] = i; c = 0; r = []; for (k = 2; k < w.Count; k += 2) { 첫글자 = Str.Code(w[k][0]); if (첫글자 >= 48 && 첫글자 <= 57) { c += w[k].ToNumber(); } else { r.Add(w[k]); } } value.Add(c); refs.Add(r);}users = []; // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼)for (i = 0; i < n; i++){ users.Add([]);}waiting = NewList(n, 0); // 아직 값을 모르는, 식에 쓴 이름의 수for (i = 0; i < n; i++){ foreach (name in refs[i]) { users[index[name]].Add(i); waiting[i] += 1; }}// 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다known = NewList(n, false);queue = [];for (i = 0; i < n; i++){ if (waiting[i] == 0) { queue.Add(i); }}for (head = 0; head < queue.Count; head++){ j = queue[head]; known[j] = true; foreach (i in users[j]) { value[i] += value[j]; waiting[i] -= 1; if (waiting[i] == 0) { queue.Add(i); } }}// 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다for (i = 0; i < n; i++){ if (known[i]) { Console.WriteLine(names[i] + " " + value[i]); } else { Console.WriteLine(names[i] + " ERR"); }}