{"problem":{"name":"I. Karel the Robot","description":{"content":"Did you know that the word \"robot\" is almost 100 years old? It was first introduced in 1920, in the science-fiction theatrical play R.U.R., written by Karel $caron(\"C\")$apek. As a tribute to this Czec","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10251I"},"statements":[{"statement_type":"Markdown","content":"Did you know that the word \"robot\" is almost 100 years old? It was first introduced in 1920, in the science-fiction theatrical play R.U.R., written by Karel $caron(\"C\")$apek. As a tribute to this Czech writer, an educational programming language was named Karel many years later at Stanford University. Your task is to implement an interpreter of a simplified version of this programming language.\n\nThe Karel programming language controls a robot named Karel, who lives in a grid of unit squares. Some of the squares are free, while others contain a barrier. Karel always occupies one of the free squares and faces one of the four cardinal directions. The two basic commands are \"move forward\" and \"turn left\". The language also provides simple conditional and looping statements. The main educational potential of the language lies in the possibility of defining new procedures for more complex tasks. \n\nOur simplified version of the language can be described by the following grammar: \n\nThere are five types of commands:\n\nA condition can be either '_b_', which is satisfied if and only if there is a barrier in the next square in Karel's current heading, or one of the four directional letters '_n_', '_s_', '_e_', or '_w_', which is satisfied if and only if Karel's current heading is north, south, east, or west, respectively. \n\nFor instance, a simple program _ub(m)_ can be understood to mean: \"keep moving forward until there is a barrier\", while _un(l)_ means \"turn to the north\". A procedure definition _R=lll_ defines a new procedure 'R' which effectively means \"turn right\".\n\nThe first line of input contains four integers $r, c, d$, and $e$, where $r$ and $c$ ($1 <= r, c <= 40$) are the dimensions of the grid in which Karel lives, $d$ ($0 <= d <= 26$) is the number of procedure definitions, and $e$ ($1 <= e <= 10$) is the number of programs to be executed.\n\nThen follow $r$ lines describing the grid (running north to south), each containing $c$ characters (running west to east), each character being either '.' (denoting a free square) or '#' (denoting a barrier). All squares outside this given area are considered barriers, which means Karel may never leave the area.\n\nEach of the next $d$ lines contains a procedure definition, associating a procedure name (one uppercase letter) with a program forming the procedure body. No procedure name is defined more than once. Procedure bodies may contain invocations of procedures that have not yet been defined.\n\nThe last $2 e$ lines describe the programs to be executed. Each such description consists of a pair of lines. The first line of each pair contains two integers $i$ and $j$ and a character $h$, where $i$ ($1 <= i <= r$) is the row and $j$ ($1 <= j <= c$) is the column of Karel's initial position, and $h in {mathtt(n , s , e , w)}$ represents Karel's initial heading. It is guaranteed that the initial position is a free square. The second line of each pair contains a program to be executed from that initial position.\n\nAll procedure bodies and all programs to be executed are at least 1 and at most 100 characters long, syntactically correct, and only contain invocations of procedures that are defined. The lines with procedure definitions and programs to be executed contain no whitespace characters.\n\nFor each program execution, output the final position of Karel after the complete program is executed from the respective initial position. Follow the format used to describe initial positions, that is, two numbers and a directional character. If a particular execution never terminates, output _inf_ instead.\n\n## Input\n\nThe first line of input contains four integers $r, c, d$, and $e$, where $r$ and $c$ ($1 <= r, c <= 40$) are the dimensions of the grid in which Karel lives, $d$ ($0 <= d <= 26$) is the number of procedure definitions, and $e$ ($1 <= e <= 10$) is the number of programs to be executed.Then follow $r$ lines describing the grid (running north to south), each containing $c$ characters (running west to east), each character being either '.' (denoting a free square) or '#' (denoting a barrier). All squares outside this given area are considered barriers, which means Karel may never leave the area.Each of the next $d$ lines contains a procedure definition, associating a procedure name (one uppercase letter) with a program forming the procedure body. No procedure name is defined more than once. Procedure bodies may contain invocations of procedures that have not yet been defined.The last $2 e$ lines describe the programs to be executed. Each such description consists of a pair of lines. The first line of each pair contains two integers $i$ and $j$ and a character $h$, where $i$ ($1 <= i <= r$) is the row and $j$ ($1 <= j <= c$) is the column of Karel's initial position, and $h in {mathtt(n , s , e , w)}$ represents Karel's initial heading. It is guaranteed that the initial position is a free square. The second line of each pair contains a program to be executed from that initial position.All procedure bodies and all programs to be executed are at least 1 and at most 100 characters long, syntactically correct, and only contain invocations of procedures that are defined. The lines with procedure definitions and programs to be executed contain no whitespace characters.\n\n## Output\n\nFor each program execution, output the final position of Karel after the complete program is executed from the respective initial position. Follow the format used to describe initial positions, that is, two numbers and a directional character. If a particular execution never terminates, output _inf_ instead.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ r, c \\in \\mathbb{Z}^+ $ be grid dimensions ($1 \\leq r, c \\leq 40$).  \nLet $ \\mathcal{G} \\in \\{ \\texttt{.}, \\texttt{\\#} \\}^{r \\times c} $ be the grid, where $ \\mathcal{G}[i][j] = \\texttt{\\#} $ denotes a barrier, $ \\texttt{.} $ denotes a free square.  \nLet $ d \\in \\mathbb{Z} $ be the number of procedure definitions ($0 \\leq d \\leq 26$).  \nLet $ \\mathcal{P} = \\{ (X, B_X) \\mid X \\in \\texttt{A-Z}, B_X \\in \\texttt{char}^* \\} $ be the set of procedure definitions, where $ B_X $ is the body of procedure $ X $.  \nLet $ e \\in \\mathbb{Z}^+ $ be the number of programs to execute ($1 \\leq e \\leq 10$).  \n\nLet $ \\mathcal{H} = \\{ \\texttt{n}, \\texttt{s}, \\texttt{e}, \\texttt{w} \\} $ be the set of headings.  \nLet $ \\mathcal{C} = \\{ \\texttt{m}, \\texttt{l}, \\texttt{u}, \\texttt{b}, \\texttt{n}, \\texttt{s}, \\texttt{e}, \\texttt{w}, \\texttt{(}, \\texttt{)} \\} \\cup \\texttt{A-Z} $ be the command alphabet.  \n\nA **state** is a triple $ (p, h) \\in \\{1, \\dots, r\\} \\times \\{1, \\dots, c\\} \\times \\mathcal{H} $, where $ p = (i,j) $ is Karel’s position and $ h $ is its heading.  \n\n**Commands**:  \n- $ \\texttt{m} $: move forward one square in current heading (if next square is free; else, halt).  \n- $ \\texttt{l} $: turn left (heading updates: $ \\texttt{n} \\to \\texttt{w}, \\texttt{w} \\to \\texttt{s}, \\texttt{s} \\to \\texttt{e}, \\texttt{e} \\to \\texttt{n} $).  \n- $ \\texttt{u}\\,C $: if condition $ C \\in \\{ \\texttt{b}, \\texttt{n}, \\texttt{s}, \\texttt{e}, \\texttt{w} \\} $ is true, execute command $ C $; else, do nothing.  \n- $ \\texttt{b}\\,P $: while condition $ C \\in \\{ \\texttt{b}, \\texttt{n}, \\texttt{s}, \\texttt{e}, \\texttt{w} \\} $ is true, execute program $ P $.  \n- $ X $: invoke procedure $ X \\in \\texttt{A-Z} $.  \n\n**Constraints**  \n1. Initial position $ (i,j) $ satisfies $ \\mathcal{G}[i][j] = \\texttt{.} $.  \n2. All procedure bodies and programs are syntactically correct and only invoke defined procedures.  \n3. Grid boundaries are barriers: any move outside $ [1,r] \\times [1,c] $ is invalid.  \n4. Procedure definitions may be recursive or refer to undefined procedures at definition time, but all invocations in programs are guaranteed to be defined.  \n\n**Objective**  \nFor each of the $ e $ program executions:  \n- Given initial state $ (i,j,h) $ and program string $ \\pi $, simulate execution of $ \\pi $ under $ \\mathcal{P} $.  \n- If the program terminates, output the final state $ (i', j', h') $.  \n- If the program does not terminate (infinite loop), output `inf`.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10251I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}