这是在大一脑子不清爽的时候出的一道题。当时看到了 carykh 的视频（见下），遂有感而发：这玩意就是个算法题啊！于是就写出了题面。
据算法组的人说，这题目意外质量蛮高的，因此放出来给大家看看。我本身并不写算法，因此题解以及测试数据都没有办法提供。试着用 AI 解决此题，AI（GPT 4o）上了动态规划，但是仍然过不了样例，估计是个比较难的题吧。
此题目欢迎转载，遵守文章协议即可。同社团的若是看到了欢迎直接使用到任意活动中，无需授权。
题目背景
本题目参考：carykh - NATHAN is a palindrome in spirit (Read description for clarification)
William Wei 是一个算法菜鸡。有一天他无意闯进了算法的世界，结果被一条叫“P1217 [USACO1.5] 回文质数 Prime Palindromes”的题目虐惨了！结果他用打表的方法通过了这题目……
William Wei 深知打表是一个非常烂的算法，于是他决定精心修炼算法技能，势必要报仇雪恨！经过不懈的努力，一年后，秉承着“打不过就加入”的原则，他编出了一道更难的回文题目，决心让所有单词都成为回文！
那么 William Wei 最终怎么样了呢？算法太难，他去隔壁 Python 组赛博炼丹去了……
话说，谁问你了？
题目描述
回文（Palindrome），即把一个单词，数字或句子等所有元素反过来和原文保持不变的文字。本题目只讨论回文英语单词，如 RACECAR（将所有字母倒过来依然拼写为 RACECAR）。
现在有一种方法，旨在让所有的单词变为“回文”。该方法允许将单词的一部分视为整体，例如 NATHAN，其本身不是回文，但是我们可以把 TH 看作一个整体，使 NA(TH)AN 由 5 个元素组成（N A TH A N），此时它便是一个“回文”单词。
遵循上述方法，做以下规定：
- 所有单词最外面需要有一层圆括号，表示将里面每个元素算作单独整体。
例如：
(RACECAR)是一个正确的“回文单词”。
- 将需要组合的元素用圆括号包围，他们将被视为整体。
例如：
(NA(TH)AN)是一个正确的“回文单词”。
- 第二条中提到的括号可以叠加。
例如：
((HYPO(T(HE)T)ICAL))是一个正确的“回文单词”。
上述图片有助于你理解该过程。如果还不理解，你可以将上述图片中“浅色的圆盘”看作转盘，“深色的圆盘”看作转盘上的物品，进行“回文”操作时，将所有转盘同时旋转 180 度即可。
按照上述方法和规定，我们可以将任意英文单词转化为“回文单词”。但 William Wei 仍不满足，因为人们可以利用这样的规则，把一个单词的所有字母都视为同一整体（例如：((RACECAR)) 也是一个正确的“回文单词”）。因此，为了保证“回文单词”的质量，特补充以下规则：
- 高质量的“回文单词”没有多余或无意义的括号对。
例如：
(RACECAR)比(((RACECAR)))质量高。 - 高质量的“回文单词”在进行回文操作时移动的字母数更多。
例如：
(RACECAR)（RACCAR这 6 个字母移动）比((RACECAR))（没有字母移动）质量高。 - 对于同一个单词，如果两个组合方案进行回文操作时所移动的字母数相同，则“字母平均移动距离”大的“回文单词”质量更高。（设每个字母间距为 1，字母平均移动距离=每个字母直线移动距离/单词所含字母总数）
例如：
(RACECAR)- 两个R移动距离为 6，两个A移动距离为 4，两个C移动距离为 2，E不移动，字母平均移动距离为 $\frac{6+6+4+4+2+2}{7}\approx3.43$。
上述例子中，(RACECAR) 是该单词（RACECAR）转换为回文单词的最高质量组合方案，我们称其为“最优回文单词”。
现在给你一个单词，请将该单词转换为“最优回文单词”。
格式
输入
一个英文单词，所有字母均大写。
输出
对应的“最优回文单词”。该单词的最外层需要有至少一层圆括号。
数据约定
对于 $30%$ 的数据，保证单词长度不超过 $10$ 个字母。
对于 $60%$ 的数据，保证单词长度不超过 $30$ 个字母。
对于 $100%$ 的数据，保证单词长度不超过 $60$ 个字母。
所有输入的单词保证有且仅有一个解。
测试样例
| |
| |
说明：该样例单词中没有重复的字母，因此把所有元素视为同一整体，此时移动字母数为 0，平均移动距离为 0。