節 n 個からなる計算木がある。 節には 1 番から n 番までの番号があり、1 番の節が根である。 一行目に n と入力値の数 m、続く n 行に 1 番から順に節が一つずつ与えられる。 節は次の六種類のどれかである。 num v の値は整数 v である。 in k の値は質問の k 番目の入力値である。 add a b の値は（a 番の節の値）+（b 番の節の値）で、sub a b の値は（a 番の節の値）−（b 番の節の値）である。 div a b の値は（a 番の節の値）÷（b 番の節の値）の商である。 商は小数部分を 0 の方へ切り捨てる（−7 ÷ 2 は −3）。 b 番の節の値が 0 なら、この節は計算できない。 if a b c d はまず a 番と b 番の節の値を求める。 （a 番の節の値）<（b 番の節の値）なら c 番の節の値が、そうでなければ d 番の節の値がこの節の値である。 選ばなかったほうの節は計算しない。 ある節の計算に必要な節のうち一つでも計算できなければ、その節も計算できない。 その次の行に質問の数 q、続く q 行に質問ごとに入力値 m 個が空白で区切られて与えられる。 節の値を返す再帰関数を作って解いてみよう。 「計算できない」は、その関数が別に区別した値として返すか、言語に合わせて例外で知らせる。 質問ごとに根の値を一行に出力せよ。 根が計算できなければ "エラー" を出力せよ。
入力
1 ≤ n ≤ 999、1 ≤ m ≤ 10、1 ≤ q ≤ 300。 すべての節の a、b、c、d を通して、2 から n までの番号がちょうど一回ずつ現れ、1 は現れない。 それらの節を子と呼ぶとき、子の番号は親の番号より大きい。 根から葉までの節の数は 500 以下。 1 ≤ k ≤ m。 v と入力値は -1,000,000 以上 1,000,000 以下の整数。 計算できる節であれば、選ばれない側の節も含めて、どの節の値も絶対値が 1,000,000,000 以下
出力
q 行
例 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
例 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
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("エラー" if v is None else str(v)) # 0이나 -1도 올바른 값이라 None으로 가른다print("\n".join(out))
JavaScriptmain.js · 28 行
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 ? "エラー" : String(v)); // 0도 올바른 값이라 !v로 묻지 않는다}console.log(out.join("\n"));
TypeScriptmain.ts · 30 行
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 ? "エラー" : String(v)); // 0도 올바른 값이라 !v로 묻지 않는다}console.log(out.join("\n"));
JavaMain.java · 50 行
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("エラー\n"); } } System.out.print(out); }}
C#Main.cs · 50 行
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 ? "エラー" : v.ToString()).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 55 行
#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) : "エラー"; out += '\n'; } std::cout << out; return 0;}
Cmain.c · 45 行
#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("エラー"); } return 0;}
Craykonmain.cray · 68 行
첫줄 = コンソール.数読み();n = 첫줄[0];마디들 = [なし];繰り返す (i = 1; i <= n; i++){ 마디들.追加(コンソール.行読み().空白除去().分ける(" "));}q = コンソール.行読み().数に();x = [];// 번호 마디의 값을 돌려준다. 계산할 수 없으면 빈값을 돌려준다// 함수 안에서 처음 넣은 이름(마디, 가, 다)은 부를 때마다 따로 생겨서 재귀해도 섞이지 않는다값(번호){ 마디 = 마디들[번호]; もし (마디[0] == "num") { 返す 마디[1].数に(); } もし (마디[0] == "in") { 返す x[마디[1].数に() - 1]; } 가 = 값(마디[1].数に()); もし (가 == なし) { 返す なし; // 빈값으로 계산하면 멈추니, 실패는 곧바로 위로 돌려보낸다 } 다 = 값(마디[2].数に()); もし (다 == なし) { 返す なし; } 選択 (마디[0]) { 場合 "add": 返す 가 + 다; 場合 "sub": 返す 가 - 다; 場合 "div": もし (다 == 0) { 返す なし; } 返す 数学.商(가, 다); // 0 쪽으로 버리는 몫 それ以外: // if: 고른 쪽 하나만 계산한다 もし (가 < 다) { 返す 값(마디[3].数に()); } 返す 값(마디[4].数に()); }}繰り返す (t = 0; t < q; t++){ x = コンソール.数読み(); v = 값(1); もし (v == なし) { コンソール.書く("エラー"); } でなければ { コンソール.書く(v); }}