4045 - Wl

Cerința

Kida a descoperit un nou joc, prin care pornind de la un număr oarecare poate ajunge la alte numere prin niște pași simpli: dacă la un moment de timp, T, Kida are numărul W, atunci la momentul de timp T + 1 ea poate să ajungă la orice alt număr L dacă:

• L < W
• L este divizibil cu W - L
• W este divizibil cu W - L
• 2 * L ≥ W

Kida are o mulțime de N numere, notată cu D. Acum, ea își pune Q întrebări de tipul: Dacă aș porni la momentul de timp T = 0 și aș avea numărul x, care este momentul de timp minim la care aș putea sa ajung la un număr din mulțimea D folosind regulile jocului descris mai sus? Dacă nu se poate ajunge la niciun număr din mulțimea D, atunci Kida va considera că răspunsul este -1.

Date de intrare

Prima linie a input-ului conține numărul N. Pe a doua linie se află N numere naturale, reprezentând elementele mulțimii D. A treia linie conține numărul Q. Ultima linie va conțin cele Q numere, reprezentând întrebările pe care și le pune Kida.

Date de ieșire

Prima linie a input-ului conține numărul N. Pe a doua linie se află N numere naturale, reprezentând elementele mulțimii D. A treia linie conține numărul Q. Ultima linie va conțin cele Q numere, reprezentând întrebările pe care și le pune Kida.

Restricții și precizări

• 1 ≤ N ≤ 10 000
• 1 ≤ D[i] ≤ 100 000
• 0 ≤ x ≤ 100 000
• 1 ≤ Q ≤ 100 000
• Subtask #1: Răspunsul pentru fiecare întrebare este cel mult 1 – 10 puncte
• Subtask #2: Răspunsul pentru fiecare întrebare este cel mult 2 – alte 20 de puncte
• Subtask #3: Fără restricții – alte 70 de puncte

Exemplul 1

Intrare

2

3 4

5

7 8 10 3 64

Ieșire

2

1

2

0

4

Exemplul 2

Intrare

3

5 6 7

4

2 8 11 14

Iesire

3

1

-1

3

d

Rezolvare

<syntaxhighlight lang="python" line>

1. 4045 - Wl

def find_divisors(n):

   divisors = set()

   # Adăugăm divizorii primi ai lui n în mulțime
   i = 2
   while i * i <= n:
       if n % i == 0:
           divisors.add(i)
           while n % i == 0:
               n //= i
       i += 1

   if n > 1:
       divisors.add(n)

   return divisors

def min_time_to_reach_d(x, divisors_d):

   time = 0

   # Pentru fiecare divizor prim al lui x, calculăm timpul minim
   for divisor in divisors_d:
       while x % divisor == 0 and (x // divisor) % 2 == 0:
           x //= divisor
           time += 1

   if x > 1:
       time += 1

   return time

def main():

   # Citirea datelor de intrare
   N = int(input())
   D = list(map(int, input().split()))
   Q = int(input())
   questions = list(map(int, input().split()))

   # Verificarea restricțiilor
   if not (1 <= N <= 10000 and all(1 <= d <= 100000 for d in D) and 1 <= Q <= 100000 and all(0 <= x <= 100000 for x in questions)):
       print("false")
       return

   # Găsirea divizorilor primi ai elementelor din D
   divisors_D = set()
   for number in D:
       divisors_D.update(find_divisors(number))

   # Răspuns la fiecare întrebare
   for question in questions:
       # Calculăm timpul minim pentru a ajunge la un număr din D
       time_to_reach_D = min_time_to_reach_d(question, divisors_D)

       if time_to_reach_D == 0:
           print(-1)
       else:
           print(time_to_reach_D)

if __name__ == "__main__":

   main()

</syntaxhighlight>