Sovago Rares-Andrei: Pagină nouă: ==Cerința== A venit primăvara și a început sezonul de concursuri pentru porumbei. La un concurs fiecare participant trebuie să trimită câte doi porumbei. Fiecare porumbel are ataşat pe picior un inel care conţine un număr. Într-o noapte, înainte de un concurs, Tavi, un mare pasionat de porumbei, are un vis în care o zână bună îi spune codurile celor doi porumbei pe care, dacă îi va trimite, va câştiga concursul. Cum Tavi este un mare uituc, dimineaţa î...

2023-04-15T16:03:12Z

Pagină nouă: ==Cerința== A venit primăvara și a început sezonul de concursuri pentru porumbei. La un concurs fiecare participant trebuie să trimită câte doi porumbei. Fiecare porumbel are ataşat pe picior un inel care conţine un număr. Într-o noapte, înainte de un concurs, Tavi, un mare pasionat de porumbei, are un vis în care o zână bună îi spune codurile celor doi porumbei pe care, dacă îi va trimite, va câştiga concursul. Cum Tavi este un mare uituc, dimineaţa î...

New page

==Cerința==

A venit primăvara și a început sezonul de concursuri pentru porumbei. La un concurs fiecare participant trebuie să trimită câte doi porumbei. Fiecare porumbel are ataşat pe picior un inel care conţine un număr. Într-o noapte, înainte de un concurs, Tavi, un mare pasionat de porumbei, are un vis în care o zână bună îi spune codurile celor doi porumbei pe care, dacă îi va trimite, va câştiga concursul. Cum Tavi este un mare uituc, dimineaţa îşi mai aminteşte doar prima parte a visului în care zâna îi spune 2 numere a şi n. El îşi mai aminteşte că numerele X şi Y (pe care le-a uitat) de pe inelele porumbeilor sunt puse în aşa fel încât rezultatul aX – aY să fie divizibil cu n. X și Y sunt numerele de pe inelele porumbeilor pe care îi va trimite la concurs.

Dându-se doua numere a şi n, să se afişeze cele două numere X şi Y cu Y minim.
== Date de intrare ==

Fișerul '''porumbei.in''' are pe prima linie numerele a și n, separate printr-un spațiu.

== Date de ieșire ==

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul porumbei.out conține două numere naturale distincte, în ordine crescătoare și separate printr-un spațiu, ce reprezintă valorile minime ale lui X și Y astfel încât rezultatul a^X – a^Y să fie divizibil cu n.

În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".
== Restricţii şi precizări ==
*2 ≤ n ≤ 2.000.000
* 2 ≤ a ≤ 2.000.000
* 0 ≤ X < Y

== Exemple ==
===Exemplul 1===
; ''porumbei.in''
:4 10
; ''ecran''
:Datele sunt introduse corect.
; ''porumbei.out''
:1 3

===Exemplul 2===
; ''porumbei.in''
:4 7
; ''ecran''
:Datele sunt introduse corect.
; ''porumbei.out''
:0 4

===Exemplul 3===
; ''porumbei.in''
:3 5000000
; ''ecran''
:Datele nu corespund restricțiilor impuse.
; ''porumbei.out''
:
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 12059 - porumbei
def validate_input(m, n, a):
"""
Validates the input values for the pigeonhole principle algorithm.

Args:
m (int): The value of the base.
n (int): The value of the modulus.
a (int): The starting value.

Raises:
ValueError: If any of the input values are invalid.

Returns:
None.
"""
if not (2 <= n <= 2000000):
raise ValueError("Invalid value for n!")
if not (2 <= a <= 2000000):
raise ValueError("Invalid value for a!")

def pigeonhole_principle(m, n):
"""
Implements the pigeonhole principle algorithm for finding the smallest non-negative integers p and q such that
m^p ≡ m^q (mod n), where 2 <= m, n <= 2,000,000.

Args:
m (int): The value of the base.
n (int): The value of the modulus.

Returns:
A tuple containing the values of p and q.
"""
v = bytearray(262145) # The vector used to mark the found remainders
v[1 // 8] = v[1 // 8] | (1 << (1 % 8)) # Mark the remainder 1 as found

a = 1
r = 1
while True:
r = (r * m) % n
if v[r // 8] & (1 << (r % 8)) != 0: # If the bit for the remainder is already set
q = a # Then there was a previous remainder equal to r, so we stop
break
else:
v[r // 8] = v[r // 8] | (1 << (r % 8))
a += 1

if r == 1:
p = 0
else:
r1 = 1
for i in range(1, q):
r1 = (r1 * m) % n
if r1 == r:
p = i
break

return (p, q)

if __name__ == "__main__":
try:
with open("porumbei.in", "r") as f, open("porumbei.out", "w") as g:
m, n = map(int, f.readline().strip().split())
a = 2 # Set a to the minimum valid value
validate_input(m, n, a) # Validate the input values
print("Datele sunt introduse corect.")

p, q = pigeonhole_principle(m, n) # Run the algorithm

g.write(f"{p} {q}\n") # Write the output to file
except ValueError as e:
print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

==Explicatie==

validate_input(m, n, a)
Această funcție validează valorile de intrare m, n, și a pentru a se asigura că îndeplinesc restricțiile impuse. Mai exact, funcția verifică dacă n și a sunt între 2 și 2,000,000 inclusiv, iar dacă nu, se ridică o excepție ValueError cu un mesaj corespunzător. Dacă valorile de intrare sunt valabile, funcția nu returnează nimic.

pigeonhole_principle(m, n)
Această funcție implementează algoritmul principiului cutiei poștale pentru a găsi cele mai mici numere naturale pozitive p și q astfel încât m^p ≡ m^q (mod n). În primul rând, se inițializează un vector de byte-uri v care va fi folosit pentru a marca resturile găsite. Se marchează restul 1 ca fiind găsit, deoarece (m^0) % n = 1. Apoi, se calculează restul r = (m^1) % n și se marchează ca fiind găsit în vectorul v. Se crește contorul a și se calculează următorul rest r = (m^a) % n. Acest lucru continuă până când se găsește un rest care a mai fost întâlnit anterior. Atunci, se oprește și se returnează perechea (p, q) de valori, unde p este valoarea minimă a lui a astfel încât m^p ≡ r (mod n) și q este valoarea minimă a lui a astfel încât m^q ≡ r (mod n) și q > p.

if __name__ == "__main__":
Această condiție verifică dacă script-ul este rulat ca program principal sau este importat ca modul în alt script Python. În acest caz, script-ul este rulat ca program principal. Acest bloc conține citirea datelor de intrare din fișier, apelarea funcției validate_input() pentru a valida datele de intrare și apelarea funcției pigeonhole_principle() pentru a rula algoritmul. În cazul în care datele nu sunt valide, se va ridica o excepție ValueError care va fi prinsă în blocul except.

try-except
Aceasta este o structură de control care permite prinderea și gestionarea excepțiilor în Python. În acest cod, folosim try-except pentru a prinde excepțiile ValueError care sunt ridicate de funcția validate_input(). Dacă o excepție ValueError este prinsă, se afișează un mesaj corespunzător.

2059 - porumbei - Revision history