CF1089J.JS Minification

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

国际编码流程公司（ICPC）所有代码均使用 Jedi Script（JS）编程语言编写。JS 不需要编译，而是以源代码形式直接交付执行。源代码中包含注释、多余的空白字符（包括行首和行尾的空格）以及其他非必要内容，这些内容会使源代码变得很大，但对代码语义没有贡献。因此，在交付执行前，需要对源文件进行压缩（minification）处理，以在保持语义不变的前提下尽可能压缩源代码体积。

你被 ICPC 雇佣来为其编写 JS 代码压缩器。幸运的是，ICPC 遵循非常严格的编程规范，其 JS 源代码的语法受到了很大限制。他们只处理整数算法，不使用浮点数和字符串。

每个 JS 源文件包含若干行。每一行包含零个或多个记号（token），记号之间可以用空格分隔。在每一行中，从井号字符（‘#’，ASCII 码 35）开始的部分（包括该井号本身）都被视为注释，直到行尾都应忽略。

每一行会从左到右解析为一系列记号，解析时会不断跳过空格，并在当前位置寻找最长的合法记号，从而将源代码转换为记号序列。所有可能的记号如下：

保留记号（reserved token）：包括各种运算符、分隔符、字面量、保留字或库函数名，在压缩过程中必须保留。保留记号是由非空格 ASCII 字符组成的固定字符串，不包含井号（‘#’）。所有保留记号会作为输入提供给压缩过程。
数字记号（number token）：由一串数字组成，数字为‘0’到‘9’的字符。
单词记号（word token）：由以下字符组成的字符串：小写字母、大写字母、数字、下划线（‘_’）和美元符号（‘$’）。单词不能以数字开头。

注意，在解析时，如果某个最长的数字或单词序列也出现在保留记号列表中，则应将其视为保留记号。

在压缩过程中，单词会按如下算法系统性地重命名：

取仅由小写字母组成的单词列表，按长度升序、字典序排列：“a”、“b”、…、“z”、“aa”、“ab”、…，但要排除所有保留记号（因为它们不算作单词）。这就是目标单词列表。
将输入记号序列中遇到的第一个单词重命名为目标单词列表中的第一个单词，并将后续所有相同的单词也重命名为该目标单词。遇到第二个新单词则重命名为目标单词列表中的第二个单词，以此类推。

压缩的目标是将给定源代码转换为一行最短（按空格计）的代码，该代码在解析后得到的记号序列与原代码一致，且所有单词都已按上述规则重命名。输出行中应包含最少数量的空格。如果有多种插入最少空格的方法，任选其一输出即可。

输入格式

第一行包含一个整数 $n$ （ $0 \le n \le 40$ ），表示保留记号的数量。

第二行包含用空格分隔的保留记号列表，列表中无重复。每个保留记号长度为 1 到 20 个字符，仅包含 ASCII 码 33（感叹号）到 126（波浪号）之间的字符，但不包含井号（‘#’）。

第三行包含一个整数 $m$ （ $1 \le m \le 40$ ），表示输入源代码的行数。

接下来的 $m$ 行为输入源代码，每行最多 80 个字符（包括行首和行尾的空格）。每行仅包含 ASCII 码 32（空格）到 126（波浪号）之间的字符。输入的源代码保证合法，并能完整解析为记号序列。

输出格式

输出一行，即压缩后的源代码。该行解析后得到的记号序列应与输入源代码一致，且所有单词已按规则重命名，并且包含的空格数最少。如果有多种插入最少空格的方法，任选其一输出即可。

输入输出样例

输入#1

16
fun while return var { } ( ) , ; > = + ++ - --
9
fun fib(num) { # compute fibs
  var return_value = 1, prev = 0, temp;
  while (num > 0) {
    temp = return_value; return_value = return_value + prev;
    prev = temp;
    num--;
  }
  return return_value;
}

输出#1

fun a(b){var c=1,d=0,e;while(b>0){e=c;c=c+d;d=e;b--;}return c;}

输入#2

10
( ) + ++ : -> >> >>: b c)
2
($val1++ + +4 kb) >> :out
b-> + 10 >>: t # using >>:

输出#2

(a+++ +4c )>> :d b->+10>>:e

说明/提示

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页