CF585D Lizard Era: Beginning

在游戏《Lizard Era: Beginning》中，主角将与三位伙伴同行：Lynn、Meliana 和 Worrigan。游戏共有 $n$ 个必做任务。每完成一个任务，必须恰好选择两位伙伴同行。 每位伙伴对主角的好感度是一个整数。初始时，每个人对主角的好感度均为 0，处于中立状态。每当主角完成任务时，他的行为会对随行的伙伴好感度产生正向或负向的影响。 请你告诉主角应当如何选择搭档，才能使在完成所有任务后，三位伙伴对主角的好感度相等。如果有多种方法可以实现该目标，请输出最终好感度数值最大的方案。

第一行包含一个正整数 $n$（$1 \leq n \leq 25$），表示重要任务的数量。 接下来的 $n$ 行，每行包含三个整数 $l_i, m_i, w_i$，分别表示当主角带上 Lynn、Meliana、Worrigan 执行第 $i$ 个任务时，他们对主角好感度的变化量。输入中的所有数值均为整数，且绝对值不超过 $10^7$。

如果无解，则第一行输出“Impossible”。 否则，输出 $n$ 行，每行为两个字符，表示主角在第 $i$ 个任务中应选择的伙伴。每行输出所选两位伙伴名字的首字母（‘L’ 表示 Lynn，‘M’ 表示 Meliana，‘W’ 表示 Worrigan），顺序不限。如果有多种方案，输出其中任意一种。

由 ChatGPT 5 翻译