slow.monster

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"
21import std.io
23let R = 100000000 // 1e8 비율 스케일 (ratio scale)
24let B = 1000000 // 1e6 나쁨도/벌점 스케일 (badness/penalty scale)
25let CAP = 25000 // 정렬 벌점 상한 (justification penalty cap)
27// ── 공용 정수 보조 (shared integer helpers) ──
28function 반올림나눗셈(분자: int, 분모: int) -> int { // round-half-up, 음이 아닌 값만
29 let 몫 = 분자 / 분모
30 let 나머지 = 분자 % 분모
31 if (나머지 >= (분모 + 1) / 2) { 몫 + 1 } else { 몫 }
33function 절댓값(값: int) -> int { if (값 < 0) { -값 } else { 값 } }
34function 첫코드포인트(텍스트: string) -> int { 텍스트.codePointAt(0) ?? -1 }
35function 단일스칼라(텍스트: string) -> bool { 텍스트.scalars().length == 1 }
37// ── 금칙분류 · 글자류 판정 (char-class predicates over a single code point) ──
38function 한글분할문자인가(코드: 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 확장 A
43 || (코드 >= 19968 && 코드 <= 40959) // U+4E00..U+9FFF CJK 통합
44 || (코드 >= 63744 && 코드 <= 64255) // U+F900..U+FAFF CJK 호환
45 || 코드 == 65292 || 코드 == 12289 || 코드 == 12290 || 코드 == 65307 || 코드 == 65306 // , 、 。 ; :
47function 줄머리금지인가(코드: 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 || 코드 == 8250
55function 줄끝금지인가(코드: int) -> bool {
56 코드 == 40 || 코드 == 91 || 코드 == 123 // ( [ {
57 || 코드 == 12300 || 코드 == 12302 || 코드 == 12298 || 코드 == 12296 // 「 『 《 〈
58 || 코드 == 8220 || 코드 == 8216 // “ ‘
59 || 코드 == 65288 || 코드 == 12304 || 코드 == 65339 || 코드 == 65371 || 코드 == 171 || 코드 == 8249
62// ── 클러스터 스칼라 전체/일부 판정 (all/any over a cluster's scalars; 빈 문자열 -> all=true, any=false) ──
63function 모두한글분할(텍스트: string) -> bool {
64 텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 한글분할문자인가(첫코드포인트(스칼라)))
66function 모두줄머리금지(텍스트: string) -> bool {
67 텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 줄머리금지인가(첫코드포인트(스칼라)))
69function 일부줄머리금지(텍스트: string) -> bool {
70 텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄머리금지인가(첫코드포인트(스칼라)))
72function 일부줄끝금지(텍스트: string) -> bool {
73 텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄끝금지인가(첫코드포인트(스칼라)))
76// ── 단어 전체 판정 (whole-string predicates; single-scalar equality) ──
77function 분할가능라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }
78function 라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }
79function 비분할공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }
80function 라틴붙임표인가(텍스트: string) -> bool {
81 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 45 || 첫코드포인트(텍스트) == 8208 || 첫코드포인트(텍스트) == 8209 || 첫코드포인트(텍스트) == 8211)
83function 쉼표마침표콜론인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 44 || 첫코드포인트(텍스트) == 46 || 첫코드포인트(텍스트) == 58) }
84function 아스키숫자인가(텍스트: string) -> bool { 텍스트.byteLength() == 1 && 첫코드포인트(텍스트) >= 48 && 첫코드포인트(텍스트) <= 57 }
86// ── 이웃 클러스터 가드 (Option<string> neighbor guards) ──
87function 다음은라틴공백아님(다음: Option<string>) -> bool {
88 match (다음) {
89 case Some(텍스트) => !라틴공백인가(텍스트)
90 case None() => true
91 }
93function 다음은줄머리금지없음(다음: Option<string>) -> bool {
94 match (다음) {
95 case Some(텍스트) => !일부줄머리금지(텍스트)
96 case None() => true
97 }
99function 다음은라틴공백(다음: Option<string>) -> bool {
100 match (다음) {
101 case Some(텍스트) => 라틴공백인가(텍스트)
102 case None() => false
103 }
105function 다음은일부줄머리금지(다음: Option<string>) -> bool {
106 match (다음) {
107 case Some(텍스트) => 일부줄머리금지(텍스트)
108 case None() => false
109 }
111function 옵션아스키숫자인가(옵션: Option<string>) -> bool {
112 match (옵션) {
113 case Some(텍스트) => 아스키숫자인가(텍스트)
114 case None() => false
115 }
118function 숫자구분자인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {
119 쉼표마침표콜론인가(현재) && 옵션아스키숫자인가(이전) && 옵션아스키숫자인가(다음)
121function 닫음부호허용인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {
122 모두줄머리금지(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !숫자구분자인가(현재, 이전, 다음)
124function 한글분할허용인가(현재: string, 다음: Option<string>) -> bool {
125 모두한글분할(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !일부줄끝금지(현재)
128// ── 분할점생성 · 단위 끝과 분할종류 (break opportunities, 인덱스 0에 센티넬) ──
129// 분할종류 토큰은 ASCII 유지(입출력 토큰).
130// 모든 후보에 적용하는 원문 문맥 금칙. 공백 뒤의 부호도 앞 낱말에 붙인다.
131function 공백코드인가(코드: int) -> bool {
132 (코드 >= 9 && 코드 <= 13) || 코드 == 32 || 코드 == 133 || 코드 == 160 || 코드 == 5760
133 || (코드 >= 8192 && 코드 <= 8202) || 코드 == 8232 || 코드 == 8233 || 코드 == 8239 || 코드 == 8287 || 코드 == 12288
135function 여는직선따옴표인가(글자들: Array<string>, 위치: int) -> bool {
136 let 코드 = 첫코드포인트(글자들[위치])
137 if (코드 != 34 && 코드 != 39) { return false }
138 if (위치 == 0) { return true }
139 let 앞 = 첫코드포인트(글자들[위치 - 1])
140 공백코드인가(앞) || 줄끝금지인가(앞)
142function 라틴낱말코드인가(코드: int) -> bool {
143 (코드 >= 65 && 코드 <= 90) || (코드 >= 97 && 코드 <= 122)
144 || (코드 >= 192 && 코드 <= 591) || (코드 >= 7680 && 코드 <= 7935)
146function 문맥경계허용인가(글자들: Array<string>, 경계: int) -> bool {
147 let mut 왼쪽 = 경계 - 1
148 while (왼쪽 >= 0) {
149 if (!공백코드인가(첫코드포인트(글자들[왼쪽]))) { break }
150 왼쪽 -= 1
151 }
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 오른쪽 += 1
163 }
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 true
176function 분할점생성(클러스터들: Array<string>) -> { 단위들: Array<int>, 종류들: Array<string> } {
177 let 개수 = 클러스터들.length
178 let mut 전체텍스트 = ""
179 for 단위 in (클러스터들) { 전체텍스트 = 전체텍스트 + 단위 }
180 let 글자들 = 전체텍스트.scalars()
181 let mut 글자끝 = 0
182 let mut 단위들 = [0]
183 let mut 종류들 = ["forced_end"]
184 for i in (0..<개수) {
185 let 단위 = 클러스터들[i]
186 let 단위끝 = i + 1
187 글자끝 += 단위.scalars().length
188 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 { 단위들: 단위들, 종류들: 종류들 }
208// ── 나쁨도 · 고정소수 줄 나쁨도 (fixed-point line badness, justification=None 경로) ──
209function 나쁨도(너비: 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 * 비례R
216 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 * B
227 기본B
230// ── 정렬벌점 · CJK 글자사이 정렬 보조 (CJK justification helpers) ──
231function 낱말공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160) }
232function U0020인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }
233function CJK정렬문자인가(코드: int) -> bool {
234 (코드 >= 4352 && 코드 <= 4607) || (코드 >= 12592 && 코드 <= 12687) || (코드 >= 13312 && 코드 <= 19903)
235 || (코드 >= 19968 && 코드 <= 40959) || (코드 >= 44032 && 코드 <= 55203) || (코드 >= 63744 && 코드 <= 64255)
237function 정렬부호코드인가(코드: int) -> bool {
238 코드 == 46 || 코드 == 44 || 코드 == 59 || 코드 == 58 || 코드 == 33 || 코드 == 63 || 코드 == 34 || 코드 == 39
239 || 코드 == 40 || 코드 == 41 || 코드 == 91 || 코드 == 93 || 코드 == 123 || 코드 == 125
240 || 코드 == 12290 || 코드 == 12289 || 코드 == 65292 || 코드 == 65294
241 || 코드 == 12300 || 코드 == 12301 || 코드 == 12302 || 코드 == 12303 || 코드 == 12298 || 코드 == 12299 || 코드 == 12296 || 코드 == 12297
243function 단일CJK인가(텍스트: string) -> bool { 단일스칼라(텍스트) && CJK정렬문자인가(첫코드포인트(텍스트)) }
244function 정렬부호단위인가(텍스트: string) -> bool {
245 텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 정렬부호코드인가(첫코드포인트(스칼라)))
247function CJK간격후보인가(왼쪽: string, 오른쪽: string) -> bool { 단일CJK인가(왼쪽) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽) }
248function 한글공백간격후보인가(왼쪽: string, 공백: string, 오른쪽: string) -> bool {
249 단일CJK인가(왼쪽) && 낱말공백인가(공백) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽)
251function CJK간격수(텍스트들: Array<string>, 시작: int, 끝: int) -> int {
252 let mut 간격 = 0
253 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 간격
265// ── 정렬벌점 · 라틴 낱말간격과 CJK 글자사이 통합 (full justification penalty, Latin + CJK) ──
266function 정렬벌점(진행: Array<int>, 텍스트들: Array<string>, 목표너비: int, 최소간격: int, 비율M: int,
267 최대조정량: int, 최대간격: int, 최대간격비율R: int, 모드: int, 마지막인가: bool, 최종비율M: int) -> int {
268 if (마지막인가) { return 0 }
269 let 개수 = 텍스트들.length
270 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])).length
277 if (간격 > 0 || 모드 == 0) {
278 let 간격조정량 = 간격 * 최대간격
279 let 가능너비 = 원래너비 + (if (최대조정량 < 간격조정량) { 최대조정량 } else { 간격조정량 })
280 let 하한 = 반올림나눗셈(목표너비 * 최종비율M, 1000)
281 if (가능너비 >= 하한) { return 0 }
282 return CAP * B + 반올림나눗셈((하한 - 가능너비) * B, 목표너비) * 1000000
283 }
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])).length
291 if (간격 < 최소간격 || 간격 == 0) { return CAP * B }
292 let 초과 = 조정량 - 간격 * 최대간격
293 if (초과 > 간격) { return CAP * B + 반올림나눗셈(초과 * B, 간격) }
294 } else {
295 let 낱말간격 = (0..<유효).filter((i: int) => U0020인가(텍스트들[i])).length
296 if (낱말간격 > 0) {
297 let 초과 = 조정량 - 낱말간격 * 최대간격
298 if (초과 > 낱말간격) { return CAP * B + 반올림나눗셈(초과 * B, 낱말간격) }
299 return 0
300 }
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 대표수 = 대표인덱스.length
307 let 불량 = 대표인덱스.reduce(false, (발견: bool, i: int) => 발견 || 진행[i] <= 1)
308 if (불량 || 대표수 == 0) { return CAP * B }
309 let 초과 = 조정량 - 간격 * 최대간격
310 let 비율R = 반올림나눗셈(조정량 * 대표수 * R, 간격 * 대표합)
311 let 비율초과 = 비율R - 최대간격비율R
312 if (초과 > 간격 || 비율초과 > 100000) {
313 let 초과항 = if (초과 > 0) { 반올림나눗셈(초과 * B, 간격) } else { 0 }
314 let 비율항 = if (비율초과 > 0) { 비율초과 * 100 } else { 0 }
315 return CAP * B + 초과항 + 비율항
316 }
317 }
318 0
321// ── 한 줄 정렬벌점 · 후보 줄 [start, endExcl)의 정렬 벌점을 슬라이스로 계산 ──
322// 정렬모드가 0보다 작으면(없음) 0이다. 마지막 줄이어도 0이다(정렬벌점 자체가 마지막 줄에 0).
323function 줄정렬벌점(진행: 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)
333// ── 줄 목표너비 · 드롭캡 줄수 안에서는 인셋만큼 줄어든 목표를 쓴다 (drop-cap line bucket inset) ──
334// 기준 = if (시작 == 0) { 첫줄목표너비 } else { 목표너비 } (첫줄목표는 본문의 첫 단위에서 시작하는 줄에만)
335// 기준 - 드롭캡인셋 (인셋은 버킷 < 드롭캡줄수일 때만)
336// 즉 첫줄목표 선택은 단위 시작(시작==0)으로, 인셋은 줄버킷(버킷)으로 키잉한다. 드롭캡 OFF(드롭캡줄수 0)면
337// 인셋은 0이므로 기준 너비를 쓴다.
338function 줄목표너비(버킷: int, 시작: int, 목표너비: int, 첫줄목표너비: int, 드롭캡줄수: int, 드롭캡인셋: int) -> int {
339 let 기준 = if (시작 == 0) { 첫줄목표너비 } else { 목표너비 }
340 if (버킷 < 드롭캡줄수) { 기준 - 드롭캡인셋 } else { 기준 }
343// ── 처리(스텝퍼 진입점) · 헤더와 단위를 파싱하고 최적분할 DP를 돌린 뒤 분할 계획을 직렬화한다 ──
344function 처리(입력: string) -> string {
345 let 줄들 = 입력.split("\n")
346 let 헤더 = 줄들[0].split(" ")
347 let 목표너비 = 헤더[0].toInt() ?? 0
348 let 첫줄목표너비_원 = 헤더[1].toInt() ?? 0
349 let 드롭캡줄수 = 헤더[2].toInt() ?? 0
350 let 드롭캡인셋 = 헤더[3].toInt() ?? 0
351 let 정렬모드 = 헤더[4].toInt() ?? -1
352 let 최소간격 = 헤더[5].toInt() ?? 1
353 let 비율M = 헤더[6].toInt() ?? 0
354 let 최대조정량 = 헤더[7].toInt() ?? 0
355 let 최대간격 = 헤더[8].toInt() ?? 0
356 let 최대간격비율R = 헤더[9].toInt() ?? 0
357 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 개수 = 클러스터들.length
371 // 접두합(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 분할점수 = 분할점단위.length
384 // ── 최적분할 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 1
394 } else {
395 (if (드롭캡줄수 < 3) { 드롭캡줄수 } else { 3 }) + 1
396 }
397 let 마지막버킷 = 버킷수 - 1
399 // 상태[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])).length
434 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 마지막 = 분할점수 - 1
457 // 종단 최소. 버킷을 가로질러 i64 strict `<` keep-first로 고르되, 가장 낮은 버킷이 먼저다. OFF면 버킷 0만 존재한다.
458 let mut 종단버킷 = -1
459 for tb in (0..<버킷수) {
460 let 종단상태 = 상태들[마지막 * 버킷수 + tb]
461 if (종단상태.있음) {
462 if (종단버킷 < 0 || 종단상태.비용 < 상태들[마지막 * 버킷수 + 종단버킷].비용) {
463 종단버킷 = tb
464 }
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 * 버킷수 + wbucket
475 let 상태 = 상태들[셀]
476 역줄들.push({ 시작: 분할점단위[상태.이전ei], 끝: 분할점단위[wi], 줄나쁨: 상태.줄나쁨 })
477 let 다음wi = 상태.이전ei
478 wbucket = 상태.이전버킷
479 wi = 다음wi
480 }
481 let mut 출력 = ""
482 let mut 총비용 = 0
483 let mut k = 역줄들.length - 1
484 while (k >= 0) {
485 let 줄 = 역줄들[k]
486 let 시작 = 줄.시작
487 let 끝 = 줄.끝
488 let 줄나쁨 = 줄.줄나쁨
489 출력 = if (출력 == "") { "{시작} {끝} {줄나쁨}" } else { "{출력}\n{시작} {끝} {줄나쁨}" }
490 총비용 += 줄나쁨
491 k -= 1
492 }
493 "{출력}\nTOTAL {총비용}"
496io.writeLine(처리(io.readStdin()))

SHA256 23792cc631f76cffacc00cad8b312aeac7278a2e96b48c9da264f88a5b246bb3