DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Pretty String

返回题目

题解

L=∣S∣L=|S|L=∣S∣라 하자. 줄이 kkk개라면 각 줄의 길이는 1,1+n,…,1+(k−1)n1,1+n,\ldots,1+(k-1)n1,1+n,…,1+(k−1)n이므로

L=k+nk(k−1)2L=k+n\frac{k(k-1)}2L=k+n2k(k−1)​

이다. k≥2k\geq2k≥2일 때 D=k(k−1)/2D=k(k-1)/2D=k(k−1)/2라 하면, L−kL-kL−k가 의 양의 배수인 경우에만 가능하고 이때 로 정해진다.

n≥1n\geq1n≥1이므로 k(k+1)/2≤Lk(k+1)/2\leq Lk(k+1)/2≤L이다. 이 조건을 만족하는 kkk를 큰 값부터 확인하여 처음 가능한 값을 고른다. 그런 다음 길이 1,1+n,…씩 를 앞에서부터 잘라 출력한다. 이면 문자열 길이가 일 때만 가능하다. 따라서 길이가 인 문자열은 답이 없다.

후보 kkk는 O(L)O(\sqrt L)O(L​)개이고, 출력에 O(L)O(L)O(L) 시간이 걸린다. 공간 복잡도는 입력 문자열을 포함해 이다.

Solution written by GPT6

DD
D
n=(L−k)/Dn=(L-k)/Dn=(L−k)/D
1,1+n,\ldots
1,1+n,…
SSS
k=1k=1k=1
111
222
O(L)O(L)O(L)