TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

37.5% (6/16)

Submission's AC Ratio

19.2% (10/52)

Description

本題滿分為125分。

給定$K$,請構造一個由小寫英文字母構成的字串$S$,使得每個前$K$個英文小寫字母的子集(不重複)的排列所形成的字串$T$都是$S$的子序列。
另外,你構造的$S$愈短,將可以拿到愈多的分數。(詳請見Output Format。)

例如若$K=3$,則abcabbaaccabccbabcbacacbcabbcacba都必須是$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$。

本題的給分方式如下所述:

  1. 若你輸出的格式錯誤,或者對於任何一個$K$,你輸出的字串$S$不滿足題目給的條件,你將會在該筆測資獲得0分。

  2. 在第一個子任務中,若每個$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分。

  3. 在第二個子任務中,評測系統會對每一個$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

2

Sample Output

a
ababba

Hints

Problem Source

Problem set by waynetuinfor / Yihda Yol
建國中學107學年度校隊選拔:初試pB

Subtasks

For Testdata: 0 ~ 0, Score: 7
For Testdata: 1 ~ 1, Score: 13
For Testdata: 2 ~ 2, Score: 27
For Testdata: 3 ~ 3, Score: 12
For Testdata: 4 ~ 4, Score: 15
For Testdata: 5 ~ 5, Score: 26
For Testdata: 6 ~ 6, Score: 25
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 262144 262144
1 1500 262144 262144
2 4500 262144 262144
3 4500 262144 262144
4 100 65536 262144
5 100 65536 262144
6 100 65536 262144