背景

蛇蛇有一个长大的梦想，你可以帮帮它吗？

描述

请编写一个程序，自动游玩贪吃蛇：

• 地图为 $n \times n$，蛇初始长度为 1，起点在 $(0,0)$。
• 地图中始终存在一个苹果，初始位置不在 $(0,0)$ 上。每当蛇吃到苹果时，蛇长度 +1，并在非蛇身的位置随机生成新苹果。
• 每一步你可以向交互器发送一次移动指令。若新头部与苹果重合则吃到苹果；否则蛇尾前进一格（长度不变）。
• 若蛇出界、与自身碰撞、或进行 180° 反向移动，游戏立即结束。
• 如果在允许的最大步数内没有结束，你的程序将被判定为“操作过多”并结束。

你的目标是让蛇最终填满整张地图（长度达到 $n^2$），获得满分；若未能完全填满，得分按蛇最终长度计算（见“评分”）。

格式

与评测端为标准输入输出交互。评测过程以行为单位进行。请确保每次输出后刷新缓冲区（fflush(stdout)），并且严格按照协议读写。

交互要求

1. 读取地图边长

   • 评测一开始会输出一行：

     n
     

     其中 $n$ 为地图边长。读入后开始游戏。

2. 你的可用指令

   你的程序可以反复输出如下两类指令中的一种（单行）：

   • 测量苹果位置

     measure
     

     评测端将回复一行：

     ax ay
     

     表示当前苹果的坐标 $(ax, ay)$。

   • 移动蛇头

     move d
     

     其中 d 为方向，取值与含义如下（坐标系均为 0 开始）：

     • 0：上（$y \leftarrow y+1$）
     • 1：下（$y \leftarrow y-1$）
     • 2：左（$x \leftarrow x-1$）
     • 3：右（$x \leftarrow x+1$）

     若游戏未结束，评测端将立即回复一行状态：

     • apple
       

       本步吃到苹果，蛇长度加 1，并生成新苹果；

     • no_apple
       

       本步未吃到苹果，蛇尾随之前进，长度不变。

3. 游戏结束信号

   无论因何原因（成功或失败）结束，评测端都会先输出一行：

   end
   

   然后结束交互并给出判分与信息。

4. 禁止的或错误行为

   下列情况将立即结束游戏并按当前长度计分：

   • 出界：新头部不在 $[0, n-1] \times [0, n-1]$；

   • 180° 反向：新头部等于上一步的倒数第二个身体格；

   • 撞到自身：

     • 若未吃苹果，尾巴会移动，允许移动到之前的尾巴位置；但若新头与身体其它任意格重合则失败；
     • 若吃到苹果，尾巴不动，若新头与蛇身任一格重合则失败；

   • 操作过多：总操作次数超过上限（评测端内部限制，足以覆盖合理策略）；

   • 无后续输出：你的程序不再输出指令导致输入耗尽。

5. 坐标与初始状态

   • 初始蛇仅占据 $(0,0)$，蛇头与蛇尾均为 $(0,0)$；
   • 初始苹果随机生成，且不在 $(0,0)$。

交互示例（仅示意）

# 评测 -> 选手
6
# 选手 -> 评测
measure
# 评测 -> 选手
3 2
# 选手 -> 评测
move 0
# 评测 -> 选手
no_apple
...
# 各种交互
...
# 结束时 评测 -> 选手
end

注意：示例仅展示格式，不代表最优策略。

评分

设地图总格数为 $T = n \times n$，蛇最终长度为 $L$（初始为 1）。归一化后的得分为：

当蛇填满整张地图（$L = T$）时直接判为满分。

范围

• 地图大小 $n \le 10$ 且为偶数。
• 坐标范围：$0 \le x,y < n$。
• 方向编码：0=上，1=下，2=左，3=右。

实现建议

大小很小，建议想想看可不可以用最简单无脑安全的方法。千万别被唬住了！