# PBinfo #4045 – wl – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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
Programul va afișa Q linii, linia i reprezentând răspunsul pentru a i-a întrebare.

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
Explicație
Din 7 putem să ajungem la 6, iar mai apoi la 3.
Din 8 putem să ajungem la 4.
Din 10 putem să ajungem la 8, iar mai apoi la 4.
Numărul 3 se află deja în mulțimea D.
De la 64 vom ajunge la 32, la 16, la 8, iar mai apoi la 4.

## Cod sursă C++

```cpp
// Soluție Bogdan Vlad-Mihai, clasa a XII-a, Liceul Teoretic "Aurel Vlaicu" Orăștie
#include <bits/stdc++.h>
using namespace std;
const int LIMIT = 100 * 1000;
const int INF = 1000 * 1000 * 1000;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n; cin >> n;
  queue<int> q;
  vector<int> minTime(LIMIT + 1, INF);
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    q.push(x);
    minTime[x] = 0;
  }
  while ((int)q.size() > 0) {
    int val = q.front();
    q.pop();
    for (int d = 1; d * d <= val; d += 1 + val % 2)
      if (val % d == 0)
        for (int add : {d, val / d})
          if (add + val <= LIMIT && minTime[add + val] > minTime[val] + 1) {
            minTime[val + add] = minTime[val] + 1;
            q.push(val + add);
          }
  }
  int m; cin >> m;
  for (int mm = 0; mm < m; mm++) {
    int x; cin >> x;
    if (minTime[x] == INF)
      cout << "-1\n";
    else
      cout << minTime[x] << "\n";
  }
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4045)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4045/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4045/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)