题目背景

数据压缩算法的目的是减少数据的大小，以便更快地传输和存储。我们经常会用到的 zip、rar 等压缩工具，就是利用数据压缩算法把多个文件或者文件夹压缩成一个更小的文件；我们的网页在传输时，通常也使用了 gzip 压缩。有些时候 (例如传输图像、视频时)，我们会允许在压缩过程中损失⼀些精度，以实现更好的压缩比。

题目描述

在这个问题里，你需要自己设计⼀个英文文本的无损压缩和解压缩算法。你的程序需要同时实现压缩器和解压缩器两部分功能：

• 压缩器输⼊⼀个仅由小写字母组成的字符串，输出⼀个压缩后的字符串。压缩后的字符串允许使用大写字母、⼩写字母和数字，但不允许使⽤其他字符。

• 解压缩器输入⼀个压缩后的字符串，还原出小写字母的字符串。

注意，在这个问题中，所有给压缩器的输如都来自人工智能 GPT-3.5-turbo 生成的英文文本保留字母 (并转换为⼩写) 后得到的，也就是说，你可以假设除了偶尔的例外，字符串是由英文单词拼接而成的。这个性质是解决问题的关键——随机序列的压缩比 “有规律” 序列的压缩要困难得多。

输入格式

输⼊数据第一行为一个大写英文单词，代表压缩/解压缩的任务类型。COMPRESS 代表压缩；DECOMPRESS 代表解压缩。

第二行一个字符串，是压缩/解压缩任务对应的文本。对于压缩任务，是一个仅包含小写字母的字符串；对于解压缩任务，字符串总是来自你程序之前 COMPRESS 压缩的结果。

输出格式

输出一行一个字符串。对于压缩任务，输出一行为压缩后的文本；对于解压缩任务，输出一行为解压缩后的文本。

见压缩包。样例仅给出了压缩任务所需的字符串 (由
人工智能 GPT-3.5-turbo 生成)，不含样例输出；你
可以在给出的样例上实验你的压缩算法。

提示

对于 $100\%$ 的数据，输⼊字符串的长度 $n$ 满足 $3\times 10^4 \leq n \leq 4\times 10^4$。

本题的评测机会两次调用你的程序：

• 第一次调用你的程序执行压缩任务，例如输⼊

COMPRESS
aaaaaaaabbbbbbbbbb

假设本次调用，你的程序输出了 a8b10 作为压缩后的文本。这个输出会被评测系统记住。

• 第二次，调用你的程序执行解压缩任务。针对刚才的例子，我们会为你的程序输⼊

DECOMPRESS
a8b10

如果你的程序解压缩输出 aaaaaaaabbbbbbbbbb（即正确解压缩得到原字符串），则被判定为“还原正确”。

对于每个测试数据，压缩和解压缩分别有 $1\ \text{s}$ 的运⾏时间限制。

对于每个测试数据，在解压缩能正确得到原字符串的前提下：

• 如果压缩率达到 $75\%$（压缩字符串的长度小于等于输⼊长度的 $\frac{3}{4}$），该测试点得满分。

• 如果压缩率达到 $80\%$（压缩字符串的长度小于等于输⼊长度的 $\frac{4}{5}$），该测试点得一半分数。

本题原始满分为 $20\text{pts}$。