STUDIO HAZE · atlas
Topaz source
Open by house policy. Topaz is our own language.
Topaz 6.0 · 5 files
Topaz 6.0 source.
Publication edits are limited to explanatory comments. Executable code is unchanged.
Rights and source notices · Source manifest
core/topaz/linebreak/줄바꿈.tpz
Topaz · 29482 B · Published file
1
// 아틀라스 줄바꿈. 한국어 식별자로 쓴 토파즈 줄바꿈기다(the published Korean line-breaker).2
//3
// 이 모듈은 아틀라스 본문 조판의 줄바꿈 알고리즘 전체를 토파즈로 구현한 실행 가능한 명세이다.4
// 네 단계로 이뤄진다.5
// 1) 금칙분류는 어디서 줄을 끊을 수 있는지 가린다(break-opportunity classifier, kinsoku).6
// 2) 나쁨도는 한 줄이 얼마나 헐겁거나 빡빡한지 매긴다(fixed-point badness).7
// 3) 정렬벌점은 양끝맞춤이 얼마나 무리인지 매긴다(justification penalty, Latin + CJK).8
// 4) 최적분할은 전체 비용이 최소인 분할을 고른다(optimal-fit integer DP).9
// 모든 연산은 정수 밀리포인트(mpt)와 정수 B 단위로 한다. 부동소수는 쓰지 않는다.10
//11
// 입력/출력 프로토콜 (스텝퍼, io.readStdin() → 처리 → io.writeLine())12
// 입력 0행 헤더 "<목표너비mpt> <첫줄목표너비mpt> <드롭캡줄수> <드롭캡인셋mpt> <정렬모드>13
// <최소간격> <비율M> <최대조정량mpt> <최대간격mpt> <최대간격비율R>"14
// 정렬모드 -1=없음, 0=라틴낱말간격, 1=CJK글자사이15
// 드롭캡줄수 0과 드롭캡인셋 0이면 드롭캡 OFF (단일 버킷)16
// 입력 1행~ "<진행mpt>\t<클러스터텍스트>" (셰이프된 클러스터 하나당 한 행, 순서대로)17
// 출력 각 줄 "<시작클러스터> <끝클러스터배타> <줄나쁨도B>"18
// 출력 마지막 "TOTAL <총비용B>"19
// 오류 센티넬 "OUT_OF_BOUNDS" 또는 "NO_PLAN"21
import std.io23
let R = 100000000 // 1e8 비율 스케일 (ratio scale)24
let B = 1000000 // 1e6 나쁨도/벌점 스케일 (badness/penalty scale)25
let CAP = 25000 // 정렬 벌점 상한 (justification penalty cap)27
// ── 공용 정수 보조 (shared integer helpers) ──28
function 반올림나눗셈(분자: int, 분모: int) -> int { // round-half-up, 음이 아닌 값만29
let 몫 = 분자 / 분모30
let 나머지 = 분자 % 분모31
if (나머지 >= (분모 + 1) / 2) { 몫 + 1 } else { 몫 }32
}33
function 절댓값(값: int) -> int { if (값 < 0) { -값 } else { 값 } }34
function 첫코드포인트(텍스트: string) -> int { 텍스트.codePointAt(0) ?? -1 }35
function 단일스칼라(텍스트: string) -> bool { 텍스트.scalars().length == 1 }37
// ── 금칙분류 · 글자류 판정 (char-class predicates over a single code point) ──38
function 한글분할문자인가(코드: int) -> bool {39
(코드 >= 4352 && 코드 <= 4607) // U+1100..U+11FF 한글 자모40
|| (코드 >= 12592 && 코드 <= 12687) // U+3130..U+318F 한글 호환 자모41
|| (코드 >= 44032 && 코드 <= 55215) // U+AC00..U+D7AF 한글 음절42
|| (코드 >= 13312 && 코드 <= 19903) // U+3400..U+4DBF CJK 확장 A43
|| (코드 >= 19968 && 코드 <= 40959) // U+4E00..U+9FFF CJK 통합44
|| (코드 >= 63744 && 코드 <= 64255) // U+F900..U+FAFF CJK 호환45
|| 코드 == 65292 || 코드 == 12289 || 코드 == 12290 || 코드 == 65307 || 코드 == 65306 // , 、 。 ; :46
}47
function 줄머리금지인가(코드: int) -> bool {48
코드 == 41 || 코드 == 93 || 코드 == 125 // ) ] }49
|| 코드 == 12301 || 코드 == 12303 || 코드 == 12299 || 코드 == 12297 // 」 』 》 〉50
|| 코드 == 44 || 코드 == 46 || 코드 == 59 || 코드 == 58 || 코드 == 33 || 코드 == 63 // , . ; : ! ?51
|| 코드 == 12289 || 코드 == 12290 // 、 。52
|| 코드 == 8221 // ”53
|| 코드 == 8217 || 코드 == 8230 || 코드 == 65289 || 코드 == 12305 || 코드 == 65341 || 코드 == 65373 || 코드 == 65292 || 코드 == 65294 || 코드 == 65307 || 코드 == 65306 || 코드 == 65281 || 코드 == 65311 || 코드 == 187 || 코드 == 825054
}55
function 줄끝금지인가(코드: int) -> bool {56
코드 == 40 || 코드 == 91 || 코드 == 123 // ( [ {57
|| 코드 == 12300 || 코드 == 12302 || 코드 == 12298 || 코드 == 12296 // 「 『 《 〈58
|| 코드 == 8220 || 코드 == 8216 // “ ‘59
|| 코드 == 65288 || 코드 == 12304 || 코드 == 65339 || 코드 == 65371 || 코드 == 171 || 코드 == 824960
}62
// ── 클러스터 스칼라 전체/일부 판정 (all/any over a cluster's scalars; 빈 문자열 -> all=true, any=false) ──63
function 모두한글분할(텍스트: string) -> bool {64
텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 한글분할문자인가(첫코드포인트(스칼라)))65
}66
function 모두줄머리금지(텍스트: string) -> bool {67
텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 줄머리금지인가(첫코드포인트(스칼라)))68
}69
function 일부줄머리금지(텍스트: string) -> bool {70
텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄머리금지인가(첫코드포인트(스칼라)))71
}72
function 일부줄끝금지(텍스트: string) -> bool {73
텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄끝금지인가(첫코드포인트(스칼라)))74
}76
// ── 단어 전체 판정 (whole-string predicates; single-scalar equality) ──77
function 분할가능라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }78
function 라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }79
function 비분할공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }80
function 라틴붙임표인가(텍스트: string) -> bool {81
단일스칼라(텍스트) && (첫코드포인트(텍스트) == 45 || 첫코드포인트(텍스트) == 8208 || 첫코드포인트(텍스트) == 8209 || 첫코드포인트(텍스트) == 8211)82
}83
function 쉼표마침표콜론인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 44 || 첫코드포인트(텍스트) == 46 || 첫코드포인트(텍스트) == 58) }84
function 아스키숫자인가(텍스트: string) -> bool { 텍스트.byteLength() == 1 && 첫코드포인트(텍스트) >= 48 && 첫코드포인트(텍스트) <= 57 }86
// ── 이웃 클러스터 가드 (Option<string> neighbor guards) ──87
function 다음은라틴공백아님(다음: Option<string>) -> bool {88
match (다음) {89
case Some(텍스트) => !라틴공백인가(텍스트)90
case None() => true91
}92
}93
function 다음은줄머리금지없음(다음: Option<string>) -> bool {94
match (다음) {95
case Some(텍스트) => !일부줄머리금지(텍스트)96
case None() => true97
}98
}99
function 다음은라틴공백(다음: Option<string>) -> bool {100
match (다음) {101
case Some(텍스트) => 라틴공백인가(텍스트)102
case None() => false103
}104
}105
function 다음은일부줄머리금지(다음: Option<string>) -> bool {106
match (다음) {107
case Some(텍스트) => 일부줄머리금지(텍스트)108
case None() => false109
}110
}111
function 옵션아스키숫자인가(옵션: Option<string>) -> bool {112
match (옵션) {113
case Some(텍스트) => 아스키숫자인가(텍스트)114
case None() => false115
}116
}118
function 숫자구분자인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {119
쉼표마침표콜론인가(현재) && 옵션아스키숫자인가(이전) && 옵션아스키숫자인가(다음)120
}121
function 닫음부호허용인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {122
모두줄머리금지(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !숫자구분자인가(현재, 이전, 다음)123
}124
function 한글분할허용인가(현재: string, 다음: Option<string>) -> bool {125
모두한글분할(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !일부줄끝금지(현재)126
}128
// ── 분할점생성 · 단위 끝과 분할종류 (break opportunities, 인덱스 0에 센티넬) ──129
// 분할종류 토큰은 ASCII 유지(입출력 토큰).130
// 모든 후보에 적용하는 원문 문맥 금칙. 공백 뒤의 부호도 앞 낱말에 붙인다.131
function 공백코드인가(코드: int) -> bool {132
(코드 >= 9 && 코드 <= 13) || 코드 == 32 || 코드 == 133 || 코드 == 160 || 코드 == 5760133
|| (코드 >= 8192 && 코드 <= 8202) || 코드 == 8232 || 코드 == 8233 || 코드 == 8239 || 코드 == 8287 || 코드 == 12288134
}135
function 여는직선따옴표인가(글자들: Array<string>, 위치: int) -> bool {136
let 코드 = 첫코드포인트(글자들[위치])137
if (코드 != 34 && 코드 != 39) { return false }138
if (위치 == 0) { return true }139
let 앞 = 첫코드포인트(글자들[위치 - 1])140
공백코드인가(앞) || 줄끝금지인가(앞)141
}142
function 라틴낱말코드인가(코드: int) -> bool {143
(코드 >= 65 && 코드 <= 90) || (코드 >= 97 && 코드 <= 122)144
|| (코드 >= 192 && 코드 <= 591) || (코드 >= 7680 && 코드 <= 7935)145
}146
function 문맥경계허용인가(글자들: Array<string>, 경계: int) -> bool {147
let mut 왼쪽 = 경계 - 1148
while (왼쪽 >= 0) {149
if (!공백코드인가(첫코드포인트(글자들[왼쪽]))) { break }150
왼쪽 -= 1151
}152
if (왼쪽 > 0 && 왼쪽 + 1 < 글자들.length) {153
let 코드 = 첫코드포인트(글자들[왼쪽])154
if ((코드 == 8217 || 코드 == 39) && 라틴낱말코드인가(첫코드포인트(글자들[왼쪽 - 1])) && 라틴낱말코드인가(첫코드포인트(글자들[왼쪽 + 1]))) { return false }155
}156
if (왼쪽 >= 0) {157
if (줄끝금지인가(첫코드포인트(글자들[왼쪽])) || 여는직선따옴표인가(글자들, 왼쪽)) { return false }158
}159
let mut 오른쪽 = 경계160
while (오른쪽 < 글자들.length) {161
if (!공백코드인가(첫코드포인트(글자들[오른쪽]))) { break }162
오른쪽 += 1163
}164
if (오른쪽 < 글자들.length) {165
let 코드 = 첫코드포인트(글자들[오른쪽])166
if (줄머리금지인가(코드)) { return false }167
if ((코드 == 34 || 코드 == 39) && !여는직선따옴표인가(글자들, 오른쪽)) { return false }168
if (코드 == 8212) {169
if (오른쪽 > 0 && 줄머리금지인가(첫코드포인트(글자들[오른쪽 - 1]))) { return false }170
if (오른쪽 + 1 < 글자들.length && 줄머리금지인가(첫코드포인트(글자들[오른쪽 + 1]))) { return false }171
}172
}173
true174
}176
function 분할점생성(클러스터들: Array<string>) -> { 단위들: Array<int>, 종류들: Array<string> } {177
let 개수 = 클러스터들.length178
let mut 전체텍스트 = ""179
for 단위 in (클러스터들) { 전체텍스트 = 전체텍스트 + 단위 }180
let 글자들 = 전체텍스트.scalars()181
let mut 글자끝 = 0182
let mut 단위들 = [0]183
let mut 종류들 = ["forced_end"]184
for i in (0..<개수) {185
let 단위 = 클러스터들[i]186
let 단위끝 = i + 1187
글자끝 += 단위.scalars().length188
let 이전: Option<string> = 클러스터들.get(i - 1)189
let 다음 = 클러스터들.get(단위끝)190
let 결과: { 종류: string, 내보냄: bool } = match (true) {191
case _ if (단위끝 == 개수) => { 종류: "forced_end", 내보냄: true }192
case _ if (!문맥경계허용인가(글자들, 글자끝)) => { 종류: "", 내보냄: false }193
case _ if (분할가능라틴공백인가(단위)) => { 종류: "latin_space", 내보냄: true }194
case _ if (라틴붙임표인가(단위)) => { 종류: "latin_hyphen", 내보냄: true }195
case _ if (닫음부호허용인가(단위, 이전, 다음)) => { 종류: "closing_punctuation", 내보냄: true }196
case _ if (한글분할허용인가(단위, 다음)) => { 종류: "korean_cluster", 내보냄: true }197
case _ if (다음은라틴공백(다음) || 비분할공백인가(단위) || 일부줄끝금지(단위) || 다음은일부줄머리금지(다음)) => { 종류: "", 내보냄: false }198
case _ => { 종류: "hard_fallback", 내보냄: true }199
}200
if (결과.내보냄) {201
단위들.push(단위끝)202
종류들.push(결과.종류)203
}204
}205
{ 단위들: 단위들, 종류들: 종류들 }206
}208
// ── 나쁨도 · 고정소수 줄 나쁨도 (fixed-point line badness, justification=None 경로) ──209
function 나쁨도(너비: int, 목표너비: int, 글자수: int, 공백수: int, 분할종류: string, 마지막인가: bool) -> int {210
let 여유 = 목표너비 - 너비211
let 절대여유 = 절댓값(여유)212
let 원시R = if (절대여유 >= 4 * 목표너비) { 4 * R } else { 절대여유 * R / 목표너비 }213
let 조정상한센티 = if (여유 >= 0) { 100 + 공백수 * 45 } else { 100 + 공백수 * 25 }214
let 비례R = 반올림나눗셈(원시R * 100, 조정상한센티)215
let 제곱 = 비례R * 비례R216
let 몫 = 반올림나눗셈(제곱, R)217
let mut 기본B = 반올림나눗셈(몫 * (1000 * B), R)218
if (마지막인가) {219
기본B = 반올림나눗셈(기본B * 2, 5)220
if (너비 * 100 < 목표너비 * 52 && 글자수 > 0) { 기본B += 500 * B }221
}222
if (여유 < 0) { 기본B += 20000 * B + 반올림나눗셈(20000 * B * 비례R, R) }223
if (분할종류 == "latin_hyphen") { 기본B += 65 * B }224
if (분할종류 == "hard_fallback") { 기본B += 50000 * B }225
if (글자수 <= 2) { 기본B += 275 * B }226
기본B += 10 * B227
기본B228
}230
// ── 정렬벌점 · CJK 글자사이 정렬 보조 (CJK justification helpers) ──231
function 낱말공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160) }232
function U0020인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }233
function CJK정렬문자인가(코드: int) -> bool {234
(코드 >= 4352 && 코드 <= 4607) || (코드 >= 12592 && 코드 <= 12687) || (코드 >= 13312 && 코드 <= 19903)235
|| (코드 >= 19968 && 코드 <= 40959) || (코드 >= 44032 && 코드 <= 55203) || (코드 >= 63744 && 코드 <= 64255)236
}237
function 정렬부호코드인가(코드: int) -> bool {238
코드 == 46 || 코드 == 44 || 코드 == 59 || 코드 == 58 || 코드 == 33 || 코드 == 63 || 코드 == 34 || 코드 == 39239
|| 코드 == 40 || 코드 == 41 || 코드 == 91 || 코드 == 93 || 코드 == 123 || 코드 == 125240
|| 코드 == 12290 || 코드 == 12289 || 코드 == 65292 || 코드 == 65294241
|| 코드 == 12300 || 코드 == 12301 || 코드 == 12302 || 코드 == 12303 || 코드 == 12298 || 코드 == 12299 || 코드 == 12296 || 코드 == 12297242
}243
function 단일CJK인가(텍스트: string) -> bool { 단일스칼라(텍스트) && CJK정렬문자인가(첫코드포인트(텍스트)) }244
function 정렬부호단위인가(텍스트: string) -> bool {245
텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 정렬부호코드인가(첫코드포인트(스칼라)))246
}247
function CJK간격후보인가(왼쪽: string, 오른쪽: string) -> bool { 단일CJK인가(왼쪽) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽) }248
function 한글공백간격후보인가(왼쪽: string, 공백: string, 오른쪽: string) -> bool {249
단일CJK인가(왼쪽) && 낱말공백인가(공백) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽)250
}251
function CJK간격수(텍스트들: Array<string>, 시작: int, 끝: int) -> int {252
let mut 간격 = 0253
for i in (시작..<끝) {254
if (i + 1 < 끝 && CJK간격후보인가(텍스트들[i], 텍스트들[i + 1])) { 간격 += 1 }255
}256
for i in (시작..<끝) {257
if (i + 2 < 끝 && 한글공백간격후보인가(텍스트들[i], 텍스트들[i + 1], 텍스트들[i + 2])) {258
if (!CJK간격후보인가(텍스트들[i], 텍스트들[i + 1])) { 간격 += 1 }259
if (!CJK간격후보인가(텍스트들[i + 1], 텍스트들[i + 2])) { 간격 += 1 }260
}261
}262
간격263
}265
// ── 정렬벌점 · 라틴 낱말간격과 CJK 글자사이 통합 (full justification penalty, Latin + CJK) ──266
function 정렬벌점(진행: Array<int>, 텍스트들: Array<string>, 목표너비: int, 최소간격: int, 비율M: int,267
최대조정량: int, 최대간격: int, 최대간격비율R: int, 모드: int, 마지막인가: bool, 최종비율M: int) -> int {268
if (마지막인가) { return 0 }269
let 개수 = 텍스트들.length270
let mut 유효 = 개수271
while (유효 > 0 && 낱말공백인가(텍스트들[유효 - 1])) { 유효 -= 1 }272
if (유효 == 0) { return CAP * B }273
if (목표너비 <= 0) { return CAP * B }274
let 원래너비 = (0..<유효).reduce(0, (합: int, i: int) => 합 + 진행[i])275
if (최종비율M > 0) {276
let 간격 = (0..<유효).filter((i: int) => U0020인가(텍스트들[i])).length277
if (간격 > 0 || 모드 == 0) {278
let 간격조정량 = 간격 * 최대간격279
let 가능너비 = 원래너비 + (if (최대조정량 < 간격조정량) { 최대조정량 } else { 간격조정량 })280
let 하한 = 반올림나눗셈(목표너비 * 최종비율M, 1000)281
if (가능너비 >= 하한) { return 0 }282
return CAP * B + 반올림나눗셈((하한 - 가능너비) * B, 목표너비) * 1000000283
}284
}285
if (원래너비 * 1000 < 목표너비 * 비율M) { return CAP * B + 반올림나눗셈((목표너비 - 원래너비) * B, 목표너비) * (if (모드 == 0) { 1000000 } else { 100000 }) }286
let 조정량 = 목표너비 - 원래너비287
if (조정량 <= 1) { return 0 }288
if (조정량 > 최대조정량) { return CAP * B + 반올림나눗셈((조정량 - 최대조정량) * B, 1000) }289
if (모드 == 0) {290
let 간격 = (0..<유효).filter((i: int) => U0020인가(텍스트들[i])).length291
if (간격 < 최소간격 || 간격 == 0) { return CAP * B }292
let 초과 = 조정량 - 간격 * 최대간격293
if (초과 > 간격) { return CAP * B + 반올림나눗셈(초과 * B, 간격) }294
} else {295
let 낱말간격 = (0..<유효).filter((i: int) => U0020인가(텍스트들[i])).length296
if (낱말간격 > 0) {297
let 초과 = 조정량 - 낱말간격 * 최대간격298
if (초과 > 낱말간격) { return CAP * B + 반올림나눗셈(초과 * B, 낱말간격) }299
return 0300
}301
let 간격 = CJK간격수(텍스트들, 0, 유효)302
if (간격 < 최소간격 || 간격 == 0) { return CAP * B }303
// 대표 CJK 진행은 단일 CJK 단위의 합과 개수로 구한다. 개수가 0이거나 진행이 1 이하면 None으로 보아 CAP를 준다.304
let 대표인덱스 = (0..<유효).filter((i: int) => 단일CJK인가(텍스트들[i]))305
let 대표합 = 대표인덱스.reduce(0, (합: int, i: int) => 합 + 진행[i])306
let 대표수 = 대표인덱스.length307
let 불량 = 대표인덱스.reduce(false, (발견: bool, i: int) => 발견 || 진행[i] <= 1)308
if (불량 || 대표수 == 0) { return CAP * B }309
let 초과 = 조정량 - 간격 * 최대간격310
let 비율R = 반올림나눗셈(조정량 * 대표수 * R, 간격 * 대표합)311
let 비율초과 = 비율R - 최대간격비율R312
if (초과 > 간격 || 비율초과 > 100000) {313
let 초과항 = if (초과 > 0) { 반올림나눗셈(초과 * B, 간격) } else { 0 }314
let 비율항 = if (비율초과 > 0) { 비율초과 * 100 } else { 0 }315
return CAP * B + 초과항 + 비율항316
}317
}318
0319
}321
// ── 한 줄 정렬벌점 · 후보 줄 [start, endExcl)의 정렬 벌점을 슬라이스로 계산 ──322
// 정렬모드가 0보다 작으면(없음) 0이다. 마지막 줄이어도 0이다(정렬벌점 자체가 마지막 줄에 0).323
function 줄정렬벌점(진행: Array<int>, 클러스터들: Array<string>, 시작: int, 끝: int, 목표너비: int,324
정렬모드: int, 최소간격: int, 비율M: int, 최대조정량: int, 최대간격: int,325
최대간격비율R: int, 마지막인가: bool, 최종비율M: int) -> int {326
if (정렬모드 < 0) { return 0 }327
if (마지막인가) { return 0 }328
let 줄진행 = (시작..<끝).map((u: int) => 진행[u])329
let 줄텍스트 = (시작..<끝).map((u: int) => 클러스터들[u])330
정렬벌점(줄진행, 줄텍스트, 목표너비, 최소간격, 비율M, 최대조정량, 최대간격, 최대간격비율R, 정렬모드, false, 최종비율M)331
}333
// ── 줄 목표너비 · 드롭캡 줄수 안에서는 인셋만큼 줄어든 목표를 쓴다 (drop-cap line bucket inset) ──334
// 기준 = if (시작 == 0) { 첫줄목표너비 } else { 목표너비 } (첫줄목표는 본문의 첫 단위에서 시작하는 줄에만)335
// 기준 - 드롭캡인셋 (인셋은 버킷 < 드롭캡줄수일 때만)336
// 즉 첫줄목표 선택은 단위 시작(시작==0)으로, 인셋은 줄버킷(버킷)으로 키잉한다. 드롭캡 OFF(드롭캡줄수 0)면337
// 인셋은 0이므로 기준 너비를 쓴다.338
function 줄목표너비(버킷: int, 시작: int, 목표너비: int, 첫줄목표너비: int, 드롭캡줄수: int, 드롭캡인셋: int) -> int {339
let 기준 = if (시작 == 0) { 첫줄목표너비 } else { 목표너비 }340
if (버킷 < 드롭캡줄수) { 기준 - 드롭캡인셋 } else { 기준 }341
}343
// ── 처리(스텝퍼 진입점) · 헤더와 단위를 파싱하고 최적분할 DP를 돌린 뒤 분할 계획을 직렬화한다 ──344
function 처리(입력: string) -> string {345
let 줄들 = 입력.split("\n")346
let 헤더 = 줄들[0].split(" ")347
let 목표너비 = 헤더[0].toInt() ?? 0348
let 첫줄목표너비_원 = 헤더[1].toInt() ?? 0349
let 드롭캡줄수 = 헤더[2].toInt() ?? 0350
let 드롭캡인셋 = 헤더[3].toInt() ?? 0351
let 정렬모드 = 헤더[4].toInt() ?? -1352
let 최소간격 = 헤더[5].toInt() ?? 1353
let 비율M = 헤더[6].toInt() ?? 0354
let 최대조정량 = 헤더[7].toInt() ?? 0355
let 최대간격 = 헤더[8].toInt() ?? 0356
let 최대간격비율R = 헤더[9].toInt() ?? 0357
let 최종비율M = if (헤더.length > 10) { 헤더[10].toInt() ?? 0 } else { 0 }358
// 시드 캡(seam caps). 목표너비는 [1, 23e9] 범위여야 한다. 벗어나면 OUT_OF_BOUNDS.359
if (목표너비 <= 0 || 목표너비 > 23000000000) { return "OUT_OF_BOUNDS" }360
let 첫줄목표너비 = if (첫줄목표너비_원 <= 0) { 목표너비 } else { 첫줄목표너비_원 }362
let mut 클러스터들: Array<string> = []363
let mut 진행: Array<int> = []364
for li in (1..<줄들.length) {365
let 부분들 = 줄들[li].split("\t")366
진행.push(부분들[0].toInt() ?? 0)367
클러스터들.push(if (부분들.length >= 2) { 부분들[1] } else { "" })368
}369
let 개수 = 클러스터들.length371
// 접두합(prefix sums). 너비와 글자수.372
let mut 너비접두 = [0]373
let mut 글자접두 = [0]374
for i in (0..<개수) {375
너비접두.push(너비접두[i] + 진행[i])376
글자접두.push(글자접두[i] + 클러스터들[i].scalars().length)377
}379
let 분할점 = 분할점생성(클러스터들)380
let 분할점단위 = 분할점.단위들381
let 분할점종류 = 분할점.종류들382
let 분할점수 = 분할점단위.length384
// ── 최적분할 2-D DP · (분할점, 버킷) 상태 ──385
// 드롭캡이 켜지면 한 줄의 인셋(따라서 목표너비, 따라서 비용)이 지금까지 방출한 줄 수(=버킷)에 따라 달라진다.386
// 그래서 같은 분할점에 줄 수가 다른 두 경로가 도달하면 둘은 서로 교환할 수 없다. 버킷을 DP의 두 번째 차원으로 둔다.387
// 버킷 = min(지금까지 방출한 줄 수, K), K = min(드롭캡줄수, 3). 버킷수 = K + 1.388
// 드롭캡 OFF면 버킷수 = 1.389
// 다음버킷 = min(이전버킷 + 1, 마지막버킷) (마지막 버킷에서 포화).390
// 2-D 상태는 평탄화(flatten)한다. 상태인덱스(ei, b) = ei * 버킷수 + b. 병렬 1-D 배열은 ei 오름차순으로,391
// 같은 ei 안에서는 버킷 오름차순으로 push된다. 각 상태는 (있음, 비용, 이전ei, 이전버킷, 줄비용)을 담는다.392
let 버킷수 = if (드롭캡줄수 <= 0 || 드롭캡인셋 <= 0) {393
1394
} else {395
(if (드롭캡줄수 < 3) { 드롭캡줄수 } else { 3 }) + 1396
}397
let 마지막버킷 = 버킷수 - 1399
// 상태[0][b]는 버킷 0만 존재하고(비용 0) 나머지 버킷은 부재다.400
let mut 상태들: Array<{ 있음: bool, 비용: int, 이전ei: int, 이전버킷: int, 줄나쁨: int }> = []401
for b0 in (0..<버킷수) {402
상태들.push({ 있음: b0 == 0, 비용: 0, 이전ei: 0, 이전버킷: 0, 줄나쁨: 0 })403
}405
for ei in (1..<분할점수) {406
let 끝단위 = 분할점단위[ei]407
let 끝종류 = 분할점종류[ei]408
// 전임자 창(predecessor window). 한 줄에 분할점이 80개를 넘게 들어갈 일은 없으므로 80개 이전의 분할점은409
// 후보에서 제외한다(O(n^2) 폭주 방지).410
let mut 이전시작 = if (ei > 80) { ei - 80 } else { 0 }411
let 넓은목표 = if (목표너비 > 첫줄목표너비) { 목표너비 } else { 첫줄목표너비 }412
while (이전시작 > 0 && 너비접두[끝단위] - 너비접두[분할점단위[이전시작 - 1]] <= 넓은목표 + 1) { 이전시작 -= 1 }413
let 마지막인가 = 끝단위 == 개수414
// 이 분할점에 도달하는 최적 상태를 다음버킷별로 모은다(최선[다음버킷]).415
let mut 최선들: Array<{ 있음: bool, 비용: int, 이전ei: int, 이전버킷: int, 줄나쁨: int }> = []416
for nb in (0..<버킷수) {417
최선들.push({ 있음: false, 비용: 0, 이전ei: 0, 이전버킷: 0, 줄나쁨: 0 })418
}420
for pi in (이전시작..<ei) {421
let 시작 = 분할점단위[pi]422
if (시작 < 끝단위) {423
let 너비 = 너비접두[끝단위] - 너비접두[시작]424
let mut 유효끝 = 끝단위425
while (유효끝 > 시작 && 낱말공백인가(클러스터들[유효끝 - 1])) { 유효끝 -= 1 }426
let 먹너비 = 너비접두[유효끝] - 너비접두[시작]427
for 이전버킷 in (0..<버킷수) {428
let 이전상태 = 상태들[pi * 버킷수 + 이전버킷]429
if (이전상태.있음) {430
// 새 줄은 인셋 목적상 이전버킷 번째 줄이다(버킷이 곧 인셋의 유효 줄 인덱스). 첫줄목표는 단위 시작(시작==0)으로 키잉한다.431
let 이줄목표 = 줄목표너비(이전버킷, 시작, 목표너비, 첫줄목표너비, 드롭캡줄수, 드롭캡인셋)432
if (!(먹너비 > 이줄목표 + 1 && 끝단위 > 시작 + 1)) {433
let 공백수 = (시작..<끝단위).filter((i: int) => 분할가능라틴공백인가(클러스터들[i])).length434
let 줄나쁨 = 나쁨도(너비, 이줄목표, 글자접두[끝단위] - 글자접두[시작], 공백수, 끝종류, 마지막인가)435
let 정렬 = 줄정렬벌점(진행, 클러스터들, 시작, 끝단위, 이줄목표, 정렬모드, 최소간격, 비율M,436
최대조정량, 최대간격, 최대간격비율R, 마지막인가, 최종비율M)437
let 줄비용 = 줄나쁨 + 정렬438
let 후보비용 = 이전상태.비용 + 줄비용439
let 다음버킷 = if (이전버킷 + 1 < 마지막버킷) { 이전버킷 + 1 } else { 마지막버킷 }440
// strict `<` keep-first. pi·버킷을 오름차순으로 도므로, 정확히 같은 i64 비용일 때는 첫(가장 낮은) 전임자가 이긴다.441
let 최선 = 최선들[다음버킷]442
if (!최선.있음 || 후보비용 < 최선.비용) {443
최선들[다음버킷] = { 있음: true, 비용: 후보비용, 이전ei: pi, 이전버킷: 이전버킷, 줄나쁨: 줄비용 }444
}445
}446
}447
}448
}449
}451
for wb in (0..<버킷수) {452
상태들.push(최선들[wb])453
}454
}456
let 마지막 = 분할점수 - 1457
// 종단 최소. 버킷을 가로질러 i64 strict `<` keep-first로 고르되, 가장 낮은 버킷이 먼저다. OFF면 버킷 0만 존재한다.458
let mut 종단버킷 = -1459
for tb in (0..<버킷수) {460
let 종단상태 = 상태들[마지막 * 버킷수 + tb]461
if (종단상태.있음) {462
if (종단버킷 < 0 || 종단상태.비용 < 상태들[마지막 * 버킷수 + 종단버킷].비용) {463
종단버킷 = tb464
}465
}466
}467
if (종단버킷 < 0) { return "NO_PLAN" }469
// 역추적(reversed 수집). (분할점, 버킷) 셀을 이전버킷을 따라 거꾸로 걸으며 줄들을 모은다.470
let mut 역줄들: Array<{ 시작: int, 끝: int, 줄나쁨: int }> = []471
let mut wi = 마지막472
let mut wbucket = 종단버킷473
while (wi > 0) {474
let 셀 = wi * 버킷수 + wbucket475
let 상태 = 상태들[셀]476
역줄들.push({ 시작: 분할점단위[상태.이전ei], 끝: 분할점단위[wi], 줄나쁨: 상태.줄나쁨 })477
let 다음wi = 상태.이전ei478
wbucket = 상태.이전버킷479
wi = 다음wi480
}481
let mut 출력 = ""482
let mut 총비용 = 0483
let mut k = 역줄들.length - 1484
while (k >= 0) {485
let 줄 = 역줄들[k]486
let 시작 = 줄.시작487
let 끝 = 줄.끝488
let 줄나쁨 = 줄.줄나쁨489
출력 = if (출력 == "") { "{시작} {끝} {줄나쁨}" } else { "{출력}\n{시작} {끝} {줄나쁨}" }490
총비용 += 줄나쁨491
k -= 1492
}493
"{출력}\nTOTAL {총비용}"494
}496
io.writeLine(처리(io.readStdin()))SHA256 23792cc631f76cffacc00cad8b312aeac7278a2e96b48c9da264f88a5b246bb3