2067 . 字串構造
TopCoder
Tags
Description
本題滿分為125分。
給定$K$，請構造一個由小寫英文字母構成的字串$S$，使得每個前$K$個英文小寫字母的子集（不重複）的排列所形成的字串$T$都是$S$的子序列。
另外，你構造的$S$愈短，將可以拿到愈多的分數。（詳請見Output Format。）
例如若$K=3$，則a、b、c、ab、ba、ac、ca、bc、cb、abc、bac、acb、cab、bca、cba都必須是$S$的子序列。
（字串$A$是字串$B$的子序列代表可以從$B$中刪除一些字元後得到$A$。）
Input Format
輸入只有正整數$X$，請你對$K=1,K=2,\cdots,K=X$都各輸出一個滿足條件的字串$S$。
每個子任務均有部分給分，詳見Output Format。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~1) | $X=8$ | 20 |
| 2 (2~7) | $X=22$ | 105 |
注意以下的範例輸入僅是用以表達輸入、輸出之格式，實際的測資中並沒有$X=2$的情況。
Output Format
請輸出$X$行，每行包含一個由小寫英文字母的字串，第$i$行的字串代表$K=i$時滿足條件的字串$S$。
本題的給分方式如下所述：
若你輸出的格式錯誤，或者對於任何一個$K$，你輸出的字串$S$不滿足題目給的條件，你將會在該筆測資獲得0分。
在第一個子任務中，若每個$S$都滿足題目給的條件，令你輸出的$X$個字串中最長的一個的長度為$P$：
(a) 若$P\leq 4\times 10^ 5$，你將在這個子任務中獲得全部的分數（20分）；
(b) 若$4\times 10^ 5 < P \leq 10^ 6$，你將在這個子任務中獲得7分；
(c) 若$P> 10^ 6$，你將在這個子任務中獲得0分。在第二個子任務中，評測系統會對每一個$K=i$設定一個門檻值$C_i$（保證在$K=i$時一定存在長度小於等於$C_i$的解）。若每個$S$都滿足題目給的條件，令你在$K=i$時輸出的字串$S$長度為$P_i$：
(a) 若對於所有$i(1\leq i\leq K)$都有$P_i\leq C_i$，你將獲得這個子任務全部的分數（105分）；
(b) 若(a)不成立，但對於所有$i$都有$P_i\leq C_i+K-3$，你將在這個子任務中獲得80分；
(c) 若(a),(b)不成立，但對於所有$i$都有$P_i\leq C_i+2K-3$，你將在這個子任務中獲得54或39分，視你的程式執行時間長短而定；
(d) 若(a),(b),(c)不成立，但對於所有$i$都有$P_i\leq 2K^ {2.5}$，你將在這個子任務中獲得27分；
(e) 若(a)~(d)均不成立，你將在這個子任務中獲得0分。
Sample Input 1
Sample Output 1
ababba
Hints
Problem Source
Problem set by waynetuinfor / Yihda Yol
建國中學107學年度校隊選拔：初試pB
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 7 |
| 2 | 1 | 13 |
| 3 | 2 | 27 |
| 4 | 3 | 12 |
| 5 | 4 | 15 |
| 6 | 5 | 26 |
| 7 | 6 | 25 |