Problem A: 跳格子游戏

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:30 Solved:21

Description

校园空地上画了一排格子,从左到右编号 1 到 N,每个格子里写着一个整数。小跳蛙站在某个格子上出发,每一步都按脚下格子里的数字跳:正数向右跳,负数向左跳。
给定 N 个整数 a1 a2 … aN,表示每个格子里的数字,以及起点 P(1 ≤ P ≤ N)。小跳蛙从 P 出发,反复执行同一条规则:设当前站在位置 x,则跳到位置 x + ax。
游戏在下列两种情况下结束:
1. 跳出格子区:某一步的落点小于 1 或大于 N;
2. 陷入循环:某一步落到了它之前已经站过的格子上。此后每一步都会重复之前走过的路,永远跳不出。
请判断小跳蛙的结局并输出:
若跳出格子区,输出 OUT t,其中 t 表示从出发到跳出为止一共跳了多少步;

若陷入循环,输出 LOOP t,其中 t 表示进入循环之前已经走过的步数。具体地说,把小跳蛙第一次重复踏上的那个格子记为 x,t 就是它第一次踏上 x 时已经跳过的步数(同样地,出发那一刻记为第 0 步)。

例如:有如下图 6个数字格,起点 P=1。 

跳格子路线为 ①→(向右跳5格) ⑥→(向左跳-4格)②→(向右跳3格)⑤→(向右跳2格)⑦。第 4 步落到 ⑦,超过⑥号格子,跳出格子区,共跳 4 步,因此输出 OUT 4。



Input

第一行两个整数 N与 P。第二行 N 个整数,依次表示 a1, a2, …, aN。

Output

输出一行,形如题目描述 OUT t 或 LOOP t,t 为整数。(注意字母与数字间空一格)

Sample Input Copy

6 1
2 3 3 1 -3 -4

Sample Output Copy

LOOP 3

样例解释 :
路线为 1 → 3 → 6 → 2 → 5 → 2 → 5 → …。前 3 步(到 3 号、到 6 号、到 2 号)是一段“引桥”,从第 3 步踏上 2 号格子之后,小跳蛙就一直在 2 号与 5 号两个格子之间来回,再也跳不出去。
2 号格子是第 3 步第一次被踩到的,也就是说进入循环之前一共走了 3 步,所以输出 LOOP 3。

HINT

1 ≤ N ≤ 1000,-1000 ≤ ai ≤ 1000,1 ≤ P ≤ N。


AI 辅助编程建议

你可以把完整题面提供给 AI,并通过多轮交流完成需求确认、程序生成、代码检查和测试修正。建议按照以下过程作答:

① 确认需求。先让 AI 用自己的话复述四个细节:每一步的落点公式(当前位置加上该格子里的数字);两种结局的判定标准;OUT 的 t 和 LOOP 的 t 各自代表什么;格子里的数字为 0 时会发生什么。这里要特别盯住 LOOP 的 t——它指的是“重复出现的那个格子第一次被踩到时已经走了几步”,而不是“发现重复时的当前步号”。如果 AI 说成后者,就让它拿样例 2 手推一遍:路线 1→3→6→2→5→2,重复的格子是 2 号,它第一次被踩到是在第 3 步,所以输出 3。

② 生成程序。请 AI 先给出实现思路,再给出可以直接运行的完整代码,并说明它打算如何保证“程序自己不会陷入死循环”。核对它是否记录每个格子“第一次被踩到时的步号”。如果它只用一个布尔标记(是否走过),要追问:布尔标记能算出 2 号格子第一次是第几步踩到的吗?——不能,只能知道“走过”,算不出步号,必须改存步号。

③ 审查逻辑。重点检查四处:起点是否在出发的那一刻就记为“第 0 步”(漏掉的话,起点在环上的情形会整段错开);落到重复格子时,输出的是不是该格子“首次被踩到的步号”,而不是当前步号;“是否重复”的判断发生在移动之后(必须先移动、再看落点,否则会漏判);跳出时是否把“跳出的那一步”也计入了步数(样例 1 应输出 5,若得到 4 就是少算了这一步)。

④ 补充测试。除题面三个样例之外,至少再构造并验证以下情况:起点就在环上(应输出 LOOP 0);引桥长度分别为 1 步、2 步的循环(应分别输出 LOOP 1、LOOP 2);路径恰好踩遍全部 M 个格子后从端点跳出(应输出 OUT M);出现负数导致向左跳出;M = 1 的退化情形;以及 M = 1000 的最大规模(例如全部为 0,应输出 LOOP 0)。每条用例都要先自己独立算出预期输出,再和程序结果比对。

⑤ 迭代修正。如果实际输出与预期不一致,把“输入 / 预期输出 / 实际输出”三样一并提供给 AI,并说明你的怀疑方向(例如“我怀疑输出的是当前步号,请确认是否应该输出该格子首次被踩到的步号”),让它定位原因。若 LOOP 的 t 恰好比预期大 1,优先检查起点有没有被误记成第 1 步。修改后必须把全部用例重新跑一遍,不能只跑刚才失败的那一条。