列印工廠 (APCS 2025-11 高級)
2.0s 256M一部印表機要完成 \(n\) 個工作。工作 \(i\) 不得早於 \(s_i\) 開始,需連續執行 \(t_i\) 單位時間,且必須在 \(d_i\) 以前或當時完成。你可以安排工作的順序及開始時間,工作不能重疊。求最大的非負整數 \(g\),使每兩個相鄰工作之間都至少休息 \(g\) 單位時間。第一件之前及最後一件之後的空檔不算。
輸入格式
第一行為 \(n\),接著 \(n\) 行各有 \(s_i,d_i,t_i\)。
輸出格式
輸出最大的整數 \(g\)。
資料範圍
\(2\le n\le8\);\(0\le s_i<d_i\le1000\);\(1\le t_i\le d_i-s_i\)。保證 \(g=0\) 時存在合法排程。
評分說明
- 30 分:\(n\le3\)。
- 70 分:無額外限制。
每筆計分測資各占 5 分。
範例輸入 1
3
1 9 3
3 20 4
4 15 2
範例輸出 1
5
範例輸入 2
3
1 4 2
0 6 3
2 8 1
範例輸出 2
0
題目來源
APCS 2025 年 11 月高級實作題第 2 題。
官方未公布題本,題敘參考 ZeroJudge r627「列印工廠」 上的重建版整理,細節可能與正式試題有出入。