Witajcie.
Ćwiczę się w algorytmice, wobec tego rozwiązuję przeszłe zadanie z Google Code Jam. Niestety, to co zakodziłem jest nazbyt wolne, by dać w ogóle wynik. Dlatego proszę o pomoc w ulepszeniu mojego rozwiązania (tzn. nie pragnę całkiem odmiennego podejścia, ciekawi mnie czy liczę coś w nadmiernych ilościach).
Zadanie - https://code.google.com/codejam/contest/6254486/dashboard#s=p2
Moje polskie skrótowe tłumaczenie:
Poprawnym ciągiem znaków jest ten, który spełnia poniższe warunki:
- każdy znak jest zerem lub jedynką
- pierwszy i ostatni znak jest jedynką
- dla liczb całkowitych 2 <= b <= 10 jeśli zinterpretujemy ciąg jako liczbę w systemie o podstawie b, to powstała liczba nie będzie pierwsza
Znajdź j ciągów znaków zadanej długości n, jako dowód poprawności dla każdej podstawy b podaj właściwy dzielnik
Są dwa przypadki testowe, n, j = 16, 50 oraz n, j = 32, 500. Mniejszy przechodzi bez większego problemu. Za to większy, cóż. Właśnie z nim mam problem. Mój kod wygląda tak:
#!/usr/bin/env python3
import sympy as sp # http://sympy.org
from sys import stderr
def nextnum(l):
'''
Generuje kolejne potencjalne ciągi
'''
for i in range(2**(l-2)):
yield '1' + bin(i)[2:].zfill(l-2) + '1'
primes = sp.primerange(2, 10**4)
def get_factor(s, b):
n = int(s, b)
# najpierw odsiej małe liczby pierwsze z dzielników
for x in primes:
if n%x == 0:
return x
# potem spróbuj efektywniejszej metody (dla większych liczb)
f = sp.pollard_rho(n)
if f != 1 and f != n:
return f
# jeśli się nie powiedzie, kontynuuj
for x in range(10**4, int(n**0.5)+1):
if n%x == 0:
return x
def main():
# liczba przypadków testowych
t = int(input())
for i in range(t):
n, j = [int(c) for c in input().split()]
print("Case #{}:".format(i+1))
g = nextnum(n)
while j:
s = next(g)
print(s, file=stderr) # dla oglądania postępu
n_in_b = [int(s, b) for b in range(2, 11)]
if all(not sp.primetest.isprime(n) for n in n_in_b):
# jeśli wszystkie są złożone,
# to znajdź najmiejszy dzielnik właściwy
l = [str(get_factor(s, b)) for b in range(2, 11)]
print(' '.join([s] + l))
j -= 1
if __name__ == '__main__':
main()