Hello, the following code always gives me RE on the judge (during the first
test set):
from math import sqrt, ceil, log
possible = [(0,1),(1,0),(0,-1),(-1,0)]
reflected = {
"E" : "W",
"W" : "E",
"S" : "N",
"N" : "S",
}
def evenReachable(Xi, Yi, Xf, Yf):
if ((Xi + Yi) == 0) or ((Xf + Yf) == 0):
return True
else:
return not ((Xf+Yf) % 2 == 0 and (Xi+Yi) % 2 == 0)
def distance(Xi, Yi, Xf, Yf):
return sqrt((Xf-Xi)**2+(Yf-Yi)**2)
def getCase(Xi, Yi, Xn, Yn):
if Xn > Xi:
return 'E'
if Xn < Xi:
return 'W'
if Yn > Yi:
return 'N'
if Yn < Yi:
return 'S'
def reflect(solution):
return ''.join([reflected[c] for c in solution])
def recursiveJumps(lowestJumps, maxJ, Xf, Yf, Xi, Yi, totalD, jumpN,
oldResult = ""):
requiredD = distance(Xi, Yi, Xf, Yf) + totalD
result = oldResult
if (jumpN > maxJ) or (jumpN > lowestJumps) or not evenReachable(Xf, Yf,
Xi, Yi):
return ("IMPOSSIBLE", float("inf"))
if (Xf == Xi and Yf == Yi):
# print("goal!")
return (result, totalD)
bestResult = None
for i,j in possible:
Xn = Xi+i*2**(jumpN-1) if jumpN-1 >= 0 else Xi
Yn = Yi+j*2**(jumpN-1) if jumpN-1 >= 0 else Yi
newD = distance(Xi,Yi, Xn, Yn) + totalD
if (newD <= requiredD):
newResult = result + getCase(Xi, Yi, Xn, Yn)
(newResult, newD) = recursiveJumps(lowestJumps, maxJ, Xf, Yf, Xn
, Yn, newD, jumpN+1, newResult)
if (newD >= requiredD) and newResult != "IMPOSSIBLE" :
bestResult = (newResult, newD)
lowestJumps = jumpN + 1
return bestResult if bestResult is not None else ("IMPOSSIBLE", float(
"inf"))
def findJumps(Xf, Yf, Xi, Yi, totalD, jumpN, solutions):
key = "{}_{}".format(Xf, Yf)
keyR = "{}_{}".format(-Xf, -Yf)
if key in solutions:
return solutions.get(key)
elif keyR in solutions:
solutions[key] = reflect(solutions[keyR])
return solutions.get(key)
else:
maxJ = ceil(log(distance(Xi, Yi, Xf, Yf))/log(2)+1) if distance(Xi,
Yi, Xf, Yf) > 0 else 1
lowestJumps = float("inf")
(result, d) = recursiveJumps(lowestJumps, maxJ + 1, Xf, Yf, Xi, Yi,
totalD, jumpN)
solutions["{}_{}".format(Xf, Yf)] = result
return result
if __name__ == "__main__":
T = int(input())
solutions = dict()
for i in range(1, T+1):
[Xf, Yf] = map(lambda i: int(i), input().split())
result = findJumps(Xf, Yf, 0, 0, 0, 1, solutions)
print("Case #{}: {}".format(i, result))
Likewise, this version, doesn't (I changed it to the other one due to LTE
on the second test):
from math import sqrt, ceil, log
MAX_SIZE = 10**4
possible = [(0,-1),(-1,0),(0,1),(1,0)]
def evenReachable(Xi, Yi, Xf, Yf):
if (Xi + Yi) == 0 or (Xf + Yf) == 0:
return True
else:
return not ((Xf+Yf) % 2 == 0 and (Xi+Yi) % 2 == 0)
def distance(Xi, Yi, Xf, Yf):
return sqrt((Xf-Xi)**2+(Yf-Yi)**2)
def getCase(Xi, Yi, Xn, Yn):
if Xn > Xi:
return 'E'
if Xn < Xi:
return 'W'
if Yn > Yi:
return 'N'
if Yn < Yi:
return 'S'
return ""
def recursiveJumps(maxJ, Xf, Yf, Xi, Yi, totalD, jumpN, covered, oldResults
= []):
requiredD = distance(Xi, Yi, Xf, Yf) + totalD
result = oldResults[-1] if len(oldResults) else ""
if (jumpN > maxJ) or evenReachable(Xf, Yf, Xi, Yi) == 0:
return ("IMPOSSIBLE", float("inf"))
if (Xf == Xi and Yf == Yi):
# print("goal!")
return (result, totalD)
possibleResults = []
for i,j in possible:
Xn = Xi+i*2**(jumpN-1) if jumpN-1 >= 0 else Xi
Yn = Yi+j*2**(jumpN-1) if jumpN-1 >= 0 else Yi
newD = distance(Xi,Yi, Xn, Yn) + totalD
if (newD <= requiredD):
newResult = result + getCase(Xi, Yi, Xn, Yn)
newResult = oldResults[0:-1]+[newResult]
(newResult, newD) = recursiveJumps(maxJ, Xf, Yf, Xn, Yn, newD,
jumpN+1, covered + [(Xn, Yn)], newResult)
if (newD >= requiredD) and newResult != "IMPOSSIBLE":
possibleResults.append((newResult, newD))
if not len(possibleResults):
return ("IMPOSSIBLE", float("inf"))
else:
possibleResults.sort(key = lambda x: len(x[0]))
return possibleResults[0]
def findJumps(Xf, Yf, Xi, Yi, totalD, jumpN):
maxJ = ceil(log(distance(Xi, Yi, Xf, Yf))/log(2)+1) if distance(Xi, Yi,
Xf, Yf) > 0 else 0
(result, d) = recursiveJumps(maxJ + 1, Xf, Yf, Xi, Yi, totalD, jumpN, [(
0,0)])
return result
if __name__ == "__main__":
T = int(input())
for i in range(1, T+1):
[Xf, Yf] = map(lambda i: int(i), input().split())
result = findJumps(Xf, Yf, 0, 0, 0, 1)
print("Case #{}: {}".format(i, result))
Do you have any idea of what might be wrong? Thanks a lot!
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/71c308e7-de70-4027-8538-dd407a55df22%40googlegroups.com.
