QOJ.ac

QOJ

Límite de tiempo: 2 s Límite de memoria: 2048 MB Puntuación total: 100

#5398. JS 代码压缩

Estadísticas

International Coding Procedures Company (ICPC) 使用 Jedi Script (JS) 编程语言编写所有代码。JS 不会被编译,而是以源代码形式交付执行。源代码包含注释、额外的空白字符(包括行尾和行首空格)以及其他非必要特征,这些特征使代码变得非常庞大,但对代码语义没有贡献。因此,在交付执行之前,会对源文件进行“压缩”(minification),以在保留语义的同时压缩源代码。

你受雇于 ICPC 编写 JS 压缩器。幸运的是,ICPC 遵循非常严格的编程规范,其 JS 源代码的语法非常受限。它们仅处理整数算法,不使用浮点数和字符串。

每个 JS 源代码包含一系列行。每一行包含零个或多个可以用空格分隔的标记(token)。在每一行中,从哈希字符(‘#’,ASCII 码 35)开始的部分(包括该哈希字符本身)被视为注释,并被忽略直到行尾。

每一行通过重复跳过空格并从当前解析位置找到尽可能长的标记,从左到右解析为一系列标记,从而将源代码转换为标记序列。所有可能的标记列出如下:

  • 保留标记(reserved token):指任何类型的运算符、分隔符、字面量、保留字或在压缩过程中应保留的库函数名称。保留标记是固定的非空格 ASCII 字符字符串,不包含哈希字符(‘#’,ASCII 码 35)。所有保留标记作为输入提供给压缩过程。
  • 数字标记(number token):由一系列数字组成,其中数字是零(‘0’)到九(‘9’)之间的字符(包含 0 和 9)。
  • 单词标记(word token):由以下集合中的一系列字符组成:小写字母、大写字母、数字、下划线(‘_’,ASCII 码 95)和美元符号(‘$’,ASCII 码 36)。单词不能以数字开头。

注意,在解析过程中,如果满足数字或单词定义的最长字符序列出现在保留标记列表中,则将其视为保留标记。

在压缩过程中,单词会按照以下算法进行系统性重命名:

  1. 取一个仅由小写字母组成的单词列表,首先按长度排序,然后按字典序排序:“a”, “b”, ..., “z”, “aa”, “ab”, ...,排除保留标记(因为它们不被视为单词)。这是目标单词列表。
  2. 将输入标记序列中遇到的第一个单词重命名为目标单词列表中的第一个单词,并且输入标记序列中该单词的所有后续出现也进行同样的重命名。将输入标记序列中遇到的第二个新单词重命名为目标单词列表中的第二个单词,依此类推。

压缩过程的目标是将给定的源代码转换为尽可能短的一行(计算空格),该行在解析后仍能得到相同的标记序列,并使用这些 JS 解析规则对单词进行相应的重命名。

输入格式

第一行包含一个整数 $n$ ($0 \le n \le 40$),表示保留标记的数量。 第二行包含保留标记列表,以空格分隔,列表中没有重复项。每个保留标记长度至少为 1,最多为 20 个字符,且仅包含 ASCII 码从 33(感叹号)到 126(波浪号)的字符,哈希字符(‘#’,ASCII 码 35)除外。 第三行包含一个整数 $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;
}
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 >>:
(a+++ +4c )>> :d b->+10>>:e

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.