DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Pretty String

Back to problem

Editorial

Let L=∣S∣L=|S|L=∣S∣. If there are kkk lines, their lengths are 1,1+n,…,1+(k−1)n1,1+n,\ldots,1+(k-1)n1,1+n,…,1+(k−1)n, so

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

For k≥2k\geq2k≥2, set D=k(k−1)/2D=k(k-1)/2D=k(k−1)/2. A split exists exactly when L−kL-kL−k is a positive multiple of , and then .

Since n≥1n\geq1n≥1, we need k(k+1)/2≤Lk(k+1)/2\leq Lk(k+1)/2≤L. Check such values of kkk from largest to smallest and choose the first valid one. Then print consecutive pieces of SS of lengths . A single line is possible only when , so a string of length has no answer.

There are O(L)O(\sqrt L)O(L​) candidate values of kkk, and printing takes O(L)O(L)O(L time. Space usage including the input string is .

Solution written by GPT6

DDD
n=(L−k)/Dn=(L-k)/Dn=(L−k)/D
S
1,1+n,…1,1+n,\ldots1,1+n,…
L=1L=1L=1
222
)
O(L)O(L)O(L)