d053: 10970 - Big Chocolate
Tags :
Accepted rate : 3177人/3249人 ( 98% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-10-19 15:31

Content

 Mohammad 最近去瑞士。因為他很愛他的朋友們,他決定要買巧克力請他們,但是由於這麼高級的巧克力很貴 (你也知道Mohammad 有點小氣!),他只買得起一片巧克力,很大的一片巧克力 (大到圖 1 也看不到全部) 來請他的朋友們。現在,他要給他的朋友每人一小塊,因為他相信人生而平等,他要每一小塊都一樣大。

這巧克力是由 M×N 個單位大小的正方形所構成的 M×N 矩形。你也可以假設 Mohammad 剛好有 M×N 個朋友等著吃巧克力。

切割巧克力時,Mohammad 可以以垂直或水平的方向沿著小方塊間的溝槽切割。切割開來的每一塊也要分別單獨地以同樣的方式來處理,直到他有 M×N 塊單位大小的巧克力為止。不幸的是,由於他很懶,只要能完成工作,他希望切越少刀越好。

你的目標就是要告訴他要把這些巧克力方塊全切開至少需要幾刀。 

圖1. Mohammad 的巧克力 

Input
輸入有好幾筆測試資料。輸入的每一行有兩個整數 1≤M≤300 表示巧克力有幾列,1≤N≤300 表示巧克力有幾欄。重覆處理輸入直到檔案結束。
Output
針對每行輸入,你的程式要輸出一行,在該行中含有要把整個巧克力切成單位大小方塊所需要的最少刀數。
Sample Input
2 2
1 1
1 5
Sample Output
3
0
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
一星秒殺題
Tags:
出處:
UVa10970 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
17624
hansen033 (HC)
d053
公式推導
99 2019-04-27 23:15
17031 d053
公式推導
408 2019-03-01 17:51
16493
Justinkuo0818 (justin)
d053
AC正確公式
266 2019-01-06 12:32
16414
ufve0704 (這也是我的line ID 喔)
d053
公式
175 2018-12-29 20:02