## 單＿＿空 (V\_\_\_\_\_\_\_\_y)
> 出題者：暴力又被TLE
> 難度：p2
> 考點：字串、實作
### Statement
哭啊，又要段考了QWQ。
暴力又被TLE 已經連續好幾次都在單字填空被扣掉一半的分數，倒也不是他不知道要填甚麼單字，而是他填的單字都不在課本裡面，就只因為不在課本裡面就算錯，簡直是在限制學生的單字量：只要知道課本內的單字就好了。台灣的英文教育，失敗到了極點。
應對如此智＿的考試方法，當然要用跟他一樣＿障的方式。暴力又被TLE 想到了祖傳的字首字尾表表（當然跟字根的那個字首字尾沒有一點關係）。眾所周知，單字填空這個大題會將挖空的單字保留第一和最後一個字母，限制答案的範圍，因此只要將要考的每個單字按照第一和最後一個字母分組，就能夠以「字首字尾」對應「單字」的方式記憶了！
但是要手寫的話實在太慢了，而且 暴力又被TLE 不喜歡手寫，手寫超躁，他忽然靈光一閃！最近不是要辦 APCS 模擬賽嗎？那就讓參賽者來幫他寫吧！
因為 暴力又被TLE 有點強迫症，他想要確保文字在使用等距字元的情況下文字整整齊齊地排列，每一行的左側都切齊，且與前一欄最長的單字間隔一個空白（如下圖藍色選取範圍），並且組和組之間要按照「第一和最後一個字母」的字典序排序，舉個例子：`"ab" < "ac" < "ba"`，而各組內則是按照整個單字做字典序排序。
換欄時，如果一組單字剛好在中間被截斷，新的一個直欄頂部要再輸出一次字首字尾（如下圖紅色框）；且**每一行最後不能有任何空白**（如示意圖游標處）。
示意圖：
<!--  -->
<!--  -->
<!--  -->
<!--  -->
<!-- 
-->
因為只是一般的段考，所以一次最多只會考 $1000$ 個單字。
### Input
第一行有兩個正整數 $n$, $m$，表示總共輸入 $n$ 個單字，而輸出的單字表中每一直欄最多 $m$ 行。
接下來 $n$ 行，每一行會有一個全由英文小寫組成的單字，代表 暴力又被TLE 這次段考要背的單字。
**測資範圍**
$0 \lt n \le 1000$
$1 \le m \le n$
$2 \le word.length \le 20$
### Output
輸出 $m$ 行文字，即單字表。需要特別注意：**每一行最後不能有任何空白**（如示意圖游標處）。
### Testcase
- Input 1
```
48 10
disappoint
achievement
ancient
contract
request
harvest
tourist
defend
regret
selfishness
apart
habit
expand
journey
demand
highlight
document
freedom
protect
concert
event
detect
comfort
sickness
defend
puzzle
divid
sincere
concept
appointment
success
demand
regret
ascent
respect
balance
result
await
effort
argument
expert
transcript
sadness
heart
elect
amusement
talent
target
```
- Output 1
```
at achievement ct concept dt document ht highlight ss sadness
amusement concert ed expand jy journey selfishness
ancient contract et effort pe puzzle sickness
apart dd defend elect pt protect success
appointment defend event rt regret tt talent
argument demand expert regret target
ascent demand fm freedom request tourist
await divid ht habit respect transcript
be balance dt detect harvest result
ct comfort disappoint heart se sincere
```
- 範例測資 1 解釋
同示意圖。
### Subtask
舊：
- Subtask 1 (0%) - $m = 1$
- Subtask 2 (0%) - 同一組的單字不會被截斷。
- Subtask 3 (0%) - $n \mid m$
- Subtask 4 (100%) - 依題意完整實作即可，我相信這題不需要子題分 ~~（絕對不是因為我懶得生）~~。
新：
- Subtask 1 (30%) - $m = n$
- Subtask 2 (70%) - 依題意完整實作即可。
### Solution
```python=
def p____n():
from sys import stdin
from collections import defaultdict
from itertools import zip_longest
n, m = map(int, input().split())
# 全部輸入並去掉結尾換行
words: list[str] = list(map(str.strip, stdin.readlines()))
# 所有字串按照字典序排序
words.sort()
# 按照頭尾字元分組
dic: defaultdict[str, list[str]] = defaultdict(list)
for word in words:
# 提取頭尾字元
key: str = word[0] + word[-1]
dic[key].append(word)
# 將頭尾字元依照字典序遍歷
s_key: list[str] = sorted(dic.keys())
# col 儲存單一直欄要輸出的字串
col: list[str] = []
# lines 儲存所有 col
lines: list[list[str]] = [col]
for key in s_key: # 每一輪遍歷一種頭尾字元
prefix = True # 是否要加上頭尾字元
for words in dic[key]: # 遍歷頭尾字元相同的單字們
# 加上一個單字
col.append(f"{key if prefix else ' '} {words}")
prefix = False # 只有第一個需要加上頭尾字元
if len(col) == m: # 換行
col = []
lines.append(col) # 新增直欄
prefix = True # 新行開頭需要輸出頭尾字元
if not col: lines.pop() # 如果最後一欄沒有任何單字就把他丟掉
# 計算每一直欄的結尾空白
for col in lines:
# 取最長的字串
max_len = max(len(i) for i in col)
for i, v in enumerate(col):
col[i] = v.ljust(max_len) # 將字串加上空白 擴增到一樣的寬度
# 用 zip 將 col 拆成一行一行輸出
# zip_longest 可以避免最後一個 col 沒有字串而使 zip 停下來
for row in zip_longest(*lines, fillvalue=""):
print(" ".join(row).rstrip()) # 去掉右側多餘空白
p____n()
```
### Generator
以下是實際用來生成測資的部分。
除了前 30% $m = n$ 的子題，後 70% 的測資都滿足 $n \nmid m$，可以使最右邊一欄未滿。
```python=
def gen_sub(testcase_idx, rand_obj):
n = rand_obj.randint(500, 1000)
if testcase_idx <= 6:
m = n
else:
while n % (m := rand_obj.randint(2, n)) == 0:
pass
assert m != 1
assert n % m != 0
words = (''.join(rand_obj.choices(ascii_lowercase,
k=rand_obj.randint(2, 20)))
for _ in range(n))
testcase = (f"{n} {m}\n"
f"{"\n".join(words)}\n")
return testcase
```
以下是用來驗證測資的部分，就是從 Solution 改來的。
大部分的 `assert` 都是用來確保數值範圍正確，比較特別的是 `assert_line_break` 這個變數，確保至少有一欄將同一組的單字截斷（後 70% 的測資），如果沒有就回到 `gen_sub` 再隨機一個。
```python=
def sol():
from sys import stdin
from collections import defaultdict
from itertools import zip_longest
n, m = map(int, input().split())
assert m != 1
assert m == n or n % m != 0
words: list[str] = list(map(str.strip, stdin.readlines()))
assert len(words) == n, f"{len(words) = }, {n = }"
words.sort()
dic: defaultdict[str, list[str]] = defaultdict(list)
for word in words:
if not word: continue
key: str = word[0] + word[-1]
dic[key].append(word)
s_key: list[str] = sorted(dic.keys())
col: list[str] = []
lines: list[list[str]] = [col]
assert_line_break = False
for key in s_key:
prefix = True
for idx, words in enumerate(dic[key]):
if idx != 0 and prefix is True:
assert_line_break = True
col.append(f"{key if prefix else ' '} {words}")
prefix = False
if len(col) == m:
col = []
lines.append(col)
prefix = True
if not col: lines.pop()
assert m == n or assert_line_break
for col in lines:
max_len = max(len(i) for i in col)
for i, v in enumerate(col):
col[i] = v.ljust(max_len)
for row in zip_longest(*lines, fillvalue=""):
print(" ".join(row).rstrip())
```
Sign in with Wallet
Connect another wallet