来自 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$$ 规则。有没有人对我在哪里犯了错误或者我应该如何 approached/solved 有其他想法？

P.S。 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

来自 Kattis 的 D+J 编程挑战

The D+J programming challenge from Kattis

python

algorithm

math

equation-solving