eval.in

Paste #554365

Python — CPython 3.4.1, pasted 3 years ago (json)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59``` ```def vampireFangs(vampire): def recurse(vampire, prevA, prevB, counts, divider): if divider < 1: # end of recursion # Product of fangs must equal original number and fangs must not # both end with a 0. if prevA * prevB == vampire and prevA % 10 + prevB % 10 > 0: # Solution found return [prevA, prevB] # It's not a solution return False # Get left-most digits (multiple of 2) of potential vampire number v = vampire//divider # Shift decimal digits of partial fangs to the left to make room for # the next digits prevA *= 10 prevB *= 10 # Calculate the min/max A digit that can potentially contribute to a # solution minDigA = v // (prevB + 10) - prevA maxDigA = 9 if prevB == 0 else (v + 1) // prevB - prevA if maxDigA > 9: maxDigA = 9 for digA in range(minDigA, maxDigA+1): if not counts[digA]: continue # this digit is not available fangA = prevA + digA counts[digA] -= 1 # Calculate the min/max B digit that can potentially contribute # to a solution minDigB = v // (fangA + 1) - prevB maxDigB = 9 if fangA == 0 else (v + 1) // fangA - prevB # Don't search mirrored A-B digits when both fangs are equal # until now. if prevA == prevB and digA > minDigB: minDigB = digA if maxDigB > 9: maxDigB = 9 for digB in range(minDigB, maxDigB+1): if not counts[digB]: continue # this digit is not available fangB = prevB + digB counts[digB] -= 1 # Recurse by considering the next two digits of the potential # vampire number, for finding the next digits to append to # both partial fangs. result = recurse(vampire, fangA, fangB, counts, divider // 100); # When solution is found: stop searching & exit search tree. if result: return result # solution found # Restore counts counts[digB] += 1 counts[digA] += 1 return False digits = str(vampire) if vampire < 0 or len(digits) % 2: return False counts = [0,0,0,0,0,0,0,0,0,0] for d in map(int, digits): counts[d] += 1 return recurse(vampire, 0, 0, counts, 10**(len(digits)-2)) vampire = int(input("Enter number: ")) print(vampire) result = vampireFangs(vampire) print(result) ```

Program Output

```Enter number: 67094221760561813454
[7654411206, 8765432109]
```

OK (0.236 sec real, 0.249 sec wall, 8 MB, 30 syscalls)