[UVa] 10257 - Dick and Jane

題目網址: http://goo.gl/upjREL

題意:
(from luckycat)


解 法:
參考 http://nc-oj.logdown.com/posts/2011/10/15/acm-10257。
假設烏龜(C)的年紀為 x 歲，而再假設 C = x + dx, 0 <= dx < 1，C 是烏龜當前實際的"實數"年齡，x 為 C 的整數部分， dx 為 C 的小數部分。
以此類推，烏龜出生時，貓(B) p 歲，所以 B = x + dx + p +dp, 0 <= dp < 1。
烏龜出生時，狗(A) y 歲，所以 A = x + dx + y + dy, 0 <= dy < 1。
由以上兩行可知，貓當前的年齡為 B' = x + p + (dx+dp), 0 <= dx+dp < 2，所以貓的年齡為 B' = x + p + { 0, 1 }，也就是可能為 x + p 或 x + p + 1。
而狗當前的年齡為 A' = x + y + (dx+dy), 0 <= dx+dy < 2 ，所以狗的年齡為 A' = x + y + { 0, 1 }。

而題目說 Dick + Jane 的"年齡" 等於 狗 + 貓 + 烏龜 的"年齡"。
也就是 D + J = ( x+y+{0,1} ) + (x+p+{0,1}) + x
=> D + J - y - p = 3*x + { 0, 1, 2 }
當 (D+J-y-p)%3 = 0 代表剛好整除，也就是 狗與貓的年齡 依序為 x+y, x+p 都不用加 1；而當 (D+J-y-p)%3 = 2 代表需要補 2 才能整除，也就是 狗與貓的年齡都需加 1，也就是 x+y+1, x+p+1；最後需要討論的是當 (D+J-y-p)%3 = 1，這時會不知道  是狗的年齡需要加 1 還是貓的年齡需要加 1。

我們知道狗實際的年齡為 A = x + dx + y + dy = x + dx + p + dp + s + ds，
而推出 y + dy = s + ds + p + dp，所以取整數部分來看的話，
因為 0 <= dy < 1, 0 <= (ds+dp) < 2，則得出 y = s + p + { 0, 1 }

接著 假設 若是當狗的年紀需要加 1 ，也就是 當我們取 A = x + dx + y + dy 的整數部分時，
答案是 A' = x+y+1，因而 1 <= dx+dy < 2
而此時 貓的年紀試不能加 1 的，也就是 B' = x+p，因而 0 <= dx+dp < 1
以上我們能代到 A 中，A = x + dx + p + dp + s + ds = x + p + s + (dx+dp) + ds，
因為 0 <= (dx+dp) + ds < 2，所以 A' = x+p+s+{0,1} = x+y+1，
且因為 x+p+s = x+y+1 不可能成立(因為 y = s+p+{0,1})，所以 x+p+s+1 = x+y+1會成立，
所以此時 y = p+s，也就是當 y = p+s 的時候，狗的年紀需要加 1 ，而貓不用。
# 另一種情況 貓加 1、狗不用，也是類似上面的方法 類推
# 就可以討論出 當(D+J-y-p)%3 = 1 兩種情況的條件！

TAG: Math,

注意:

程式碼: