P11851 [TOIP 2023] 分子環

$\textcolor{red}{\textbf{本題有 Special Judge，會依照解的好壞程度動態給分。}}$

A 博士是學界研究外星球物質的最高權威，他因為發現外星球中的 `X` 與 `Y` 兩種地球不存在的分子以及其形成的特殊化合物結構而被提名諾貝爾獎。在博士研究中，這兩種分子不論是與自己或另一種分子間都可以形成化學鍵，並且更進一步地發現，任意大於等於 $3$ 個 `X` 與 `Y` 分子都可以以任意順序形成一個環狀的化合物；環狀化合物中每一個分子與其前一個（逆時針方向）和後一個（順時針方向）分子分別形成鍵結，並廣泛分布在外星球上。A 博士將這種環狀的化合物結構命名為**分子環**，為了方便表示這種分子環，A博士決定以任意一個分子做為起點順時針依序寫下各個分子形成的字串作為此分子環的表示。例如 `XYY` 與 `YYX` 與 `YXY` 都是指同一種分子環的構造。 A 博士也發現了當分子環形成時，這個分子環的不穩定程度與**最多連續相同分子**的數量為正比，因此他決定稱這個數字為**分子環的不穩定度**。舉例來說分子環 `YXY` 中因為最多有 $2$ 個連續的 `Y`（第一和第三個分子在環狀中相鄰），不穩定度為 $2$；同理， `XXYXXYXX` 分子環中因為可以找到 $4$ 個連續的 `X`（分子環表示中第 $1, 2, 7, 8$ 個分子），因此不穩定度為 $4$。 在研究完分子環的性質後，A博士希望能合成出多種不同的分子環來證明他的理論。具體來說，他希望合成的分子環滿足下列的性質： * 有 $a$ 個分子前後都是 `X` 分子 * 有 $b$ 個分子前後都是 `Y` 分子 * 以及有 $c$ 個分子前後分別是一個 `X` 分子和一個 `Y` 分子，前後順序可以顛倒 為了讓博士繼續進行他的研究，A博士決定請你幫忙寫個程式計算滿足條件的分子環。並且他希望你的程式能輸出**不穩定度較低的分子環**來降低合成的難度。由於分子環的表示有很多種，也不一定只有一種分子環滿足博士要求，你只需要輸出任意一種滿足條件的分子環結構即可。 此題的得分會由你輸出的分子環不穩定度決定，請見《評分說明》一節。

> $a$ $b$ $c$ * $a$ 代表分子環中有多少個分子前後都是 `X` 分子 * $b$ 代表分子環中有多少個分子前後都是 `Y` 分子 * $c$ 代表分子環中有多少個分子前後有一個 `X` 及一個 `Y` 分子（可以前後順序顛倒）

若找得到分子環滿足要求，請輸出： > $K$ > $M$ * $K$ 為輸出分子環的不穩定度。 * $M$ 為一長度 $a+b+c$ 且只包含 `X, Y` 字元的字串，表示分子環的結構。 若沒有分子環能滿足博士的要求，那請輸出： > $-1$

### 測資限制 * $0 \le a, b, c \le 10^5$。 * $a+b+c \ge 3$。 * 以上變數皆為整數。 ### 評分說明 對每筆有解的輸入檔，評分程式會計算一個 $K^{*}$ 值代表滿足博士要求的最小穩定度。若你的程式輸出的分子環正確且滿足博士要求，則該筆測試資料得分為： $$\textbf{round}(\frac{1000}{1 + \min\{19, K - K^{*}\}}) \div 1000$$ 乘以該筆子任務配分，其中 `round(x)` 代表對 $x$ 四捨五入取至整數位。該子任務的得分為所有輸入檔最小的得分，並請注意若有以下情況則該筆輸入以 $0$ 分計： * 不滿足題目要求，包括 * 與 `XX`, `YY`, `XY` 相鄰的分子數並非規定的 $a$, $b$, $c$ 個 * 有解卻輸出 `-1` * 無解但輸出有解 * 輸出的 $K$ 值並非 $M$ 的不穩定度。 ### 子任務 本題共有四組子任務，條件限制如下所示。每一組可有一或多筆測試資料，取該組所有測試資料中最低分為該子任務得分。 | 子任務 | 分數 | 額外輸入限制 | | :------: | :----: | ------------ | | 1 | $8$ | $a + b + c \le 15$ | | 2 | $29$ | $a, b, c \le 20$ | | 3 | $21$ | $b=0$ 且 $2a \ge c$ | | 4 | $42$ | 無額外限制 |