k187. pD. 分子環 (molecule) - 高中生程式解題系統

內容

題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing

請特別注意，由於Zerojudge測資數量限制，本題為 $T$ 行版，請見輸入輸出說明。

由於原題有Special Judge，本題若你的答案不是最佳解，你會獲得WA，並且會在評分詳細結果中顯示你在該筆測資獲得的最小%數，如以下格式：

#0: 1% WA (line:0)
Minimum :50% score
您的答案為：your output is legal
正確答案為：get partial

$A$ 博士是學界研究外星球物質的最高權威，他因為發現外星球中的 $X$ 與 $Y$ 兩種地球不存在的分子以及其形成的特殊化合物結構而被提名諾貝爾獎。在博士研究中，這兩種分子不論是與自己或另一種分子間都可以形成化學鍵，並且更進一步地發現，任意大於等於 $3$ 個 $X$ 與 $Y$ 分子都可以以任意順序形成一個環狀的化合物；環狀化合物中每一個分子與其前一個（逆時針方向）和後一個（順時針方向）分子分別形成鍵結，並廣泛分布在外星球上。 $A$ 博士將這種環狀的化合物結構命名為分子環，為了方便表示這種分子環， $A$ 博士決定以任意一個分子做為起點順時針依序寫下各個分子形成的字串作為此分子環的表示。例如 $X Y Y$ 與 $Y Y X$ 與 $Y X Y$ 都是指同一種分子環的構造。

$A$ 博士也發現了當分子環形成時，這個分子環的不穩定程度與最多連續相同分子的數量為正比，因此他決定稱這個數字為分子環的不穩定度。舉例來說分子環 $Y X Y$ 中因為最多有 $2$ 個連續的 $Y$ （第一和第三個分子在環狀中相鄰），不穩定度為 $2$ ；同理， $X X Y X X Y X X$ 分子環中因為可以找到 $4$ 個連續的 $X$ （分子環表示中第 $1, 2, 7, 8$ 個分子），因此不穩定度為 $4$ 。

在研究完分子環的性質後， $A$ 博士希望能合成出多種不同的分子環來證明他的理論。具體來說，他希望合成的分子環滿足下列的性質：

• 有 $a$ 個分子前後都是 $X$ 分子

• 有 $b$ 個分子前後都是 $Y$ 分子

• 以及有 $c$ 個分子前後分別是一個 $X$ 分子和一個 $Y$ 分子，前後順序可以顛倒

為了讓博士繼續進行他的研究， $A$ 博士決定請你幫忙寫個程式計算滿足條件的分子環。並且他希望你的程式能輸出不穩定度較低的分子環來降低合成的難度。由於分子環的表示有很多種，也不一定只有一種分子環滿足博士要求，你只需要輸出任意一種滿足條件的分子環結構即可。

此題的得分會由你輸出的分子環不穩定度決定，請見《評分說明》一節。

測資限制

• $0 \leq a, b, c \leq 10^{5}$ 。
• $a + b + c \geq 3$ 。
• 以上變數皆為整數。

評分說明

對每筆有解的輸入檔，評分程式會計算一個 $K^{*}$ 值代表滿足博士要求的最小穩定度。若你的程式輸出的分子環正確且滿足博士要求，則該筆測試資料得分為：

乘以該筆子任務配分，其中 $r o u n d (x)$ 代表對 $x$ 四捨五入取至整數位。該子任務的得分為所有輸入檔最小的得分，並請注意若有以下情況則該筆輸入以 $0$ 分計：

$r o u n d (\frac{1000}{1 + m i n ({19, K - K^{*}})}) \div 1000$

• 不滿足題目要求，包括
– 與 $X X, Y Y, X Y$ 相鄰的分子數並非規定的 $a, b, c$ 個
– 有解卻輸出 $- 1$
– 無解但輸出有解
• 輸出的 $K$ 值並非 $M$ 的不穩定度。

輸入說明

輸入格式：

$T$

$a_{1}$ $b_{1}$ $c_{1}$

$a_{2}$ $b_{2}$ $c_{2}$

...

$a_{T}$ $b_{T}$ $c_{T}$

• $T$ 代表有接著有 $T$ 行，共有 $T$ 筆測資
• $a_{i}$ 代表分子環中有多少個分子前後都是 X 分子
• $b_{i}$ 代表分子環中有多少個分子前後都是 Y 分子
• $c_{i}$ 代表分子環中有多少個分子前後有一個 X 及一個 Y 分子（可以前後順序顛倒）

保證 $\sum a_{i} \leq 2 \times 10^{5}$ , $\sum b_{i} \leq 2 \times 10^{5}$ , $\sum c_{i} \leq 2 \times 10^{5}$

輸出說明

對於每筆測資：

若找得到分子環滿足要求，請輸出兩行：

K

M

• $K$ 為輸出分子環的不穩定度。
• $M$ 為一長度 $a_{i} + b_{i} + c_{i}$ 且只包含 X, Y 字元的字串，表示分子環的結構。
若沒有分子環能滿足博士的要求，那請輸出一行：

- 1

範例輸入 #1

範例輸出 #1

-1
2
XXYXY
2
XXYY
1
XYXYXYXY
3
XYYYXYYXYXXXYXXYXX

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (1%): 1.0s , <1K
公開測資點#1 (8%): 1.0s , <1K
公開測資點#2 (29%): 2.0s , <1K
公開測資點#3 (3%): 2.0s , <1K
公開測資點#4 (3%): 2.0s , <1K
公開測資點#5 (3%): 2.0s , <1K
公開測資點#6 (3%): 2.0s , <1K
公開測資點#7 (3%): 2.0s , <1K
公開測資點#8 (3%): 2.0s , <1K
公開測資點#9 (3%): 2.0s , <1K
公開測資點#10 (4%): 2.0s , <1K
公開測資點#11 (4%): 2.0s , <1K
公開測資點#12 (4%): 3.0s , <1K
公開測資點#13 (4%): 2.0s , <1K
公開測資點#14 (4%): 2.0s , <1K
公開測資點#15 (4%): 2.0s , <1K
公開測資點#16 (4%): 2.0s , <1K
公開測資點#17 (4%): 2.0s , <1K
公開測資點#18 (4%): 2.0s , <1K
公開測資點#19 (5%): 2.0s , <1K

提示：

題目和測資來源 : twpca

因為礙於系統問題測試資料沒辦法完整的放上來，所以也許會有測資不夠強的狀況，歡迎提出。

因為Zerojudge上Special Judge跑的速度較慢，於是調整時限。

子任務	分數	額外輸入限制	測資點
1	8	$a + b + c \leq 15$	#01
2	29	$a, b, c \leq 20$	#02
3	21	$b = 0$ 且 $2 a \geq c$	#03~#09
4	42	無額外限制	#10~#19

如果題目有問題歡迎來信詢問！

標籤:

dp 數學構造法

出處:

TOI入營考 2023 [管理者： Ststone1687 (Ststone) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」