B. Vasya and Types

Codeforces
IDCF87B
Time1000ms
Memory256MB
Difficulty
implementationstrings
English · Original
Chinese · Translation
Formal · Original
Programmer Vasya is studying a new programming language &K*. The &K* language resembles the languages of the C family in its syntax. However, it is more powerful, which is why the rules of the actual C-like languages are unapplicable to it. To fully understand the statement, please read the language's description below carefully and follow it and not the similar rules in real programming languages. There is a very powerful system of pointers on &K* — you can add an asterisk to the right of the existing type _X_ — that will result in new type _X_ * . That is called pointer-definition operation. Also, there is the operation that does the opposite — to any type of _X_, which is a pointer, you can add an ampersand — that will result in a type &_X_, to which refers _X_. That is called a dereference operation. The &K* language has only two basic data types — _void_ and _errtype_. Also, the language has operators _typedef_ and _typeof_. * The operator "_typedef _A_ _B__" defines a new data type _B_, which is equivalent to _A_. _A_ can have asterisks and ampersands, and _B_ cannot have them. For example, the operator _typedef void** ptptvoid_ will create a new type _ptptvoid_, that can be used as _void**_. * The operator "_typeof _A__" returns type of _A_, brought to _void_, that is, returns the type _void**...*_, equivalent to it with the necessary number of asterisks (the number can possibly be zero). That is, having defined the _ptptvoid_ type, as shown above, the _typeof ptptvoid_ operator will return _void**_. An attempt of dereferencing of the _void_ type will lead to an error: to a special data type _errtype_. For _errtype_ the following equation holds true: _errtype*_ = _&errtype_ = _errtype_. An attempt to use the data type that hasn't been defined before that will also lead to the _errtype_. Using _typedef_, we can define one type several times. Of all the definitions only the last one is valid. However, all the types that have been defined earlier using this type do not change. Let us also note that the dereference operation has the lower priority that the pointer operation, in other words &_T_ *  is always equal to _T_. Note, that the operators are executed consecutively one by one. If we have two operators "_typedef &void a_" and "_typedef a* b_", then at first _a_ becomes _errtype_, and after that _b_ becomes _errtype* = errtype_, but **not** _&void* = void_ (see sample 2). Vasya does not yet fully understand this powerful technology, that's why he asked you to help him. Write a program that analyzes these operators. ## Input The first line contains an integer _n_ (1 ≤ _n_ ≤ 100) — the number of operators. Then follow _n_ lines with operators. Each operator is of one of two types: either "_typedef _A_ _B__", or "_typeof _A__". In the first case the _B_ type differs from _void_ and _errtype_ types, and besides, doesn't have any asterisks and ampersands. All the data type names are non-empty lines of no more than 20 lowercase Latin letters. The number of asterisks and ampersands separately in one type in any operator does not exceed 10, however if we bring some types to _void_ with several asterisks, their number may exceed 10. ## Output For every _typeof_ operator print on the single line the answer to that operator — the type that the given operator returned. [samples] ## Note Let's look at the second sample. After the first two queries _typedef_ the _b_ type is equivalent to _void*_, and _c_ — to _void**_. The next query _typedef_ redefines _b_ — it is now equal to _&b = &void* = void_. At that, the _c_ type doesn't change. After that the _c_ type is defined as _&&b* = &&void* = &void = errtype_. It doesn't influence the _b_ type, that's why the next _typedef_ defines _c_ as _&void* = void_. Then the _b_ type is again redefined as _&void = errtype_. Please note that the _c_ type in the next query is defined exactly as _errtype******* = errtype_, and not _&void******* = void******_. The same happens in the last _typedef_.
程序员 Vasya 正在学习一种新的编程语言 &K*。&K* 语言在语法上类似于 C 家族的语言。然而,它更加强大,因此实际 C 类语言的规则不适用于它。为了完全理解题意,请仔细阅读以下语言描述,并严格遵循它,而非现实编程语言中的类似规则。 &K* 语言拥有一个非常强大的指针系统——你可以在现有类型 #cf_span[X] 的右侧添加一个星号,从而得到新类型 #cf_span[X * ],这称为指针定义操作。同时,也存在一个相反的操作:对于任何指针类型 #cf_span[X],你可以添加一个 ampersand(&),从而得到类型 #cf_span[&X],它指向 #cf_span[X]。这称为解引用操作。 &K* 语言只有两种基本数据类型:_void_ 和 _errtype_。此外,该语言包含操作符 _typedef_ 和 _typeof_。 对 _void_ 类型进行解引用将导致错误:产生一个特殊数据类型 _errtype_。对于 _errtype_,以下等式成立:_errtype*_#cf_span[ = ]_&errtype_#cf_span[ = ]_errtype_。尝试使用此前未定义的数据类型也会导致 _errtype_。 使用 _typedef_,我们可以多次定义同一个类型。所有定义中,只有最后一个有效。然而,之前使用该类型定义的其他类型不会改变。 还需注意,解引用操作的优先级低于指针操作,即 #cf_span[&T * ] 始终等于 #cf_span[T]。 请注意,操作符是依次逐条执行的。如果我们有两个操作符:“_typedef &void a_” 和 “_typedef a* b_”,那么首先 _a_ 变为 _errtype_,之后 _b_ 变为 _errtype* = errtype_,但 *不是* _&void* = void_(见样例 2)。 Vasya 尚未完全理解这种强大的技术,因此他请求你的帮助。请编写一个程序来分析这些操作符。 第一行包含一个整数 #cf_span[n](#cf_span[1 ≤ n ≤ 100])——操作符的数量。接下来是 #cf_span[n] 行操作符。每个操作符属于以下两种类型之一:“_typedef #cf_span[A] #cf_span[B]_” 或 “_typeof #cf_span[A]_”。在第一种情况下,#cf_span[B] 类型不同于 _void_ 和 _errtype_,且不包含任何星号或 ampersand。 所有数据类型名称均为不超过 20 个小写拉丁字母的非空字符串。在任何操作符中,单个类型内的星号和 ampersand 数量各自不超过 10,但如果将某些类型展开为 _void_ 并叠加多个星号,其数量可能超过 10。 对于每个 _typeof_ 操作符,请在单独一行输出该操作符返回的类型。 ## Input 第一行包含一个整数 #cf_span[n](#cf_span[1 ≤ n ≤ 100])——操作符的数量。接下来是 #cf_span[n] 行操作符。每个操作符属于以下两种类型之一:“_typedef #cf_span[A] #cf_span[B]_” 或 “_typeof #cf_span[A]_”。在第一种情况下,#cf_span[B] 类型不同于 _void_ 和 _errtype_,且不包含任何星号或 ampersand。所有数据类型名称均为不超过 20 个小写拉丁字母的非空字符串。在任何操作符中,单个类型内的星号和 ampersand 数量各自不超过 10,但如果将某些类型展开为 _void_ 并叠加多个星号,其数量可能超过 10。 ## Output 对于每个 _typeof_ 操作符,请在单独一行输出该操作符返回的类型。 [samples] ## Note 让我们看第二个样例。 在前两个 _typedef_ 操作后,_b_ 类型等价于 _void*_,_c_ 类型等价于 _void**_。 下一个 _typedef_ 重新定义了 _b_ —— 它现在等于 _&b = &void* = void_。此时,_c_ 类型保持不变。 之后,_c_ 类型被定义为 _&&b* = &&void* = &void = errtype_。这不会影响 _b_ 类型,因此下一个 _typedef_ 将 _c_ 定义为 _&void* = void_。 然后,_b_ 类型再次被重新定义为 _&void = errtype_。请注意,下一个查询中 _c_ 类型被定义为 _errtype******* = errtype_,而非 _&void******* = void******_。最后一个 _typedef_ 也是如此。
**Definitions:** - Basic types: $\text{void}$, $\text{errtype}$ - Pointer operation: For any type $T$, $T^*$ is the pointer type to $T$ - Dereference operation: For any pointer type $T = S^*$, $\&T = S$; if $T$ is not a pointer (i.e., $T = \text{void}$ or $T = \text{errtype}$), then $\&T = \text{errtype}$ - Special rule: $\text{errtype}^* = \&\text{errtype} = \text{errtype}$ - Precedence: $\&T^* = T$ (dereference has lower precedence than pointer) - Undefined type reference → $\text{errtype}$ **Given:** - $n$ operators ($1 \leq n \leq 100$), each is either: - $\texttt{typedef } A \texttt{ } B$: define alias $B$ for type $A$ - $\texttt{typeof } A$: output the normalized form of type $A$ **Constraints:** - Type names (identifiers) are strings of 1–20 lowercase Latin letters - Each type expression contains at most 10 asterisks and 10 ampersands - Typedefs are sequential; only the last definition of a type is active, prior uses of that type are unaffected - All type expressions must be normalized using the following reduction rules: 1. $\&\text{void} = \text{errtype}$ 2. $\text{void}^* = \text{void}^*$ 3. $\&\text{errtype} = \text{errtype}^* = \text{errtype}$ 4. $\&T^* = T$ (for any $T$) 5. Any undefined identifier → $\text{errtype}$ **Normalization Rules (for type expressions):** Let a type expression be a base type with a sequence of $k$ asterisks ($*$) and $m$ ampersands ($\&$) applied in some order. Due to precedence $\&T^* = T$, we can reduce any expression to a canonical form: - Let $k$ = number of `*` - Let $m$ = number of `&` - Apply reduction: each `&` cancels one `*` from the rightmost pair, but if $m > k$, then the remaining $m - k$ `&` are applied to the base type - After cancellation: remaining `*` count: $k' = \max(0, k - m)$ - Remaining `&` count: $m' = \max(0, m - k)$ Then: - If base type is $\text{void}$: - If $m' > 0$: result is $\text{errtype}$ - Else: result is $\text{void}^{k'}$ - If base type is $\text{errtype}$: result is $\text{errtype}$ (regardless of $k', m'$) - If base type is an alias $X$: - Resolve $X$ to its current definition (recursively) - Then apply $k'$ asterisks and $m'$ ampersands as above **Objective:** For each $\texttt{typeof } A$ operator, output the normalized type expression of $A$ after applying all prior typedefs. **Implementation Outline (Formalized):** - Maintain a dictionary $D$: identifier → normalized type (as tuple: $(\text{base}, k, m)$) - Initially: $D[\text{void}] = (\text{void}, 0, 0)$, $D[\text{errtype}] = (\text{errtype}, 0, 0)$ - For each operator: - If `typedef A B`: - Normalize $A$ → get $(\text{base}_A, k_A, m_A)$ - Set $D[B] = (\text{base}_A, k_A, m_A)$ - If `typeof A`: - Normalize $A$ → get $(\text{base}, k, m)$ - Apply reduction: $k' = \max(0, k - m)$, $m' = \max(0, m - k)$ - If $\text{base} = \text{errtype}$: output "errtype" - Else if $\text{base} = \text{void}$: - If $m' > 0$: output "errtype" - Else: output "void" + $k'$ asterisks (i.e., "void" + "*" * $k'$) - Else (alias): resolve recursively and apply same logic **Note:** All type expressions are parsed as sequences of `&` and `*` applied to a base identifier. The parser must strip all `&` and `*` from the expression to extract the base identifier and counts. Example: `&&b***` → base = `b`, $k=3$, $m=2$ → $k'=1$, $m'=0$ → normalize `b` with one `*`
Samples
Input #1
5
typedef void* ptv
typeof ptv
typedef &&ptv node
typeof node
typeof &ptv
Output #1
void*
errtype
void
Input #2
17
typedef void* b
typedef b* c
typeof b
typeof c
typedef &b b
typeof b
typeof c
typedef &&b* c
typeof c
typedef &b* c
typeof c
typedef &void b
typeof b
typedef b******* c
typeof c
typedef &&b* c
typeof c
Output #2
void*
void**
void
void**
errtype
void
errtype
errtype
errtype
API Response (JSON)
{
  "problem": {
    "name": "B. Vasya and Types",
    "description": {
      "content": "Programmer Vasya is studying a new programming language &K*. The &K* language resembles the languages of the C family in its syntax. However, it is more powerful, which is why the rules of the actual ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF87B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Programmer Vasya is studying a new programming language &K*. The &K* language resembles the languages of the C family in its syntax. However, it is more powerful, which is why the rules of the actual ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "程序员 Vasya 正在学习一种新的编程语言 &K*。&K* 语言在语法上类似于 C 家族的语言。然而,它更加强大,因此实际 C 类语言的规则不适用于它。为了完全理解题意,请仔细阅读以下语言描述,并严格遵循它,而非现实编程语言中的类似规则。\n\n&K* 语言拥有一个非常强大的指针系统——你可以在现有类型 #cf_span[X] 的右侧添加一个星号,从而得到新类型 #cf_span[X * ],这称为...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n- Basic types: $\\text{void}$, $\\text{errtype}$\n- Pointer operation: For any type $T$, $T^*$ is the pointer type to $T$\n- Dereference operation: For any pointer type $T = S^*$, $\\&T = ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments