1
樹如下:距離失敗
(1,1)
/ \
(2,1) (1,2)
/\ /\
(3,1)(2,3) (3,2)(1,3)
and onward
根是(1,1),在樹中的所有值都是元組。
Where (x,y) is an element of the tree:
The leftChild will be (x+y,y)
The rightChild will be (x,x+y)
我正在構建一個函數,它可以找到根(1,1)的距離。我無法從頭開始構建樹,因爲這太費時。
我發現距離正在搜索的元組有1個距離,我們必須用最小值減去最大值。我們可以倒退。
1 2
(3,2)->(1,2)->(1,1)
(3,2)->(3-2,2) = (1,2)->(1,2-1) = (1,1)
given this is always true:
if x > y:
newtuple = (x-y,y)
distance += 1
else if y > x:
newtuple = (x,y-x)
distance += 1
然而,因爲可能的測試案例甚至可能達到x = 10^50,這甚至太慢了。 (x,y)=(1,1),所以我發現正式地找到x與y的減法量,反之亦然,以使得x> y變爲y < x,反之亦然。因此X - Y(一定的時間,比如說z)將使x小於y ... X - Y * z = y 通過代數找到z ... z =(YX)/( -Y)
這是到目前爲止我的代碼:
from decimal import Decimal
import math
def answer(M,F):
M = int(M)
F = int(F)
i = 0
while True:
if M == 1 and F == 1:
return str(i)
if M > F:
x = math.ceil((F-M)/(-F))
M -= F*x
elif F > M:
x = math.ceil((M-F)/(-M))
F -= M*x
else:
if F == M and F != 1:
return "impossible"
i += x
if M < 1 or F < 1:
return "impossible"
return str(i)
而且它不是通過某種未知的測試案例,但通過了所有的測試情況下,我能想到的。我可能會失敗哪些測試用例?我的代碼在哪裏錯了?
p.s.使用十進制模塊,只是從代碼中刪除,使更多的可讀性。
你能提供一個原始問題的鏈接嗎? – Tempux
@ sudomakeinstall2 http://pastebin.com/tJ2p3YN7 –
是否來自在線法官,我可以測試我的實施情況? – Tempux