4045 - Wl
Cerința[edit | edit source]
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 cuW - L
W
este divizibil cuW - 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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
- 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:[edit | edit source]
Intrare
2 3 4 5 7 8 10 3 64
Ieșire
2 1 2 0 4
Rezolvare[edit | edit source]
<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>