a128: Sharing Chocolate
Tags :
Accepted rate : 20人/49人 ( 41% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-03-04 18:36

Content

 

你手上有一塊x*y大小的長方形巧克力,分給你的N個朋友,而你的每個朋友想吃的大小也都不一樣.


你的巧克力是由多個方形小塊所並排組成,每一排與每一列之間都有巧克力製造商幫你劃好的分割線.

你能沿著這些行列的分割線將巧克力一分為二,而你決定重複利用這些分割線來做出最漂亮的切割.

如此一來你的每一個朋友將可獲得大小適當且由完整的小塊巧克力組成的大塊矩形巧克力.


請寫一個程式計算是否存在一種可行的分割方法.

 

圖9的大巧克力包含了3x4塊小塊巧克力,你能用3次的分割將它切成向右圖的3塊長方形巧克力(即第一個範例測資的一種分割方案)

 

Input
本題包含多組測試資料,表示多塊未分割的大塊巧克力,每筆測資第一行包含一個整數n表示你需要切割的份數.
緊接著一行包含兩個整數x,y表整塊巧克力的長寬大小.下一行包含n個正整數表每個欲切割出來小塊巧克力的面積大小.

讀到n=0表測資結束.
Output
對於每組測資若存在一種分割方案請輸出"Case #: Yes"若無法方割出符合大小的巧克力請輸出"Case #: No".#字號表測資的序號.
Sample Input #1
4 
3 4 
6 3 2 1 
2 
2 3 
1 5 
0
Sample Output #1
Case 1: Yes
Case 2: No
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (1%): 1.0s , <1M
公開 測資點#1 (99%): 1.0s , <1M
Hint :

这题与原题不尽相同。

约定:
1≤N≤15
1≤x*y≤10000

而且最后必须把巧克力分完。

以上由liouzhou_101注。

Tags:
出處:
ACM ICPC World Finals [管理者:
pcsh710742 (ms0472904)
]


ID User Problem Subject Hit Post Date
19731
tsyr (tsyr)
a128
531 2019-10-24 17:35