1537 . 木板裁切問題
TopCoder
Tags
Description
最近隔壁農場的 Farmer John 遇到了一個麻煩──他的柵欄又被奶牛 Bessie 給撞壞了，而他的柵欄形狀十分特殊，
是由一個多邊形(Polygon)組成的，且每個角的角度皆不同。令他頭疼的是，被撞壞的地方不只一處，且有的地方是多邊形柵欄的邊被撞壞，
而有的地方卻是角被撞壞，偏偏賣木材的商人又很坑錢，故意不將木材切成一單位一單位賣，逼他一定要買長度為特定單位的木材(長度分別為 3, 5, 7, 11, ...)，
而他卻又沒有鋸子可以切割木材，於是他不知道該用最少多少的錢才能買到足夠的木材完全覆蓋住損壞的地方(木材可以重複覆蓋同一個地方)，
對於有點窮的 Farmer John 來說，這真的是讓他著急死了!!
然而，讓人感到欣慰的是，這個問題過了不久馬上就被隔壁的隔壁農場的 Farmer Jiang 以優秀的計算技巧解決了，
而聽到了這個消息的你，除了替 Farmer John 感到高興外，也對出手相救的 Farmer Jiang 感到敬佩，但同時間，
你突然想到，如果當初 Farmer John 有鋸子，或許就不會這麼麻煩了，但，那麼長度為 L 的木材究竟有幾種裁切的方法呢?
(注意: 因為技術問題，你只能裁切成整數單位且最小 1 單位的木材)
Input Format
第一行有一個整數 N (1≦N≦100)，代表共有 N 條木材要被考慮。
對於每筆測試資料都有一行，包含著一個正整數 L (2≦L≦25)，代表木材的長度，
請將此長度 L 的木材做裁切並輸出其結果。
Output Format
對於第 Pi 塊木板，
第 1 行請輸出 "Plank Pi:"(不含"") 代表這是第 Pi 塊木板。
第 2+k 行請輸出第 k 種裁切的方案，假設長度 L 的木板可以切成 n 塊長度為 Sj(1≦j≦n) 的小木板，請輸出 S1, S2, S3, ..., Sn ( S1≦S2≦...≦Sn )
(注意: 若有多種方案，請將 S1 較小的方案先輸出，若兩方案 S1 一樣，則將 S2 較小的方案先輸出，以此類推...)
Sample Input 1
3
5
Sample Output 1
1, 1, 1
1, 2
Plank 2:
1, 1, 1, 1, 1
1, 1, 1, 2
1, 1, 3
1, 2, 2
1, 4
2, 3
Hints
Problem Source
原TIOJ1537 / Problem Setter: Skyly
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |