魔法珠游戏

题目描述

Freda 和 rainbow 是超自然之界学校(Preternatural Kingdom University，简称PKU)魔法学院的学生。

为了展示新学的魔法，他们决定进行一场对弈。

初始状态

起初 Freda 面前有 $n$ 堆魔法珠，其中第 $i$ 堆有 $a_i$ 颗。

游戏规则

Freda 和 rainbow 可以轮流进行以下操作：

1. 选择：选择 $n$ 堆中魔法珠数量大于 1 的任意一堆。记该堆魔法珠的数量为 $p$。
2. 分解：$p$ 有 $b_1, b_2, \ldots, b_m$ 这 $m$ 个小于 p 的约数（不包括 $p$ 本身）。施展魔法把这一堆魔法珠变成 $m$ 堆，每堆各有 $b_1, b_2, \ldots, b_m$ 颗魔法珠。
3. 消失：选择这 $m$ 堆中的一堆魔法珠，施展魔法令其消失。

注意：

• 一次操作过后，魔法珠的堆数会增加 $m-2$（因为原来有1堆，变成$m$堆再消失1堆，净增$m-2$堆）
• 各堆中魔法珠数量的总和可能会发生变化（因为消失了一堆）

输赢条件

当轮到某人操作时，如果每堆中魔法珠的数量均为 1，那么他就输了。

Freda 和 rainbow 都采取最好的策略，从 Freda 开始。

输入格式

输入包含多组测试数据。

每组数据：

• 第一行包含一个整数 $n$。
• 第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 堆的魔法珠数量 $a_i$。

输出格式

对于每组数据，在两人均采取最佳策略的前提下：

• 若 Freda 能获胜，输出 freda
• 若 Rainbow 能获胜，输出 rainbow

每个结果占一行。

数据范围

• $1 \le n \le 100$
• $1 \le a_i \le 1000$

输入样例

3
2 2 2
3
1 3 5

输出样例

freda
rainbow

样例解释

第一个样例：$n=3, a=[2,2,2]$

初始状态： 3堆，每堆2颗魔法珠

分析：

• 每堆2颗魔法珠，2的真约数只有1（因为2是质数，真约数只有1）
• 操作过程：
  1. 选择一堆2颗的魔法珠，将其分解为1堆1颗的魔法珠（$m=1$）
  2. 然后必须选择这1堆令其消失
  3. 操作后，这堆魔法珠完全消失，堆数减少1堆

SG值计算：

• 对于一堆2颗魔法珠，只有一种操作方式：变成一堆1颗，然后消失
• 这相当于直接移除这堆魔法珠
• 整个游戏可以看作多堆的Nim游戏，每堆2的SG值为1
• 3堆SG值异或：$1 \oplus 1 \oplus 1 = 1 \neq 0$，所以先手必胜

因此，Freda（先手）获胜，输出 freda

第二个样例：$n=3, a=[1,3,5]$

初始状态： 3堆，分别有1颗、3颗、5颗魔法珠

分析：

• 堆1：1颗（已经是终态，不能操作）
• 堆3：3颗，真约数有1
• 堆5：5颗，真约数有1

SG值计算：

• 对于质数$p$，真约数只有1，操作方式只有一种：变成一堆1颗然后消失，SG值为1
• 堆1的SG值为0（不能操作）
• 堆3的SG值为1
• 堆5的SG值为1
• 总SG值：$0 \oplus 1 \oplus 1 = 0$，所以先手必败

因此，Freda（先手）必败，输出 rainbow

游戏特性分析

约数分解规则

对于一堆有 $p$ 颗魔法珠：

• 找出 $p$ 的所有真约数（小于 $p$ 的正约数）
• 假设有 $m$ 个真约数：$b_1, b_2, \ldots, b_m$
• 操作：将这堆变成 $m$ 堆，每堆分别有 $b_1, b_2, \ldots, b_m$ 颗
• 然后从这 $m$ 堆中选择一堆令其消失

操作的本质

一次操作相当于：

1. 移除一堆有 $p$ 颗魔法珠的堆
2. 增加 $(m-1)$ 堆新堆（因为消失了一堆，净增 $m-2$，但实际新产生 $m$ 堆，消失1堆）
3. 新堆的大小是 $p$ 的真约数

终态判定

当所有堆都只有1颗魔法珠时，当前玩家输（因为无法选择大于1的堆进行操作）

策略分析

这是一个组合游戏，可以使用 SG定理 进行分析：

1. 每堆魔法珠是独立的子游戏
2. 整个游戏的SG值是各堆SG值的异或和
3. 如果总SG值不为0，先手必胜；否则先手必败

对于一堆有 $p$ 颗魔法珠的游戏：

• 计算所有可能的后续状态的SG值
• 当前状态的SG值是这些后继状态SG值的mex（最小非负整数未出现值）

时空限制

• 时间限制：1秒
• 空间限制：64MB