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

Exemplu:

Intrare

2
3 4
5
7 8 10 3 64

Ieșire

2
1
2
0
4

Rezolvare

<syntaxhighlight lang="python" line="1"> from collections import deque

INF = float('inf') MAX_VAL = 100001

def check_restrictions(n, initial_values, queries):

   if not (1 <= n <= 100):
       print("Datele nu corespund restrictiilor impuse")
       return False
   if not all(1 <= x <= 100000 for x in initial_values):
       print("Datele nu corespund restrictiilor impuse")
       return False
   if not (1 <= len(queries) <= 100):
       print("Datele nu corespund restrictiilor impuse")
       return False
   if not all(1 <= x <= 100000 for x in queries):
       print("Datele nu corespund restrictiilor impuse")
       return False
   return True

def lee(n, initial_values, queries):

   minim = [INF] * (MAX_VAL + 1)
   q = deque(initial_values)

   for x in initial_values:
       minim[x] = 0

   while q:
       x = q.popleft()
       for d in range(1, int(x**0.5) + 1):
           if x % d == 0:
               if x + d <= MAX_VAL and minim[x + d] > minim[x] + 1:
                   minim[x + d] = minim[x] + 1
                   q.append(x + d)
               if x + (x // d) <= MAX_VAL and minim[x + (x // d)] > minim[x] + 1:
                   minim[x + (x // d)] = minim[x] + 1
                   q.append(x + (x // d))

   results = []
   for x in queries:
       if minim[x] == INF:
           results.append(-1)
       else:
           results.append(minim[x])
   
   return results

def main():

   n = int(input())
   initial_values = list(map(int, input().split()))
   q = int(input())
   queries = list(map(int, input().split()))

   if check_restrictions(n, initial_values, queries):
       results = lee(n, initial_values, queries)
       for res in results:
           print(res)

if __name__ == "__main__":

   main()

</syntaxhighlight>