python - Kattis 的 D+J 编程挑战

Question

问题如下:

Dick is d=12 years old. When we say this, we mean that it is at least twelve and not yet thirteen years since Dick was born.

Dick and Jane have three pets: Spot the dog, Puff the Cat, and Yertle the Turtle. Spot was s years old when Puff was born; Puff was p years old when Yertle was born; Spot was yy years old when Yertle was born. The sum of Spot’s age, Puff’s age, and Yertle’s age equals the sum of Dick’s age (d) and Jane’s age (j). How old are Spot, Puff, and Yertle?

给定的输入是 s,p,y,j，所需的输出是:spot 的年龄、puff 的年龄和 yertle 的年龄。

我的解决方案如下:

import sys
import math

d = 12
for line in sys.stdin:
    line = [int(x) for x in line.strip("\n").split()]

    s = line[0]
    p = line[1]
    y = line[2]
    j = line[3]

    yertle = (d+j-y-p)/3.0
    difference = yertle - math.floor(yertle)
    if difference > 0.5:
        # for the 0.66666 cases
        spot = puff = int(math.ceil(yertle+p))
        yertle = int(math.floor(yertle))
    else:
        # for the 0.33333 cases
        yertle = int(math.floor(yertle))
        puff = yertle + p
        spot = d+j - puff - yertle

    print spot,puff,yertle

但在某些输入上它是不正确的，例如:s=5、p=5、y=10、j=10。因为对于这些规范，狗的实际年龄是:spot=12.333、puff=7.333、yertle=2.333，但因为我们正在进行整数除法，所以我们得到 12,7,2。然而，这些结果并不满足 $$spot + puff + yertle = dick + jane$$ 规则。有人对我在哪里犯了错误或者我应该如何处理/解决这个问题有其他想法吗？

附注link for problem source

Answer 1

不要使用浮点算术，使用整数。

让我们表示D+J = DJ，Spot的年龄S，Puff的年龄P，Yertle的年龄Y

Let's Spot 生日时间为零，因此 Puff 出生在区间 [s, s+1)，Yertle 出生在区间 [y, y+1) 。当前时间位于[S, S+1) 区间内。

如果我们查看时间线，我们可以看到

   S = y + Y
   or
   S = y + Y + 1
and 
   S = s + P
   or
   S = s + P + 1

年龄总和是

 DJ = S + Y + P = S + S - y + S - s - (0, 1, 2)

其中 (0,1,2) 是可能的附录

 3 * S = DJ + y + s + (0,1,2)

我们可以看到右侧部分必须能被3整除，因此接下来的计算取决于值

 M =  (DJ + y + s) modulo 3

case M = 0: (5 5 10 9)
     S = (DJ + y + s) / 3 = (21 + 15) / 3 = 12
     P = S - s = 12 - 5 = 7
     Y = S - y = 12 - 10 = 2

case M = 1: (5 5 10 10)
     here we should add 2 to make sum 37 divisible by 3
     S = (DJ + y + s + 2) / 3 = (22 + 15 + 2) / 3 = 13
     P = S - s  - 1 = 13 - 5 = 1 =  7
     Y = S - y  - 1 = 13 - 10 - 1 = 2

now more complex case M = 2 (5 5 11 10):
    here we should add 1 to make sum 38 divisible by 3 
    and solve - where use 1 - for P or for Y calculation?
    We can determine this evaluating s/p/y relation:
    if y = s + p + 1 then use 1 for Puff's age else for Yertle
    (because Puff's fraction is larger then Yertle's fraction, 
    she was born in the later year period)
    here 11 = 5 + 5 + 1, so
    S = (22 + 16 + 1) / 3 = 13
    Y = S - y = 13 - 11 = 2
    P = S - s - 1 = 13 - 5 - 1 = 7