QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8365. 重复搬题

Statistics

题目描述

不是一道交互题。

小 q 找到了一个年代非常久远的游戏机,这个游戏机上有一个非常简单的游戏:

有一个迷宫,它可以看成由 $10$ 行 $10$ 列的方格组成。每个方格是空地或者障碍物。其中的一个空地为起点,另一个空地为终点。

小 q 需要操控一个人物从起点走到终点。游戏机有四个方向按键,对应东('E')南('S')西('W')北('N')。与此同时,游戏机还有一个确定键。小 q 可以连续按下一些方向键,再按下确定键,人物就会依次执行这些方向键的移动命令。对每个移动命令,人物会向对应方向移动一个格子。如果会走到障碍物上或走出地图,则这次移动失败,否则这次移动成功。连续的一些方向键和一次确定键被称作一次指令。

游戏中一关的过程为,初始人物在起点,小 q 可以多次给人物下指令,人物在任意一个时刻(包括连续指令的中间时刻)到达终点就通过了这一关。

小 q 想要通关这个游戏,但很不幸的是,游戏机的屏幕坏了,因此小 q 看不到迷宫中的状态(障碍的位置以及当前人物的位置),小 q 只能通过屏幕边界判断迷宫的大小(当然,已知是 $10\times 10$ )。

更不幸的是,小 q 发现,在他进入游戏后,只要按下第一次确定键,在这局游戏剩余的时间中,他将无法再使用方向键,这就意味着,小 q 只能下一次指令!

更更更不幸的是,小 q 发现,一局游戏的时间是有限制的,只能让人物执行不超过 $10000$ 个移动命令!所以小 q 最多只能按下 $10000$ 次方向键!

通关一局游戏可以获得 $10000$ 的分数。但在此之外,游戏时间也会影响小 q 的得分。人物每执行一个移动命令(无论成功与否),需要花费 $1$ 单位的时间。当人物第一次到达终点时,游戏通关,自动结束。设结束时花费的总时间为 $t$ 单位时间(包含到达终点的那一次移动),那么就需要在通关得分的基础上,扣除 $t$ 的分数,即得分为 $10000-t$ 。如果所有方向键指令都被执行后仍未到达过终点,在游戏的 $10000$ 个单位时间结束后,会被自动视为通关失败。那么不仅通关的 $10000$ 分拿不到,还会因消耗了 $10000$ 的总时间而扣除 $10000$ 的分数,即得分为 $-10000$ !

小 q 这下子一下就不会了,属实是感觉这个游戏机属于是属于是了。于是他向你求助,希望你能告诉他他应该怎么下这唯一的一次指令才能得到尽量高的分数。你需要写一份代码,输出一个由 'E','S','W','N' 构成的长度不超过 $10000$ 的字符串,表示你认为小 q 应该下的指令。

不幸中的万幸是,你知道迷宫地图的生成方式。生成方式如下所示:首先,选择 $10\times 10$ 方格图上的 $20$ 个格子,将他们标记。其次,尝试放置障碍物 $500$ 次。对于每次尝试,随机选择一个 $10\times 10$ 中的方格。如果这个方格还是空地且未被标记,将这个方格变为障碍物。在此之后,如果那 $20$ 个标记的格子仍然可以互相通过上下左右不经过障碍物到达,那么这个障碍物会被保留下来;否则,障碍物将被移出,该方格重新变为空地。在尝试放置完障碍物中,会开始选择迷宫的起点与终点。游戏机会在所有距离最远(距离定义为需要经过的格子数量)的方格对中等概率随机选择一个,并将其中的一个设为起点,另一个设为终点。

那么你的任务就是让你输出的指令能平均获得更高的分数。每组数据中会包含 $1000$ 个预先用该生成方式生成的迷宫,但你并不知道。在你的程序输出指令之后,会将你的指令依次操作在这些迷宫上,得到的平均分数就是这组数据返回的分数。

输入格式

你不需要输入任何东西。

输出格式

一行由 'E','S','W','N' 构成的长度不超过 $10000$ 的字符串,表示你认为小 q 应该下的指令。

'E' 'S' 'W' 'N' 对应的指令分别表示从当前位置 $(x,y)$ 移动到 $(x,y+1),(x+1,y),(x,y-1),(x-1,y)$ 。

样例输入

(empty)

样例输出

WWWNNNWWWSSSWWWSSSWWWEEESSSEEESSSEEESSSWWWNNNWWWSSSWWWNNNEEEWWWNNNWWWSSSEEEWWWSSS

样例解释

下图是一个由题目中生成方式生成的迷宫,其中圆为起点,叉为终点。该样例输出可以通过该迷宫。

image-20220602230529081

数据范围

subtask1(100pts):无特殊限制。

子任务 1 中包含 $20$ 个测试点。计分方式如下:

如果输出的字符串中包含除 'E','S','W','N' 以外的字符或长度超过 $10000$ ,分数为 $0$ 分。否则按照如下方式计算分数( $S$ 为该组数据中得到的平均分数):

$S$ 的值 对应分数
$S\leq 0$ $0$
$0 < S < 9100$ $\frac{8.1\times 10^7}{(10^4-S)^2}$
$S\geq 9100$ $100$

子任务得分取每个测试点得分的最小值。