[AHOI2006]可可的文本编辑器

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file editor.in Output file editor.out

这些日子,可可不和卡卡一起玩了,原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗?

为了明确任务目标,可可对“文本编辑器”做了一个抽象的定义:

文本:由 0 个或多个字符构成的序列。这些字符的 ASCII 码在闭区间 [32, 126] 内,也就是说,这些字符均为可见字符或空格。

光标:在一段文本中用于指示位置的标记,可以位于文本的第一个字符之前,文本的最后一个字符之后或文本的某两个相邻字符之间。

文本编辑器:为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空,我们就说这个文本编辑器是空的。


操作名称

输入文件中的格式

功能

MOVE(k)

Move k

将光标移动到第k个字符之后,如果k=0 ,将光标移到文本第一个字符之前

INSERT(n, s)

Insert n S

在光标后插入长度为n的字符串s,光标位置不变,n3 1

DELETE(n)

Delete n

删除光标后的n个字符,光标位置不变,n3 1

ROTATE(n)

Rotate n

反转光标后的n个字符,光标位置不变,n3 1

GET ()

Get

输出光标后的一个字符,光标位置不变

PREV()

Prev

光标前移一个字符

NEXT()

Next

光标后移一个字符


比如从一个空的文本编辑器开始,依次执行下表中操作,可以有对应的结果:

操作

操作前的文本

操作后的结果

INSERT(13,"Balanced□ eert")

|(只有光标,文本为空)

|Balanced□eert

MOVE(2)

|Balanced□eert

Ba|lanced□eert

DELETE(5)

Ba|lanced□eert

Ba|d□eert

NEXT()

Ba|d□eert

Bad|□eert

INSERT(7,"□editor")

Bad|□eert

Bad|□editor□eert

MOVE(0)

Bad|□editor□eert

|Bad□editor□eert

GET ()

|Bad□editor□eert

输出"B"

MOVE(11)

|Bad□editor□eert

Bad□editor□|eert

ROTATE(4)

Bad□editor□|eert

Bad□editor□|tree

GET()

Bad□editor□|tree

输出"t"

上表中,“|”表示光标,“ □ ”表示空格。

[ 任务 ]

编写一个程序:

•  建立一个空的文本编辑器。

•  从输入文件中读入一些操作指令并执行。

•  对所有执行过的 GET 操作,将指定的内容写入输出文件。

[ 输入格式 ]

输入文件中第一行是指令条数 N ,以下是需要执行的 N 个操作。

除了回车符之外,输入文件的所有字符的 ASCII 码都在闭区间 [32, 126] 内。且行尾没有空格。

[ 输出格式 ]

输出文件 editor.out 的每行依次对应输入文件中每条 GET 指令的输出,不得有任何多余的字符。

[ 输入样例 ]


10 
Insert 13 
Balanced eert 
Move 2 
Delete 5 
Next  
Insert 7 
editor 
Move 0 
Get 
Move 11 
Rotate 4 
Get


[ 输出样例 ]

B

t

[ 数据约束和评分方法 ]

对输入数据我们有如下假定:

•  MOVE 操作不超过 50 000 个, INSERT 、 DELETE 和 ROTATE 操作作的总个数不超过 6 000 , GET 操作不超过 20 000 个, PREV 和 NEXT 操作的总个数不超过 20 000 。

•  所有 INSERT 插入的字符数之和不超过 2M ( 1M =1 024*1 024 )。

•  DELETE 操作、 ROTATE 操作和 GET 操作执行时光标后必然有足够的字符。 MOVE 、 PREV 、 NEXT 操作不会把光标移动到非法位置。

•  输入文件没有错误。


对C++选手的提示:经测试,对最大的测试数据使用fstream进行输入有可能会比使用stdio慢很多,因此建议在可以的情况下使用后者。

本题不设部分分,对于每个测试点只有当你的程序的输出和我们的标准输出完全一致时才可以得到相应的分数。