You are given a program in a tiny language.
The program is a sequence of tokens separated by spaces, and there are only four kinds of tokens: { opens a block, } closes a block, name=value assigns, and ?name asks.
The whole program is also a block (the outermost one), and { and } always match.
Tokens run once each from front to back, and an inner block runs at the position of its {.
If a block directly contains (not inside its inner blocks) at least one name=value, that name belongs to the whole block, even when the assignment comes after a question.
A question ?name searches outward, starting from the block directly around it, until it meets the first block that owns that name.
If there is no such block, print "undefined".
If the block found has not assigned that name yet, print "unbound".
Otherwise print the last value that block assigned to that name before the question.
When a block ends, its names and values disappear, and it never affects other blocks.
Print one line per question, in order.
Input
Tokens are given over several lines, separated by single spaces (a line end also ends a token). At most 10,000 tokens, nesting depth at most 1,000 not counting the outermost block, at least one question. Names are 1–10 lowercase English letters, values are integers from 0 to 1,000,000,000 without leading zeros.
Output
One line per question: the value, "undefined" or "unbound"
Example 1 · stdin
x=1 ?x {
?x x=2 ?x ?y
{ ?x }
} ?x ?z
stdout
1
unbound
2
undefined
2
1
undefined
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
These rules match Python functions: a name assigned anywhere in a function is local to the whole function, so reading it before the assignment gives UnboundLocalError instead of the outer value (JavaScript's let, too, gives a ReferenceError instead of the outer value when read before the let line in the same block). The solution makes one recursive call per block: first it puts an 'unbound' cell for each name the block owns on top of that name's stack, then runs the block in order, and finally removes those cells. A question then only looks at the top cell of the name's stack. Here the scope of the solution's own variables matters. What must be separate per call (the block number, the list of names the block owns, the scanning position) goes in local variables, and what all calls share (the block counter, the output) lives outside. Python needs global block_count to assign an outer name inside a function; without it the name becomes local and raises UnboundLocalError. JavaScript/TypeScript update the outer let through the closure, Java/C# use a static field, and C/C++ a global variable. In Craykon, a variable created at the top level of the main body (outside functions and blocks) is the same single variable inside functions, so if the k used inside the function is also used in the main body, a recursive call overwrites the outer call's k — pick names used only inside the function. The blocks also nest 1,000 deep, so the recursion goes over 1,000 levels. Python's default limit is 1,000, so raise it with sys.setrecursionlimit; Craykon handles a few thousand levels. The traps are (1) forgetting global, (2) the recursion limit, (3) creating a name only when it is assigned (then a question before the assignment prints the outer value instead of "unbound"), and (4) sharing a name between the main body and a function in Craykon.
Pythonmain.py · 65 lines
import syssys.setrecursionlimit(10_000) # 블록이 1,000겹까지 겹친다. Python 기본 한도는 1,000tokens = sys.stdin.read().split()# 짝 괄호 자리: match[i] = i번 '{'와 짝인 '}'의 자리match = [0] * len(tokens)opened = []for i, tok in enumerate(tokens): if tok == "{": opened.append(i) elif tok == "}": match[opened.pop()] = i# 이름마다 칸 더미: 맨 위 칸이 지금 보이는 블록의 것. 칸은 [블록 번호, 값], 값 -1은 아직 넣지 않음cells = {}block_count = 0out = []def run(lo, hi): """lo..hi-1 칸이 한 블록이다. 이 블록이 가진 이름을 먼저 모두 세운 뒤 차례로 실행한다.""" global block_count block_count += 1 me = block_count owned = [] i = lo while i < hi: # 1단계: 블록 안 어디에서든 넣는 이름은 블록 전체의 것 tok = tokens[i] if tok == "{": i = match[i] + 1 continue if "=" in tok: name = tok[: tok.index("=")] stack = cells.setdefault(name, []) if not stack or stack[-1][0] != me: stack.append([me, -1]) owned.append(name) i += 1 i = lo while i < hi: # 2단계: 차례로 실행 tok = tokens[i] if tok == "{": run(i + 1, match[i]) i = match[i] + 1 continue if tok[0] == "?": stack = cells.get(tok[1:]) if not stack: out.append("undefined") elif stack[-1][1] == -1: out.append("unbound") else: out.append(str(stack[-1][1])) else: name, value = tok.split("=") cells[name][-1][1] = int(value) # 맨 위 칸은 이 블록의 것 i += 1 for name in owned: # 블록을 나가면 이 블록의 칸을 걷는다 cells[name].pop()run(0, len(tokens))print("\n".join(out))
JavaScriptmain.js · 58 lines
const tokens = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((t) => t !== "");// 짝 괄호 자리: match[i] = i번 '{'와 짝인 '}'의 자리const match = new Array(tokens.length).fill(0);const opened = [];tokens.forEach((tok, i) => { if (tok === "{") opened.push(i); else if (tok === "}") match[opened.pop()] = i;});// 이름마다 칸 더미: 맨 위 칸이 지금 보이는 블록의 것. 칸은 { block, value }, value -1은 아직 넣지 않음const cells = new Map();let blockCount = 0; // 함수 밖에서 만든 let — 안에서 고치면 이 하나가 바뀐다const out = [];// lo..hi-1 칸이 한 블록이다. 이 블록이 가진 이름을 먼저 모두 세운 뒤 차례로 실행한다function run(lo, hi) { const me = ++blockCount; const owned = []; for (let i = lo; i < hi; i++) { // 1단계: 블록 안 어디에서든 넣는 이름은 블록 전체의 것 const tok = tokens[i]; if (tok === "{") { i = match[i]; continue; } const eq = tok.indexOf("="); if (eq < 0) continue; const name = tok.slice(0, eq); if (!cells.has(name)) cells.set(name, []); const stack = cells.get(name); if (stack.length === 0 || stack[stack.length - 1].block !== me) { stack.push({ block: me, value: -1 }); owned.push(name); } } for (let i = lo; i < hi; i++) { // 2단계: 차례로 실행 const tok = tokens[i]; if (tok === "{") { run(i + 1, match[i]); i = match[i]; } else if (tok[0] === "?") { const stack = cells.get(tok.slice(1)); if (!stack || stack.length === 0) out.push("undefined"); else if (stack[stack.length - 1].value === -1) out.push("unbound"); else out.push(String(stack[stack.length - 1].value)); } else { const [name, value] = tok.split("="); const stack = cells.get(name); stack[stack.length - 1].value = Number(value); // 맨 위 칸은 이 블록의 것 } } for (const name of owned) cells.get(name).pop(); // 블록을 나가면 이 블록의 칸을 걷는다}run(0, tokens.length);console.log(out.join("\n"));
TypeScriptmain.ts · 66 lines
import { readFileSync } from "node:fs";const tokens: string[] = readFileSync(0, "utf8").split(/\s+/).filter((t) => t !== "");// 짝 괄호 자리: match[i] = i번 '{'와 짝인 '}'의 자리const match: number[] = new Array<number>(tokens.length).fill(0);const opened: number[] = [];tokens.forEach((tok, i) => { if (tok === "{") opened.push(i); else if (tok === "}") match[opened.pop()!] = i;});// 이름마다 칸 더미: 맨 위 칸이 지금 보이는 블록의 것. value -1은 아직 넣지 않음interface Cell { block: number; value: number;}const cells = new Map<string, Cell[]>();let blockCount = 0; // 함수 밖에서 만든 let — 안에서 고치면 이 하나가 바뀐다const out: string[] = [];// lo..hi-1 칸이 한 블록이다. 이 블록이 가진 이름을 먼저 모두 세운 뒤 차례로 실행한다function run(lo: number, hi: number): void { const me = ++blockCount; const owned: string[] = []; for (let i = lo; i < hi; i++) { // 1단계: 블록 안 어디에서든 넣는 이름은 블록 전체의 것 const tok = tokens[i]; if (tok === "{") { i = match[i]; continue; } const eq = tok.indexOf("="); if (eq < 0) continue; const name = tok.slice(0, eq); let stack = cells.get(name); if (stack === undefined) { stack = []; cells.set(name, stack); } if (stack.length === 0 || stack[stack.length - 1].block !== me) { stack.push({ block: me, value: -1 }); owned.push(name); } } for (let i = lo; i < hi; i++) { // 2단계: 차례로 실행 const tok = tokens[i]; if (tok === "{") { run(i + 1, match[i]); i = match[i]; } else if (tok[0] === "?") { const stack = cells.get(tok.slice(1)); if (stack === undefined || stack.length === 0) out.push("undefined"); else if (stack[stack.length - 1].value === -1) out.push("unbound"); else out.push(String(stack[stack.length - 1].value)); } else { const [name, value] = tok.split("="); const stack = cells.get(name)!; stack[stack.length - 1].value = Number(value); // 맨 위 칸은 이 블록의 것 } } for (const name of owned) cells.get(name)!.pop(); // 블록을 나가면 이 블록의 칸을 걷는다}run(0, tokens.length);console.log(out.join("\n"));
JavaMain.java · 70 lines
import java.io.*;import java.util.*;public class Main { // 이름마다 칸 더미의 한 칸. value -1은 아직 넣지 않음 static final class Cell { final int block; long value = -1; Cell(int block) { this.block = block; } } static String[] tokens; static int[] match; static final Map<String, ArrayDeque<Cell>> cells = new HashMap<>(); static int blockCount = 0; // static 필드: 모든 호출이 같은 하나를 본다 static final StringBuilder out = new StringBuilder(); // lo..hi-1 칸이 한 블록이다. 이 블록이 가진 이름을 먼저 모두 세운 뒤 차례로 실행한다 static void run(int lo, int hi) { int me = ++blockCount; List<String> owned = new ArrayList<>(); // 지역 변수: 호출마다 따로 for (int i = lo; i < hi; i++) { // 1단계: 블록 안 어디에서든 넣는 이름은 블록 전체의 것 String tok = tokens[i]; if (tok.equals("{")) { i = match[i]; continue; } int eq = tok.indexOf('='); if (eq < 0) continue; String name = tok.substring(0, eq); ArrayDeque<Cell> stack = cells.computeIfAbsent(name, k -> new ArrayDeque<>()); if (stack.isEmpty() || stack.peek().block != me) { stack.push(new Cell(me)); owned.add(name); } } for (int i = lo; i < hi; i++) { // 2단계: 차례로 실행 String tok = tokens[i]; if (tok.equals("{")) { run(i + 1, match[i]); i = match[i]; } else if (tok.charAt(0) == '?') { ArrayDeque<Cell> stack = cells.get(tok.substring(1)); if (stack == null || stack.isEmpty()) out.append("undefined\n"); else if (stack.peek().value == -1) out.append("unbound\n"); else out.append(stack.peek().value).append('\n'); } else { int eq = tok.indexOf('='); cells.get(tok.substring(0, eq)).peek().value = Long.parseLong(tok.substring(eq + 1)); } } for (String name : owned) cells.get(name).pop(); // 블록을 나가면 이 블록의 칸을 걷는다 } public static void main(String[] args) throws IOException { String all = new String(System.in.readAllBytes()).trim(); tokens = all.split("\\s+"); match = new int[tokens.length]; ArrayDeque<Integer> opened = new ArrayDeque<>(); for (int i = 0; i < tokens.length; i++) { if (tokens[i].equals("{")) opened.push(i); else if (tokens[i].equals("}")) match[opened.pop()] = i; } run(0, tokens.length); System.out.print(out); }}
C#Main.cs · 83 lines
using System;using System.Collections.Generic;using System.Text;class Program{ // 이름마다 칸 더미의 한 칸. Value -1은 아직 넣지 않음 class Cell { public int Block; public long Value = -1; } static string[] tokens; static int[] match; static readonly Dictionary<string, Stack<Cell>> cells = new Dictionary<string, Stack<Cell>>(); static int blockCount = 0; // static 필드: 모든 호출이 같은 하나를 본다 static readonly StringBuilder output = new StringBuilder(); // lo..hi-1 칸이 한 블록이다. 이 블록이 가진 이름을 먼저 모두 세운 뒤 차례로 실행한다 static void Run(int lo, int hi) { int me = ++blockCount; var owned = new List<string>(); // 지역 변수: 호출마다 따로 for (int i = lo; i < hi; i++) // 1단계: 블록 안 어디에서든 넣는 이름은 블록 전체의 것 { string tok = tokens[i]; if (tok == "{") { i = match[i]; continue; } int eq = tok.IndexOf('='); if (eq < 0) continue; string name = tok.Substring(0, eq); if (!cells.TryGetValue(name, out var stack)) { stack = new Stack<Cell>(); cells[name] = stack; } if (stack.Count == 0 || stack.Peek().Block != me) { stack.Push(new Cell { Block = me }); owned.Add(name); } } for (int i = lo; i < hi; i++) // 2단계: 차례로 실행 { string tok = tokens[i]; if (tok == "{") { Run(i + 1, match[i]); i = match[i]; } else if (tok[0] == '?') { if (!cells.TryGetValue(tok.Substring(1), out var stack) || stack.Count == 0) output.Append("undefined\n"); else if (stack.Peek().Value == -1) output.Append("unbound\n"); else output.Append(stack.Peek().Value).Append('\n'); } else { int eq = tok.IndexOf('='); cells[tok.Substring(0, eq)].Peek().Value = long.Parse(tok.Substring(eq + 1)); } } foreach (string name in owned) cells[name].Pop(); // 블록을 나가면 이 블록의 칸을 걷는다 } static void Main() { tokens = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); match = new int[tokens.Length]; var opened = new Stack<int>(); for (int i = 0; i < tokens.Length; i++) { if (tokens[i] == "{") opened.Push(i); else if (tokens[i] == "}") match[opened.Pop()] = i; } Run(0, tokens.Length); Console.Write(output); }}
C++main.cpp · 70 lines
#include <iostream>#include <string>#include <unordered_map>#include <vector>// 이름마다 칸 더미의 한 칸. value -1은 아직 넣지 않음struct Cell { int block; long long value;};std::vector<std::string> tokens;std::vector<int> match;std::unordered_map<std::string, std::vector<Cell>> cells;int blockCount = 0; // 전역 변수: 모든 호출이 같은 하나를 본다std::string out;// lo..hi-1 칸이 한 블록이다. 이 블록이 가진 이름을 먼저 모두 세운 뒤 차례로 실행한다void run(int lo, int hi) { int me = ++blockCount; std::vector<std::string> owned; // 지역 변수: 호출마다 따로 for (int i = lo; i < hi; i++) { // 1단계: 블록 안 어디에서든 넣는 이름은 블록 전체의 것 const std::string& tok = tokens[i]; if (tok == "{") { i = match[i]; continue; } size_t eq = tok.find('='); if (eq == std::string::npos) continue; std::string name = tok.substr(0, eq); auto& stack = cells[name]; if (stack.empty() || stack.back().block != me) { stack.push_back({me, -1}); owned.push_back(name); } } for (int i = lo; i < hi; i++) { // 2단계: 차례로 실행 const std::string& tok = tokens[i]; if (tok == "{") { run(i + 1, match[i]); i = match[i]; } else if (tok[0] == '?') { auto it = cells.find(tok.substr(1)); if (it == cells.end() || it->second.empty()) out += "undefined\n"; else if (it->second.back().value == -1) out += "unbound\n"; else out += std::to_string(it->second.back().value) + "\n"; } else { size_t eq = tok.find('='); cells[tok.substr(0, eq)].back().value = std::stoll(tok.substr(eq + 1)); } } for (const auto& name : owned) cells[name].pop_back(); // 블록을 나가면 이 블록의 칸을 걷는다}int main() { std::ios::sync_with_stdio(false); std::string tok; while (std::cin >> tok) tokens.push_back(tok); match.assign(tokens.size(), 0); std::vector<int> opened; for (int i = 0; i < (int)tokens.size(); i++) { if (tokens[i] == "{") opened.push_back(i); else if (tokens[i] == "}") { match[opened.back()] = i; opened.pop_back(); } } run(0, (int)tokens.size()); std::cout << out;}
Cmain.c · 100 lines
#include <stdio.h>#include <string.h>#define MAXT 10000#define HASH 32768/* 토큰을 미리 풀어 둔다: kind 0 '{', 1 '}', 2 넣기, 3 질문 */static int kind[MAXT], nid[MAXT], match[MAXT], ntok = 0;static long long val[MAXT];/* 이름 → 번호(열린 주소 해시) */static char names[MAXT][12];static int nnames = 0, table[HASH];int name_id(const char *s, int len) { unsigned h = 0; for (int i = 0; i < len; i++) h = h * 31 + (unsigned char)s[i]; for (h %= HASH;; h = (h + 1) % HASH) { if (table[h] == -1) { memcpy(names[nnames], s, len); names[nnames][len] = '\0'; table[h] = nnames; return nnames++; } const char *t = names[table[h]]; if ((int)strlen(t) == len && memcmp(t, s, len) == 0) return table[h]; }}/* 이름마다 칸 더미: top[이름]이 맨 위 칸, 칸마다 블록 번호·값(-1은 아직 넣지 않음)·아래 칸 */static int top[MAXT], cell_block[MAXT], cell_prev[MAXT], ncells = 0;static long long cell_value[MAXT];/* 블록마다 가진 이름: 호출마다 base부터 쌓고 나갈 때 base로 되돌린다 */static int owned[MAXT], nowned = 0;static int block_count = 0; /* 전역 변수: 모든 호출이 같은 하나를 본다 *//* lo..hi-1 칸이 한 블록이다. 이 블록이 가진 이름을 먼저 모두 세운 뒤 차례로 실행한다 */void run(int lo, int hi) { int me = ++block_count; int base = nowned; /* 지역 변수: 호출마다 따로 */ for (int i = lo; i < hi; i++) { /* 1단계: 블록 안 어디에서든 넣는 이름은 블록 전체의 것 */ if (kind[i] == 0) { i = match[i]; continue; } if (kind[i] != 2) continue; int id = nid[i]; if (top[id] == -1 || cell_block[top[id]] != me) { cell_block[ncells] = me; cell_value[ncells] = -1; cell_prev[ncells] = top[id]; top[id] = ncells++; owned[nowned++] = id; } } for (int i = lo; i < hi; i++) { /* 2단계: 차례로 실행 */ if (kind[i] == 0) { run(i + 1, match[i]); i = match[i]; } else if (kind[i] == 3) { int c = top[nid[i]]; if (c == -1) puts("undefined"); else if (cell_value[c] == -1) puts("unbound"); else printf("%lld\n", cell_value[c]); } else if (kind[i] == 2) { cell_value[top[nid[i]]] = val[i]; /* 맨 위 칸은 이 블록의 것 */ } } while (nowned > base) { /* 블록을 나가면 이 블록의 칸을 걷는다 */ int id = owned[--nowned]; top[id] = cell_prev[top[id]]; }}int main(void) { memset(table, -1, sizeof table); memset(top, -1, sizeof top); static char buf[32]; int opened[MAXT], nopen = 0; while (scanf("%31s", buf) == 1) { int i = ntok++; if (buf[0] == '{') { kind[i] = 0; opened[nopen++] = i; } else if (buf[0] == '}') { kind[i] = 1; match[opened[--nopen]] = i; } else if (buf[0] == '?') { kind[i] = 3; nid[i] = name_id(buf + 1, (int)strlen(buf + 1)); } else { char *eq = strchr(buf, '='); kind[i] = 2; nid[i] = name_id(buf, (int)(eq - buf)); sscanf(eq + 1, "%lld", &val[i]); } } run(0, ntok); return 0;}
Craykonmain.cray · 116 lines
// 이름마다 칸 더미: 맨 위 칸이 지금 보이는 블록의 것. 칸은 [블록 번호, 값], 값 -1은 아직 넣지 않음// 함수 안에서 쓰는 이름(lo, hi, blockId, owned, k, tok …)은 아래 본문에서 쓰지 않는다:// 본문 맨 바깥에서 만든 이름은 모든 호출이 함께 쓰는 하나가 되기 때문이다실행(lo, hi){ blockCount += 1; blockId = blockCount; owned = []; k = lo; while (k < hi) { tok = tokens[k]; if (tok == "{") { k = match[k] + 1; } else { eq = tok.IndexOf("="); if (eq >= 0) { name = tok.Substring(0, eq); if (!cells.Contains(name)) { cells[name] = []; } stack = cells[name]; if (stack.Count == 0 || stack[stack.Count - 1][0] != blockId) { stack.Add([blockId, -1]); owned.Add(name); } } k += 1; } } k = lo; while (k < hi) { tok = tokens[k]; if (tok == "{") { 실행(k + 1, match[k]); k = match[k]; } else if (tok[0] == "?") { name = tok.Substring(1); if (!cells.Contains(name) || cells[name].Count == 0) { out += "undefined\n"; } else { stack = cells[name]; cell = stack[stack.Count - 1]; if (cell[1] == -1) { out += "unbound\n"; } else { out += cell[1] + "\n"; } } } else { eq = tok.IndexOf("="); stack = cells[tok.Substring(0, eq)]; stack[stack.Count - 1][1] = tok.Substring(eq + 1).ToNumber(); // 맨 위 칸은 이 블록의 것 } k += 1; } foreach (name in owned) { stack = cells[name]; stack.RemoveAt(stack.Count - 1); }}tokens = [];line = Console.ReadLine();while (line != null){ foreach (t in line.Split(" ")) { if (t != "") { tokens.Add(t); } } line = Console.ReadLine();}// 짝 괄호 자리: match[i] = i번 '{'와 짝인 '}'의 자리match = NewList(tokens.Count, 0);opened = [];for (i = 0; i < tokens.Count; i++){ if (tokens[i] == "{") { opened.Add(i); } else if (tokens[i] == "}") { match[opened[opened.Count - 1]] = i; opened.RemoveAt(opened.Count - 1); }}cells = Dict();blockCount = 0; // 본문에서 만든 이름이라 함수 안에서 바꾸면 이 하나가 바뀐다out = "";실행(0, tokens.Count);Console.Write(out);