Oros Ioana Diana at 16:27, 18 May 2024

2024-05-18T16:27:36Z

Oros Ioana Diana at 16:24, 18 May 2024

2024-05-18T16:24:10Z

← Older revision		Revision as of 16:24, 18 May 2024
Line 44:		Line 44:
	: -1		: -1
	: 3		: 3
	<br>		<br>d
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
Line 110:		Line 110:

	</syntaxhighlight>		</syntaxhighlight>

	~~== Explicatie ==~~
	~~Din 7 putem să ajungem la 6, iar mai apoi la 3.~~
	~~<br>~~
	~~Din 8 putem să ajungem la 4.~~
	~~<br>~~
	~~Din 10 putem să ajungem la 8, iar mai apoi la 4.~~
	~~<br>~~
	~~Numărul 3 se află deja în mulțimea D.~~
	~~<br>~~
	~~De la 64 vom ajunge la 32, la 16, la 8, iar mai apoi la 4.~~

Oros Ioana Diana: Pagină nouă: == 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...

2024-01-08T19:09:07Z

Pagină nouă: == 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...

New page

== 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
 
== Rezolvare ==
<syntaxhighlight lang="python" line>
#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>

== Explicatie ==
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.

4045 - Wl - Revision history

Oros Ioana Diana at 16:27, 18 May 2024

Oros Ioana Diana at 16:24, 18 May 2024