A calculation tree that evaluates only the chosen side
There is a calculation tree of n nodes. The nodes are numbered 1 to n, and node 1 is the root.
The first line gives n and the number of input values m, and the next n lines give the nodes in order from node 1. Each node is one of six kinds.
The value of num v is the integer v.
The value of in k is the k-th input value of the query.
The value of add a b is (value of node a) + (value of node b), and the value of sub a b is (value of node a) − (value of node b).
The value of div a b is the quotient of (value of node a) ÷ (value of node b), with the fractional part dropped toward 0 (−7 ÷ 2 is −3). If the value of node b is 0, this node cannot be calculated.
if a b c d first finds the values of nodes a and b. If (value of node a) < (value of node b), the value of node c is this node's value; otherwise the value of node d is. The node that is not chosen is not calculated.
If any node needed to calculate a node cannot be calculated, that node cannot be calculated either.
The next line gives the number of queries q, and the next q lines give m input values for each query, separated by spaces.
Solve it with a recursive function that returns a node's value. The function reports 'cannot be calculated' either by returning a separate marker value or, where the language suits it, by throwing an exception.
For each query, print the value of the root on one line. If the root cannot be calculated, print "error".
Input
1 ≤ n ≤ 999, 1 ≤ m ≤ 10, 1 ≤ q ≤ 300. Across the a, b, c, d of all nodes, each number from 2 to n appears exactly once and 1 never appears. Calling those nodes children, a child's number is greater than its parent's. Any path from the root to a leaf has at most 500 nodes. 1 ≤ k ≤ m. v and the input values are integers from -1,000,000 to 1,000,000. Every node that can be calculated, including nodes on an unchosen side, has a value with absolute value at most 1,000,000,000
Output
q lines
Example 1 · stdin
9 1
if 2 3 4 7
in 1
num 0
div 5 6
num 100
in 1
sub 8 9
num 0
in 1
4
5
-7
0
-3
stdout
-5
-14
0
-33
Example 2 · stdin
7 3
add 2 3
in 1
div 4 5
num -7
sub 6 7
in 2
in 3
4
1 3 1
0 5 5
-1 9 2
4 2 4
stdout
-2
error
-2
7
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
Languages return 'no value' in different ways: Python None, JS/TS null (in TS write number | null, and checking === null narrows it to number), C# int?, C++ std::optional<int>, Craykon null. C returns whether it succeeded and puts the value through a pointer int *out. The Java solution uses an exception: dividing an int by 0 makes / throw ArithmeticException, which travels up through all the callers to the catch at the top by itself. Trap ① picking a special value: using -1 or 0 to mean 'cannot be calculated' mixes it up with real answers -1 and 0. ② calculating the side that is not chosen: if you compute c = value(...) and d = value(...) first and then choose, a division by 0 on the unchosen side prints "error". ③ forgetting return in the recursion: Python silently returns None and JS undefined. In C the value is undefined, and Java and C# reject it at compile time. ④ division by zero: Python raises ZeroDivisionError, Java ArithmeticException, C# DivideByZeroException, Craykon Mathf.Quot stops, and in C and C++ it is undefined behaviour. JS/TS do not stop; they give Infinity or NaN. ⑤ the quotient: Python // rounds down, so -7 // 2 is -4. Craykon / divides into decimals, so use Mathf.Quot. ⑥ C# int? passes null through + - / by itself, but a < b is simply false when either side is null, so without a check you get d's value instead of an error. Craykon stops when you calculate with or compare null.
Pythonmain.py · 43 lines
import sysdata = sys.stdin.read().split("\n")n, m = map(int, data[0].split())nodes = [None] + [data[i].split() for i in range(1, n + 1)]q = int(data[n + 1])def div(a, b): # 0 쪽으로 버리는 몫. Python의 //는 아래로 내려서 음수에서 다르다 qt = abs(a) // abs(b) return qt if (a < 0) == (b < 0) else -qtdef value(i, x): """i번 마디의 값을 돌려준다. 계산할 수 없으면 None을 돌려준다.""" op, *args = nodes[i] if op == "num": return int(args[0]) if op == "in": return x[int(args[0]) - 1] a = value(int(args[0]), x) if a is None: return None # 실패는 곧바로 위로 돌려보낸다 b = value(int(args[1]), x) if b is None: return None if op == "add": return a + b if op == "sub": return a - b if op == "div": return None if b == 0 else div(a, b) # if: 고른 쪽 하나만 계산한다 return value(int(args[2]) if a < b else int(args[3]), x)out = []for line in data[n + 2:n + 2 + q]: x = list(map(int, line.split())) v = value(1, x) out.append("error" if v is None else str(v)) # 0이나 -1도 올바른 값이라 None으로 가른다print("\n".join(out))
JavaScriptmain.js · 28 lines
const data = require("fs").readFileSync(0, "utf8").split("\n");const [n] = data[0].split(" ").map(Number);const nodes = [null];for (let i = 1; i <= n; i++) nodes.push(data[i].trim().split(" "));const q = Number(data[n + 1]);// i번 마디의 값을 돌려준다. 계산할 수 없으면 null을 돌려준다function value(i, x) { const [op, ...args] = nodes[i]; const k = args.map(Number); if (op === "num") return k[0]; if (op === "in") return x[k[0] - 1]; const a = value(k[0], x); if (a === null) return null; // 실패는 곧바로 위로 돌려보낸다 const b = value(k[1], x); if (b === null) return null; if (op === "add") return a + b; if (op === "sub") return a - b; if (op === "div") return b === 0 ? null : Math.trunc(a / b); // JS는 0으로 나눠도 멈추지 않고 Infinity를 준다 return value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다}const out = [];for (const line of data.slice(n + 2, n + 2 + q)) { const v = value(1, line.trim().split(" ").map(Number)); out.push(v === null ? "error" : String(v)); // 0도 올바른 값이라 !v로 묻지 않는다}console.log(out.join("\n"));
TypeScriptmain.ts · 30 lines
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").split("\n");const [n] = data[0].split(" ").map(Number);const nodes: string[][] = [[]];for (let i = 1; i <= n; i++) nodes.push(data[i].trim().split(" "));const q = Number(data[n + 1]);// i번 마디의 값을 돌려준다. 계산할 수 없으면 null을 돌려준다function value(i: number, x: number[]): number | null { const [op, ...args] = nodes[i]; const k = args.map(Number); if (op === "num") return k[0]; if (op === "in") return x[k[0] - 1]; const a = value(k[0], x); if (a === null) return null; // 실패는 곧바로 위로 돌려보낸다(검사해야 a가 number로 좁혀진다) const b = value(k[1], x); if (b === null) return null; if (op === "add") return a + b; if (op === "sub") return a - b; if (op === "div") return b === 0 ? null : Math.trunc(a / b); // JS는 0으로 나눠도 멈추지 않고 Infinity를 준다 return value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다}const out: string[] = [];for (const line of data.slice(n + 2, n + 2 + q)) { const v = value(1, line.trim().split(" ").map(Number)); out.push(v === null ? "error" : String(v)); // 0도 올바른 값이라 !v로 묻지 않는다}console.log(out.join("\n"));
JavaMain.java · 50 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static String[] op; static int[][] arg; // i번 마디의 값을 돌려준다. 0으로 나누면 Java의 / 가 ArithmeticException을 던지고, // 그 예외가 부른 쪽들을 거쳐 맨 위까지 올라간다 static int value(int i, int[] x) { int[] k = arg[i]; switch (op[i]) { case "num": return k[0]; case "in": return x[k[0] - 1]; case "add": return value(k[0], x) + value(k[1], x); case "sub": return value(k[0], x) - value(k[1], x); case "div": return value(k[0], x) / value(k[1], x); // int의 / 는 0 쪽으로 버린다 default: // if: 고른 쪽 하나만 계산한다 return value(k[0], x) < value(k[1], x) ? value(k[2], x) : value(k[3], x); } } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]); op = new String[n + 1]; arg = new int[n + 1][]; for (int i = 1; i <= n; i++) { String[] p = in.readLine().trim().split(" "); op[i] = p[0]; arg[i] = new int[p.length - 1]; for (int j = 1; j < p.length; j++) arg[i][j - 1] = Integer.parseInt(p[j]); } int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { String[] p = in.readLine().trim().split(" "); int[] x = new int[p.length]; for (int j = 0; j < p.length; j++) x[j] = Integer.parseInt(p[j]); try { out.append(value(1, x)).append('\n'); } catch (ArithmeticException e) { out.append("error\n"); } } System.out.print(out); }}
C#Main.cs · 50 lines
using System;using System.Linq;using System.Text;class Program{ static string[] op = Array.Empty<string>(); static int[][] arg = Array.Empty<int[]>(); // i번 마디의 값을 돌려준다. 계산할 수 없으면 null(int?)을 돌려준다 static int? Value(int i, int[] x) { int[] k = arg[i]; if (op[i] == "num") return k[0]; if (op[i] == "in") return x[k[0] - 1]; int? a = Value(k[0], x); if (a is null) return null; // 실패는 곧바로 위로 돌려보낸다 int? b = Value(k[1], x); if (b is null) return null; switch (op[i]) { case "add": return a + b; case "sub": return a - b; case "div": return b == 0 ? null : a / b; // int의 / 는 0 쪽으로 버린다 default: return Value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다 } } static void Main() { int n = int.Parse(Console.ReadLine().Split(' ')[0]); op = new string[n + 1]; arg = new int[n + 1][]; for (int i = 1; i <= n; i++) { string[] p = Console.ReadLine().Trim().Split(' '); op[i] = p[0]; arg[i] = p.Skip(1).Select(int.Parse).ToArray(); } int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int t = 0; t < q; t++) { int[] x = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); int? v = Value(1, x); sb.Append(v is null ? "error" : v.ToString()).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 55 lines
#include <iostream>#include <optional>#include <string>#include <vector>struct Node { std::string op; std::vector<int> k;};std::vector<Node> nodes;std::vector<int> x;// i번 마디의 값을 돌려준다. 계산할 수 없으면 값이 없는 optional(std::nullopt)std::optional<int> value(int i) { const Node &nd = nodes[i]; if (nd.op == "num") return nd.k[0]; if (nd.op == "in") return x[nd.k[0] - 1]; auto a = value(nd.k[0]); if (!a) return std::nullopt; // 실패는 곧바로 위로 돌려보낸다 auto b = value(nd.k[1]); if (!b) return std::nullopt; if (nd.op == "add") return *a + *b; if (nd.op == "sub") return *a - *b; if (nd.op == "div") { if (*b == 0) return std::nullopt; return *a / *b; // 0 쪽으로 버린다 } return value(*a < *b ? nd.k[2] : nd.k[3]); // if: 고른 쪽 하나만 계산한다}int main() { std::ios::sync_with_stdio(false); int n, m, q; std::cin >> n >> m; nodes.resize(n + 1); for (int i = 1; i <= n; i++) { Node &nd = nodes[i]; std::cin >> nd.op; int cnt = nd.op == "if" ? 4 : (nd.op == "num" || nd.op == "in") ? 1 : 2; nd.k.resize(cnt); for (int &v : nd.k) std::cin >> v; } std::cin >> q; x.resize(m); std::string out; for (int t = 0; t < q; t++) { for (int &v : x) std::cin >> v; auto v = value(1); out += v ? std::to_string(*v) : "error"; out += '\n'; } std::cout << out; return 0;}
Cmain.c · 45 lines
#include <stdio.h>#include <string.h>static char op[1001]; /* n a s d i: num add sub div if, 'x'는 in */static int arg[1001][4];static int x[10];/* i번 마디의 값을 *out에 넣고 1을 돌려준다. 계산할 수 없으면 0을 돌려준다. 값과 성공 여부를 따로 돌려주니 -1이나 0도 올바른 값으로 쓸 수 있다 */static int value(int i, int *out) { int *k = arg[i], a, b; if (op[i] == 'n') { *out = k[0]; return 1; } if (op[i] == 'x') { *out = x[k[0] - 1]; return 1; } if (!value(k[0], &a) || !value(k[1], &b)) return 0; /* 실패는 곧바로 위로 */ switch (op[i]) { case 'a': *out = a + b; return 1; case 's': *out = a - b; return 1; case 'd': if (b == 0) return 0; /* C에서 0으로 나누면 정의되지 않은 동작 */ *out = a / b; /* C99부터 0 쪽으로 버린다 */ return 1; default: /* if: 고른 쪽 하나만 계산한다 */ return value(a < b ? k[2] : k[3], out); }}int main(void) { int n, m, q; char name[8]; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%7s", name); int cnt = strcmp(name, "if") == 0 ? 4 : strcmp(name, "num") == 0 || strcmp(name, "in") == 0 ? 1 : 2; op[i] = strcmp(name, "in") == 0 ? 'x' : strcmp(name, "if") == 0 ? 'i' : name[0]; for (int j = 0; j < cnt; j++) scanf("%d", &arg[i][j]); } scanf("%d", &q); for (int t = 0; t < q; t++) { for (int j = 0; j < m; j++) scanf("%d", &x[j]); int v; if (value(1, &v)) printf("%d\n", v); else puts("error"); } return 0;}
Craykonmain.cray · 68 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];마디들 = [null];for (i = 1; i <= n; i++){ 마디들.Add(Console.ReadLine().Trim().Split(" "));}q = Console.ReadLine().ToNumber();x = [];// 번호 마디의 값을 돌려준다. 계산할 수 없으면 빈값을 돌려준다// 함수 안에서 처음 넣은 이름(마디, 가, 다)은 부를 때마다 따로 생겨서 재귀해도 섞이지 않는다값(번호){ 마디 = 마디들[번호]; if (마디[0] == "num") { return 마디[1].ToNumber(); } if (마디[0] == "in") { return x[마디[1].ToNumber() - 1]; } 가 = 값(마디[1].ToNumber()); if (가 == null) { return null; // 빈값으로 계산하면 멈추니, 실패는 곧바로 위로 돌려보낸다 } 다 = 값(마디[2].ToNumber()); if (다 == null) { return null; } switch (마디[0]) { case "add": return 가 + 다; case "sub": return 가 - 다; case "div": if (다 == 0) { return null; } return Mathf.Quot(가, 다); // 0 쪽으로 버리는 몫 default: // if: 고른 쪽 하나만 계산한다 if (가 < 다) { return 값(마디[3].ToNumber()); } return 값(마디[4].ToNumber()); }}for (t = 0; t < q; t++){ x = Console.ReadNumbers(); v = 값(1); if (v == null) { Console.WriteLine("error"); } else { Console.WriteLine(v); }}