Bitnami MediaWiki - User contributions [en]

27930

2024-01-16T15:48:26Z

Cata: Pagină nouă: '''27930 (Nicolae Mușuroia) ''' : ''Fie'' <math>z_1, z_2</math> ''respectiv'' <math>z_3</math>, ''afixele vârfurilor triunghiului'' <math>A_1A_2A_3</math>, ''înscris în cercul'' <math>C(0,1)</math>. ''Arătați că triunghiul'' <math>A_1A_2A_3</math> ''este echilateral dacă și numai dacă'' <math>(z_1+z_2)(z_2+z_3)(z_3+z_1) \not= 0</math> ''și'' <math>\frac{1}{z_1+z_2} + \frac{1}{z_2+z_3} + \frac{1}{z_3+z_1} = 0</math>. '''Soluție.''' Dacă <math>A_1A...

'''27930 (Nicolae Mușuroia) '''
 
 
: ''Fie'' <math>z_1, z_2</math> ''respectiv'' <math>z_3</math>, ''afixele vârfurilor triunghiului'' <math>A_1A_2A_3</math>, ''înscris în cercul'' <math>C(0,1)</math>. ''Arătați că triunghiul'' <math>A_1A_2A_3</math> ''este echilateral dacă și numai dacă'' <math>(z_1+z_2)(z_2+z_3)(z_3+z_1) \not= 0</math> ''și'' <math>\frac{1}{z_1+z_2} + \frac{1}{z_2+z_3} + \frac{1}{z_3+z_1} = 0</math>.

'''Soluție.''' Dacă <math>A_1A_2A_3</math> este triunghi echilateral, afixele punctelor <math> A_1, A_2, A_3</math> sunt <math>z_1, \epsilon z_1</math> și <math> \epsilon ^2 z_1</math>, unde <math>\epsilon \in \mathbb{C} </math> astfel încât <math> \epsilon ^2 + \epsilon + 1 = 0</math>, iar relația din enunț se verifică prin calcul elementar.
: Reciproc, condiția din enunț se scrie echivalent
<math display="block>(z_1+z_2)(z_2+z_3) + (z_2+z_3)(z_3+z_1) + (z_3+z_1)(z_1+z_2) = 0,</math>

iar după calcule se rescrie <math>(z_1+z_2+z_3)^2 = -(z_1z_2+z_2z_3+z_3z_1)</math>.
: Întrucât <math>|z_1| = |z_2| = |z_3| = 1</math>, deducem că
<math display="block"> \overline{z_1+z_2+z_3} = \frac{1}{z_1} + \frac{1}{z_2} + \frac{1}{z_3} = \frac{z_1z_2+z_2z_3+z_3z_1}{z_1z_2z_3} = -\frac{(z_1+z_2+z_3)^2}{z_1z_2z_3}.</math>
: Trecând la module, rezultă că <math>|z_1+z_2+z_3| = |z_1+z_2+z_3|^2</math>. Întrucât ortocentrul <math>H</math> al triunghiului <math>A_1A_2A_3</math> are afixul <math>h = z_1+z_2+z_3</math>, obținem <math>|h| \in \{0,1\}</math>.
: Dacă <math>|h| = 1</math>, atunci <math> H \in C(0,1)</math>. Rezultă că triunghiul <math>A_1A_2A_3</math> este dreptunghic și <math>z_1+z_2 = 0</math> sau <math>z_2+z_3 = 0</math> sau <math>z_3+z_1 = 0</math>, fals.
: Așadar, <math>|h| = 0</math>, deci <math> H = O</math>, adică triunghiul <math>A_1A_2A_3</math> este echilateral.

Gazeta Matematică

2024-01-16T15:05:21Z

Cata:

Această pagină conține o listă cu numerele revistei ''[https://gmb.ssmr.ro/ Gazeta Matematică]'' care conțin articole/probleme cu autori membri ai [https://ssmr.cunbm.utcluj.ro/ Filialei Maramureș] a [https://ssmr.ro/ Societății de Științe Matematice din România].
{| class="wikitable mw-collapsible"
|+
!Anul
!Numărul
!Numărul problemei
!Clasa
!Domeniu
|-
|rowspan="13" |2022
|rowspan="3"|1
| [[28247]]
|11
|Matrice
|-
| [[28250]]
|12
|integrala Riemann
|-
| [[28251]]
|12
|integrala Riemann
|-
|2
| [[S:L22.58]]
|10
| ecuație cu logaritmi
|-
|4 - [[Gazeta Matematică nr 4 2022|link]]
| [[28315]]
|10
|numere complexe
|-
|5
| [[28338]]
|10
|numere complexe
afixe
|-
|6-7-8
| [[28354]]
|9
|vectori
|-
|rowspan="4" |10 - [[Gazeta Matematică nr 10 2022|link]]
| [[28437]]
|11
|șir recurent
|-
|[[E:16379]]
|5
|numere naturale
|-
|[[E:16380]]
|5
|puteri
|-
|[[E:16382]]
|5
|puteri
|-
|rowspan="2"|11
| [[E:16407]]
|5
|cub perfect
|
|-
| [[28450]]
|9
|progresii aritmetice
|-
|rowspan = "7" |2021
|rowspan = "3" |6-7-8 - [[Gazeta Matematică nr 6-7-8 din 2021|link]]
|[[E:15990]]
|5
|numere naturale
|-
| [[E:15991]]
|5
|numere naturale
|-
| [[E:15992]]
|5
|numere naturale
|-
|rowspan= "3" | 11
|[[28203]]
|12
|funcție primitivabilă
|-
|[[S:L21.287]]
|9
|puteri
|-
|[[S:E21.313]]
|8
|ecuație
|-
|rowspan= "1" | 12
|[[28208]]
|9
|vectori
|-
|rowspan ="5"|2020
|rowspan ="3"| 4 - [[Gazeta Matematică nr 4 2020|link]]
|[[15698|E:15698]]
|6
|pătrate perfecte
|-
|[[E:15694]]
|5
|teorema împărțirii cu rest
|-
|[[E:15695]]
|5
|numere naturale
|-
|5
|[[E:15714]]
|6
|divizibilitate
probabilitate
|-
|11
|[[27930]]
|
|
|-
|rowspan="3" |2018
|rowspan="3" |4 - [[Gazeta Matematică nr 4 2018|link]]
| [[S:E18.128]]
|
|
|-
|[[S:E18.131]]
|
|
|-
| [[S:E18.131]]
|
|
|-
|2017
|6-7-8
|[[27401]]
|10
|inegalitate
|-
|rowspan="10" |2015
|rowspan="2"|1
|[[27024]]
|12
|
|-
|[[27020]]
|10
|coeficienți binomiali
|-
|2 - [[Gazeta Matematică nr 2 2015|link]]
|[[27036]]
|11
|ecuații funcționale
|-
|3 - [[Gazeta Matematică nr 2 2015|link]]
|[[27024]]
|12
|ecuații funcționale
|-
|rowspan="6"|9
|[[E:14892]]
|8
|patrulater inscriptibil
|-
|[[S:E15.208]]
|5
|sumă de numere consecutive
|-
|[[S:E15.239]]
|8
|Teorema lui Pitagora
|-
|[[S:L15.236]]
|12
|funcție primitivabilă
|-
|[[S:L15.231]]
|12
|limita unui șir
|-
|[[S:L15.228]]
|11
|limita unui șir
|-
|-
|2014
|1
|[[14682]]
|6
|Geometrie
|-
|rowspan="2"| 2013
|rowspan="2"|1
|[[26713]]
|11
|șiruri, limită
|-
|E:[[14440]]
|5
|pătrat perfect
|-
|rowspan="4"| 2012
|rowspan="2"|4
|[[E:14336]]
|
|ecuație funcțională
|-
|[[E:14331]]
| 7 & 8
|numere prime
|-
|rowspan="2"|9 - [[Gazeta Matematică nr 9 2012|link]]
|E:[[14380]]
|5
|numere naturale
|-
|[[14383|E:14383]]
|6
|cmmdc & cmmmc
|-
|rowspan="2"| 2011
|rowspan="2"|7-8-9 - [[Gazeta Matematică nr 789 2011|link]]
|[[E:14223]]
|7
|rezolvarea triunghiului
|-
|[[E:14228]]
|7
|radicali
|}

2001 - Huge Control

2023-05-14T14:34:27Z

Cata:

==Cerința==
Cifra de control a unui număr se obţine efectuând suma cifrelor sale, apoi suma cifrelor acestei sume etc. până se obţine o sumă formată dintr-o singură cifră. De exemplu, cifra de control a numărului 713 este 2. (7 + 1 + 3 = 11, 1 + 1 = 2).

Un număr de tip Huge este un număr natural de maxim 1.000.000 de cifre.

În fișierul hugecontrol.in se găsește memorat un număr N, de tip Huge. Calculati și afișati cifra de control a numărului.

==Date de intrare==
Programul citește din fișierul de intrare hugecontrol.in numărul N, de tip Huge.

==Date de ieșire==
Programul va afișa în fișierul de ieșire hugecontrol.out numărul digit, reprezentând cifra de control a lui N, alături de un mesaj de validare a datelor introduse ("Input valid" sau "Input invalid" după caz).

==Restricții și precizări==
N este un număr cu proprietăți caracteristice tipului Huge.
==Exemplu==
; Intrare
: 713
; Ieșire
: Input valid
: 2
==Explicație==
7 + 1 + 3 = 11, 1 + 1 = 2

==Rezolvare==
<syntaxhighlight lang="python">
def is_valid_number(n):
return n.isdigit() and len(n) <= 1000000

def compute_control_digit(n):
nr = 0

for c in n:
nr = nr * 10 + int(c)
nr %= 9

return 9 if nr == 0 else nr

if __name__ == "__main__":
with open("hugecontrol.in", "r") as fin, open("hugecontrol.out", "w") as fout:
n = fin.readline().strip()

if not is_valid_number(n):
print("Input invalid")
return
else:
print("Input valid")

control_digit = compute_control_digit(n)
fout.write(str(control_digit))

</syntaxhighlight>

==Explicație cod==

Aceste funcții aparțin unui program care primește un număr mare și verifică dacă este valid, apoi calculează și scrie într-un fișier cifra de control a numărului dat.

`is_valid_number(n)` este o funcție care primește un șir de caractere `n` și returnează `True` dacă șirul este format din cifre și are lungimea mai mică sau egală cu un milion, altfel returnează `False`. Această funcție este utilizată pentru a verifica dacă numărul de intrare este valid.

`compute_control_digit(n)` este o funcție care primește un șir de caractere `n` și calculează cifra de control a numărului dat. Algoritmul pentru a calcula cifra de control este următorul:

# Se pornește cu valoarea 0 pentru variabila `nr`.
# Se parcurge fiecare caracter din șirul de intrare `n`.
# Pentru fiecare caracter, se multiplică `nr` cu 10 și se adaugă valoarea numerică a caracterului.
# Se face modulo 9 pentru a reduce `nr` la un număr între 0 și 8.
# Când toți caracterele sunt procesate, se returnează 9 dacă `nr` este egal cu 0, altfel se returnează valoarea din `nr`.

În codul principal, `__name__ == "__main__"` asigură faptul că blocul de cod din interiorul lui este executat numai atunci când fișierul este rulat ca un script și nu ca modul importat.

În interiorul blocului principal, fișierul "hugecontrol.in" este deschis și citit, iar primul rând este citit ca șirul de intrare `n`. Apoi, se verifică dacă numărul este valid folosind `is_valid_number(n)`. Dacă numărul nu este valid, se afișează mesajul "Input invalid" și programul se termină. Altfel, se afișează mesajul "Input valid" și se calculează cifra de control folosind `compute_control_digit(n)`. Această cifră de control este scrisă în fișierul "hugecontrol.out" folosind `fout.write(str(control_digit))`.

2553 - Josephus

2023-05-14T14:33:06Z

Cata:

==Cerința==
Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!

Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.

Josephus ar fi preferat să se predea. Pe ce poziție ar fi trebuit să se afle soldatul pentru a putea realiza acest lucru?

==Date de intrare==
Se va citi un singur număr natural nenul, n.

==Date de ieșire==
Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață, alături de un mesaj de validare a datelor introduse ("Input valid"; se afișează "n trebuie să fie între i și 10^18" în caz contrar).

==Restricții și precizări==
* 1 ≤ n ≤ 1018;
* Se garantează că există o soluție pentru oricare n;
==Exemplu==
; Intrare
: 41
; Ieșire
: Input valid
: 19
==Explicație==
1 ⇒ 2 
3 ⇒ 4 
… 
39 ⇒ 40 
41 ⇒ 1 
3 ⇒ 5 
… 
39 ⇒ 41 
3 ⇒ 7 
11 ⇒ 15 
……… 
19 ⇒ 35 

==Rezolvare==
<syntaxhighlight lang="python">
def calculate_exponent(n):
exponent = 0
save_n = n
while save_n != 1:
save_n //= 2
exponent += 1
return exponent

def is_power_of_two(n):
exponent = calculate_exponent(n)
return (1 << exponent) == n

def calculate_result(n):
exponent = calculate_exponent(n)
if is_power_of_two(n):
return 1
else:
return ((n - (1 << exponent)) << 1) + 1

def validate_n(n):
if not 1 <= n <= 10**18:
raise ValueError("n trebuie să fie între i și 10^18")
else:
print("Input valid")

if __name__ == "__main__":
n = int(input())
validate_n(n)
print(calculate_result(n))

</syntaxhighlight>

==Explicație cod==
Acest program implementează trei funcții care lucrează împreună pentru a verifica dacă un număr întreg n este o putere a lui 2 și pentru a calcula un rezultat bazat pe n.

Funcția "calculate_exponent" primește un număr întreg n și calculează exponentul său în baza 2. Exponentul este calculat prin împărțirea repetată a lui n la 2 până când n ajunge la valoarea 1, numărul de împărțiri fiind exponentul.

Funcția "is_power_of_two" primește un număr întreg n și verifică dacă este o putere a lui 2, comparându-l cu 2 ridicat la exponentul calculat în funcția anterioară.

Funcția "calculate_result" primește un număr întreg n și calculează rezultatul bazat pe aceasta. Dacă n este o putere a lui 2, rezultatul va fi 1, altfel va fi calculat după o formulă dată.

Funcția "validate_n" primește un număr întreg n și verifică dacă se încadrează între 1 și 10^18 inclusiv. Dacă n nu se încadrează în această plajă, funcția va arunca o excepție "ValueError".

În metoda "main", se primește un număr întreg n de la utilizator, se validează și se calculează și se afișează rezultatul apelând funcția "calculate_result".

3223 - Scobitoare

2023-05-14T14:32:27Z

Cata:

==Cerința==
Lui Ion îi plac scobitorile. Norocul său a fost că black friday tocmai a venit și a cumpărat un număr infinit de scobitori (să zicem că o duce destul de bine). Ținând cont că are extrem de multe scobitori, el a vrut să se joace cu ele, așa că a creat un joc.

La primul pas, el pune o singură scobitoare în mijlocul mesei. Începând cu al doilea pas, el pune câte o scobitoare la fiecare capăt liber al scobitorilor plasate până acum, astfel încât cele două scobitori sunt perpendiculare și mijlocul scobitorii noi se afla la vârful scobitorii vechi. Un vârf de scobitoare este liber dacă nu atinge o altă scobitoare.

Determinați
: 1. Numărul de scobitori aflate pe masă la pasul N.
: 2. Numărul de scobitori care au fost adăugate la pasul N.

==Date de intrare==
Fișierul de intrare scobitoare.in conține pe prima linie două numere: P, care va reprezenta cerința, și N, cu semnificația din enunț.

==Date de ieșire==
Fișierul de ieșire scobitoare.out va conține numărul cerut, iar consola va afișa mesajul de validare a datelor ("Date de intrare valide" sau "Date de intrare invalide", în funcție de validitatea datelor).

==Restricții și precizări==
* 1 &les; n &les; 1000

==Exemplu==
; scobitoare.in
: 2 197
; scobitoare.out
: 60
; Consolă
: Date de intrare valide

==Rezolvare==
<syntaxhighlight lang="python">
import math

def T(n):
if n == 1:
return 1
elif n == 2:
return 3
elif n == 3:
return 7
elif n == 4:
return 11
else:
Puterea = 0
PutereDeDoi = 1
while PutereDeDoi < n:
Puterea += 1
PutereDeDoi *= 2

if PutereDeDoi == n:
return (int(math.pow(2, 2 * Puterea + 1)) + 1) // 3
else:
PutereDeDoi = PutereDeDoi // 2
return T(PutereDeDoi) + 2 * T(n - PutereDeDoi) + T(n - PutereDeDoi + 1) - 1

def validate_input(n):
if n < 1 or n > 1000:
return False
else:
return True

def read_input():
with open("scobitoare.in", "r") as f:
p = int(f.readline())
n = int(f.readline())
if not validate_input(n):
print("Date de intrare invalide")
return
return p, n

def write_output(output):
with open("scobitoare.out", "w") as g:
g.write(str(output))
print("Date de intrare valide\n")

if __name__ == "__main__":
inputs = read_input()
if inputs:
p, n = inputs
if p == 1:
output = T(n)
else:
output = T(n) - T(n - 1)
write_output(output)

</syntaxhighlight>
==Explicație cod==
Acest cod este scris în limbajul Python și conține următoarele funcții:

1. Funcția "T(n)" calculează valoarea funcției T definită recursiv după cum urmează: T(1) = 1, T(2) = 3, T(3) = 7, T(4) = 11, T(n) = 2*T(n-1) + T(n-2) + T(n-3) - 1 pentru n > 4. În cazul în care n este o putere a lui 2, se aplică o formulă alternativă care folosește funcția "pow" din biblioteca Python "math".

2. Funcția "validate_input(n)" returnează "True" dacă n se află între 1 și 1000 și "False" altfel.

3. Funcția "read_input()" citește din fișierul "scobitoare.in" două numere întregi: "p" și "n". Funcția verifică dacă n este valid folosind funcția "validate_input(n)". În caz contrar, scrie în consolă mesajul "Date de intrare invalide" și se termină.

4. Funcția "write_output(output)" scrie valoarea "output" în fișierul "scobitoare.out".

5. În blocul "if __name__ == '__main__':", funcția "read_input()" este apelată pentru a citi inputul. Dacă inputul este valid, se calculează valoarea lui "output" folosind funcția "T(n)" și se apelează funcția "write_output(output)" pentru a scrie outputul în fișierul "scobitoare.out". În cazul în care p este diferit de 1, se calculează diferența dintre T(n) și T(n-1).

1973 - Hambar2

2023-05-14T14:29:31Z

Cata:

==Enunț==
Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de arie maximă ce conține doar valori 0, pe care va construi un hambar, va câștiga mâna frumoasei Gîrcella.

==Cerința==
Ajutați-l pe Cavalerul de Aur să câștige această întrecere.

==Date de intrare==
Fișierul de intrare hambar2.in conține pe prima linie numerele N și M, reprezentând dimensinunea matricei respectiv numărul de pomi, iar pe următoarele M linii se vor găsi două numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

==Date de ieșire==
Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.
În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau instrucțiuni cu privire la n sau m).
==Restricții și precizări==
* 1 ≤ N, M ≤ 1000
* Nu se vor afla 2 sau mai mulți pomi în același loc.
==Exemplu==
; hambar2.in
: 5 5
: 1 3
: 2 1
: 2 5
: 5 1
: 5 5
; hambar2.out
: 12
; Consolă
: Input valid
==Rezolvare==
<syntaxhighlight lang="python">
nMAX = 1000

def clear(stiva):
while stiva:
stiva.pop()

def calculate_histogram(n, mat):
h = [0] * (n + 1)

for i in range(1, n+1):
for j in range(1, n+1):
if not mat[i][j]:
h[j] += 1
else:
h[j] = 0

return h

def calculate_left_boundary(n, h):
st = [0] * (n + 1)
stiva = []

for j in range(1, n+1):
while stiva and h[stiva[-1]] >= h[j]:
stiva.pop()

if not stiva:
st[j] = 0
else:
st[j] = stiva[-1]

stiva.append(j)

return st

def calculate_right_boundary(n, h):
dr = [0] * (n + 1)
stiva = []

for j in range(n, 0, -1):
while stiva and h[stiva[-1]] >= h[j]:
stiva.pop()

if not stiva:
dr[j] = n+1
else:
dr[j] = stiva[-1]

stiva.append(j)

return dr

def calculate_max_rect(n, mat):
arieMAX = 0

h = calculate_histogram(n, mat)
st = calculate_left_boundary(n, h)
dr = calculate_right_boundary(n, h)

for j in range(1, n+1):
arieMAX = max(arieMAX, h[j] * (dr[j] - st[j] - 1))

return arieMAX

def validate_input(n, m):
if not 1 <= n <= 1000:
raise ValueError("n trebuie să fie între 1 și 1000")
return 0
if not 1 <= m <= 1000:
raise ValueError("m trebuie să fie între 1 și 1000")
return 0
return 1

if __name__ == '__main__':
with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:
n, m = map(int, fin.readline().split())
if validate_input(n, m):
print("Input valid")

mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
for _ in range(m):
x, y = map(int, fin.readline().split())
mat[x][y] = True

fout.write(str(calculate_max_rect(n, mat)))

</syntaxhighlight>

==Explicație==
Acest cod implementează o soluție pentru problema de a găsi cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe într-o matrice dată de dimensiunea n x n. Mai precis, codul conține următoarele funcții:

- Funcția "clear" golește conținutul unei stive date ca argument;
- Funcția "calculate_histogram" calculează histograma pentru matricea dată și returnează o listă de dimensiune n+1, unde primul element este 0 și următoarele elemente reprezintă înălțimea coloanelor corespunzătoare din matrice;
- Funcțiile "calculate_left_boundary" și "calculate_right_boundary" calculează limitele stângi, respectiv drepte ale dreptunghiurilor care conțin fiecare coloană din matricea dată și care au înălțimile date de histograma calculată anterior. Acestea returnează două liste de dimensiune n+1, unde primul și ultimul element sunt 0, iar restul elementelor reprezintă limitele stângi sau drepte corespunzătoare;
- Funcția "calculate_max_rect" calculează cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe în matricea dată, folosind funcțiile "calculate_histogram", "calculate_left_boundary" și "calculate_right_boundary";
- Funcția "validate_input" verifică dacă valorile n și m sunt în intervalul [1, 1000] și generează o excepție în caz contrar.

În secțiunea "if __name__ == '__main__':" se deschide fișierul "hambar2.in" pentru citire și fișierul "hambar2.out" pentru scriere, se citește dimensiunea matricei și numărul de elemente albe din aceasta și se verifică dacă valorile introduse sunt valide. Dacă sunt, se construiește matricea folosind elementele citite și se apelează funcția "calculate_max_rect" pentru a calcula cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe. Rezultatul este scris în fișierul "hambar2.out".

4211 - ElimZTRec

2023-05-03T07:17:52Z

Cata:

== Cerința ==
Scrieți funcția recursivă ElimZTRec care primind ca parametru un număr natural nenul n, returnează numărul obținut prin eliminarea eventualelor cifre de 0 de la sfârșitul lui n.

== Restricții și precizări ==
* 1 ≤ n ≤ 2.147.000.000
* Numele funcției este ElimZTRec.
* Se recomandă utilizarea recursivității în rezolvarea problemei.

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte.", apoi pe un rând nou un mesaj dat în funcție de valoarea returnată de funcția ElimZTRec, reprezentând numărul cerut. În cazul în care numărul introdus depășește limitele date, se va afișa "Numarul introdus nu este valid.", iar dacă numărul introdus nu este întreg, se va afișa "Nu ati introdus un numar intreg."

==Exemplu 1==
; Intrare
: Introduceti un numar natural intre 1 si 2147000000: 240
; Ieșire
: Datele introduse sunt valide.
: Numarul fara zerouri la final este: 24
==Exemplu 2==
; Intrare
: Introduceti un numar natural intre 1 si 2147000000: 123
; Ieșire
: Datele introduse sunt valide.
: Numarul fara zerouri la final este: 123
== Rezolvare ==
<syntaxhighlight lang="python">
def validate_n(n):
if isinstance(n, int) and n >= 1 and n <= 2147000000:
return True
else:
return False

def ElimZTRec(n):
if n % 10 != 0:
return n
else:
return ElimZTRec(n // 10)

if __name__ == "__main__":
n = input("Introduceti un numar natural intre 1 si 2147000000: ")
try:
n = int(n)
if validate_n(n):
result = ElimZTRec(n)
print("Datele introduse sunt valide.")
print(f"Numarul fara zerouri la final este: {result}")
else:
print("Numarul introdus nu este valid.")
except ValueError:
print("Nu ati introdus un numar natural.")
</syntaxhighlight>

==Explicație==
Funcția validate_n(n) verifică dacă valoarea argumentului n este un număr întreg pozitiv între 1 și 2147000000 (valoarea maximă pe 32 de biți). Dacă această condiție este îndeplinită, funcția returnează True, altfel returnează False.

Funcția ElimZTRec(n) primește un număr natural n și elimină zerourile de la sfârșitul acestuia recursiv, până când ultima cifră a numărului este diferită de 0. În cazul în care ultima cifră a numărului este diferită de 0, funcția returnează valoarea inițială a numărului, altfel apelează funcția recursiv cu n împărțit la 10.

În secțiunea if __name__ == "__main__":, programul primește de la utilizator un număr natural, îl validează folosind funcția validate_n(n), apelează funcția ElimZTRec(n) pentru a elimina zerourile de la sfârșitul numărului și afișează rezultatul. Dacă numărul introdus de utilizator nu este valid, se afișează un mesaj corespunzător.

4262 - FiboRec

2023-05-03T07:17:33Z

Cata:

== Cerința ==
Scrieți funcția recursivă cu antetul 
<code>def FiboRec(x, y)</code> 
care primind ca parametri două numere întregi x și y, returnează 1 dacă x și y și sunt doi termeni consecutivi ai șirului Fibonacci, sau returnează 0 în caz contrar.

== Restricții și precizări ==
* Primii zece termeni ai șirului Fibonacci sunt: 1,1,2,3,5,8,13,21,34,55.
* Dacă x și y sunt termeni consecutivi ai șirului Fibonacci, atunci trebuie ca x &les; y.
* Se recomandă utilizarea recursivității în rezolvarea problemei.

==Date de intrare==
Programul citește de la tastatură numerele x și y.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte.", apoi pe un rând nou un mesaj dat în funcție de valoarea returnată de funcția FiboRec, reprezentând numărul cerut. În cazul în care x &ges; y, se va afișa "Valorile introduse nu sunt valide.", iar dacă numerele introduse nu sunt întregi, se va afișa "Valorile introduse nu sunt numere intregi."

==Exemplu 1==
; Intrare
: Introduceti valoarea lui x: 5
: Introduceti valoarea lui y: 8
; Ieșire
: Datele introduse sunt corecte.
: Numerele 5 si 8 sunt consecutive in sirul Fibonacci.
==Exemplu 2==
; Intrare
: Introduceti valoarea lui x: 5
: Introduceti valoarea lui y: 9
; Ieșire
: Datele introduse sunt corecte.
: Numerele 5 si 9 nu sunt consecutive in sirul Fibonacci.

== Rezolvare ==
<syntaxhighlight lang="python">
def validate_FiboRec(x, y):
if isinstance(x, int) and isinstance(y, int) and x <= y and y > 0:
return True
else:
return False

def FiboRec(x, y):
if x == y:
return 1
elif x > y or y < 1:
return 0
else:
return FiboRec(y - x, x)

if __name__ == "__main__":
x = input("Introduceti valoarea lui x: ")
y = input("Introduceti valoarea lui y: ")
try:
x = int(x)
y = int(y)
if validate_FiboRec(x, y):
result = FiboRec(x, y)
print("Datele introduse sunt corecte.")
if result == 1:
print(f"Numerele {x} si {y} sunt consecutive in sirul Fibonacci.")
else:
print(f"Numerele {x} si {y} nu sunt consecutive in sirul Fibonacci.")
else:
print("Valorile introduse nu sunt valide.")
except ValueError:
print("Valorile introduse nu sunt numere intregi.")
</syntaxhighlight>

==Explicație==
Prima funcție, `validate_FiboRec(x, y)`, verifică dacă valorile `x` și `y` sunt numere întregi, dacă `x` este mai mic sau egal cu `y`, iar `y` este mai mare decât zero. Dacă toate condițiile sunt îndeplinite, funcția returnează `True`, altfel returnează `False`.

A doua funcție, `FiboRec(x, y)`, folosește o abordare recursivă pentru a verifica dacă două numere întregi consecutive se află în șirul Fibonacci între `x` și `y`. Funcția verifică dacă `x` și `y` sunt egale și, în acest caz, returnează 1, pentru că orice număr este considerat a fi în șirul Fibonacci. Dacă `x` este mai mare decât `y` sau `y` este mai mic sau egal cu 0, funcția returnează 0. În celelalte cazuri, funcția calculează următorul număr din șirul Fibonacci folosind formula F(n) = F(n-1) + F(n-2) și continuă recursiv cu această formulă până când se ajunge la numărul `y-x`.

În funcția principală, se citesc de la tastatură valorile `x` și `y`. Se încearcă conversia valorilor la numere întregi și se verifică dacă acestea sunt valide folosind funcția `validate_FiboRec`. Dacă valorile sunt valide, se apelează funcția `FiboRec` pentru a verifica dacă numerele sunt consecutive în șirul Fibonacci și se afișează un mesaj corespunzător. Dacă valorile `x` și `y` nu sunt valide, se afișează un mesaj de eroare.

4210 - FCrescRec

2023-05-03T07:16:22Z

Cata:

== Cerința ==
Scrieți funcția recursivă FCrescRec care primind ca parametru un număr natural n, returnează 1 dacă cifrele sale, începând cu cifra unităţilor sunt dispuse în ordine crescătoare, sau returnează 0 dacă n nu are cifrele în ordine crescătoare.

== Restricții și precizări ==
* 0 &les; n &les; 2.147.000.000
* Numele funcției este FCrescRec.
* Se recomandă utilizarea recursivității în rezolvarea problemei.
==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte.", apoi pe un rând nou un mesaj în funcție de rezultatul funcției FCrescRec, care specifică dacă numărul are cifre crescătoare începând de la cifra unităților. În cazul în care numărul introdus depășește limitele date, se va afișa "Numarul introdus nu este valid.", iar dacă numărul introdus nu este întreg, se va afișa "Nu ati introdus un numar intreg."
: Notă: Crescător începând de la cifra unităților este un alt mod de a spune că cifrele numărului sunt descrescătoare.
== Exemplu 1==
; Intrare
: Introduceti un numar intreg pozitiv: 4
; Ieșire
: Datele introduse sunt corecte.
: Cifrele numarului 4 sunt in ordine crescatoare.
==Exemplu 2==
; Intrare
: Introduceti un numar intreg pozitiv: 975311
; Ieșire
: Datele introduse sunt corecte.
: Cifrele numarului 975311 sunt in ordine crescatoare.
==Exemplu 3==
; Intrare
: Introduceti un numar intreg pozitiv: 43711
; Ieșire
: Datele introduse sunt corecte.
: Cifrele numarului 43711 nu sunt in ordine crescatoare.
== Rezolvare ==
<syntaxhighlight lang="python">
def validate_n(n):
if isinstance(n, int) and n >= 0 and n <= 2147000000:
return True
else:
return False

def FCrescRec(n):
if n < 10:
return 1
elif n % 10 > (n // 10) % 10:
return 0
else:
return FCrescRec(n // 10)

if __name__ == "__main__":
n = input("Introduceti un numar intreg pozitiv: ")
try:
n = int(n)
if validate_n(n):
result = FCrescRec(n)
print("Datele introduse sunt corecte.")
if result == 1:
print(f"Cifrele numarului {n} sunt in ordine crescatoare.")
else:
print(f"Cifrele numarului {n} nu sunt in ordine crescatoare.")
else:
print("Numarul introdus nu este valid.")
except ValueError:
print("Nu ati introdus un numar intreg.")
</syntaxhighlight>
==Explicație==
Acest cod implementează o funcție de validare a unui număr întreg n, validate_n(n), care verifică dacă numărul este de tip întreg, este mai mare sau egal cu 0 și mai mic sau egal cu 2147000000 (adica 2^31 - 1).

Funcția FCrescRec(n) verifică recursiv dacă cifrele numărului întreg n sunt în ordine crescătoare.

În funcția principală (if __name__ == "__main__":), utilizatorul este întâi întrebat să introducă un număr întreg pozitiv. Apoi se verifică dacă numărul introdus este valid folosind funcția de validare și, dacă este valid, se apelează funcția FCrescRec(n) pentru a verifica dacă cifrele sunt în ordine crescătoare sau nu. Se afișează apoi un mesaj corespunzător rezultatului verificării.

4208 - ExistaImpareRec

2023-05-03T07:15:51Z

Cata:

== Cerința ==
Scrieți funcția recursivă ExistaImpareRec care primind ca parametru un număr natural n, returnează 1 dacă n conține cel puțin o cifră impară, sau returnează 0 dacă n conține doar cifre pare.
== Restricții și precizări ==
* 0 ≤ n ≤ 231 - 1
* Numele funcției este ExistaImpareRec.
* Se recomandă utilizarea recursivității în rezolvarea problemei.
==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte.", apoi pe un rând nou mesajul cerut în funcție de cifrele pare ale numărului introdus. În cazul în care numărul introdus depășește limitele date, se va afișa "Numarul introdus nu este valid.", iar dacă numărul introdus nu este întreg, se va afișa "Nu ati introdus un numar intreg."
== Exemplu 1 ==
; Intrare
: Introduceti un numar intreg intre 0 si 2^31 - 1: 240
; Ieșire
: Datele introduse sunt corecte.
: Toate cifrele numarului 240 sunt pare.
==Exemplu 2==
; Intrare
: Introduceti un numar intreg intre 0 si 2^31 - 1: 2134
; Ieșire
: Datele introduse sunt corecte.
: Exista cel putin o cifra impara in numarul 2134.
== Rezolvare ==
<syntaxhighlight lang="python">
def validate_n(n):
if isinstance(n, int) and n >= 0 and n <= 2**31 - 1:
return True
else:
return False

def ExistaImpareRec(n):
if n == 0:
return 0
elif n % 2 == 1:
return 1
else:
return ExistaImpareRec(n // 10)

if __name__ == "__main__":
n = input("Introduceti un numar intreg intre 0 si 2^31 - 1: ")
try:
n = int(n)
if validate_n(n):
result = ExistaImpareRec(n)
print("Datele introduse sunt corecte.")
if result == 1:
print(f"Exista cel putin o cifra impara in numarul {n}.")
else:
print(f"Toate cifrele numarului {n} sunt pare.")
else:
print("Numarul introdus nu este valid.")
except ValueError:
print("Nu ati introdus un numar intreg.")
</syntaxhighlight>
==Explicație==
* validate_n(n) - Verifică dacă n este un întreg pozitiv și se încadrează în intervalul 0 și 2^31 - 1. În caz contrar, returnează False.
* ExistaImpareRec(n) - Verifică recursiv dacă ultima cifră a lui n este impară. Dacă n este zero, returnează 0 pentru a indica că numărul nu conține cifre impare. În caz contrar, verifică dacă ultima cifră este impară. Dacă este impară, returnează 1. Altfel, apelează funcția cu n împărțit la 10, pentru a verifica următoarea cifră.
* if __name__ == "__main__": - Acesta este punctul de intrare în program. În această secțiune, utilizatorul poate introduce un număr întreg n. Codul verifică dacă n este un număr întreg valid și se încadrează în intervalul specificat. În caz afirmativ, apelul ExistaImpareRec(n) și afișează un mesaj corespunzător.

2283 - Caraghios

2023-05-03T07:14:33Z

Cata:

Se consideră un șir S de cifre nenule. O secvență a șirului S este o succesiune de cifre din S care apar pe poziții consecutive. Un număr n asociat unei secvențe din S este numărul în baza 10 care se formează cu toate cifrele din secvența respectivă, în ordinea în care apar în aceasta.

Un număr n se numește caraghios dacă este egal cu pătratul sumei cifrelor lui n.

==Cerința==
Dându-se un șir S de cifre nenule, să se determine câte dintre secvențele din S au numere asociate caraghioase.

==Date de intrare==
Fișierul de intrare caraghios.in conține pe prima linie șirul S de cifre nenule.

==Date de ieșire==
Fișierul de ieșire caraghios.out va conține pe prima linie numărul de secvențe din S care au asociate numere caraghioase.
În consolă se va afișa un mesaj de validare a datelor ("Input valid!" sau "Input invalid! Numărul de cifre trebuie să fie mai mic sau egal cu 1.000.000." după caz).
==Restricții și precizări==
* Șirul S va conține maxim 1.000.000 de cifre
==Exemplu==
; caraghios.in
: 28113
; caraghios.out
: 3
; Consolă
: Input valid!
==Explicație exemplu==
Toate secvențele lui S sunt: 2, 28, 281, 2811, 28113, 8, 81, 811, 8113, 1, 11, 113, 1, 13, 3
Există 3 secvențe care au asociate numere caraghioase: 81, 1, 1
: 81 = (8+1)*(8+1), 1 = 1*1, 1 = 1*1

==Rezolvare==
<syntaxhighlight lang="python">
def validate_input(input_str):
"""
Verifică dacă input-ul are maxim 1.000.000 de cifre.
:param input_str: șirul de caractere de verificat
:return: True dacă input-ul este valid, False în caz contrar
"""
return len(input_str) <= 1000000

def count_caraghios(input_str):
"""
Calculează numărul de apariții a cifrei 1 într-un șir dat.
:param input_str: șirul de caractere de analizat
:return: numărul de apariții a cifrei 1, conform cerințelor specifice
"""
nr = 0
x = input_str[0]
if x == '1':
nr += 1
for y in input_str[1:]:
if y == '1':
nr += 1
if x == '8':
nr += 1
x = y
return nr

if __name__ == "__main__":
input_file = "caraghios.in"
output_file = "caraghios.out"
with open(input_file, "r") as f:
input_str = f.read().strip()
if not validate_input(input_str):
print("Input invalid! Numărul de cifre trebuie să fie mai mic sau egal cu 1.000.000.")
return
else:
print("Input valid!")
nr = count_caraghios(input_str)
with open(output_file, "w") as f:
f.write(str(nr))

</syntaxhighlight>

==Explicație cod==
În cadrul programului, se utilizează două funcții:

Funcția validate_input primește un șir de caractere input_str și returnează True dacă șirul are cel mult 1.000.000 de caractere.

Funcția count_caraghios primește un șir de caractere input_str și calculează numărul de apariții a cifrei 1 în șir, respectând condiția specifică legată de cifra 8.

În cadrul blocului main se deschide fișierul de intrare caraghios.in, se citește conținutul său într-un șir de caractere și se validează input-ul folosind funcția validate_input. Dacă input-ul este invalid, se afișează un mesaj corespunzător și programul se încheie. În caz contrar, se calculează numărul de apariții a cifrei 1 folosind funcția count_caraghios, iar rezultatul este scris în fișierul de ieșire caraghios.out.

1675 - Calc

2023-05-03T07:12:34Z

Cata:

==Cerința==
La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.

Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

Cunoscând N, să se determine:

Numărul de zile modulo 1000000007 în care se desfășoară concursul.
Configurațiile laboratorului în ziua X-1 și ziua X+1, cunoscând configurația zilei X.
==Date de intrare==
Fişierul de intrare calc.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.

Pe linia a doua vom avea numărul natural N.

Pe linia a treia se va găsi un șir de N cifre binare, fără spații între ele, reprezentând configurația corectă realizată de administrator în ziua X.

==Date de ieșire==
Dacă valoarea lui p este 1, se va rezolva numai punctul 1) din cerință.
În acest caz, în fişierul de ieşire calc.out se va scrie un singur număr natural Z reprezentând numărul de zile în care se desfășoară concursul pentru cele N echipe.

Dacă valoarea lui p este 2, se va rezolva numai punctul 2) din cerință.
În acest caz, fişierul de ieşire calc.out va conține două linii. Pe prima linie se vor scrie N cifre binare, fără spații între ele, reprezentând configurația rețelei din ziua precedentă, iar pe a doua linie N cifre binare, fără spații între ele, reprezentând configurația din ziua următoare. Dacă în ziua precedentă nu există o configurație conform cerințelor problemei, se va scrie pe prima linie valoarea -1. Dacă în ziua următoare nu există o configurație conform cerințelor problemei, se va scrie pe a doua linie valoarea -1.

Consola va afișa "Input valid" sau instrucțiuni de introducere a datelor.
==Restricții și precizări==
* 1 &les; N &les; 100000
* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
==Exemplul 1==
; calc.in

: 1
: 3
: 001
; calc.out

: 3
; Consola
: Input valid
==Exemplul 2==
; calc.in

: 2
: 3
: 001
; calc.out

: -1
: 100
; Consola
: Input valid
==Rezolvare==
<syntaxhighlight lang="python">
MODULO = 1000 * 1000 * 1000 + 7

def read_input():
with open("calc.in", "r") as f:
tip = int(f.readline().strip())
n = int(f.readline().strip())
s = f.readline().strip()
return tip, n, s

def write_output(prev, next):
with open("calc.out", "w") as f:
f.write(f"{prev}\n{next}\n")

def compute_prev(s):
n = len(s)
prev = list(s)
if s[n - 1] == "1" and s[n - 2] == "1":
prev[n - 1] = prev[n - 2] = "0"
else:
i = n - 2
while i >= 0 and s[i] == "0":
i -= 1
if i < 0:
prev = "-1"
else:
prev[i] = "0"
for j in range(i + 2, n):
prev[j] = "1"
return "".join(prev)

def compute_next(s):
n = len(s)
next = list(s)
if s[n - 1] == "0" and s[n - 2] == "0":
next[n - 1] = next[n - 2] = "1"
else:
i = n - 1
while i >= 0 and s[i] == "1":
i -= 1
if i < 0:
next = "-1"
else:
next[i - 1] = "1"
next[i] = "0"
oldi = i
for j in range(i + 1, n):
next[j] = "0"
if (n - 1 - oldi) % 2 == 0:
next[n - 1] = "1"
return "".join(next)

def compute_fibonacci(n):
if n <= 1:
return 1
a, b = 1, 1
for i in range(2, n + 1):
c = (a + b) % MODULO
a, b = b, c
return b

def validate_input(tip: int, N: int, S: str) -> bool:
if tip not in (1, 2):
print("tip trebuie sa fie 1 sau 2")
return False
if not (1 <= N <= 100000):
print("N trebuie sa fie intre 1 si 100000")
return False
if len(S) != N or not set(S).issubset({'0', '1'}):
print("S trebuie sa fie un sir de N caractere '0' sau '1'")
return False
print("Input valid")
return True

if __name__ == "__main__":
tip, n, s = read_input()
if not validate_input(tip, n, s):
exit(1)
if tip == 1:
result = compute_fibonacci(n)
write_output(result, result)
return

if n == 1:
write_output("-1", "-1")
return

prev = compute_prev(s)
next = compute_next(s)
write_output(prev, next)

</syntaxhighlight>

==Explicație cod==
MODULO = 1000 * 1000 * 1000 + 7: definește valoarea modulo care va fi utilizată în funcția compute_fibonacci.

def read_input(): definește o funcție care citește intrarea din fișierul "calc.in". Prima linie a fișierului reprezintă tipul de operație de efectuat (tip), a doua linie reprezintă lungimea șirului (n), iar a treia linie reprezintă șirul (s). Funcția returnează valorile tipul, n și s.

def write_output(prev, next): definește o funcție care scrie ieșirea în fișierul "calc.out". Ieșirea constă din două linii: prev și next. Funcția primește două argumente: prev și next.

def compute_prev(s): definește o funcție care primește un șir s ca intrare și returnează șirul anterior în ordinea lexicografică. Dacă șirul anterior nu există, funcția returnează -1.

def compute_next(s): definește o funcție care primește un șir s ca intrare și returnează următorul șir în ordinea lexicografică. Dacă următorul șir nu există, funcția returnează -1.

def compute_fibonacci(n): definește o funcție care calculează al n-lea număr Fibonacci folosind o abordare iterativă. Funcția returnează valoarea celui de-al n-lea număr Fibonacci.

def validate_input(tip: int, N: int, S: str) -> bool: definește o funcție care validează intrarea. Verifică dacă valoarea tipului este 1 sau 2, dacă valoarea n se află între 1 și 100000 și dacă șirul s conține doar caracterele "0" și "1". Dacă intrarea este validă, funcția returnează True; în caz contrar, returnează False.

if name == "main": este punctul de intrare principal al programului. Mai întâi, se citește intrarea folosind funcția read_input și se validează utilizând funcția validate_input. Dacă intrarea nu este validă, programul se încheie cu o eroare. Dacă tipul de operație (tip) este 1, se calculează al n-lea număr Fibonacci folosind funcția compute_fibonacci și se scrie ieșirea în fișierul "calc.out". Dacă tipul de operație este 2, se calculează șirurile anterioare și următoare în ordinea lexicografică folosind funcțiile compute_prev și compute_next, respectiv, și se scrie ieșirea în fișierul "calc.out".

1124 - Patrate

2023-05-03T07:03:42Z

Cata:

==Cerința==
Dându-se n, un număr natural, să se afle numărul de pătrate care au colţurile coordonate numere întregi cuprinse între 0 şi n inclusiv.

==Date de intrare==
Programul citește de la tastatură un număr natural n.

==Date de ieșire==
Programul va afişa pe ecran un număr natural, reprezentând numărul de pătrate formate cu cele (n+1)2 puncte. Deoarece rezultatul poate fi mare, se va afişa răspunsul modulo 666013. De asemenea, se afișează un mesaj de validare a datelor introduse ("Input valid" sau instructiuni de introducere pentru n).

==Restricții și precizări==
* 1 &les; n &les; 2.000.000.000
* Pentru teste în valoare de 30 de puncte, n ≤ 10
* Pentru teste în valoare de 75 de puncte, n ≤ 2.000.000
==Exemplu==
; Intrare

: 2
; Ieșire
: Input valid
: 6
==Explicație exemplu==
Pătratele ce se formează au colţurile:

# (0, 0), (0, 1), (1, 1), (1, 0)
# (0, 1), (0, 2), (1, 2), (1, 1)
# (1, 0), (1, 1), (2, 1), (2, 0)
# (1, 1), (1, 2), (2, 2), (2, 1)
# (0, 0), (0, 2), (2, 2), (2, 0)
# (0, 1), (1, 2), (2, 1), (1, 0)

==Rezolvare==
<syntaxhighlight lang="python">
def validate_input(n):
if n < 1 or n > 2000000000:
raise ValueError("n trebuie sa fie intre 1 si 2.000.000.000")
else:
print("Input valid")

def calculate_sum(n):
validate_input(n)
sol = 0
mod = 666013

n %= mod

for i in range(n):
sol += (n - i) * (n - i) * (i + 1)
sol %= mod

return sol

if __name__ == "__main__":
n = int(input())
sol = calculate_sum(n)
print(sol)

</syntaxhighlight>

==Explicație cod==
Acest cod definește trei funcții și o funcție principală:

Funcția validate_input(n) verifică dacă valoarea parametrului n este cuprinsă între 1 și 2.000.000.000, și aruncă o excepție ValueError dacă nu este.

Funcția calculate_sum(n) primește un parametru n și calculează suma unei anumite formule matematice, bazată pe valoarea lui n și un număr constant (mod = 666013). Apoi, funcția returnează această sumă.

Funcția main() citește un număr întreg de la tastatură, apelează funcția calculate_sum(n) pentru a calcula suma corespunzătoare, și apoi afișează rezultatul.

Dacă acest script este rulat ca un program, atunci funcția main() este apelată.

2724 - LSQ

2023-05-03T07:02:14Z

Cata:

==Cerința==
Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1.

==Date de intrare==
Fișierul de intrare lsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei..

==Date de ieșire==
Fișierul de ieșire lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa. Consola va afișa un mesaj de validare a datelor ("Input valid" sau "Input invalid" după caz).

==Restricții și precizări==
* 1 &les; N, M &les; 1000
* Se consideră pătrat și cel de latură 1 (conține doar un element).
==Exemplu==
; lsq.in

: 7 7
: 0000000
: 0111100
: 0101111
: 0100101
: 0111111
: 0000011
: 0000011
; lsq.out

: 4
; Consola
: Input valid
==Explicație==

0 0 0 0 0 0 0 
0 1 1 1 1 0 0 
0 1 0 1 1 1 1 
0 1 0 0 1 0 1 
0 1 1 1 1 1 1 
0 0 0 0 0 1 1 
0 0 0 0 0 1 1 

==Rezolvare==
<syntaxhighlight lang="python">
Nmax = 1005

def compute_matrices(N, M, A):
LDL = [[0] * M for _ in range(N)]
CDL = [[0] * M for _ in range(N)]
LRU = [[0] * M for _ in range(N)]
CRU = [[0] * M for _ in range(N)]

for i in range(N):
for j in range(M):
if A[i][j] == 1:
LDL[i][j] = 1 + LDL[i][j - 1] if j > 0 else 1
CDL[i][j] = 1 + CDL[i - 1][j] if i > 0 else 1

for i in range(N - 1, -1, -1):
for j in range(M - 1, -1, -1):
if A[i][j] == 1:
LRU[i][j] = 1 + LRU[i][j + 1] if j < M - 1 else 1
CRU[i][j] = 1 + CRU[i + 1][j] if i < N - 1 else 1

return LDL, CDL, LRU, CRU

def find_largest_square(N, M, A):
LDL, CDL, LRU, CRU = compute_matrices(N, M, A)
ans = 0
for i in range(N):
for j in range(M):
for L in range(min(LDL[i][j], CDL[i][j]), ans, -1):
if L <= min(LRU[i - L + 1][j - L + 1], CRU[i - L + 1][j - L + 1]):
ans = L
break
return ans

def validate_input(n: int, m: int) -> bool:
return 1 <= n <= 1000 and 1 <= m <= 1000

if __name__ == "__main__":
with open("lsq.in", "r") as fin, open("lsq.out", "w") as fout:
N, M = map(int, fin.readline().split())
A = [list(map(int, fin.readline().strip())) for _ in range(N)]
if not validate_input(N, M):
print("Input invalid")
return
else:
print("Input valid")
ans = find_largest_square(N, M, A)
fout.write(str(ans) + "\n")

</syntaxhighlight>

==Explicație cod==
Acest program calculează dimensiunea celui mai mare pătrat format numai din cifra 1 într-o matrice bidimensională dată.

Funcția `compute_matrices` calculează patru matrici: `LDL`, `CDL`, `LRU`, `CRU`, fiecare fiind de aceeași dimensiune ca matricea de intrare `A`. Matricile `LDL` și `CDL` conțin lungimile celor mai lungi segmente consecutive de cifra 1 din stânga și, respectiv, de sus de fiecare celulă, iar matricile `LRU` și `CRU` conțin lungimile celor mai lungi segmente consecutive de cifra 1 din dreapta și, respectiv, de jos de fiecare celulă.

În denumirea matricelor din funcția `compute_matrices`, primele trei litere reprezintă inițialele direcțiilor de la care începe numărătoarea segmentelor de cifra 1. Astfel, matricea `LDL` conține lungimile segmentelor consecutive de cifra 1 din stânga fiecărei celule, începând de la stânga și mergând spre dreapta, matricea `CDL` conține lungimile segmentelor consecutive de cifra 1 de sus fiecărei celule, începând de sus și mergând în jos, iar matricea `LRU` conține lungimile segmentelor consecutive de cifra 1 din dreapta fiecărei celule, începând de la dreapta și mergând spre stânga, iar matricea `CRU` conține lungimile segmentelor consecutive de cifra 1 de jos fiecărei celule, începând de jos și mergând în sus.

Funcția `find_largest_square` parcurge fiecare celulă din matricea de intrare și, pentru fiecare celulă, verifică dacă poate fi colțul stânga-sus al unui pătrat și, în caz afirmativ, încearcă să-l mărească progresiv până la limita minimă dintre lungimile segmentelor de cifra 1 din matricile `LDL`, `CDL`, `LRU` și `CRU`.

Funcția `validate_input` verifică dacă dimensiunile matricei de intrare sunt între 1 și 1000 inclusiv, iar blocul `if __name__ == "__main__":` citește datele de intrare din fișierul "lsq.in", validează dimensiunile matricei de intrare, calculează dimensiunea celui mai mare pătrat de cifra 1 și scrie rezultatul în fișierul "lsq.out".

2724 - LSQ

2023-05-03T07:01:09Z

Cata:

==Cerința==
Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1.

==Date de intrare==
Fișierul de intrare lsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei..

==Date de ieșire==
Fișierul de ieșire lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa. Consola va afișa un mesaj de validare a datelor ("Input valid" sau "Input invalid" după caz).

==Restricții și precizări==
* 1 &les; N, M &les; 1000
* Se consideră pătrat și cel de latură 1 (conține doar un element).
==Exemplu==
; lsq.in

: 7 7
: 0000000
: 0111100
: 0101111
: 0100101
: 0111111
: 0000011
: 0000011
; lsq.out

: 4
; Consola
: Input valid
==Explicație==

0 0 0 0 0 0 0 
0 1 1 1 1 0 0 
0 1 0 1 1 1 1 
0 1 0 0 1 0 1 
0 1 1 1 1 1 1 
0 0 0 0 0 1 1 
0 0 0 0 0 1 1 

==Rezolvare==
<syntaxhighlight lang="python">
Nmax = 1005

def compute_matrices(N, M, A):
LDL = [[0] * M for _ in range(N)]
CDL = [[0] * M for _ in range(N)]
LRU = [[0] * M for _ in range(N)]
CRU = [[0] * M for _ in range(N)]

for i in range(N):
for j in range(M):
if A[i][j] == 1:
LDL[i][j] = 1 + LDL[i][j - 1] if j > 0 else 1
CDL[i][j] = 1 + CDL[i - 1][j] if i > 0 else 1

for i in range(N - 1, -1, -1):
for j in range(M - 1, -1, -1):
if A[i][j] == 1:
LRU[i][j] = 1 + LRU[i][j + 1] if j < M - 1 else 1
CRU[i][j] = 1 + CRU[i + 1][j] if i < N - 1 else 1

return LDL, CDL, LRU, CRU

def find_largest_square(N, M, A):
LDL, CDL, LRU, CRU = compute_matrices(N, M, A)
ans = 0
for i in range(N):
for j in range(M):
for L in range(min(LDL[i][j], CDL[i][j]), ans, -1):
if L <= min(LRU[i - L + 1][j - L + 1], CRU[i - L + 1][j - L + 1]):
ans = L
break
return ans

def validate_input(n: int, m: int) -> bool:
return 1 <= n <= 1000 and 1 <= m <= 1000

def main():
with open("lsq.in", "r") as fin, open("lsq.out", "w") as fout:
N, M = map(int, fin.readline().split())
A = [list(map(int, fin.readline().strip())) for _ in range(N)]
if not validate_input(N, M):
print("Input invalid")
return
else:
print("Input valid")
ans = find_largest_square(N, M, A)
fout.write(str(ans) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicație cod==
Acest program calculează dimensiunea celui mai mare pătrat format numai din cifra 1 într-o matrice bidimensională dată.

Funcția `compute_matrices` calculează patru matrici: `LDL`, `CDL`, `LRU`, `CRU`, fiecare fiind de aceeași dimensiune ca matricea de intrare `A`. Matricile `LDL` și `CDL` conțin lungimile celor mai lungi segmente consecutive de cifra 1 din stânga și, respectiv, de sus de fiecare celulă, iar matricile `LRU` și `CRU` conțin lungimile celor mai lungi segmente consecutive de cifra 1 din dreapta și, respectiv, de jos de fiecare celulă.

În denumirea matricelor din funcția `compute_matrices`, primele trei litere reprezintă inițialele direcțiilor de la care începe numărătoarea segmentelor de cifra 1. Astfel, matricea `LDL` conține lungimile segmentelor consecutive de cifra 1 din stânga fiecărei celule, începând de la stânga și mergând spre dreapta, matricea `CDL` conține lungimile segmentelor consecutive de cifra 1 de sus fiecărei celule, începând de sus și mergând în jos, iar matricea `LRU` conține lungimile segmentelor consecutive de cifra 1 din dreapta fiecărei celule, începând de la dreapta și mergând spre stânga, iar matricea `CRU` conține lungimile segmentelor consecutive de cifra 1 de jos fiecărei celule, începând de jos și mergând în sus.

Funcția `find_largest_square` parcurge fiecare celulă din matricea de intrare și, pentru fiecare celulă, verifică dacă poate fi colțul stânga-sus al unui pătrat și, în caz afirmativ, încearcă să-l mărească progresiv până la limita minimă dintre lungimile segmentelor de cifra 1 din matricile `LDL`, `CDL`, `LRU` și `CRU`.

Funcția `validate_input` verifică dacă dimensiunile matricei de intrare sunt între 1 și 1000 inclusiv, iar funcția `main` citește datele de intrare din fișierul "lsq.in", validează dimensiunile matricei de intrare, calculează dimensiunea celui mai mare pătrat de cifra 1 și scrie rezultatul în fișierul "lsq.out".

1735 - divquery

2023-05-03T06:54:54Z

Cata:

==Cerința==
Se dă un vector indexat de la 1 cu n elemente numere naturale. Să se răspundă la q întrebări de forma x y, cu semnificația: “Care este cel mai mare divizor comun al elementelor cu indici cuprinși între x și y, inclusiv?”

==Date de intrare==
Fișierul de intrare divquery.in conține pe prima linie numerele n și q, pe a doua linie cele n numere naturale ale vectorului, iar de la linia 3 începând, q linii, pe fiecare aflându-se doua numere x y, reprezentând întrebările.

==Date de ieșire==
Fișierul de ieșire divquery.out va conține q linii, pe fiecare linie i aflându-se răspunsul la întrebarea i. În consolă se va afișa un mesaj de validare a datelor ("Datele de intrare sunt valide!" sau "Datele de intrare nu sunt valide!" după caz).

==Restricții și precizări==
* 1 &les; n &les; 100.000
* 1 &les; ai &les; 100.000
* 1 &les; q &les; 1.000.000
==Exemplu==
; divquery.in

: 5 4
: 1 3 18 2 3
: 1 5
: 2 3
: 3 4
: 2 4
; divquery.out

: 1
: 3
: 2
: 1
; Consola
: Datele de intrare sunt valide!
==Explicație exemplu==
În intervalul [1,5] cmmdc-ul este 1
În intervalul [2,3] cmmdc-ul este 3
În intervalul [3,4] cmmdc-ul este 2
În intervalul [2,4] cmmdc-ul este 1

==Rezolvare==
<syntaxhighlight lang="python">
def cmmdc(a, b):
while b:
r = a % b
a = b
b = r
return a

def read_input(filename):
with open(filename, 'r') as fin:
n, q = map(int, fin.readline().split())
a = list(map(int, fin.readline().split()))
queries = []
for _ in range(q):
x, y = map(int, fin.readline().split())
queries.append((x, y))
return n, a, queries

def compute_logs(n):
logs = [0] * (n+1)
for i in range(2, n+1):
logs[i] = 1 + logs[i//2]
return logs

def compute_sparse_table(a):
n = len(a)
logs = compute_logs(n)
st = [[0]*n for _ in range(logs[n]+1)]
st[0] = a
for i in range(1, logs[n]+1):
for j in range(n-(1<<i)+1):
st[i][j] = cmmdc(st[i-1][j], st[i-1][j+(1<<(i-1))])
return st, logs

def process_queries(a, queries, st, logs):
results = []
for x, y in queries:
dif = y - x + 1
l = logs[dif]
dif = dif - (1 << l)
res = cmmdc(st[l][x-1], st[l][x-1+dif])
results.append(res)
return results

def write_output(filename, results):
with open(filename, 'w') as fout:
for res in results:
fout.write(str(res) + '\n')

def validate_input(n, a, q):
if not (1 <= n <= 100000):
return False
if not all(1 <= x <= 100000 for x in a):
return False
if not (1 <= x <= 1000000 for x in q):
return False
return True

if __name__ == '__main__':
n, a, queries = read_input('divquery.in')
if not validate_input(n, a, queries):
print("Datele de intrare nu sunt valide!")
return
else:
print("Datele de intrare sunt valide!")
st, logs = compute_sparse_table(a)
results = process_queries(a, queries, st, logs)
write_output('divquery.out', results)

</syntaxhighlight>

==Explicație cod==
Acest cod este o implementare a unei soluții pentru problema "DivQuery", care se ocupă cu determinarea celui mai mare divizor comun dintr-un interval dat dintr-un șir de numere.

Funcția "cmmdc(a, b)" calculează cel mai mare divizor comun dintre două numere folosind algoritmul Euclid.

Funcția "read_input(filename)" citește datele de intrare dintr-un fișier și returnează numărul de elemente din șir (n), lista cu elementele (a) și o listă cu perechi de numere (queries), reprezentând intervalele pentru care trebuie calculat cel mai mare divizor comun.

Funcția "compute_logs(n)" calculează logaritmul în baza 2 pentru numerele de la 2 la n și returnează o listă cu valorile obținute. Aceste valori sunt utilizate pentru a determina numărul de niveluri din tabelul rar.

Funcția "compute_sparse_table(a)" construiește un tabel rar (sparse table) pentru șirul de numere dat (a). Tabelul este reprezentat ca o matrice (st) cu (logs[n]+1) niveluri și n coloane. Primul nivel al matricei conține elementele din șir, iar fiecare nivel următor se construiește pe baza nivelului precedent. Matricea este construită astfel încât pentru orice subinterval din șir se poate calcula cel mai mare divizor comun folosind două valori din tabelul rar.

Funcția "process_queries(a, queries, st, logs)" calculează cel mai mare divizor comun pentru fiecare interval din lista de intervale (queries) folosind tabela rară și returnează o listă cu rezultatele obținute.

Funcția "write_output(filename, results)" scrie rezultatele într-un fișier de ieșire.

Funcția "validate_input(n, a, q)" verifică dacă datele de intrare sunt valide, adică numărul de elemente din șir să fie între 1 și 100000, elementele din șir să fie între 1 și 100000, iar intervalele să fie între 1 și 1000000.

Blocul "if name == 'main':" este partea principală din cod care apelează celelalte funcții pentru a rezolva problema și afișează un mesaj de eroare în cazul în care datele de intrare nu sunt valide.

1461 - Meteoriti

2023-05-03T06:52:16Z

Cata:

Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N linii și M coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare repriză, pe fiecare celulă a unui dreptunghi bine delimitat, au căzut exact C meteoriți. După ce ploaia s-a oprit, pe fiecare celulă se afla un “bloc” de piatră de înălțime egală cu numărul meteoriților căzuți în acea celulă. Arpsod, foarte furios, a luat următoarea decizie: va construi un laborator exact peste meteoriții căzuți, de unde își va pedepsi dușmanii. El a hotărât că cel mai bun amplasament pentru acest laborator este la înălțime maximă. Totodată, el își dorește ca laboratorul lui să aibă o suprafață cât mai mare.

==Cerința==
Deoarece Arpsod şi arhitectul său, Ierdnac, sunt prea ocupaţi să pregătească schița viitorului laborator, vă roagă pe voi să determinați aria maximă a unei suprafețe cu celule învecinate, de înălțime maximă precum și numărul de fire de ‘noledge rămase neatinse după căderea meteoriților ( poate au ratat vreunu’ ! ).

==Date de intrare==
Pe prima linie a fișierului meteoriti.in se află trei numere naturale separate prin spațiu: N și M, reprezentând dimensiunile plantației și R, reprezentând numărul de reprize de meteoriți. Pe următoarele R linii se vor afla cinci valori separate prin spațiu: r1 c1 r2 c2 C, unde r1 c1 reprezintă coordonatele colțului stânga sus ( linie coloană ) iar r2 c2 coordonatele colțului dreapta jos ( linie coloană ) ale dreptiunghiului pe care vor cădea meteoriți iar C reprezintă numărul de meteoriți ce vor cădea pe fiecare celulă din cele delimitate.

==Date de ieșire==
În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.
În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau "Input invalid" după caz).
==Restricții și precizări==
* 4 ≤ N, M ≤ 2.000
* 1 ≤ R ≤ 100.000
* 1 ≤ r1 ≤ r2 ≤ N
* 1 ≤ c1 ≤ c2 ≤ M
* 1 ≤ C ≤ 20.000
* Două celule se consideră vecine dacă au cel puțin o latură comună.
* Înălțimea inițială a celulelor se consideră 0.
* Se garantează că pentru 30% din teste 4 ≤ N, M ≤ 300 și 1 ≤ R ≤ 300
* Pentru rezolvarea corectă a primei cerinţe se acordă 80% din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 20% din punctajul pe testul respectiv
* Fișierul de ieșire TREBUIE să conțină exact DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
* Dacă îi veți da răspunsul corect vrăjitorului, acesta vă va primi și pe voi prin laboratorul său.
* NU este bine să îl supărați pe vrăjitor!
==Exemplu==
; meteoriti.in
: 5 6 7
: 2 2 4 3 1
: 4 4 4 6 2
: 1 5 4 6 1
: 2 5 3 6 1
: 2 3 4 3 1
: 5 1 5 3 3
: 4 2 4 2 1

; meteoriti.out
: 3 12
; Consolă
: Input valid
==Explicație==
Matricea după meteoriţi:
0 0 0 0 1 1
0 1 2 0 2 2
0 1 2 0 2 2
0 2 2 2 3 3
3 3 3 0 0 0

Înălțimea maximă este 3 iar aria maximă a unei suprafețe de înălțime 3 este tot 3

==Rezolvare==
<syntaxhighlight lang="python">
nmax = 2*10**3
# liste care stochează schimbările de linie și coloană pentru a putea naviga în matricea 2D a meteoritelor din program
dl = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def is_valid(n, m, k):
if not(4 <= n <= 2000) or not(4 <= m <= 2000):
return False
if not(1 <= k <= 100000):
return False
for i in range(k):
r1, c1, r2, c2, x = meteorites[i]
if not(1 <= r1 <= r2 <= n) or not(1 <= c1 <= c2 <= m):
return False
if not(1 <= x <= 20000):
return False
return True

def build():
global a
for j in range(m):
for i in range(1, n):
a[i][j] += a[i-1][j]
for i in range(n):
for j in range(1, m):
a[i][j] += a[i][j-1]

def inside(x, y):
return (0 <= x < n) and (0 <= y < m)

def fill(i, j, hmax):
global was_here
q = [(i, j)]
was_here[i][j] = True
area = 1
while q:
f1, f2 = q.pop(0)
for p in range(4):
iv, jv = f1+dl[p], f2+dc[p]
if inside(iv, jv) and a[iv][jv] == hmax and not was_here[iv][jv]:
area += 1
was_here[iv][jv] = True
q.append((iv, jv))
return area

def solve():
global was_here
hmax, amax, area0 = 0, 0, 0
for i in range(n):
for j in range(m):
if a[i][j] >= hmax and not was_here[i][j]:
area = fill(i, j, a[i][j])
if a[i][j] == hmax:
amax = max(amax, area)
else:
amax = area
hmax = max(hmax, a[i][j])
if not a[i][j]:
area0 += 1
with open('meteoriti.out', 'w') as f:
f.write(f"{amax} {area0}")

if __name__=="__main__":
with open('meteoriti.in', 'r') as f:
n, m, k = map(int, f.readline().split())
if not is_valid(n,m,k):
print("Input invalid")
else:
print("Input valid")
a = [[0] * (nmax + 1) for _ in range(nmax + 1)]
was_here = [[False] * (nmax + 1) for _ in range(nmax + 1)]
for i in range(k):
r1, c1, r2, c2, x = map(int, f.readline().split())
r1, r2 = r1 - 1, r2 - 1
c1, c2 = c1 - 1, c2 - 1
a[r1][c1] += x
a[r1][c2 + 1] -= x
a[r2 + 1][c1] -= x
a[r2 + 1][c2 + 1] += x
build()
solve()

</syntaxhighlight>

==Explicație cod==
Acest program prelucrează date de intrare din fișierul "meteoriti.in", verifică dacă datele de intrare sunt valide și determină cea mai mare zonă de teren afectată de meteorit și numărul total de zone afectate într-un teren reprezentat prin matricea a.

Funcția "is_valid" verifică dacă dimensiunile matricei și numărul de evenimente sunt în intervalul specificat și dacă coordonatele și intensitățile meteoritilor sunt, de asemenea, în intervalul specificat.

Funcția "build" construiește matricea a prin adunarea sumei în direcția verticală și orizontală, astfel încât a[i][j] să conțină suma de la (0,0) la (i,j) în matricea de intrare.

Funcția "inside" verifică dacă coordonatele sunt în interiorul matricei.

Funcția "fill" utilizează o parcurgere BFS (Breadth-First-Search) pentru a găsi cea mai mare zonă continuă de teren cu aceeași înălțime în jurul unui punct dat din matricea a. Aceasta returnează numărul de celule din zona respectivă.

Funcția "solve" utilizează funcția "fill" pentru a căuta zonele de teren cu aceeași înălțime și pentru a determina cea mai mare zonă de teren afectată de meteorit și numărul total de zone afectate. Rezultatele sunt afișate în fișierul "meteoriti.out".

În funcția principală, datele de intrare sunt citite din fișierul "meteoriti.in", verificate și prelucrate prin funcțiile "build" și "solve".

1248 - carti2

2023-05-03T06:47:31Z

Cata:

==Cerința==
Un filipinez cultivat are X cărți pe care dorește să le vândă. Pentru aceasta, el merge pe strada Plopilor fără soț unde se află n case. Acesta știe că în fiecare dintre cele n case se vor vinde un număr de cărți.

Filipinezul cultivat începe să vândă de la o casă a și trece pe la toate casele succesive până când nu mai are cărți de vândut.

Determinați intervalul minim lexicografic [a, b] între care filipinezul să-și vândă cărțile, astfel încât să vândă un număr maxim de carți, mai mic sau egal cu X

==Date de intrare==
Fișierul de intrare carti2.in conține pe prima linie numerele n și X, iar pe a doua linie n numere naturale separate prin spații reprezntând numărul de cărți pe care le va vinde la fiecare casă.

==Date de ieșire==
Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.
În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau ValueError cu un mesaj de corectare a datelor).
==Restricții și precizări==
* 1 ≤ n ≤ 100.000
* 1 ≤ X ≤ 1.000.000.000
* numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000
==Exemplu==
; carti2.in
: 5 9
: 1 2 3 4 5
; carti2.out
: 2 4
; Consolă
: Input valid
==Explicație==
Intervalul [2, 4], deoarece 2 + 3 + 4 = 9

==Rezolvare==
<syntaxhighlight lang="python">
import sys

Inf = 0x3f3f3f3f

sys.stdin = open('carti2.in', 'r')
sys.stdout = open('carti2.out', 'w')

def validate_input(n, x):
if not 1 <= n <= 100000:
raise ValueError("Valoare invalidă pentru n. Trebuie să fie între 1 și 100000.")
if not 1 <= x <= 1000000000:
raise ValueError("Valoare invalidă pentru x. Trebuie să fie între 1 și 1000000000.")

def read_input():
n, x = map(int, input().split())
validate_input(n, x)
print("Input valid")
sp = [0] * (n + 1)
for i in range(1, n + 1):
y = int(input())
sp[i] = sp[i-1] + y
return n, x, sp

def CautBin(x, poz, n, sp):
st = poz
dr = n
PozCautata = 0
while st <= dr:
mij = (st + dr) // 2
if sp[mij] - sp[poz-1] <= x:
PozCautata = mij
st = mij + 1
elif sp[mij] - sp[poz-1] > x:
dr = mij - 1
return PozCautata

def find_books(n, x, sp):
maxim = 0
st = 0
dr = 0
for i in range(1, n + 1):
poz = CautBin(x, i, n, sp)
if sp[poz] - sp[i-1] > maxim and sp[poz] - sp[i-1] <= x:
maxim = sp[poz] - sp[i-1]
st = i
dr = poz
return st, dr

if __name__ == "__main__":
try:
n, x, sp = read_input()
st, dr = find_books(n, x, sp)
print(st, dr)
except ValueError as ve:
print(str(ve))

</syntaxhighlight>

==Explicație cod==
Acest cod începe prin importarea modulului "sys", care oferă funcții și variabile utilizate pentru a manipula funcționalitatea specifică a sistemului de operare. Apoi, se definește o valoare infinită numită "Inf" care este utilizată mai târziu în cod.

În continuare, fișierele de intrare și ieșire sunt deschise pentru citire și scriere, respectiv, utilizând metoda "open" a modulului "sys". Fișierul de intrare "carti2.in" va fi utilizat pentru citirea datelor de intrare, iar fișierul de ieșire "carti2.out" va fi utilizat pentru afișarea rezultatelor.

Funcția "validate_input" primește doi parametri "n" și "x" și verifică dacă aceștia sunt în intervalul [1, 100000] și [1, 1000000000], respectiv. Dacă nu sunt, atunci se generează o excepție "ValueError" cu un mesaj corespunzător.

Funcția "read_input" citește valorile "n" și "x" de la intrare, le validează folosind funcția "validate_input", afișează un mesaj de "Input valid" și apoi citește "n" numere întregi de la intrare și le stochează într-o listă numită "sp". Lista "sp" este o listă de suma acumulată, care conține suma primelor "i" numere din intrare la fiecare poziție "i".

Funcția "CautBin" primește patru parametri: valoarea "x" pe care o căutăm, poziția "poz" la care începem căutarea, numărul total de cărți "n" și lista "sp" cu suma acumulată. Această funcție caută poziția maximă "PozCautata" astfel încât suma acumulată de la poziția "poz" până la poziția "PozCautata" să fie mai mică sau egală cu "x". Căutarea se face utilizând o căutare binară, care reduce numărul de operații necesare în comparație cu o căutare liniară.

Funcția "find_books" primește trei parametri: numărul total de cărți "n", valoarea maximă a sumei "x" și lista "sp" cu suma acumulată. Această funcție găsește cele mai multe cărți consecutive pe care le putem cumpăra, astfel încât suma totală a prețurilor lor să fie mai mică sau egală cu "x". Funcția utilizează funcția "CautBin" pentru a găsi poziția maximă "PozCautata" astfel încât suma acumulată să fie mai mică sau egală cu "x" și apoi compară această sumă cu maximul curent și, dacă este mai mare, actualizează valorile "maxim", "st" și "dr".

Blocul `if __name__ == "__main__"` reprezintă o convenție folosită în Python pentru a verifica dacă scriptul curent este rulat ca program principal (adica rulat direct, nu importat ca modul în alt script).

Dacă scriptul este rulat ca program principal, blocul de cod sub acest `if` va fi executat, altfel va fi ignorat. În acest caz, `try`/`except` blocul este folosit pentru a prinde orice excepții care pot fi ridicate în timpul rulării codului din funcțiile `read_input()` și `find_books()`.

Astfel, dacă există excepții de tipul `ValueError` ridicate de funcția `validate_input()`, acestea vor fi prinse și mesajul de eroare corespunzător va fi afișat. Dacă nu apar erori, funcția `find_books()` este apelată și rezultatul acesteia (în acest caz, valorile `st` și `dr`) vor fi afișate la ieșirea standard.

2001 - Huge Control

2023-05-03T06:41:04Z

Cata:

Cifra de control a unui număr se obţine efectuând suma cifrelor sale, apoi suma cifrelor acestei sume etc. până se obţine o sumă formată dintr-o singură cifră. De exemplu, cifra de control a numărului 713 este 2. (7 + 1 + 3 = 11, 1 + 1 = 2).

Un număr de tip Huge este un număr natural de maxim 1.000.000 de cifre.

==Cerința==
În fișierul hugecontrol.in se găsește memorat un număr N, de tip Huge. Calculati și afișati cifra de control a numărului.

==Date de intrare==
Programul citește din fișierul de intrare hugecontrol.in numărul N, de tip Huge.

==Date de ieșire==
Programul va afișa în fișierul de ieșire hugecontrol.out numărul digit, reprezentând cifra de control a lui N, alături de un mesaj de validare a datelor introduse ("Input valid" sau "Input invalid" după caz).

==Restricții și precizări==
N este un număr cu proprietăți caracteristice tipului Huge.
==Exemplu==
; Intrare
: 713
; Ieșire
: Input valid
: 2
==Explicație==
7 + 1 + 3 = 11, 1 + 1 = 2

==Rezolvare==
<syntaxhighlight lang="python">
def is_valid_number(n):
return n.isdigit() and len(n) <= 1000000

def compute_control_digit(n):
nr = 0

for c in n:
nr = nr * 10 + int(c)
nr %= 9

return 9 if nr == 0 else nr

if __name__ == "__main__":
with open("hugecontrol.in", "r") as fin, open("hugecontrol.out", "w") as fout:
n = fin.readline().strip()

if not is_valid_number(n):
print("Input invalid")
return
else:
print("Input valid")

control_digit = compute_control_digit(n)
fout.write(str(control_digit))

</syntaxhighlight>

==Explicație cod==

Aceste funcții aparțin unui program care primește un număr mare și verifică dacă este valid, apoi calculează și scrie într-un fișier cifra de control a numărului dat.

`is_valid_number(n)` este o funcție care primește un șir de caractere `n` și returnează `True` dacă șirul este format din cifre și are lungimea mai mică sau egală cu un milion, altfel returnează `False`. Această funcție este utilizată pentru a verifica dacă numărul de intrare este valid.

`compute_control_digit(n)` este o funcție care primește un șir de caractere `n` și calculează cifra de control a numărului dat. Algoritmul pentru a calcula cifra de control este următorul:

# Se pornește cu valoarea 0 pentru variabila `nr`.
# Se parcurge fiecare caracter din șirul de intrare `n`.
# Pentru fiecare caracter, se multiplică `nr` cu 10 și se adaugă valoarea numerică a caracterului.
# Se face modulo 9 pentru a reduce `nr` la un număr între 0 și 8.
# Când toți caracterele sunt procesate, se returnează 9 dacă `nr` este egal cu 0, altfel se returnează valoarea din `nr`.

În codul principal, `__name__ == "__main__"` asigură faptul că blocul de cod din interiorul lui este executat numai atunci când fișierul este rulat ca un script și nu ca modul importat.

În interiorul blocului principal, fișierul "hugecontrol.in" este deschis și citit, iar primul rând este citit ca șirul de intrare `n`. Apoi, se verifică dacă numărul este valid folosind `is_valid_number(n)`. Dacă numărul nu este valid, se afișează mesajul "Input invalid" și programul se termină. Altfel, se afișează mesajul "Input valid" și se calculează cifra de control folosind `compute_control_digit(n)`. Această cifră de control este scrisă în fișierul "hugecontrol.out" folosind `fout.write(str(control_digit))`.

1992 - PlatouAT

2023-05-03T06:37:37Z

Cata:

==Cerința==
Se definește operația AT un procedeu prin care se schimbă caracterul 'A' în 'T' și caracterul 'T' în 'A'. Operația poate fi modelată ca o funcție astfel: AT(A) = T și AT(T) = A. Operația se generalizează pentru orice secvență de caractere formată din literele A și T. De exemplu, dacă se aplică operația AT pentru secvența AAATTA, se va obține TTTAAT. Notăm AT(AAATTA) = TTTAAT.

Considerăm șirul infinit S, definit după următoarea regulă:

* S1 = ATTA
* S2 = ATTATAATTAATATTA
* S3 = ATTATAATTAATATTATAATATTAATTATAATTAATATTAATTATAATATTATAATTAATATTA
În general: Sn = Sn-1 AT(Sn-1 ) AT(Sn-1 ) Sn-1 .

Se dau n numere naturale: k1 , k2 , k3 ... kn. Pentru fiecare număr ki se determină caracterul de pe poziția ki dintr-un element al șirului S care are cel puțin ki caractere. Cu aceste caractere se construiește un nou șir V.

Să se determine un număr L cu toți biții setați, reprezentând lungimea maximă a unei secvențe maximale de caractere 'T' din șirul V. Dacă în șirul V nu există nicio astfel de secvență se va afișa mesajul NU EXISTA.

==Date de intrare==
Programul citește de la tastatură numărul n, iar apoi cele n numere naturale de forma ki, separate prin spații.

==Date de ieșire==
Programul va afișa pe ecran numărul L cerut sau mesajul NU EXISTA, alături de un mesaj de confirmare a datelor ("Input valid" sau "Input invalid" după caz).

==Restricții și precizări==
* L &les; N &les; 1.111.111;
* cele n numere citite vor fi mai mici decât 261;
* un număr natural are toți biții setați dacă reprezentarea sa binară conține numai cifre 1;
* pentru un șir dat, o secvență de elemente cu o anumită proprietate este maximală dacă la secvență nu se mai pot adăuga elemente cu acea proprietatea. De exemplu, în șirul qweauaiopaert secvența de vocale eauaio este maximală, dar secvența eaua nu este maximală pentru că la ea se mai pot adăuga alte vocale.

==Exemple==
===Exemplul 1:===
; Intrare
: 5
: 1 2 2 2 1
;Ieșire
: Input valid
: 3
Explicație
S-a format șirul V : ATTTA, cea mai lunga secvență de elemente T are lungimea 3, iar 3 este un număr cu toți biții setați.

===Exemplul 2:===
;Intrare
: 20
: 1 2 1 2 2 2 1 2 2 2 2 2 2 2 1 1 1 1 1 1
;Ieșire
: Input valid
: 7
Explicație
S-a format șirul V : ATATTTATTTTTTTAAAAAA, lungimile secvențelor sunt : 1, 3, 7, toate aceste numere au biții setați, însă, cea mai lungă secvență este de 7 T-uri.

===Exemplul 3:===
;Intrare
: 6
: 1 2 3 2 3 1
; Ieșire
: Input valid
: NU EXISTA
Explicație
S-a format șirul V : ATTTTA, cea mai lungă secvență de elemente T are lungimea 4, iar 4 NU este un număr cu toți biții setați.

===Exemplul 4:===
; Intrare
: 15
: 6 3 2 3 4 3 3 2 3 2 2 3 2 1 1
; Ieșire
: Input valid
: 3
Explicație
S-a format șirul V : ATTTATTTTTTTTAA, cea mai lungă secvență de elemente T are lungimea 8, dar 8 NU este un număr cu toți biții setați. Cea mai lungă secvență de elemente T, de lungime L, L fiind un număr cu toți biții setați, este TTT și are lungime 3.

==Rezolvare==
<syntaxhighlight lang="python">
def all_bits(x):
return (x and not (x & (x-1))) # verifica daca toate bitii lui x sunt setati la 1

def validate_input(x):
return x < 2**61 and all_bits(x)

def get_secv(x):
secv = 1
while secv < x: # caut lungimea sirului, putere de 4, care cuprinde pozitia x
secv <<= 2
return secv

def reduce_to_first_cadran(x, secv):
cadran = x // secv + (x % secv != 0) # aflu "cadranul" in care ma aflu, raportat la lungimea secventelor
if cadran == 1:
return x, 65 # cazul de baza, nu sufera transformari
elif cadran == 2 or cadran == 3:
x -= (cadran - 1) * secv # reduc x ul in primul cadran
return x, 149 - 65 # se schimba valoarea
else:
x -= 3 * secv # reduc x ul in primul cadran
return x, 65

def process_input(n):
for i in range(n):
x = int(input())
if validate_input(x):
print("Input valid")
secv = get_secv(x)
x, c = reduce_to_first_cadran(x, secv)
yield x, secv, c
else:
print("Input invalid")

if __name__ == '__main__':
n = int(input())
lmax = 0
l = 0
start = False

for x, secv, c in process_input(n):
if x == 2 or x == 3:
c = 149 - c
if c == ord('T'):
if not start:
start = True
l = 1
else:
l += 1
else:
if all_bits(l + 1):
lmax = max(lmax, l)
l = 0
start = False

if all_bits(l + 1):
lmax = max(lmax, l)

if lmax:
print(lmax)
else:
print("NU EXISTA")

</syntaxhighlight>

==Explicație cod==
Acest cod implementează o funcționalitate care primește un număr n și n valori întregi de la utilizator. Funcția verifică dacă fiecare valoare îndeplinește anumite condiții și, dacă da, efectuează anumite transformări și calculează lungimea celei mai lungi secvențe continue de caractere 'T' în codul ASCII obținut în urma transformărilor.

Funcția all_bits(x) primește un întreg și verifică dacă toți biții sunt setați la 1. Funcția validate_input(x) verifică dacă valoarea introdusă x este mai mică decât 2^61 și toți biții sunt setați la 1. Funcția get_secv(x) calculează cea mai mare putere de 4 mai mică decât valoarea introdusă x.

Funcția reduce_to_first_cadran(x, secv) primește două valori, o valoare întreagă x și o valoare secv și calculează în ce cadran se află x raportat la secv, reducând x la valoarea sa din primul cadran (între 0 și secv). Funcția returnează valoarea x și c, care este un număr în funcție de cadranul în care se află x.

Funcția process_input(n) primește un întreg n și citește n valori întregi de la utilizator. Pentru fiecare valoare, se verifică dacă aceasta îndeplinește condițiile necesare și, în caz afirmativ, se calculează secvența și cadranul corespunzătoare, și se returnează o secvență de trei valori: x, secv și c.

Blocul __main__ primește un întreg n și apelează funcția process_input(n) pentru a procesa valorile introduse. Pentru fiecare valoare x, se aplică anumite transformări și se calculează lungimea celei mai lungi secvențe continue de caractere 'T' în codul ASCII obținut. Lungimea maximă a secvenței este afișată la sfârșitul funcției.

În general, codul este folosit pentru a procesa și transforma date și pentru a calcula anumite valori specifice, cum ar fi lungimea celei mai lungi secvențe de caractere.

2553 - Josephus

2023-05-03T06:36:41Z

Cata: /* Exemplu */

Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!

==Cerința==
Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.

Josephus ar fi preferat să se predea. Pe ce poziție ar fi trebuit să se afle soldatul pentru a putea realiza acest lucru?

==Date de intrare==
Se va citi un singur număr natural nenul, n.

==Date de ieșire==
Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață, alături de un mesaj de validare a datelor introduse ("Input valid"; se afișează "n trebuie să fie între i și 10^18" în caz contrar).

==Restricții și precizări==
* 1 ≤ n ≤ 1018;
* Se garantează că există o soluție pentru oricare n;
==Exemplu==
; Intrare
: 41
; Ieșire
: Input valid
: 19
==Explicație==
1 ⇒ 2 
3 ⇒ 4 
… 
39 ⇒ 40 
41 ⇒ 1 
3 ⇒ 5 
… 
39 ⇒ 41 
3 ⇒ 7 
11 ⇒ 15 
……… 
19 ⇒ 35 

==Rezolvare==
<syntaxhighlight lang="python">
def calculate_exponent(n):
exponent = 0
save_n = n
while save_n != 1:
save_n //= 2
exponent += 1
return exponent

def is_power_of_two(n):
exponent = calculate_exponent(n)
return (1 << exponent) == n

def calculate_result(n):
exponent = calculate_exponent(n)
if is_power_of_two(n):
return 1
else:
return ((n - (1 << exponent)) << 1) + 1

def validate_n(n):
if not 1 <= n <= 10**18:
raise ValueError("n trebuie să fie între i și 10^18")
else:
print("Input valid")

if __name__ == "__main__":
n = int(input())
validate_n(n)
print(calculate_result(n))

</syntaxhighlight>

==Explicație cod==
Acest program implementează trei funcții care lucrează împreună pentru a verifica dacă un număr întreg n este o putere a lui 2 și pentru a calcula un rezultat bazat pe n.

Funcția "calculate_exponent" primește un număr întreg n și calculează exponentul său în baza 2. Exponentul este calculat prin împărțirea repetată a lui n la 2 până când n ajunge la valoarea 1, numărul de împărțiri fiind exponentul.

Funcția "is_power_of_two" primește un număr întreg n și verifică dacă este o putere a lui 2, comparându-l cu 2 ridicat la exponentul calculat în funcția anterioară.

Funcția "calculate_result" primește un număr întreg n și calculează rezultatul bazat pe aceasta. Dacă n este o putere a lui 2, rezultatul va fi 1, altfel va fi calculat după o formulă dată.

Funcția "validate_n" primește un număr întreg n și verifică dacă se încadrează între 1 și 10^18 inclusiv. Dacă n nu se încadrează în această plajă, funcția va arunca o excepție "ValueError".

În metoda "main", se primește un număr întreg n de la utilizator, se validează și se calculează și se afișează rezultatul apelând funcția "calculate_result".

1973 - Hambar2

2023-05-03T06:36:20Z

Cata: /* Exemplu */

==Enunț==
Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de arie maximă ce conține doar valori 0, pe care va construi un hambar, va câștiga mâna frumoasei Gîrcella.

==Cerința==
Ajutați-l pe Cavalerul de Aur să câștige această întrecere.

==Date de intrare==
Fișierul de intrare hambar2.in conține pe prima linie numerele N și M, reprezentând dimensinunea matricei respectiv numărul de pomi, iar pe următoarele M linii se vor găsi două numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

==Date de ieșire==
Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.
În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau instrucțiuni cu privire la n sau m).
==Restricții și precizări==
* 1 ≤ N, M ≤ 1000
* Nu se vor afla 2 sau mai mulți pomi în același loc.
==Exemplu==
; hambar2.in
: 5 5
: 1 3
: 2 1
: 2 5
: 5 1
: 5 5
:hambar2.out
: 12
; Consolă
: Input valid
==Rezolvare==
<syntaxhighlight lang="python">
nMAX = 1000

def clear(stiva):
while stiva:
stiva.pop()

def calculate_histogram(n, mat):
h = [0] * (n + 1)

for i in range(1, n+1):
for j in range(1, n+1):
if not mat[i][j]:
h[j] += 1
else:
h[j] = 0

return h

def calculate_left_boundary(n, h):
st = [0] * (n + 1)
stiva = []

for j in range(1, n+1):
while stiva and h[stiva[-1]] >= h[j]:
stiva.pop()

if not stiva:
st[j] = 0
else:
st[j] = stiva[-1]

stiva.append(j)

return st

def calculate_right_boundary(n, h):
dr = [0] * (n + 1)
stiva = []

for j in range(n, 0, -1):
while stiva and h[stiva[-1]] >= h[j]:
stiva.pop()

if not stiva:
dr[j] = n+1
else:
dr[j] = stiva[-1]

stiva.append(j)

return dr

def calculate_max_rect(n, mat):
arieMAX = 0

h = calculate_histogram(n, mat)
st = calculate_left_boundary(n, h)
dr = calculate_right_boundary(n, h)

for j in range(1, n+1):
arieMAX = max(arieMAX, h[j] * (dr[j] - st[j] - 1))

return arieMAX

def validate_input(n, m):
if not 1 <= n <= 1000:
raise ValueError("n trebuie să fie între 1 și 1000")
return 0
if not 1 <= m <= 1000:
raise ValueError("m trebuie să fie între 1 și 1000")
return 0
return 1

if __name__ == '__main__':
with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:
n, m = map(int, fin.readline().split())
if validate_input(n, m):
print("Input valid")

mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
for _ in range(m):
x, y = map(int, fin.readline().split())
mat[x][y] = True

fout.write(str(calculate_max_rect(n, mat)))

</syntaxhighlight>

==Explicație==
Acest cod implementează o soluție pentru problema de a găsi cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe într-o matrice dată de dimensiunea n x n. Mai precis, codul conține următoarele funcții:

- Funcția "clear" golește conținutul unei stive date ca argument;
- Funcția "calculate_histogram" calculează histograma pentru matricea dată și returnează o listă de dimensiune n+1, unde primul element este 0 și următoarele elemente reprezintă înălțimea coloanelor corespunzătoare din matrice;
- Funcțiile "calculate_left_boundary" și "calculate_right_boundary" calculează limitele stângi, respectiv drepte ale dreptunghiurilor care conțin fiecare coloană din matricea dată și care au înălțimile date de histograma calculată anterior. Acestea returnează două liste de dimensiune n+1, unde primul și ultimul element sunt 0, iar restul elementelor reprezintă limitele stângi sau drepte corespunzătoare;
- Funcția "calculate_max_rect" calculează cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe în matricea dată, folosind funcțiile "calculate_histogram", "calculate_left_boundary" și "calculate_right_boundary";
- Funcția "validate_input" verifică dacă valorile n și m sunt în intervalul [1, 1000] și generează o excepție în caz contrar.

În secțiunea "if __name__ == '__main__':" se deschide fișierul "hambar2.in" pentru citire și fișierul "hambar2.out" pentru scriere, se citește dimensiunea matricei și numărul de elemente albe din aceasta și se verifică dacă valorile introduse sunt valide. Dacă sunt, se construiește matricea folosind elementele citite și se apelează funcția "calculate_max_rect" pentru a calcula cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe. Rezultatul este scris în fișierul "hambar2.out".

2319 - abc

2023-05-03T06:35:08Z

Cata:

==Cerința==
Se dau două numere naturale nenule a şi b, iar produsul lor îl notăm cu c. Aflaţi cel mai mare divizor propriu al lui A=2c-1.

==Date de intrare==
Programul citește de la tastatură numerele a şi b, separate prin spațiu.

==Date de ieșire==
Programul va afișa pe ecran numărul D, reprezentând cel mai mare divizor propriu al lui A, alături de un mesaj de validare a datelor introduse ("Input valid" sau instrucțiuni pentru reintroducerea lui a sau b).

==Restricții și precizări==
* 2 &les; a &les; 20
* 2 &les; b &les; 10.000
* Un divizor propriu al lui A este diferit de 1 şi de A
==Exemplu==
; Intrare
: 3 2
; Ieșire
: Input valid
: 21
==Explicație==
Avem c=6 şi A=26-1=63. Cel mai mare divizor propriu al lui A este 21.

==Rezolvare==
<syntaxhighlight lang="python">
def validate_a(a):
if not (2 <= a <= 20):
raise ValueError("a trebuie să fie între 2 și 20")

def validate_b(b):
if not (2 <= b <= 10000):
raise ValueError("b trebuie să fie între 2 și 10000")

def gcd(a, b):
while b:
a, b = b, a % b
return a

def largest_proper_divisor_of_A(a, b):
validate_a(a)
validate_b(b)
print("Input valid")

c = a * b
A = 2 ** c - 1

divisors = []
for i in range(2, int(A ** 0.5) + 1):
if A % i == 0:
divisors.append(i)
if i != A // i:
divisors.append(A // i)

divisors.sort(reverse=True)

for divisor in divisors:
if gcd(A, divisor) == divisor:
return divisor

raise ValueError("Nu există divizori proprii pentru A")

def main():
a, b = map(int, input("Introduceți a și b, separate prin spațiu: ").split())
divisor = largest_proper_divisor_of_A(a, b)
print(f"Cel mai mare divizor propriu al lui A este: {divisor}")

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicație cod==
Acest cod definește patru funcții: validate_a(a), validate_b(b), gcd(a, b) și largest_proper_divisor_of_A(a, b), și apoi apelează funcția main() dacă script-ul este rulat ca program principal.

Funcția validate_a(a) verifică dacă argumentul a este un număr între 2 și 20. Dacă nu, generează o excepție de tip ValueError.

Funcția validate_b(b) verifică dacă argumentul b este un număr între 2 și 10000. Dacă nu, generează o excepție de tip ValueError.

Funcția gcd(a, b) calculează cel mai mare divizor comun (gcd) al lui a și b folosind algoritmul Euclid.

Funcția largest_proper_divisor_of_A(a, b) primește doi argumente a și b, validează valorile lor cu ajutorul funcțiilor validate_a(a) și validate_b(b) și scrie un mesaj de confirmare a validării datelor introduse, calculează c = a * b și A = 2 ** c - 1, și apoi găsește cel mai mare divizor propriu al lui A. Un divizor propriu al unui număr este un divizor strict mai mic decât acel număr. Dacă nu există niciun divizor propriu al lui A, funcția generează o excepție de tip ValueError.

Funcția main() citește de la tastatură două numere întregi separate prin spațiu, apoi apelează funcția largest_proper_divisor_of_A(a, b) pentru a găsi cel mai mare divizor propriu al lui A și îl afișează.

1992 - PlatouAT

2023-05-03T06:33:51Z

Cata:

==Cerința==
Se definește operația AT un procedeu prin care se schimbă caracterul 'A' în 'T' și caracterul 'T' în 'A'. Operația poate fi modelată ca o funcție astfel: AT(A) = T și AT(T) = A. Operația se generalizează pentru orice secvență de caractere formată din literele A și T. De exemplu, dacă se aplică operația AT pentru secvența AAATTA, se va obține TTTAAT. Notăm AT(AAATTA) = TTTAAT.

Considerăm șirul infinit S, definit după următoarea regulă:

* S1 = ATTA
* S2 = ATTATAATTAATATTA
* S3 = ATTATAATTAATATTATAATATTAATTATAATTAATATTAATTATAATATTATAATTAATATTA
În general: Sn = Sn-1 AT(Sn-1 ) AT(Sn-1 ) Sn-1 .

Se dau n numere naturale: k1 , k2 , k3 ... kn. Pentru fiecare număr ki se determină caracterul de pe poziția ki dintr-un element al șirului S care are cel puțin ki caractere. Cu aceste caractere se construiește un nou șir V.

Să se determine un număr L cu toți biții setați, reprezentând lungimea maximă a unei secvențe maximale de caractere 'T' din șirul V. Dacă în șirul V nu există nicio astfel de secvență se va afișa mesajul NU EXISTA.

==Date de intrare==
Programul citește de la tastatură numărul n, iar apoi cele n numere naturale de forma ki, separate prin spații.

==Date de ieșire==
Programul va afișa pe ecran numărul L cerut sau mesajul NU EXISTA, alături de un mesaj de confirmare a datelor ("Input valid" sau "Input invalid" după caz).

==Restricții și precizări==
* L &les; N &les; 1.111.111;
* cele n numere citite vor fi mai mici decât 261;
* un număr natural are toți biții setați dacă reprezentarea sa binară conține numai cifre 1;
* pentru un șir dat, o secvență de elemente cu o anumită proprietate este maximală dacă la secvență nu se mai pot adăuga elemente cu acea proprietatea. De exemplu, în șirul qweauaiopaert secvența de vocale eauaio este maximală, dar secvența eaua nu este maximală pentru că la ea se mai pot adăuga alte vocale.

==Exemple==
===Exemplul 1:===
; Intrare
: 5
: 1 2 2 2 1
;Ieșire
: Input valid
: 3
Explicație
S-a format șirul V : ATTTA, cea mai lunga secvență de elemente T are lungimea 3, iar 3 este un număr cu toți biții setați.

===Exemplul 2:===
;Intrare
: 20
: 1 2 1 2 2 2 1 2 2 2 2 2 2 2 1 1 1 1 1 1
;Ieșire
: Input valid
: 7
Explicație
S-a format șirul V : ATATTTATTTTTTTAAAAAA, lungimile secvențelor sunt : 1, 3, 7, toate aceste numere au biții setați, însă, cea mai lungă secvență este de 7 T-uri.

===Exemplul 3:===
;Intrare
: 6
: 1 2 3 2 3 1
; Ieșire
: Input valid
: NU EXISTA
Explicație
S-a format șirul V : ATTTTA, cea mai lungă secvență de elemente T are lungimea 4, iar 4 NU este un număr cu toți biții setați.

===Exemplul 4:===
; Intrare
: 15
: 6 3 2 3 4 3 3 2 3 2 2 3 2 1 1
; Ieșire
: Input valid
: 3
Explicație
S-a format șirul V : ATTTATTTTTTTTAA, cea mai lungă secvență de elemente T are lungimea 8, dar 8 NU este un număr cu toți biții setați. Cea mai lungă secvență de elemente T, de lungime L, L fiind un număr cu toți biții setați, este TTT și are lungime 3.

==Rezolvare==
<syntaxhighlight lang="python">
def all_bits(x):
return (x and not (x & (x-1))) # verifica daca toate bitii lui x sunt setati la 1

def validate_input(x):
return x < 2**61 and all_bits(x)

def get_secv(x):
secv = 1
while secv < x: # caut lungimea sirului, putere de 4, care cuprinde pozitia x
secv <<= 2
return secv

def reduce_to_first_cadran(x, secv):
cadran = x // secv + (x % secv != 0) # aflu "cadranul" in care ma aflu, raportat la lungimea secventelor
if cadran == 1:
return x, 65 # cazul de baza, nu sufera transformari
elif cadran == 2 or cadran == 3:
x -= (cadran - 1) * secv # reduc x ul in primul cadran
return x, 149 - 65 # se schimba valoarea
else:
x -= 3 * secv # reduc x ul in primul cadran
return x, 65

def process_input(n):
for i in range(n):
x = int(input())
if validate_input(x):
print("Input valid")
secv = get_secv(x)
x, c = reduce_to_first_cadran(x, secv)
yield x, secv, c
else:
print("Input invalid")

def main():
n = int(input())
lmax = 0
l = 0
start = False

for x, secv, c in process_input(n):
if x == 2 or x == 3:
c = 149 - c
if c == ord('T'):
if not start:
start = True
l = 1
else:
l += 1
else:
if all_bits(l + 1):
lmax = max(lmax, l)
l = 0
start = False

if all_bits(l + 1):
lmax = max(lmax, l)

if lmax:
print(lmax)
else:
print("NU EXISTA")

if __name__ == '__main__':
main()

</syntaxhighlight>

==Explicație cod==
Acest cod implementează o funcționalitate care primește un număr n și n valori întregi de la utilizator. Funcția verifică dacă fiecare valoare îndeplinește anumite condiții și, dacă da, efectuează anumite transformări și calculează lungimea celei mai lungi secvențe continue de caractere 'T' în codul ASCII obținut în urma transformărilor.

Funcția all_bits(x) primește un întreg și verifică dacă toți biții sunt setați la 1. Funcția validate_input(x) verifică dacă valoarea introdusă x este mai mică decât 2^61 și toți biții sunt setați la 1. Funcția get_secv(x) calculează cea mai mare putere de 4 mai mică decât valoarea introdusă x.

Funcția reduce_to_first_cadran(x, secv) primește două valori, o valoare întreagă x și o valoare secv și calculează în ce cadran se află x raportat la secv, reducând x la valoarea sa din primul cadran (între 0 și secv). Funcția returnează valoarea x și c, care este un număr în funcție de cadranul în care se află x.

Funcția process_input(n) primește un întreg n și citește n valori întregi de la utilizator. Pentru fiecare valoare, se verifică dacă aceasta îndeplinește condițiile necesare și, în caz afirmativ, se calculează secvența și cadranul corespunzătoare, și se returnează o secvență de trei valori: x, secv și c.

Funcția main() primește un întreg n și apelează funcția process_input(n) pentru a procesa valorile introduse. Pentru fiecare valoare x, se aplică anumite transformări și se calculează lungimea celei mai lungi secvențe continue de caractere 'T' în codul ASCII obținut. Lungimea maximă a secvenței este afișată la sfârșitul funcției.

În general, codul este folosit pentru a procesa și transforma date și pentru a calcula anumite valori specifice, cum ar fi lungimea celei mai lungi secvențe de caractere.

2716 - UnuDoi

2023-05-03T06:31:16Z

Cata:

==Cerința==
Se dă operația x:{1,2}→{1,2} astfel încât 1=2 și 2=1. Operația se poate extinde asupra oricărei secvențe formate cu cifre de 1 și 2, de exemplu 121121212=212212121.

Se consideră șirul infinit s format cu cifre de 1 și 2, generat incremental prin extindere, după următoarea regulă de concatenare:

* s1=1221
* s2=1221211221121221
* …
* sk+1=sksksksk, pentru orice număr natural k.

Dându-se un număr natural n, să se determine a n-a cifră a șirului infinit s.

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Programul va afișa pe ecran un mesaj de validare a datelor ("Date de intrare valide" pentru date valide; "Valoarea lui n trebuie sa fie intre 1 si 10^8" dacă n depășește valorile cerute) și a n-a cifră a șirului s.

==Restricții și precizări==
* 1 &les; n &les; 108

==Exemplu==
; Intrare
: Introduceti valoarea lui n: 11
; Ieșire
: Date de intrare valide
: 1
;Intrare
: Introduceti valoarea lui n: 20
; Ieșire
: Date de intrare valide
: 2

==Rezolvare==
<syntaxhighlight lang="python">
def validate_input(n):
if 1 <= n <= 10**8:
return True
else:
return False

def calculate_k(n):
k = 1
while n >= 4:
if n % 4 == 2 or n % 4 == 3:
k = 3 - k
if n % 4 != 0:
n = n // 4 + 1
else:
n = n // 4
if n % 4 == 2 or n % 4 == 3:
k = 3 - k
return k

if __name__ == "__main__":
n = int(input("Introduceti valoarea lui n: "))
if validate_input(n):
print("Date de intrare valide")
k = calculate_k(n)
print(k)
else:
print("Valoarea lui n trebuie sa fie intre 1 si 10^8")

</syntaxhighlight>

==Explicatie==
Acest cod Python definește două funcții și le folosește pentru a calcula o valoare k în funcție de valoarea introdusă de utilizator pentru n.

Funcția validate_input primește un argument n și returnează True dacă n se află în intervalul [1, 10^8], altfel returnează False.

Funcția calculate_k primește un argument n și calculează o valoare k folosind o serie de condiții. În esență, funcția împarte repetat valoarea n la 4 și schimbă valoarea lui k în funcție de restul împărțirii lui n la 4. Aceasta se repetă până când n devine mai mic decât 4.

În funcția principală, utilizatorul este întâmpinat cu un prompt și îi este cerut să introducă o valoare pentru n. Dacă valoarea este validă, funcția calculate_k este apelată cu n ca argument și valoarea rezultată pentru k este afișată. Dacă valoarea n este invalidă, se afișează un mesaj de eroare.

2553 - Josephus

2023-05-03T06:30:43Z

Cata:

Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!

==Cerința==
Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.

Josephus ar fi preferat să se predea. Pe ce poziție ar fi trebuit să se afle soldatul pentru a putea realiza acest lucru?

==Date de intrare==
Se va citi un singur număr natural nenul, n.

==Date de ieșire==
Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață, alături de un mesaj de validare a datelor introduse ("Input valid"; se afișează "n trebuie să fie între i și 10^18" în caz contrar).

==Restricții și precizări==
* 1 ≤ n ≤ 1018;
* Se garantează că există o soluție pentru oricare n;
==Exemplu==
; Intrare
: 41
; Ieșire
: Valid input
: 19
==Explicație==
1 ⇒ 2 
3 ⇒ 4 
… 
39 ⇒ 40 
41 ⇒ 1 
3 ⇒ 5 
… 
39 ⇒ 41 
3 ⇒ 7 
11 ⇒ 15 
……… 
19 ⇒ 35 

==Rezolvare==
<syntaxhighlight lang="python">
def calculate_exponent(n):
exponent = 0
save_n = n
while save_n != 1:
save_n //= 2
exponent += 1
return exponent

def is_power_of_two(n):
exponent = calculate_exponent(n)
return (1 << exponent) == n

def calculate_result(n):
exponent = calculate_exponent(n)
if is_power_of_two(n):
return 1
else:
return ((n - (1 << exponent)) << 1) + 1

def validate_n(n):
if not 1 <= n <= 10**18:
raise ValueError("n trebuie să fie între i și 10^18")
else:
print("Input valid")

if __name__ == "__main__":
n = int(input())
validate_n(n)
print(calculate_result(n))

</syntaxhighlight>

==Explicație cod==
Acest program implementează trei funcții care lucrează împreună pentru a verifica dacă un număr întreg n este o putere a lui 2 și pentru a calcula un rezultat bazat pe n.

Funcția "calculate_exponent" primește un număr întreg n și calculează exponentul său în baza 2. Exponentul este calculat prin împărțirea repetată a lui n la 2 până când n ajunge la valoarea 1, numărul de împărțiri fiind exponentul.

Funcția "is_power_of_two" primește un număr întreg n și verifică dacă este o putere a lui 2, comparându-l cu 2 ridicat la exponentul calculat în funcția anterioară.

Funcția "calculate_result" primește un număr întreg n și calculează rezultatul bazat pe aceasta. Dacă n este o putere a lui 2, rezultatul va fi 1, altfel va fi calculat după o formulă dată.

Funcția "validate_n" primește un număr întreg n și verifică dacă se încadrează între 1 și 10^18 inclusiv. Dacă n nu se încadrează în această plajă, funcția va arunca o excepție "ValueError".

În metoda "main", se primește un număr întreg n de la utilizator, se validează și se calculează și se afișează rezultatul apelând funcția "calculate_result".

1973 - Hambar2

2023-05-03T06:28:33Z

Cata:

==Enunț==
Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de arie maximă ce conține doar valori 0, pe care va construi un hambar, va câștiga mâna frumoasei Gîrcella.

==Cerința==
Ajutați-l pe Cavalerul de Aur să câștige această întrecere.

==Date de intrare==
Fișierul de intrare hambar2.in conține pe prima linie numerele N și M, reprezentând dimensinunea matricei respectiv numărul de pomi, iar pe următoarele M linii se vor găsi două numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

==Date de ieșire==
Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.
În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau instrucțiuni cu privire la n sau m).
==Restricții și precizări==
* 1 ≤ N, M ≤ 1000
* Nu se vor afla 2 sau mai mulți pomi în același loc.
==Exemplu==
; hambar2.in
: 5 5
: 1 3
: 2 1
: 2 5
: 5 1
: 5 5
:hambar2.out
: 12
; Consolă
: Valid input
==Rezolvare==
<syntaxhighlight lang="python">
nMAX = 1000

def clear(stiva):
while stiva:
stiva.pop()

def calculate_histogram(n, mat):
h = [0] * (n + 1)

for i in range(1, n+1):
for j in range(1, n+1):
if not mat[i][j]:
h[j] += 1
else:
h[j] = 0

return h

def calculate_left_boundary(n, h):
st = [0] * (n + 1)
stiva = []

for j in range(1, n+1):
while stiva and h[stiva[-1]] >= h[j]:
stiva.pop()

if not stiva:
st[j] = 0
else:
st[j] = stiva[-1]

stiva.append(j)

return st

def calculate_right_boundary(n, h):
dr = [0] * (n + 1)
stiva = []

for j in range(n, 0, -1):
while stiva and h[stiva[-1]] >= h[j]:
stiva.pop()

if not stiva:
dr[j] = n+1
else:
dr[j] = stiva[-1]

stiva.append(j)

return dr

def calculate_max_rect(n, mat):
arieMAX = 0

h = calculate_histogram(n, mat)
st = calculate_left_boundary(n, h)
dr = calculate_right_boundary(n, h)

for j in range(1, n+1):
arieMAX = max(arieMAX, h[j] * (dr[j] - st[j] - 1))

return arieMAX

def validate_input(n, m):
if not 1 <= n <= 1000:
raise ValueError("n trebuie să fie între 1 și 1000")
return 0
if not 1 <= m <= 1000:
raise ValueError("m trebuie să fie între 1 și 1000")
return 0
return 1

if __name__ == '__main__':
with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:
n, m = map(int, fin.readline().split())
if validate_input(n, m):
print("Input valid")

mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
for _ in range(m):
x, y = map(int, fin.readline().split())
mat[x][y] = True

fout.write(str(calculate_max_rect(n, mat)))

</syntaxhighlight>

==Explicație==
Acest cod implementează o soluție pentru problema de a găsi cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe într-o matrice dată de dimensiunea n x n. Mai precis, codul conține următoarele funcții:

- Funcția "clear" golește conținutul unei stive date ca argument;
- Funcția "calculate_histogram" calculează histograma pentru matricea dată și returnează o listă de dimensiune n+1, unde primul element este 0 și următoarele elemente reprezintă înălțimea coloanelor corespunzătoare din matrice;
- Funcțiile "calculate_left_boundary" și "calculate_right_boundary" calculează limitele stângi, respectiv drepte ale dreptunghiurilor care conțin fiecare coloană din matricea dată și care au înălțimile date de histograma calculată anterior. Acestea returnează două liste de dimensiune n+1, unde primul și ultimul element sunt 0, iar restul elementelor reprezintă limitele stângi sau drepte corespunzătoare;
- Funcția "calculate_max_rect" calculează cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe în matricea dată, folosind funcțiile "calculate_histogram", "calculate_left_boundary" și "calculate_right_boundary";
- Funcția "validate_input" verifică dacă valorile n și m sunt în intervalul [1, 1000] și generează o excepție în caz contrar.

În secțiunea "if __name__ == '__main__':" se deschide fișierul "hambar2.in" pentru citire și fișierul "hambar2.out" pentru scriere, se citește dimensiunea matricei și numărul de elemente albe din aceasta și se verifică dacă valorile introduse sunt valide. Dacă sunt, se construiește matricea folosind elementele citite și se apelează funcția "calculate_max_rect" pentru a calcula cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe. Rezultatul este scris în fișierul "hambar2.out".

2225 - complementar

2023-05-03T06:24:26Z

Cata:

Se consideră o matrice binară cu n linii și m coloane. Spunem că două linii L1, L2 din matrice sunt complementare dacă a[L1][j] ≠ a[L2][j], pentru orice j=1..m (adică acolo unde pe linia L1 este 0, pe linia L2 este 1 și invers).

==Cerința==
Să se determine numărul de perechi de linii (L1, L2) cu L1 < L2 cu proprietatea că sunt complementare.

==Date de intrare==
Fișierul de intrare complementar.in conține pe prima linie numerele n și m. Pe următoarele n linii, fără spații între ele, sunt câte m de valori binare.

==Date de ieșire==
Fișierul de ieșire complementar.out va conține un singur număr natural reprezentând numărul perechi de linii complementare.
În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau "Input în afara limitelor" în funcție de datele introduse).
==Restricții și precizări==
* 1 ≤ n ≤ 200 000
* 4 ≤ m ≤ 30
==Exemplu==
; complementar.in
: 5 6
: 101001
: 010110
: 010110
: 111111
: 000000
; complementar.out
: 3
; Consolă
: Valid input
==Explicație==
Cele trei perechi de linii complementare sunt (1,2), (1,3) și (4,5).

==Rezolvare==
<syntaxhighlight lang="python">
def read_input():
with open('complementar.in', 'r') as f:
n, m = map(int, f.readline().split())
return n, m

def validate_input(n, m):
if not (1 <= n <= 200000):
return False
if not (4 <= m <= 30):
return False
return True

def compute_model(m):
model = 0
for i in range(m):
model += (1 << i)
return model

def parse_binary(s):
x = 0
exponent = 0
for j in range(len(s) - 1, -1, -1):
if s[j] == '1':
x += (1 << exponent)
exponent += 1
return x

def read_data(n):
p = {}
with open('complementar.in', 'r') as f:
f.readline() # ignore first line
for i in range(n):
s = f.readline().strip()
x = parse_binary(s)
if x not in p:
p[x] = 0
p[x] += 1
return p

def compute_answer(p, model):
ans = 0
for e in p:
y = (model ^ e)
if y in p:
ans += p[e] * p[y]
p[y] = 0
return ans

def write_output(ans):
with open('complementar.out', 'w') as f:
f.write(str(ans) + '\n')

if __name__ == '__main__':
n, m = read_input()
if not validate_input(n, m):
print("Input în afara limitelor")
return
else:
print("Input valid")
model = compute_model(m)
p = read_data(n)
ans = compute_answer(p, model)
write_output(ans)

</syntaxhighlight>

==Explicație cod==
Acest cod este un program Python care citește date de intrare din fișierul 'complementar.in', validează aceste date, apoi citește date suplimentare și calculează un răspuns, pe care îl scrie în fișierul 'complementar.out'.

Funcția read_input() citește primele două valori din fișierul de intrare și le returnează ca o tuplă.

Funcția validate_input() primește cele două valori citite de funcția read_input() și verifică dacă sunt în limitele specificate. Dacă nu, funcția returnează False, altfel returnează True.

Funcția compute_model() primește o valoare m și calculează un model folosind un loop for care construiește o valoare binară formată din m cifre de 1.

Funcția parse_binary() primește o valoare binară sub forma unui șir de caractere și o convertește într-o valoare întreagă.

Funcția read_data() citește datele suplimentare din fișierul de intrare și le stochează într-un dicționar, numărul de apariții ale fiecărei valori binare fiind valoarea asociată cu cheia binară în dicționar.

Funcția compute_answer() primește dicționarul creat de funcția read_data() și modelul calculat de funcția compute_model(), calculează complementul fiecărei valori din dicționar și verifică dacă complementul este prezent în dicționar. Dacă este prezent, funcția calculează produsul numărului de apariții ale valorii inițiale și complementare și îl adaugă la răspuns. Funcția returnează răspunsul.

Funcția write_output() primește răspunsul și îl scrie în fișierul de ieșire 'complementar.out'.

Funcția main() este funcția principală care apelează celelalte funcții pentru a citi datele de intrare, valida datele, calcula răspunsul și scrie răspunsul în fișierul de ieșire. Dacă datele de intrare nu sunt valide, funcția afișează un mesaj de eroare și returnează.

Instrucțiunea if name == 'main': verifică dacă acest script este executat ca un program independent și, dacă este așa, apelează funcția main().

2700 - RadixSort

2023-05-03T06:22:42Z

Cata:

==Cerința==
Fiind dat un șir cu n elemente, nu neapărat distincte, se cere sortarea crescătoare a acestuia folosind metoda Radix Sort.

==Date de intrare==
Fișierul de intrare radixsort.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

==Date de ieșire==
Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat. În consolă se va scrie un mesaj de validare al input-ului("Input valid!" sau "Input invalid!" după caz).

==Restricții și precizări==
* 2 &les; n &les; 1.000.000;
* numerele de pe a doua linie a fișierului de intrare vor avea maximum 9 cifre.
==Exemplu==
; radixsort.in
: 8
: 170 20 45 75 90 802 24 2
; radixsort.out
: 2 20 24 45 75 90 170 802
; Ieșire consolă
: Input valid
==Rezolvare==
<syntaxhighlight lang="python">
import math

def getMax(n, arr):
maxX = arr[0]
for i in range(1, n):
if arr[i] > maxX:
maxX = arr[i]
return maxX

def validateInput(n, arr):
if n < 2 or n > 1000000:
return False

for i in range(n):
if abs(arr[i]) > 999999999:
return False

return True

def countingSort(n, exp, arr, output):
count = [0] * 32

for i in range(n):
count[(arr[i]//exp)%32] += 1

for i in range(1, 32):
count[i] += count[i - 1]

for i in range(n - 1, -1, -1):
output[count[(arr[i]//exp)%32] - 1] = arr[i]
count[(arr[i]//exp)%32] -= 1

for i in range(n):
arr[i] = output[i]

def radixSort(n, arr):
m = getMax(n, arr)

output = [0] * n

exp = 1
while m // exp > 0:
countingSort(n, exp, arr, output)
exp *= 32

if __name__ == '__main__':
with open("radixsort.in", "r") as fin:
with open("radixsort.out", "w") as fout:
n = int(fin.readline())
arr = list(map(int, fin.readline().split()))

if not validateInput(n, arr):
print("Input invalid!")
exit()
else:
print("Input valid!")

radixSort(n, arr)

for i in range(n):
fout.write(str(arr[i]) + ' ')

</syntaxhighlight>

==Explicație==
Acest cod implementează algoritmul de sortare radix sort pe o listă de întregi.

Funcția `getMax(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`, și returnează cel mai mare element din listă.

Funcția `validateInput(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`, și returnează `True` dacă input-ul este valid (adică `n` este între 2 și 1000000 și toți elementele din listă au valori absolute mai mici decât 999999999) și `False` altfel.

Funcția `countingSort(n, exp, arr, output)` primește ca parametrii un număr întreg `n`, un număr întreg `exp`, o listă de `n` întregi `arr` și o listă de `n` întregi `output`. Implementează algoritmul de sortare counting sort pentru o cifră specifică (dată de `exp`), în baza 32. Folosește un array `count` de dimensiune 32 pentru a număra de câte ori apare fiecare cifră și apoi reordonează lista `arr` în ordinea specificată de cifra respectivă.

Funcția `radixSort(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`. Implementează algoritmul de sortare radix sort, iterând prin fiecare cifră a numerelor și apelând funcția `countingSort` pentru fiecare cifră în parte, începând cu cifra cea mai puțin semnificativă.

Funcția `__main__` citește input-ul din fișierul "radixsort.in", validează input-ul folosind funcția `validateInput`, sortează lista de numere folosind `radixSort`, și afișează rezultatul în fișierul "radixsort.out".

1924 - QStiva

2023-05-03T06:18:43Z

Cata:

==Cerința==
Se dă o stivă inițial vidă. Să se efectueze Q operații de forma:

1 x: Se adaugă x în stivă.
2: Se șterge elementul din vârful stivei.
3 S: Se întreabă dacă se poate scrie valoarea S ca sumă de elemente aflate în stivă. Fiecare element poate fi folosit o singură dată în calcularea sumei. Răspunsul va fi 1 în caz afirmativ și 0 în caz negativ.

==Date de intrare==
Fișierul de intrare qstiva.in conține pe prima linie numărul Q, iar pe următoarele Q linii se vor afla operațiile descrise mai sus.

==Date de ieșire==
Fișierul de ieșire qstiva.out va conține răspunsurile operațiilor de tipul 3, câte un răspuns pe linie, în ordinea în care acestea apar în fișierul de intrare. În consolă se va afișa un mesaj de validare a datelor introduse în fișierul de intrare ("Input valid" sau "Input invalid" după caz).

==Restricții și precizări==
* 1 &les; Q &les; 100000
* pentru o operație de tipul 1, 1 ≤ x ≤ 1000
* pentru o operație de tipul 3, 1 ≤ S ≤ 1000
* nu se vor efectua operații de tipul 2 sau de tipul 3 dacă stiva este goală.

==Exemplu==
; qstiva.in

: 8
: 1 12
: 2
: 1 1
: 3 2
: 1 2
: 1 12
: 3 13
: 2
; qstiva.out
: 0
: 1
; Ieșire consolă
: Input valid
==Rezolvare==
<syntaxhighlight lang="python">
import sys
from typing import List
from bitarray import bitarray

nmax = 100001
Smax = 1000

def validate_input(queries: List[List[int]]) -> bool:
if not 1 <= len(queries) <= 100000:
return False
stack_size = 0
for query in queries:
t = query[0]
if t == 1:
x = query[1]
if not 1 <= x <= 1000:
return False
stack_size += 1
elif t == 2:
if stack_size == 0:
return False
stack_size -= 1
elif t == 3:
x = query[1]
if not 1 <= x <= 1000:
return False
if stack_size == 0:
return False
return True

def read_input() -> List[List[int]]:
with open("qstiva.in", "r") as fin:
Q = int(fin.readline().strip())
queries = []
for _ in range(Q):
query = list(map(int, fin.readline().split()))
queries.append(query)
if not validate_input(queries):
raise ValueError("Input invalid")
return queries

def solve_queries(queries: List[List[int]]) -> List[int]:
n = 0
dp = [bitarray(Smax+2) for _ in range(nmax)]
dp[0][0] = 1
ans = []
for query in queries:
t = query[0]
if t == 1:
x = query[1]
n += 1
dp[n].setall(False)
for i in range(Smax-x+1, Smax+1):
dp[n][i] = dp[n-1][i]
for i in range(Smax-x, -1, -1):
if dp[n-1][i]:
dp[n][i+x] = dp[n][i] = True
elif t == 2:
n -= 1
elif t == 3:
x = query[1]
ans.append(int(dp[n][x]))
return ans

def write_output(ans: List[int]) -> None:
with open("qstiva.out", "w") as fout:
for a in ans:
fout.write(str(a) + "\n")

if __name__ == "__main__":
try:
queries = read_input()
print("Input valid", file=sys.stdout)
except ValueError as e:
print(e, file=sys.stderr)
sys.exit(1)
ans = solve_queries(queries)
write_output(ans)

</syntaxhighlight>

==Explicație==
Funcția validate_input verifică dacă input-ul este valid, adică dacă este în conformitate cu restricțiile problemei. Funcția read_input citește input-ul din fișierul "qstiva.in" și îl validează folosind funcția validate_input. Funcția solve_queries primește input-ul validat și rezolvă problema "Q-Stack" utilizând tehnica de programare dinamică. Funcția write_output scrie rezultatul în fișierul "qstiva.out". Funcția main este funcția principală care apelează celelalte funcții în ordine pentru a citi input-ul, a rezolva problema și a scrie rezultatul.

Algoritmul utilizează o matrice dp de dimensiuni nmax x Smax+2, unde dp[i][j] este True dacă există un subsir de lungime i cu o sumă de elemente egală cu j. Matricea este inițializată cu dp[0][0] = True, pentru că există un subsir de lungime zero cu suma elementelor zero. Algoritmul primește trei tipuri de interogări:

Adaugă elementul x la stack.
Elimină ultimul element adăugat la stack.
Verifică dacă există un subsir de elemente care au o sumă egală cu x.
Pentru fiecare interogare de tipul 1, se creează un nou rând în matricea dp, inițializat cu False. Pentru fiecare element i din matricea anterioară care are valoarea True, se actualizează valorile dp[n][i+x] și dp[n][i] pe baza valorii anterioare dp[n-1][i].

Pentru fiecare interogare de tipul 2, se elimină ultimul rând din matricea dp.

Pentru fiecare interogare de tipul 3, se verifică dacă există un subsir de elemente din stack care au o sumă egală cu x. Dacă da, se adaugă 1 în lista de rezultate ans, altfel se adaugă 0.

În final, lista de rezultate este scrisă în fișierul "qstiva.out".

1899 - AfisMinime

2023-05-03T06:16:24Z

Cata:

==Cerința==
Se dă un vector cu n elemente, numere naturale. Fie două numere x și y, cu proprietatea că 1 ≤ x , y ≤ n.

Scrieți un program care răspunde la m întrebări de tipul “Care este elementul minim din intervalul [x , y]?”.

==Date de intrare==
Pe prima linie a fișierului afisminime.in sunt date numerele n și m. Pe a doua linie se vor afla n numere naturale, fiind elementele vectorului. Următoarele m linii vor conține câte 2 numere reprezentând valorile x și y, care definesc întrebările.

==Date de ieșire==
În fișierul de ieșire afisminime.out, se va afișa un mesaj de validare a datelor, după care vor fi m linii, fiecare conținând câte un număr, pe linia i aflându-se răspunsul pentru întrebarea i. Consola rămâne goală.

==Restricții și precizări==
* 1 ≤ n ≤ 100.000
* 1 ≤ m ≤ 1.000.000
* 1 ≤ x , y ≤ n
==Exemplu==
; afisminime.in
: 5 4
: 1 3 18 2 3
: 1 5
: 2 3
: 3 4
: 2 4
; afisminime.out
: Input valid
: 1
: 3
: 2
: 2
==Explicație==
în intervalul [1 , 5] minimul este 1
în intervalul [2 , 3] minimul este 3
în intervalul [3 , 4] minimul este 2
în intervalul [2 , 4] minimul este 2

==Rezolvare==
<syntaxhighlight lang="python">
import sys
from typing import List

def query(i: int, j: int, r: List[List[int]], lg2: List[int]) -> int:
e = lg2[j - i + 1]
p2 = 1 << e
return min(r[e][i + p2 - 1], r[e][j])

def solve(n: int, q: int, arr: List[int]) -> List[int]:
NMAX = 10 ** 5
r = [[0] * (NMAX + 1) for _ in range(17)]
lg2 = [-1] * (NMAX + 1)
res = []

for i in range(1, n + 1):
x = arr[i-1]
r[0][i] = x
lg2[i] = 1 + lg2[i >> 1]

for i in range(1, lg2[n] + 1):
for j in range(1 << i, n + 1):
r[i][j] = min(r[i - 1][j - (1 << (i - 1))], r[i - 1][j])

for i in range(q):
x, y = map(int, input().split())
res.append(query(x, y, r, lg2))

return res

def validate(n: int, q: int, arr: List[int]) -> bool:
if not (1 <= n <= 100000):
return False
if not (1 <= q <= 1000000):
return False
for i in arr:
if not (1 <= i <= n):
return False
return True

if __name__ == "__main__":
# Input and output files
sys.stdin = open('afisminime.in', 'r')
sys.stdout = open('afisminime.out', 'w')

n, q = map(int, input().split())
arr = [int(input()) for i in range(n)]

if not validate(n, q, arr):
print("Input invalid")
sys.exit()
else:
print("Input valid")

res = solve(n, q, arr)
for r in res:
print(r)

sys.stdin.close()
sys.stdout.close()

</syntaxhighlight>

==Explicatie cod==
Acest cod Python definește trei funcții și un validator de intrare pentru a rezolva o problemă specifică de programare.

Funcția "query" primește ca parametri o pereche de numere întregi și două liste de întregi. Scopul acestei funcții este de a returna valoarea minimă din intervalul inclus între cele două numere întregi în prima listă, utilizând informațiile stocate în a doua listă.

Funcția "solve" primește ca parametri un număr întreg n, un număr întreg q și o listă de întregi. Scopul acestei funcții este de a rezolva problema specifică de programare, unde trebuie să găsești valoarea minimă dintr-un interval de elemente din lista dată. Aceasta construiește o matrice pentru a memora informațiile necesare, apoi calculează valorile minime pentru fiecare interval de dimensiuni diferite, folosind funcția "query", și le stochează într-o listă numită "res".

Funcția "validate" primește ca parametri același tip de date ca funcția "solve". Scopul acestei funcții este de a verifica dacă input-ul dat este valid pentru problema specifică de programare. Aceasta verifică dacă dimensiunile listei de intrare și a intervalului sunt în limitele permise și dacă toate elementele din lista de intrare sunt cuprinse în intervalul de la 1 la n.

În blocul "if name == "main":", codul deschide fișierele de intrare și ieșire, citeste input-ul, verifică dacă input-ul este valid și apelează funcția "solve" dacă input-ul este valid. În cele din urmă, funcția "solve" afișează output-ul în fișierul de ieșire și închide fișierele de intrare și ieșire.

4206 - CifDiv3Rec

2023-05-03T06:10:56Z

Cata:

== Cerinţa ==
Să se scrie o funcție Python recursivă care să returneze numărul cifrelor divizibile cu 3 ale unui număr natural n transmis ca parametru.

== Restricţii şi precizări ==
* Numele funcției va fi CifDiv3Rec
* Funcția va avea un parametru reprezentând numărul dat n
* 0 &les; n &les; 2.000.000.000

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte.", apoi pe un rând nou un mesaj dat în funcție de valoarea returnată de funcția CifDiv3Rec, reprezentând numărul cerut. În cazul în care numărul introdus depășește limitele date, se va afișa "Numarul introdus nu este valid.", iar dacă numărul introdus nu este întreg, se va afișa "Nu ati introdus un numar intreg."

==Exemplu==
; Intrare
: Introduceți un număr întreg pozitiv: 2009376
; Ieșire
: Datele introduse sunt corecte.
: Numărul de cifre divizibile cu 3 din numărul introdus este: 5

== Rezolvare ==
<syntaxhighlight lang="python">
def validate_n(n):
if isinstance(n, int) and n >= 0 and n <= 2_000_000_000:
return True
else:
return False

def CifDiv3Rec(n):
if n == 0:
return 0
elif n % 10 % 3 == 0:
return 1 + CifDiv3Rec(n // 10)
else:
return CifDiv3Rec(n // 10)

if __name__ == "__main__":
n = input("Introduceți un număr întreg pozitiv: ")
try:
n = int(n)
if validate_n(n):
result = CifDiv3Rec(n)
print("Datele introduse sunt corecte.")
if result == 0:
print("Nu există cifre divizibile cu 3 în numărul introdus.")
else:
print(f"Numărul de cifre divizibile cu 3 din numărul introdus este: {result}")
else:
print("Numărul introdus nu este valid.")
except ValueError:
print("Nu ați introdus un număr întreg.")
</syntaxhighlight>

==Explicație==
Acest cod este scris în Python și este alcătuit din două funcții și o secvență de cod care le utilizează.

Funcția `validate_n(n)` primește un singur argument, `n`, și verifică dacă acesta este un număr întreg pozitiv în intervalul [0, 2_000_000_000]. Funcția returnează `True` dacă `n` este valid și `False` altfel.

Funcția `CifDiv3Rec(n)` primește un singur argument, `n`, și returnează numărul de cifre divizibile cu 3 din numărul `n`. Funcția face acest lucru recursiv prin împărțirea numărului la 10 (pentru a elimina ultima cifră) și verificarea dacă acea cifră este divizibilă cu 3. Dacă este divizibilă, funcția adaugă 1 la rezultat și continuă recursiv cu restul numărului. Dacă cifra nu este divizibilă cu 3, funcția continuă recursiv cu restul numărului. Când numărul devine 0, recursivitatea se oprește și funcția returnează rezultatul acumulat.

În secvența de cod care utilizează aceste funcții, utilizatorul este întâi rugat să introducă un număr întreg pozitiv. Acest număr este apoi validat prin apelarea funcției `validate_n(n)`. Dacă numărul este valid, este apelată funcția `CifDiv3Rec(n)` pentru a calcula numărul de cifre divizibile cu 3 din numărul introdus. Dacă rezultatul este 0, se afișează un mesaj corespunzător, altfel se afișează numărul de cifre divizibile cu 3 găsite. Dacă numărul introdus nu este valid sau nu este un număr întreg, se afișează un mesaj corespunzător.

1240 - Ab3

2023-05-03T06:09:17Z

Cata:

==Cerința==
Să se determine pentru n numere a valoarea b maximă astfel încât b3 + b &les; a.

==Date de intrare==
Datele de intrare conțin pe prima linie numărul n, iar pe următoarele n linii câte un număr a.

==Date de ieșire==
Datele de ieșire vor conține n linii cu câte un număr fiecare, răspunsul la fiecare întrebare, pe lângă mesajul de validare a datelor introduse ("Date de intrare valide" pentru date valide, "Date de intrare invalide" în vaz contrar).

==Restricții și precizări==
* 1 &les; n &les; 100.000
* 0 &les; a &les; 1018

==Exemple==
; Intrare
: 5
: 1
: 9
: 36
: 27
: 89
; Ieșire
: Date de intrare valide
: 0
: 1
: 3
: 2
: 4

==Explicație==
: 13 + 1 = 2
: 23 + 2 = 10
: 33 + 3 = 30
: 43 + 4 = 68
: 53 + 5 = 130

==Rezolvare==
<syntaxhighlight lang="python">
def validate_input(n, values):
if n < 1 or n > 100000:
return False
for value in values:
if value < 0 or value > 10**18:
return False
return True

def solve_problem(n, values):
st = 1 << 19
results = []
for i in range(n):
a = values[i]
b = 0
for step in range(st, 0, -1):
if (b + step) * (b + step) * (b + step) + (b + step) <= a:
b += step
results.append(str(b))
return results

if __name__ == '__main__':
n = int(input())
values = []
for i in range(n):
values.append(int(input()))

if validate_input(n, values):
print("Date de intrare valide")
results = solve_problem(n, values)
for result in results:
print(result)
else:
print("Date de intrare invalide")
</syntaxhighlight>
==Explicație cod==
Această bucată de cod are două funcții principale:

1. Funcția `validate_input(n, values)`: Această funcție primește doi parametri: un număr întreg `n` și o listă de numere întregi `values`. Funcția verifică dacă `n` este în intervalul [1, 100000] și dacă fiecare valoare din lista `values` este în intervalul [0, 10^18]. Dacă oricare dintre aceste condiții nu este îndeplinită, funcția returnează `False`. În caz contrar, returnează `True`.

2. Funcția `solve_problem(n, values)`: Această funcție primește doi parametri: un număr întreg `n` și o listă de numere întregi `values`. Funcția rezolvă o problemă specifică și returnează o listă de șiruri de caractere. Pentru fiecare valoare `a` din lista `values`, funcția calculează cel mai mare număr întreg `b` pentru care `(b + step) ^ 3 + (b + step) <= a` pentru un anumit interval de `step`. Rezultatul final este o listă de șiruri de caractere, care reprezintă valorile pentru fiecare `b` calculat pentru fiecare valoare `a`.

În funcția principală, se citește întâi numărul `n` și valorile asociate. Dacă valorile sunt valide (verificate prin apelul funcției `validate_input(n, values)`), atunci se afișează "Date de intrare valide". Apoi, se calculează rezultatele prin apelul funcției `solve_problem(n, values)` și se afișează. În caz contrar, se afișează "Date de intrare invalide".

3489 - Numara punctele

2023-05-03T06:07:39Z

Cata:

==Cerința==
Considerăm o suprață plană în formă de pătrat având latura de 100 de unități și două mulțimi:
* Mulțimea P de puncte având coordonatele numere reale pozitive mai mici decat 100 (deci aparținând pătratului).
* Mulțimea ordonată C de cercuri având centrul în același pătrat și cu raza variabilă (se poate întâmpla ca centrul să fie în punctul p(1,1) și cercul să aibă raza de 3, deci să aibă o porțiune înafara pătratului).

Se dorește să se stabilească, pentru fiecare dintre cercurile din mulțimea C, câte puncte din mulțimea P se află în interior (sau pe marginea acestuia).

==Date de intrare==
Programul citește de la tastatură numărul n de puncte, iar apoi n cupluri de numere reale, separate prin spații reprezentând coordonatele fiecărui punct. După ce a citit valorile reprezentând coordonatele punctelor, se va citi numărul m de cercuri și vor apoi cele m triplete reprezentând coordonatele centrului cercului respectiv raza cercului.

==Date de ieșire==
În cazul în care datele sunt valide, se va afișa un mesaj de confirmare ("Datele introduse sunt corecte."; "Unul sau mai multe numere introduse nu sunt valide." se va afișa în caz contrar), iar pentru fiecare cerc citit se va afișa pe câte o linie diferită câte puncte sunt in interiorul său sau pe frontieră. În caz contrar, se va afișa un mesaj de eroare.

==Restricții și precizări==
* 1≤n≤100000
* Pentru fiecare punct p(x,y) avem x∈[0,100] respectiv y∈[0,100]
* 1≤m≤10000
* Pentru fiecare cerc c(x,y,r) avem x∈[0,100], y∈[0,100] și r∈[0,30]

==Exemplu==
; Intrare
: 3
: 6.39 24.96
: 6.23 6.17
: 20.0 20.0
: 3
: 23.05 83 10.57
: 15.00 15.00 10.0
: 10.0 20.0 10
; Ieșire
: Datele introduse sunt corecte.
: 0
: 1
: 2

==Rezolvare==
<syntaxhighlight lang="python">
def validare(n: int, puncte: list[tuple[float, float]], m: int, cercuri: list[tuple[float, float, float]]) -> bool:
# verificam numarul de puncte si de cercuri
if not 1 <= n <= 100000 or not 1 <= m <= 10000:
return False

# verificam coordonatele punctelor si ale cercurilor
for p in puncte:
if not 0 <= p[0] <= 100 or not 0 <= p[1] <= 100:
return False

for c in cercuri:
if not 0 <= c[0] <= 100 or not 0 <= c[1] <= 100 or c[2] <= 0:
return False

return True

def numar_puncte_in_cercuri(puncte, cercuri):
numar_puncte = []
for cerc in cercuri:
num_puncte_in_cerc = 0
for punct in puncte:
distanta = ((punct[0] - cerc[0]) ** 2 + (punct[1] - cerc[1]) ** 2) ** 0.5
if distanta <= cerc[2]:
num_puncte_in_cerc += 1
numar_puncte.append(num_puncte_in_cerc)
return numar_puncte

if __name__ == "__main__":
# citirea numarului de puncte
n = int(input())
# citirea coordonatelor fiecarui punct
puncte = []
for i in range(n):
x, y = input().split()
x = float(x)
y = float(y)
puncte.append((x, y))
# citirea numarului de cercuri
m = int(input())
# citirea coordonatelor si razei fiecarui cerc
cercuri = []
for i in range(m):
x, y, r = input().split()
x = float(x)
y = float(y)
r = float(r)
cercuri.append((x, y, r))
# validarea datelor introduse
if validare(n, puncte, m, cercuri):
print("Datele introduse sunt corecte.")
# numarul de puncte din interiorul fiecarui cerc
numar_puncte = numar_puncte_in_cercuri(puncte, cercuri)
# afisarea numarului de puncte din interiorul fiecarui cerc
for i in numar_puncte:
print(i)
else:
print("Unul sau mai multe numere introduse nu sunt valide.")
</syntaxhighlight>

==Explicație==
Acest cod are două funcții definite și o secțiune principală de cod.

Funcția `validare` primește ca argumente un număr întreg `n`, o listă de perechi de coordonate (x,y) reprezentând punctele și un număr întreg `m` și o listă de tupluri (x,y,r) reprezentând cercurile. Funcția verifică dacă numărul de puncte și cercuri este în limitele permise și dacă coordonatele și razele cercurilor sunt valide (în intervalul 0-100). În cazul în care aceste condiții nu sunt îndeplinite, funcția returnează `False`, altfel returnează `True`.

Funcția `numar_puncte_in_cercuri` primește ca argumente lista de puncte și cea de cercuri și returnează o listă cu numărul de puncte din fiecare cerc.

În secțiunea principală de cod, mai întâi se citește numărul de puncte, apoi coordonatele fiecărui punct, apoi numărul de cercuri și coordonatele și razele acestora. După aceea se validează datele introduse. În cazul în care sunt valide, se afișează mesajul "Datele introduse sunt corecte." și se calculează numărul de puncte din fiecare cerc cu ajutorul funcției `numar_puncte_in_cercuri`, iar apoi se afișează numărul de puncte din fiecare cerc. În caz contrar, se afișează mesajul "Unul sau mai multe numere introduse nu sunt valide.".

2716 - UnuDoi

2023-05-03T06:03:13Z

Cata:

Se dă operația x:{1,2}→{1,2} astfel încât 1=2 și 2=1. Operația se poate extinde asupra oricărei secvențe formate cu cifre de 1 și 2, de exemplu 121121212=212212121.

Se consideră șirul infinit s format cu cifre de 1 și 2, generat incremental prin extindere, după următoarea regulă de concatenare:

* s1=1221
* s2=1221211221121221
* …
* sk+1=sksksksk, pentru orice număr natural k.
==Cerința==
Dându-se un număr natural n, să se determine a n-a cifră a șirului infinit s.

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Programul va afișa pe ecran un mesaj de validare a datelor ("Date de intrare valide" pentru date valide; "Valoarea lui n trebuie sa fie intre 1 si 10^8" dacă n depășește valorile cerute) și a n-a cifră a șirului s.

==Restricții și precizări==
* 1 &les; n &les; 108

==Exemplu==
; Intrare
: Introduceti valoarea lui n: 11
; Ieșire
: Date de intrare valide
: 1
;Intrare
: Introduceti valoarea lui n: 20
; Ieșire
: Date de intrare valide
: 2

==Rezolvare==
<syntaxhighlight lang="python">
def validate_input(n):
if 1 <= n <= 10**8:
return True
else:
return False

def calculate_k(n):
k = 1
while n >= 4:
if n % 4 == 2 or n % 4 == 3:
k = 3 - k
if n % 4 != 0:
n = n // 4 + 1
else:
n = n // 4
if n % 4 == 2 or n % 4 == 3:
k = 3 - k
return k

if __name__ == "__main__":
n = int(input("Introduceti valoarea lui n: "))
if validate_input(n):
print("Date de intrare valide")
k = calculate_k(n)
print(k)
else:
print("Valoarea lui n trebuie sa fie intre 1 si 10^8")

</syntaxhighlight>

==Explicatie==
Acest cod Python definește două funcții și le folosește pentru a calcula o valoare k în funcție de valoarea introdusă de utilizator pentru n.

Funcția validate_input primește un argument n și returnează True dacă n se află în intervalul [1, 10^8], altfel returnează False.

Funcția calculate_k primește un argument n și calculează o valoare k folosind o serie de condiții. În esență, funcția împarte repetat valoarea n la 4 și schimbă valoarea lui k în funcție de restul împărțirii lui n la 4. Aceasta se repetă până când n devine mai mic decât 4.

În funcția principală, utilizatorul este întâmpinat cu un prompt și îi este cerut să introducă o valoare pentru n. Dacă valoarea este validă, funcția calculate_k este apelată cu n ca argument și valoarea rezultată pentru k este afișată. Dacă valoarea n este invalidă, se afișează un mesaj de eroare.

3050 - ncif

2023-05-03T05:59:23Z

Cata:

==Cerința==
Fie n un numar natural.
Pentru n seturi de doua numere naturale a si b, sa se afiseze cate cifre are ab.

==Date de intrare==
Fișierul de intrare ncif.in conține pe prima linie numărul n, iar pe urmatoarele n linii cate doua numere naturale a si b separate prin spații.

==Date de ieșire==
Fișierul de ieșire ncif.out va conține un mesaj de validare a datelor ("Date de intrare valide"), și pe fiecare linie următoare un număr reprezentând câte cifre are ab. În cazul în care a sau b depășesc limitele date, se va afișa "a și b trebuie să fie între 0 și 100000". Consola va rămâne goală, întrucât mesajul de validare apare în fișier.

==Restricții și precizări==
* 1 &les; n &les; 10.000
* 0 &les; a, b &les; 100.000

==Exemplu==
; ncif.in
: 4
: 1 1
: 2 10
: 3 9
: 100 100
; ncif.out
: Date de intrare valide
: 1
: 4
: 5
: 201

==Rezolvare==
<syntaxhighlight lang="python">
from math import log10

def calculeaza_numar_cifre(a: int, b: int) -> int:
if not (0 <= a <= 100000 and 0 <= b <= 100000):
raise ValueError("a și b trebuie să fie între 0 și 100000")
return int(b * log10(a)) + 1

def proceseaza_intrari(n: int, intrari: list) -> list:
rezultate = []
for i in range(n):
a, b = intrari[i]
rezultate.append(calculeaza_numar_cifre(a, b))
return rezultate

def scrie_fisier_iesire(nume_fisier: str, rezultate: list, valid: bool):
with open(nume_fisier, "w") as f:
if valid:
print("Date de intrare valide", file=f)
for r in rezultate:
print(r, file=f)

if __name__ == "__main__":
with open("ncif.in") as f:
n = int(next(f))
intrari = [list(map(int, next(f).split())) for _ in range(n)]
rezultate = proceseaza_intrari(n, intrari)
scrie_fisier_iesire("ncif.out", rezultate, True)

</syntaxhighlight>

==Explicatie==
Acest program primește un fișier de intrare "ncif.in", care conține un număr n și n perechi de numere întregi a și b. Programul calculează numărul de cifre din b la puterea a și stochează rezultatele într-un fișier de ieșire "ncif.out".

Funcția "calculeaza_numar_cifre" primește două numere întregi a și b și calculează numărul de cifre din b la puterea a, utilizând formula logaritmică.

Funcția "proceseaza_intrari" primește numărul de intrări și lista de perechi de numere întregi a și b, apoi apelază funcția "calculeaza_numar_cifre" pentru fiecare pereche de numere și stochează rezultatele într-o listă "rezultate".

Funcția "scrie_fisier_iesire" primește numele fișierului de ieșire și listă de rezultate și scrie fiecare rezultat în fișierul de ieșire.

În final, în blocul "main", programul citește datele de intrare din fișierul "ncif.in", procesează intrările și scrie rezultatele în fișierul "ncif.out".

3100 - suma perm circ

2023-05-03T05:55:05Z

Cata:

==Cerința==
Scrieți un program care citește un număr natural n și care să calculeze și să afișeze suma S a tuturor numerelor obținute prin permutări circulare ale cifrelor lui n cu o poziție.

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Programul va afișa pe ecran mesajul de validare ("Date de intrare valide") și numărul S, reprezentând suma cerută.
În cazul în care datele nu sunt valide, se va afișa un mesaj corespunzător care descrie eroarea dată.

==Restricții și precizări==
* n are cel mult 100.000 de cifre

==Exemplu==
; Intrare
: 165
; Ieșire
: Date de intrare valide
: 1332
Numere obținute din 165 prin permutări circulare sunt 165, 651 și 516, iar suma lor este 1332.

==Rezolvare==
<syntaxhighlight lang="python>
def validate_input(s):
if len(s) > 100000:
print("Error: n are mai mult de 100000 de cifre")
return False
for c in s:
if not c.isdigit():
print("Error: n trebuie să conțină doar cifre")
return False
return True

def citire(A):
s = input()
if not validate_input(s):
return
else:
print("Date de intrare valide")
l = len(s)
for i in range(l-1, -1, -1):
A[l-i] = int(s[i])
A[0] = l

def afisare(A):
for i in range(A[0], 0, -1):
print(A[i], end='')

def prod(B, x):
t = 0
for i in range(1, B[0]+1):
t = B[i] * x + t
B[i] = t % 10
t //= 10
while t:
B[0] += 1
B[B[0]] = t % 10
t //= 10

if __name__ == "__main__":
N = [0] * 100001
S = [0] * 100001
citire(N)
S[0] = N[0]
for i in range(1, N[0]+1):
S[i] = 1
sumcf = sum(N[1:N[0]+1])
prod(S, sumcf)
afisare(S)

</syntaxhighlight>

==Explicație==
Acest program efectuează următoarele operații:

1. Funcția "validate_input(s)" primește un șir de caractere "s" și verifică dacă acesta are lungimea mai mică sau egală cu 100.000 și dacă toate caracterele din "s" sunt cifre. În cazul în care una dintre aceste condiții nu este îndeplinită, se afișează un mesaj de eroare și se returnează valoarea "False", altfel se returnează valoarea "True".

2. Funcția "citire(A)" primește un vector "A" și citește un șir de caractere "s" de la tastatură. Apoi, apelează funcția "validate_input(s)" pentru a verifica dacă șirul "s" este valid. Dacă acesta nu este valid, se încheie funcția, altfel se initializează vectorul "A" cu cifrele din "s" și se actualizează prima poziție a vectorului cu lungimea șirului "s".

3. Funcția "afisare(A)" primește un vector "A" și afișează cifrele din vector în ordine inversă.

4. Funcția "prod(B, x)" primește un vector "B" și un număr întreg "x" și efectuează înmulțirea vectorului "B" cu numărul "x". Mai precis, se parcurge vectorul "B" și se înmulțește fiecare element cu "x", ținând cont și de restul din împărțirea cu 10, iar rezultatul este reținut într-o variabilă "t". Apoi, fiecare element din "B" este actualizat cu restul din împărțirea dintre produsul corespunzător și 10, iar variabila "t" este actualizată cu câtul împărțirii dintre produsul corespunzător și 10. Dacă variabila "t" mai are valoare, aceasta este adăugată la finalul vectorului "B", iar prima poziție a vectorului este actualizată cu noua lungime a vectorului.

5. În blocul principal de cod, se declară două vectori "N" și "S" cu o capacitate de 100.001 elemente și se inițializează cu valoarea 0. Se apelează funcția "citire(N)" pentru a citi un număr întreg mare de la tastatură și se inițializează vectorul "S" cu valorile 1 pe primele "N[0]" poziții. Se calculează suma cifrelor din numărul "N" și se stochează în variabila "sumcf". Apoi, se apelează funcția "prod(S, sumcf)" pentru a efectua produsul dintre vectorul "S" și suma cifrelor. În final, se apelează funcția "afisare(S)" pentru a afișa rezultatul înmulțirii.

3223 - Scobitoare

2023-05-03T05:52:22Z

Cata:

==Cerința==
Lui Ion îi plac scobitorile. Norocul său a fost că black friday tocmai a venit și a cumpărat un număr infinit de scobitori (să zicem că o duce destul de bine). Ținând cont că are extrem de multe scobitori, el a vrut să se joace cu ele, așa că a creat un joc.

La primul pas, el pune o singură scobitoare în mijlocul mesei. Începând cu al doilea pas, el pune câte o scobitoare la fiecare capăt liber al scobitorilor plasate până acum, astfel încât cele două scobitori sunt perpendiculare și mijlocul scobitorii noi se afla la vârful scobitorii vechi. Un vârf de scobitoare este liber dacă nu atinge o altă scobitoare.

Determinați
: 1. Numărul de scobitori aflate pe masă la pasul N.
: 2. Numărul de scobitori care au fost adăugate la pasul N.

==Date de intrare==
Fișierul de intrare scobitoare.in conține pe prima linie două numere: P, care va reprezenta cerința, și N, cu semnificația din enunț.

==Date de ieșire==
Fișierul de ieșire scobitoare.out va conține pe prima linie mesajul de validare a datelor ("Date de intrare valide" sau "Date de intrare invalide", în funcție de validitatea datelor), iar pe următorul rând numărul cerut.

==Restricții și precizări==
* 1 &les; n &les; 1000

==Exemplu==
; scobitoare.in
: 2 197
; scobitoare.out
: Date de intrare valide
: 60

==Rezolvare==
<syntaxhighlight lang="python">
import math

def T(n):
if n == 1:
return 1
elif n == 2:
return 3
elif n == 3:
return 7
elif n == 4:
return 11
else:
Puterea = 0
PutereDeDoi = 1
while PutereDeDoi < n:
Puterea += 1
PutereDeDoi *= 2

if PutereDeDoi == n:
return (int(math.pow(2, 2 * Puterea + 1)) + 1) // 3
else:
PutereDeDoi = PutereDeDoi // 2
return T(PutereDeDoi) + 2 * T(n - PutereDeDoi) + T(n - PutereDeDoi + 1) - 1

def validate_input(n):
if n < 1 or n > 1000:
return False
else:
return True

def read_input():
with open("scobitoare.in", "r") as f:
p = int(f.readline())
n = int(f.readline())
if not validate_input(n):
with open("scobitoare.out", "w") as g:
g.write("Date de intrare invalide")
return
return p, n

def write_output(output):
with open("scobitoare.out", "w") as g:
g.write("Date de intrare valide\n")
g.write(str(output))

if __name__ == "__main__":
inputs = read_input()
if inputs:
p, n = inputs
if p == 1:
output = T(n)
else:
output = T(n) - T(n - 1)
write_output(output)

</syntaxhighlight>
==Explicație cod==
Acest cod este scris în limbajul Python și conține următoarele funcții:

1. Funcția "T(n)" calculează valoarea funcției T definită recursiv după cum urmează: T(1) = 1, T(2) = 3, T(3) = 7, T(4) = 11, T(n) = 2*T(n-1) + T(n-2) + T(n-3) - 1 pentru n > 4. În cazul în care n este o putere a lui 2, se aplică o formulă alternativă care folosește funcția "pow" din biblioteca Python "math".

2. Funcția "validate_input(n)" returnează "True" dacă n se află între 1 și 1000 și "False" altfel.

3. Funcția "read_input()" citește din fișierul "scobitoare.in" două numere întregi: "p" și "n". Funcția verifică dacă n este valid folosind funcția "validate_input(n)". În caz contrar, scrie în fișierul "scobitoare.out" mesajul "Date de intrare invalide" și se termină.

4. Funcția "write_output(output)" scrie valoarea "output" în fișierul "scobitoare.out".

5. În blocul "if __name__ == '__main__':", funcția "read_input()" este apelată pentru a citi inputul. Dacă inputul este valid, se calculează valoarea lui "output" folosind funcția "T(n)" și se apelează funcția "write_output(output)" pentru a scrie outputul în fișierul "scobitoare.out". În cazul în care p este diferit de 1, se calculează diferența dintre T(n) și T(n-1).

2924 - FactorialInnEasy

2023-05-03T05:50:29Z

Cata:

==Cerința==
Se dă numărul natural n. Să se afișeze numărul de cifre a lui (n!)n.

==Date de intrare==
Programul citește de la tastatură numărul natural n.

==Date de ieșire==
După ce se afișează mesajul de validitate a datelor introduse corespunzător ("Date de intrare valide" în cazul în care datele respectă cerințele; "Input-ul trebuie să fie un număr întreg" pentru cazul în care n nu este număr întreg; "Input invalid: {eroare}" în orice alt caz), programul va afișa pe ecran numărul de cifre a lui (n!)n formatat într-un mesaj, astfel: Numărul de cifre din ({n}!)^{n} este {numărul de cifre}

==Restricții și precizări==
* n &les; 106
==Exemplu==
; Intrare
: Introduceți un număr pozitiv: 3
; Ieșire
: Date de intrare valide
: Numărul de cifre din (3!)^3 este 3
==Explicație exemplu==
(3!)3=216

==Rezolvare==
<syntaxhighlight lang="python">
def validate_input(n: str) -> int:
try:
n = int(n)
if n < 1:
raise ValueError("Input-ul trebuie să fie un număr întreg")
return n
except ValueError as e:
print(f"Input invalid: {e}")

def compute_factorial_power(n: int) -> int:
factorial = 1
for i in range(2, n+1):
factorial *= i
return factorial ** n

def count_digits(number: int) -> int:
return len(str(number))

if __name__ == "__main__":
n = input("Introduceți un număr pozitiv: ")
n = validate_input(n)
if n:
factorial_power = compute_factorial_power(n)
digit_count = count_digits(factorial_power)
print("Date de intrare valide")
print(f"Numărul de cifre din ({n}!)^{n} este {digit_count}")
</syntaxhighlight>
==Explicație cod==
Funcția `validate_input(n: str) -> int` primește un string `n` și încearcă să îl transforme într-un număr întreg. Dacă acest lucru este posibil și numărul obținut este mai mare sau egal cu 1, atunci funcția returnează acel număr. În caz contrar, funcția aruncă o excepție și afișează un mesaj de eroare.

Funcția `compute_factorial_power(n: int) -> int` primește un număr întreg `n` și calculează valoarea expresiei `(n!)^n`, unde `n!` reprezintă factorialul lui `n`. Funcția utilizează un ciclu for pentru a calcula factorialul lui `n`, iar apoi ridică acest factorial la puterea `n`.

Funcția `count_digits(number: int) -> int` primește un număr întreg `number` și returnează numărul de cifre ale acestuia. Funcția convertește numărul într-un string și returnează lungimea acestui string.

În funcția `main`, se citește un număr pozitiv de la tastatură și se validează folosind funcția `validate_input`. Dacă numărul este valid, se calculează valoarea expresiei cerute utilizând funcția `compute_factorial_power`, iar apoi se numără cifrele acestei valori utilizând funcția `count_digits`. Rezultatul este afișat la ecran.

4044 - camere

2023-05-03T05:45:26Z

Cata:

==Cerința==
Te afli într-o cameră de formă dreptunghiulară, privită sub forma unei matrici cu N linii și M coloane. Camera depozitează alune, nuci și castane, fiecare celulă din matrice fiind însemnată cu un caracter din mulțimea {'A', 'N', 'C'}. Caracterul 'A' reprezintă o alună, 'N' o nucă, iar 'C' o castană. Dorești să imparți în mod cât mai egal cu sora ta gustările din cameră, iar cum castanele depozitate nu sunt comestibilie, tu ai dori să vezi câte submatrici cu laturile paralele cu cele ale camerei poți alege, astfel încât numărul de alune să fie egal cu numărul de nuci.

==Date de intrare==
Prima linie din input conține numerele N și M. Pe următoarele N linii se vor găsi câte M caractere din mulțime {'A', 'N', 'C'}, reprezentând elementele matricii.

==Date de ieșire==
Se efectuează verificarea, care va afișa un mesaj corespunzător în funcție de input-ul dat și cerințele de validitate ale problemei. Dacă testele de validitate sunt efectuate cu succes, pe un rând nou se va afișa un singur număr, reprezentând valoarea cerută.

==Restricții și precizări==
* 1 &les; N, M &les; 300

==Exemplu==
; Intrare
: 3 4
: ACNN
: NCCA
: AACN
; Ieșire
: Date de intrare valide
: 18
==Explicație exemplu==
Printre submatricile numărate se află cele cu colțurile în punctele {(1, 1), (3, 4)}, {(3, 3), (3, 3)}, {(1, 1), (2, 1)}, etc.

==Rezolvare==
<syntaxhighlight lang="python">
from typing import List

def validate_input(N: int, M: int, matrix: List[List[str]]) -> bool:
# Verifică dacă N și M sunt în intervalul specificat
if not (1 <= N <= 300) or not (1 <= M <= 300):
return False
# Verifică dacă matricea conține doar caracterele {'A', 'N', 'C'}
for i in range(N):
for j in range(M):
if matrix[i][j] not in {'A', 'N', 'C'}:
return False
return True

def count_submatrices(N: int, M: int, matrix: List[List[str]]) -> int:
count = 0
# Iterează prin toate submatricile posibile ale matricei
for i in range(N):
for j in range(M):
for k in range(i, N):
for l in range(j, M):
# Calculează numărul de alune și nuci în submatrice
num_almonds = sum(matrix[p][q] == 'A' for p in range(i, k+1) for q in range(j, l+1))
num_walnuts = sum(matrix[p][q] == 'N' for p in range(i, k+1) for q in range(j, l+1))
# Verifică dacă numărul de alune este egal cu numărul de nuci
if num_almonds == num_walnuts:
count += 1
return count

if __name__ == '__main__':
# Citirea datelor de intrare
N, M = map(int, input().split())
matrix = [list(input().strip()) for _ in range(N)]

# Validarea datelor de intrare
if not validate_input(N, M, matrix):
print("Date de intrare invalide")
return
else:
print("Date de intrare valide")
# Rezolvarea problemei și afișarea rezultatului
result = count_submatrices(N, M, matrix)
print(result)

</syntaxhighlight>
==Explicație cod==
Programul are trei funcții principale:

1. `validate_input`: verifică dacă datele de intrare sunt valide. Verifică dacă N și M se încadrează în intervalul specificat și dacă matricea conține doar caracterele {'A', 'N', 'C'}.

2. `count_submatrices`: calculează numărul de submatrici ale matricei pentru care numărul de caractere 'A' este egal cu numărul de caractere 'N'. Iterează prin toate submatricile posibile ale matricei și verifică condiția.

3. `main`: citește datele de intrare, validează datele, rezolvă problema și afișează rezultatul.

Programul citește N și M de la intrarea standard, apoi citește matricea de dimensiune N x M. Apoi, datele de intrare sunt validate folosind funcția `validate_input`. Dacă datele de intrare sunt valide, programul calculează numărul de submatrici ale matricei pentru care numărul de caractere 'A' este egal cu numărul de caractere 'N', folosind funcția `count_submatrices`. Rezultatul este afișat la ieșirea standard.

2826 - Duplicare1

2023-05-03T05:42:45Z

Cata:

==Cerința==
Subprogramul duplicare are doi parametri, în această ordine:

* n, prin care primește un număr natural (n∈[1,104]);
* d, prin care furnizează numărul obţinut prin duplicarea fiecărei cifre pare a lui n sau -1 dacă acesta nu are nicio cifră pară.
Scrieți definiția completă a subprogramului în Python.

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Date de intrare valide", apoi pe un rând nou numărul cerut cu cifrele pare duplicate. În cazul în care numărul introdus nu corespunde restricțiilor date, se va afișa "Date de intrare invalide"

==Exemplu==
; Intrare
: 2380
; Ieșire
: Date de intrare valide
: 2238800

==Rezolvare==
<syntaxhighlight lang="python>
def validate_input(n: int, d: int) -> bool:
# Verificăm dacă n este între 1 și 10^4
if n < 1 or n > 10 ** 4:
return False

# Verificăm dacă d este între -1 și 10^9
if d < -1 or d > 10 ** 9:
return False

return True

def duplicare(n: int, d: int) -> int:
# Initializăm numărul rezultat cu 0
result = 0

# Parcurgem cifrele numărului n
while n > 0:
# Extragerea ultimei cifre din n
cifra = n % 10

# Dacă cifra este pară, o adăugăm de două ori în numărul rezultat
if cifra % 2 == 0:
result = result * 100 + cifra * 10 + cifra
else:
result = result * 10 + cifra

# Trecem la următoarea cifră
n //= 10

# Dacă nu am adăugat nicio cifră pară, returnăm -1
if result == 0:
return -1
else:
return result

if __name__ == '__main__':
# Citim numarul n de la tastatura
n = int(input("Introduceti numarul n: "))

# Apelam subprogramul duplicare si afisam rezultatul
d = duplicare(n)
if not validate_input(n, d):
print("Date de intrare invalide")
else:
print("Date de intrare valide")
if d == -1:
print("Numarul n nu are cifre pare")
else:
print(f"Numarul obtinut prin duplicarea cifrelor pare din {n} este: {d}")

</syntaxhighlight>

==Explicație==
Acest program are două funcții și un bloc de cod principal:

1. Funcția `validate_input` primește doi parametri: `n` și `d`, ambele de tip int. Funcția verifică dacă `n` se află între 1 și 10^4 și dacă `d` se află între -1 și 10^9. Dacă ambele condiții sunt adevărate, funcția returnează True, altfel returnează False.

2. Funcția `duplicare` primește doi parametri: `n` și `d`, ambele de tip int. Funcția parcurge cifrele numărului `n` și, pentru fiecare cifră pară, o adaugă de două ori la `result`. Dacă `n` nu are cifre pare, funcția returnează -1. Altfel, funcția returnează numărul obținut prin duplicarea cifrelor pare.

3. Blocul principal citește un număr întreg `n` de la tastatură, apelează funcția `duplicare` și afișează rezultatul. Dacă datele de intrare sunt invalide (potrivit funcției `validate_input`), se afișează un mesaj de eroare. Dacă `duplicare` returnează -1, se afișează un mesaj care indică că `n` nu are cifre pare, iar în caz contrar se afișează numărul obținut prin duplicarea cifrelor pare.

3489 - Numara punctele

2023-05-03T04:52:06Z

Cata:

==Cerința==
Considerăm o suprață plană în formă de pătrat având latura de 100 de unități și două mulțimi:
* Mulțimea P de puncte având coordonatele numere reale pozitive mai mici decat 100 (deci aparținând pătratului).
* Mulțimea ordonată C de cercuri având centrul în același pătrat și cu raza variabilă (se poate întâmpla ca centrul să fie în punctul p(1,1) și cercul să aibă raza de 3, deci să aibă o porțiune înafara pătratului).

Se dorește să se stabilească, pentru fiecare dintre cercurile din mulțimea C, câte puncte din mulțimea P se află în interior (sau pe marginea acestuia).

==Date de intrare==
Programul citește de la tastatură numărul n de puncte, iar apoi n cupluri de numere reale, separate prin spații reprezentând coordonatele fiecărui punct. După ce a citit valorile reprezentând coordonatele punctelor, se va citi numărul m de cercuri și vor apoi cele m triplete reprezentând coordonatele centrului cercului respectiv raza cercului.

==Date de ieșire==
În cazul în care datele sunt valide, se va afișa un mesaj de confirmare, iar pentru fiecare cerc citit se va afișa pe câte o linie diferită câte puncte sunt in interiorul său sau pe frontieră. În caz contrar, se va afișa un mesaj de eroare.

==Restricții și precizări==
* 1≤n≤100000
* Pentru fiecare punct p(x,y) avem x∈[0,100] respectiv y∈[0,100]
* 1≤m≤10000
* Pentru fiecare cerc c(x,y,r) avem x∈[0,100], y∈[0,100] și r∈[0,30]

==Exemplu==
; Intrare
: 3
: 6.39 24.96
: 6.23 6.17
: 20.0 20.0
: 3
: 23.05 83 10.57
: 15.00 15.00 10.0
: 10.0 20.0 10
; Ieșire
: Datele introduse sunt corecte.
: 0
: 1
: 2

==Rezolvare==
<syntaxhighlight lang="python">
def validare(n: int, puncte: list[tuple[float, float]], m: int, cercuri: list[tuple[float, float, float]]) -> bool:
# verificam numarul de puncte si de cercuri
if not 1 <= n <= 100000 or not 1 <= m <= 10000:
return False

# verificam coordonatele punctelor si ale cercurilor
for p in puncte:
if not 0 <= p[0] <= 100 or not 0 <= p[1] <= 100:
return False

for c in cercuri:
if not 0 <= c[0] <= 100 or not 0 <= c[1] <= 100 or c[2] <= 0:
return False

return True

def numar_puncte_in_cercuri(puncte, cercuri):
numar_puncte = []
for cerc in cercuri:
num_puncte_in_cerc = 0
for punct in puncte:
distanta = ((punct[0] - cerc[0]) ** 2 + (punct[1] - cerc[1]) ** 2) ** 0.5
if distanta <= cerc[2]:
num_puncte_in_cerc += 1
numar_puncte.append(num_puncte_in_cerc)
return numar_puncte

if __name__ == "__main__":
# citirea numarului de puncte
n = int(input())
# citirea coordonatelor fiecarui punct
puncte = []
for i in range(n):
x, y = input().split()
x = float(x)
y = float(y)
puncte.append((x, y))
# citirea numarului de cercuri
m = int(input())
# citirea coordonatelor si razei fiecarui cerc
cercuri = []
for i in range(m):
x, y, r = input().split()
x = float(x)
y = float(y)
r = float(r)
cercuri.append((x, y, r))
# validarea datelor introduse
if validare(n, puncte, m, cercuri):
print("Datele introduse sunt corecte.")
# numarul de puncte din interiorul fiecarui cerc
numar_puncte = numar_puncte_in_cercuri(puncte, cercuri)
# afisarea numarului de puncte din interiorul fiecarui cerc
for i in numar_puncte:
print(i)
else:
print("Unul sau mai multe numere introduse nu sunt valide.")
</syntaxhighlight>

==Explicație==
Acest cod are două funcții definite și o secțiune principală de cod.

Funcția `validare` primește ca argumente un număr întreg `n`, o listă de perechi de coordonate (x,y) reprezentând punctele și un număr întreg `m` și o listă de tupluri (x,y,r) reprezentând cercurile. Funcția verifică dacă numărul de puncte și cercuri este în limitele permise și dacă coordonatele și razele cercurilor sunt valide (în intervalul 0-100). În cazul în care aceste condiții nu sunt îndeplinite, funcția returnează `False`, altfel returnează `True`.

Funcția `numar_puncte_in_cercuri` primește ca argumente lista de puncte și cea de cercuri și returnează o listă cu numărul de puncte din fiecare cerc.

În secțiunea principală de cod, mai întâi se citește numărul de puncte, apoi coordonatele fiecărui punct, apoi numărul de cercuri și coordonatele și razele acestora. După aceea se validează datele introduse. În cazul în care sunt valide, se afișează mesajul "Datele introduse sunt corecte." și se calculează numărul de puncte din fiecare cerc cu ajutorul funcției `numar_puncte_in_cercuri`, iar apoi se afișează numărul de puncte din fiecare cerc. În caz contrar, se afișează mesajul "Unul sau mai multe numere introduse nu sunt valide.".

0023 - Oglindit1

2023-05-03T04:15:30Z

Cata:

==Cerinţa==
Să se scrie o funcție Python care să determine oglinditul unui număr natural transmis ca parametru. Funcția va întoarce rezultatul prin intermediul unui parametru de ieşire.

==Restricţii şi precizări==
* numele funcției va fi oglindit
* funcția va avea doi parametri: primul parametru reprezintă numărul pentru care se calculează oglinditul, iar la doilea parametru reprezintă valoarea calculată
* numărul pentru care se calculează oglinditul va fi mai mic decât 1.000.000.000

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt valide.", apoi pe un rând nou oglinditul numărului introdus. În cazul în care numărul introdus depășește limitele date, se va afișa "n trebuie să fie un număr natural mai mic decât 1.000.000.000", iar dacă numărul introdus nu este întreg, se va afișa "n trebuie să fie de tip întreg"

==Exemplu==
; Intrare
: Introduceți un număr natural mai mic decât 1.000.000.000: 12345
; Ieșire
: Datele introduse sunt valide.
: Oglinditul numărului 12345 este 54321.

==Rezolvare==
<syntaxhighlight lang="python">
def oglindit(n, ogl=None):
if ogl is None:
ogl = 0
while n > 0:
ogl = ogl * 10 + n % 10
n = n // 10
return ogl

def validare_oglindit(n):
if not isinstance(n, int):
raise TypeError("n trebuie să fie de tip întreg")
if n <= 0 or n >= 1000000000:
raise ValueError("n trebuie să fie un număr natural mai mic decât 1.000.000.000")

if __name__ == "__main__":
n = int(input("Introduceți un număr natural mai mic decât 1.000.000.000: "))
validare_oglindit(n)
print("Datele introduse sunt valide.")
ogl = 0
ogl = oglindit(n, ogl)
print(f"Oglinditul numărului {n} este {ogl}.")
</syntaxhighlight>

==Explicație==
Funcția oglindit(n, ogl=None) primește un număr natural n și returnează oglinditul acestuia. Oglinditul unui număr este numărul obținut prin scrierea cifrelor numărului dat în ordine inversă. Această funcție realizează acest lucru prin utilizarea unui loop while care extrage fiecare cifră a numărului dat prin împărțirea acestuia cu 10 și adăugarea cifrei obținute la oglindă (ogl) prin înmulțire cu 10 și adunare cu cifra. După extragerea fiecărei cifre, numărul inițial este împărțit la 10 prin îndepărtarea cifrei extrase. Când toate cifrele au fost extrase, funcția returnează oglinda numărului.

Funcția validare_oglindit(n) primește un număr natural n și verifică dacă acesta este un număr întreg și dacă este mai mic decât 1.000.000.000. Dacă aceste condiții nu sunt îndeplinite, funcția va genera o eroare de tipul TypeError sau ValueError.

În secțiunea if __name__ == "__main__": a codului, utilizatorul este întâmpinat cu un mesaj prin intermediul funcției input() și numărul introdus de utilizator este stocat în variabila n. Apoi, funcția validare_oglindit(n) este apelată pentru a verifica dacă numărul dat este valid. Dacă acesta este valid, se afișează un mesaj care confirmă validitatea datelor, iar funcția oglindit(n, ogl) este apelată pentru a calcula oglinditul numărului introdus de utilizator. Rezultatul este afișat cu ajutorul funcției print().

0032 - EliminareCifre

2023-05-03T04:03:39Z

Cata:

==Cerinţa==
Să se scrie definiția completă a funcției Python P care primește prin intermediul parametrului n un număr natural cu cel mult 9 cifre, iar prin intermediul parametrului c o cifră. Funcția întoarce tot prin intermediul parametrului n numărul obținut prin eliminarea tuturor aparițiilor cifrei c.

==Restricţii şi precizări==
* numele funcției va fi P
* funcția va avea doi parametri: primul parametru este n, iar al doilea este c
* dacă după eliminare numărul obținut nu mai conține nici o cifră sau conține doar cifre 0, rezultatul va fi 0

==Date de intrare==
Programul citește de la tastatură numerele n și c.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt valide.", apoi pe un rând nou numărul n fără cifrele c. În cazul în care n sau c depășesc limitele date ori nu sunt numere întregi, se va afișa un mesaj corespunzător în funcție de eroarea generată.

==Exemplu==
; Intrare
: Introduceți un număr natural cu cel mult 9 cifre: 2524722
: Introduceți o cifră între 0 și 9: 5
; Ieșire
: Datele introduse sunt valide.
: Numărul obținut prin eliminarea cifrei 5 din 2524722 este: 224722

==Rezolvare==
<syntaxhighlight lang="python">
def validare_P(n, c):
if not isinstance(n, int) or n < 0:
raise ValueError("n trebuie să fie un număr natural")
if not isinstance(c, int) or not 0 <= c <= 9:
raise ValueError("c trebuie să fie o cifră între 0 și 9")

def P(n, c):
validare_P(n, c)
n_str = str(n)
n_fara_c = "".join([cifra for cifra in n_str if cifra != str(c)])
if len(n_fara_c) == 0 or all(cifra == "0" for cifra in n_fara_c):
return 0
return int(n_fara_c)

if __name__ == "__main__":
try:
n = int(input("Introduceți un număr natural cu cel mult 9 cifre: "))
c = int(input("Introduceți o cifră între 0 și 9: "))
validare_P(n, c)
print("Datele introduse sunt valide.")
rezultat = P(n, c)
print(f"Numărul obținut prin eliminarea cifrei {c} din {n} este: {rezultat}")
except Exception as ex:
print(f"O eroare a survenit: {ex}")
</syntaxhighlight>

==Explicație==
Funcția `validare_P(n, c)` este utilizată pentru a verifica dacă argumentele primite de funcția `P(n, c)` respectă anumite condiții. Aceasta verifică dacă `n` este un număr natural (întreg pozitiv) și dacă `c` este o cifră între 0 și 9. Dacă oricare dintre aceste condiții nu este îndeplinită, se va arunca o excepție de tip `ValueError` cu un mesaj corespunzător.

Funcția `P(n, c)` primește două argumente: `n`, un număr natural cu cel mult 9 cifre și `c`, o cifră între 0 și 9. Aceasta mai întâi verifică dacă argumentele primite sunt valide, folosind funcția `validare_P(n, c)`. Apoi, convertește numărul `n` la un șir de caractere și elimină toate aparițiile cifrei `c` din șirul obținut, folosind o listă de comprimare și funcția `join()`. Dacă șirul obținut are lungimea 0 sau conține doar cifra 0, se va returna 0. În caz contrar, se va returna numărul format din șirul obținut, folosind funcția `int()`.

În blocul `if __name__ == "__main__":` se citește numărul `n` și cifra `c` de la tastatură. Se verifică apoi dacă acestea sunt valide, folosind funcția `validare_P(n, c)`. Dacă acestea sunt valide, se afișează un mesaj de confirmare și se calculează rezultatul apelând funcția `P(n, c)`. În caz contrar, se va afișa mesajul de eroare corespunzător.

0894 - CifMinMax

2023-05-03T03:56:11Z

Cata:

==Cerinţa==
Să se scrie o funcție Python care să determine cea mai mare și cea mai mică cifră a unui număr natural transmis ca parametru. Funcția va întoarce rezultatele prin intermediul unor parametri de ieşire.

==Restricţii şi precizări==
* numele funcției va fi cifminmax
* funcția va avea trei parametri: primul parametru reprezintă numărul pentru care se calculează valorile cerute;al doilea parametru va reprezenta cifra maximă, iar al treilea va reprezenta cifra minimă
* numărul pentru care se calculează cele doua valori va fi mai mic decât 2.000.000.000

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Date de intrare valide.", apoi pe un rând nou cea mai mare și cea mai mică cifră din numărul introdus. În cazul în care numărul introdus depășește limitele date, se va afișa "Date de intrare invalide."

==Exemplu==
; Intrare
: 12345
; Ieșire
: Date de intrare valide
: Cea mai mare cifra este: 5
: Cea mai mica cifra este: 1

==Rezolvare==
<syntaxhighlight lang="python">
def validate_cifminmax(n, max_cif, min_cif):
if n >= 2000000000:
return False
return True

def cifminmax(n, max_cif, min_cif):
while n > 0:
cif = n % 10
if cif > max_cif:
max_cif = cif
if cif < min_cif:
min_cif = cif
n //= 10
return max_cif, min_cif

if __name__ == '__main__':
n = 123456789
max_cif = -1
min_cif = 10

if validate_cifminmax(n, max_cif, min_cif):
print("Date de intrare valide")
max_cif, min_cif = cifminmax(n, max_cif, min_cif)
print("Cea mai mare cifra este:", max_cif)
print("Cea mai mica cifra este:", min_cif)
else:
print("Date de intrare invalide")
</syntaxhighlight>

==Explicație==
Acest cod definește trei funcții și verifică dacă datele de intrare sunt valide pentru a calcula cea mai mare și cea mai mică cifră a unui număr dat.

Funcția `validate_cifminmax` primește trei argumente: `n`, `max_cif`, și `min_cif`. Funcția verifică dacă valoarea `n` este mai mică decât 2000000000 și returnează `True` dacă da, `False` în caz contrar. Această funcție este folosită pentru a verifica dacă numărul dat este un număr valid, adică dacă acesta este mai mic decât 2 miliarde.

Funcția `cifminmax` primește trei argumente: `n`, `max_cif`, și `min_cif`. Această funcție calculează cea mai mare și cea mai mică cifră a lui `n`. Se începe prin a atribui `max_cif` o valoare inițială de -1 și `min_cif` o valoare inițială de 10. Apoi, folosind un ciclu `while`, se extrage fiecare cifră a lui `n` prin împărțirea lui `n` la 10 și reținerea restului. Dacă cifra extrasă este mai mare decât valoarea curentă a lui `max_cif`, aceasta devine noua valoare a lui `max_cif`. Dacă cifra extrasă este mai mică decât valoarea curentă a lui `min_cif`, aceasta devine noua valoare a lui `min_cif`. La sfârșitul ciclului, funcția returnează cele două valori `max_cif` și `min_cif`.

În `main` se inițializează variabilele `n`, `max_cif` și `min_cif`. Apoi, se verifică dacă datele de intrare sunt valide apelând funcția `validate_cifminmax`. Dacă datele sunt valide, se afișează un mesaj corespunzător, se calculează cea mai mare și cea mai mică cifră a lui `n` folosind funcția `cifminmax`, și se afișează rezultatele. Dacă datele de intrare nu sunt valide, se afișează un alt mesaj.

0894 - CifMinMax

2023-05-03T03:52:03Z

Cata:

1675 - Calc

2023-04-28T08:04:16Z

Cata:

La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.

Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

==Cerința==
Cunoscând N, să se determine:

Numărul de zile modulo 1000000007 în care se desfășoară concursul.
Configurațiile laboratorului în ziua X-1 și ziua X+1, cunoscând configurația zilei X.
==Date de intrare==
Fişierul de intrare calc.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.

Pe linia a doua vom avea numărul natural N.

Pe linia a treia se va găsi un șir de N cifre binare, fără spații între ele, reprezentând configurația corectă realizată de administrator în ziua X.

==Date de ieșire==
Dacă valoarea lui p este 1, se va rezolva numai punctul 1) din cerință.
În acest caz, în fişierul de ieşire calc.out se va scrie un singur număr natural Z reprezentând numărul de zile în care se desfășoară concursul pentru cele N echipe.

Dacă valoarea lui p este 2, se va rezolva numai punctul 2) din cerință.
În acest caz, fişierul de ieşire calc.out va conține două linii. Pe prima linie se vor scrie N cifre binare, fără spații între ele, reprezentând configurația rețelei din ziua precedentă, iar pe a doua linie N cifre binare, fără spații între ele, reprezentând configurația din ziua următoare. Dacă în ziua precedentă nu există o configurație conform cerințelor problemei, se va scrie pe prima linie valoarea -1. Dacă în ziua următoare nu există o configurație conform cerințelor problemei, se va scrie pe a doua linie valoarea -1.

==Restricții și precizări==
* 1 &les; N &les; 100000
* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
==Exemplul 1==
; calc.in

: 1
: 3
: 001
; calc.out

: 3
; Consola
: Input valid
==Exemplul 2==
; calc.in

: 2
: 3
: 001
; calc.out

: -1
: 100
; Consola
: Input valid
==Rezolvare==
<syntaxhighlight lang="python">
MODULO = 1000 * 1000 * 1000 + 7

def read_input():
with open("calc.in", "r") as f:
tip = int(f.readline().strip())
n = int(f.readline().strip())
s = f.readline().strip()
return tip, n, s

def write_output(prev, next):
with open("calc.out", "w") as f:
f.write(f"{prev}\n{next}\n")

def compute_prev(s):
n = len(s)
prev = list(s)
if s[n - 1] == "1" and s[n - 2] == "1":
prev[n - 1] = prev[n - 2] = "0"
else:
i = n - 2
while i >= 0 and s[i] == "0":
i -= 1
if i < 0:
prev = "-1"
else:
prev[i] = "0"
for j in range(i + 2, n):
prev[j] = "1"
return "".join(prev)

def compute_next(s):
n = len(s)
next = list(s)
if s[n - 1] == "0" and s[n - 2] == "0":
next[n - 1] = next[n - 2] = "1"
else:
i = n - 1
while i >= 0 and s[i] == "1":
i -= 1
if i < 0:
next = "-1"
else:
next[i - 1] = "1"
next[i] = "0"
oldi = i
for j in range(i + 1, n):
next[j] = "0"
if (n - 1 - oldi) % 2 == 0:
next[n - 1] = "1"
return "".join(next)

def compute_fibonacci(n):
if n <= 1:
return 1
a, b = 1, 1
for i in range(2, n + 1):
c = (a + b) % MODULO
a, b = b, c
return b

def validate_input(tip: int, N: int, S: str) -> bool:
if tip not in (1, 2):
print("tip trebuie sa fie 1 sau 2")
return False
if not (1 <= N <= 100000):
print("N trebuie sa fie intre 1 si 100000")
return False
if len(S) != N or not set(S).issubset({'0', '1'}):
print("S trebuie sa fie un sir de N caractere '0' sau '1'")
return False
print("Input valid")
return True

def main():
tip, n, s = read_input()
if not validate_input(tip, n, s):
exit(1)
if tip == 1:
result = compute_fibonacci(n)
write_output(result, result)
return

if n == 1:
write_output("-1", "-1")
return

prev = compute_prev(s)
next = compute_next(s)
write_output(prev, next)

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicație cod==
Programul citește datele de intrare din fișierul "calc.in", validează datele de intrare, apoi își dă seama dacă tipul problemei este 1 sau 2.

Dacă tipul problemei este 1, programul calculează numărul Fibonacci de ordine n și scrie rezultatul în fișierul "calc.out". Dacă tipul problemei este 2, programul calculează valorile anterioară și următoare a unui șir de biți și scrie cele două rezultate în fișierul "calc.out".

Pentru a calcula valorile anterioară și următoare, programul apelează funcțiile "compute_prev(s)" și "compute_next(s)" care primesc ca parametru un șir de biți și întorc valoarea anterioară și următoarea valoare, respectiv.

Pentru a verifica dacă datele de intrare sunt valide, programul utilizează funcția "validate_input(tip: int, N: int, S: str) -> bool". Dacă datele de intrare nu sunt valide, programul afișează un mesaj de eroare și se termină.

1124 - Patrate

2023-04-28T08:02:09Z

Cata:

==Cerința==
Dându-se n, un număr natural, să se afle numărul de pătrate care au colţurile coordonate numere întregi cuprinse între 0 şi n inclusiv.

==Date de intrare==
Programul citește de la tastatură un număr natural n.

==Date de ieșire==
Programul va afişa pe ecran un număr natural, reprezentând numărul de pătrate formate cu cele (n+1)2 puncte. Deoarece rezultatul poate fi mare, se va afişa răspunsul modulo 666013. De asemenea, se afișează un mesaj de validare a datelor introduse.

==Restricții și precizări==
* 1 &les; n &les; 2.000.000.000
* Pentru teste în valoare de 30 de puncte, n ≤ 10
* Pentru teste în valoare de 75 de puncte, n ≤ 2.000.000
==Exemplu==
; Intrare

: 2
; Ieșire
: Valid input
: 6
==Explicație==
Pătratele ce se formează au colţurile:

# (0, 0), (0, 1), (1, 1), (1, 0)
# (0, 1), (0, 2), (1, 2), (1, 1)
# (1, 0), (1, 1), (2, 1), (2, 0)
# (1, 1), (1, 2), (2, 2), (2, 1)
# (0, 0), (0, 2), (2, 2), (2, 0)
# (0, 1), (1, 2), (2, 1), (1, 0)

==Rezolvare==
<syntaxhighlight lang="python">
def validate_input(n):
if n < 1 or n > 2000000000:
raise ValueError("n trebuie sa fie intre 1 si 2.000.000.000")
else:
print("Valid input")

def calculate_sum(n):
validate_input(n)
sol = 0
mod = 666013

n %= mod

for i in range(n):
sol += (n - i) * (n - i) * (i + 1)
sol %= mod

return sol

def main():
n = int(input())
sol = calculate_sum(n)
print(sol)

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicație cod==
Acest cod definește trei funcții și o funcție principală:

Funcția validate_input(n) verifică dacă valoarea parametrului n este cuprinsă între 1 și 2.000.000.000, și aruncă o excepție ValueError dacă nu este.

Funcția calculate_sum(n) primește un parametru n și calculează suma unei anumite formule matematice, bazată pe valoarea lui n și un număr constant (mod = 666013). Apoi, funcția returnează această sumă.

Funcția main() citește un număr întreg de la tastatură, apelează funcția calculate_sum(n) pentru a calcula suma corespunzătoare, și apoi afișează rezultatul.

Dacă acest script este rulat ca un program, atunci funcția main() este apelată.

2724 - LSQ

2023-04-28T08:00:49Z

Cata:

==Cerința==
Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1.

==Date de intrare==
Fișierul de intrare lsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei..

==Date de ieșire==
Fișierul de ieșire lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa.

==Restricții și precizări==
* 1 &les; N, M &les; 1000
* Se consideră pătrat și cel de latură 1 (conține doar un element).
==Exemplu==
; lsq.in

: 7 7
: 0000000
: 0111100
: 0101111
: 0100101
: 0111111
: 0000011
: 0000011
; lsq.out

: 4
; Consola
: Valid input
==Explicație==

0 0 0 0 0 0 0 
0 1 1 1 1 0 0 
0 1 0 1 1 1 1 
0 1 0 0 1 0 1 
0 1 1 1 1 1 1 
0 0 0 0 0 1 1 
0 0 0 0 0 1 1 

==Rezolvare==
<syntaxhighlight lang="python">
Nmax = 1005

def compute_matrices(N, M, A):
LDL = [[0] * M for _ in range(N)]
CDL = [[0] * M for _ in range(N)]
LRU = [[0] * M for _ in range(N)]
CRU = [[0] * M for _ in range(N)]

for i in range(N):
for j in range(M):
if A[i][j] == 1:
LDL[i][j] = 1 + LDL[i][j - 1] if j > 0 else 1
CDL[i][j] = 1 + CDL[i - 1][j] if i > 0 else 1

for i in range(N - 1, -1, -1):
for j in range(M - 1, -1, -1):
if A[i][j] == 1:
LRU[i][j] = 1 + LRU[i][j + 1] if j < M - 1 else 1
CRU[i][j] = 1 + CRU[i + 1][j] if i < N - 1 else 1

return LDL, CDL, LRU, CRU

def find_largest_square(N, M, A):
LDL, CDL, LRU, CRU = compute_matrices(N, M, A)
ans = 0
for i in range(N):
for j in range(M):
for L in range(min(LDL[i][j], CDL[i][j]), ans, -1):
if L <= min(LRU[i - L + 1][j - L + 1], CRU[i - L + 1][j - L + 1]):
ans = L
break
return ans

def validate_input(n: int, m: int) -> bool:
return 1 <= n <= 1000 and 1 <= m <= 1000

def main():
with open("lsq.in", "r") as fin, open("lsq.out", "w") as fout:
N, M = map(int, fin.readline().split())
A = [list(map(int, fin.readline().strip())) for _ in range(N)]
if not validate_input(N, M):
print("Invalid input!")
return
else:
print("Valid input")
ans = find_largest_square(N, M, A)
fout.write(str(ans) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicație cod==
Acesta este un program Python care calculează dimensiunea celui mai mare pătrat complet format din cifrele de 1 dintr-o matrice dată. Matricea este dată ca o listă de liste de cifre. Algoritmul folosit pentru a găsi răspunsul constă în calcularea a patru matrice auxiliare, folosind programarea dinamică pentru a calcula lungimea celui mai mare pătrat posibil cu colțul din stânga sus la poziția curentă. Apoi, se parcurge matricea și se caută cel mai mare pătrat complet, verificând dacă toate cele patru laturi au o lungime cel puțin egală cu dimensiunea pătratului. În caz afirmativ, se actualizează dimensiunea maximă a pătratului.

Funcția validate_input() verifică dacă intrarea este validă, adică dacă dimensiunea matricei se află între 1 și 1000 inclusiv. Funcția main() citește matricea din fișierul "lsq.in", validează intrarea și apoi calculează și scrie dimensiunea celui mai mare pătrat complet în fișierul "lsq.out".

1735 - divquery

2023-04-28T07:59:05Z

Cata: /* Date de ieșire */

==Cerința==
Se dă un vector indexat de la 1 cu n elemente numere naturale. Să se răspundă la q întrebări de forma x y, cu semnificația: “Care este cel mai mare divizor comun al elementelor cu indici cuprinși între x și y, inclusiv?”

==Date de intrare==
Fișierul de intrare divquery.in conține pe prima linie numerele n și q, pe a doua linie cele n numere naturale ale vectorului, iar de la linia 3 începând, q linii, pe fiecare aflându-se doua numere x y, reprezentând întrebările.

==Date de ieșire==
Fișierul de ieșire divquery.out va conține q linii, pe fiecare linie i aflându-se răspunsul la întrebarea i. În consolă se va afișa un mesaj de validare a datelor.

==Restricții și precizări==
* 1 &les; n &les; 100.000
* 1 &les; ai &les; 100.000
* 1 &les; q &les; 1.000.000
==Exemplu==
; divquery.in

: 5 4
: 1 3 18 2 3
: 1 5
: 2 3
: 3 4
: 2 4
; divquery.out

: 1
: 3
: 2
: 1
; Consola
: Datele de intrare sunt valide!
==Explicație==
În intervalul [1,5] cmmdc-ul este 1
În intervalul [2,3] cmmdc-ul este 3
În intervalul [3,4] cmmdc-ul este 2
În intervalul [2,4] cmmdc-ul este 1

==Rezolvare==
<syntaxhighlight lang="python">
def cmmdc(a, b):
while b:
r = a % b
a = b
b = r
return a

def read_input(filename):
with open(filename, 'r') as fin:
n, q = map(int, fin.readline().split())
a = list(map(int, fin.readline().split()))
queries = []
for _ in range(q):
x, y = map(int, fin.readline().split())
queries.append((x, y))
return n, a, queries

def compute_logs(n):
logs = [0] * (n+1)
for i in range(2, n+1):
logs[i] = 1 + logs[i//2]
return logs

def compute_sparse_table(a):
n = len(a)
logs = compute_logs(n)
st = [[0]*n for _ in range(logs[n]+1)]
st[0] = a
for i in range(1, logs[n]+1):
for j in range(n-(1<<i)+1):
st[i][j] = cmmdc(st[i-1][j], st[i-1][j+(1<<(i-1))])
return st, logs

def process_queries(a, queries, st, logs):
results = []
for x, y in queries:
dif = y - x + 1
l = logs[dif]
dif = dif - (1 << l)
res = cmmdc(st[l][x-1], st[l][x-1+dif])
results.append(res)
return results

def write_output(filename, results):
with open(filename, 'w') as fout:
for res in results:
fout.write(str(res) + '\n')

def validate_input(n, a, q):
if not (1 <= n <= 100000):
return False
if not all(1 <= x <= 100000 for x in a):
return False
if not (1 <= x <= 1000000 for x in q):
return False
return True

def main():
n, a, queries = read_input('divquery.in')
if not validate_input(n, a, queries):
print("Datele de intrare nu sunt valide!")
return
else:
print("Datele de intrare sunt valide!")
st, logs = compute_sparse_table(a)
results = process_queries(a, queries, st, logs)
write_output('divquery.out', results)

if __name__ == '__main__':
main()

</syntaxhighlight>

==Explicație cod==
Acest cod este o implementare a unei soluții pentru problema "DivQuery", care se ocupă cu determinarea celui mai mare divizor comun dintr-un interval dat dintr-un șir de numere.

Funcția "cmmdc(a, b)" calculează cel mai mare divizor comun dintre două numere folosind algoritmul Euclid.

Funcția "read_input(filename)" citește datele de intrare dintr-un fișier și returnează numărul de elemente din șir (n), lista cu elementele (a) și o listă cu perechi de numere (queries), reprezentând intervalele pentru care trebuie calculat cel mai mare divizor comun.

Funcția "compute_logs(n)" calculează logaritmul în baza 2 pentru numerele de la 2 la n și returnează o listă cu valorile obținute. Aceste valori sunt utilizate pentru a determina numărul de niveluri din tabelul rar.

Funcția "compute_sparse_table(a)" construiește un tabel rar (sparse table) pentru șirul de numere dat (a). Tabelul este reprezentat ca o matrice (st) cu (logs[n]+1) niveluri și n coloane. Primul nivel al matricei conține elementele din șir, iar fiecare nivel următor se construiește pe baza nivelului precedent. Matricea este construită astfel încât pentru orice subinterval din șir se poate calcula cel mai mare divizor comun folosind două valori din tabelul rar.

Funcția "process_queries(a, queries, st, logs)" calculează cel mai mare divizor comun pentru fiecare interval din lista de intervale (queries) folosind tabela rară și returnează o listă cu rezultatele obținute.

Funcția "write_output(filename, results)" scrie rezultatele într-un fișier de ieșire.

Funcția "validate_input(n, a, q)" verifică dacă datele de intrare sunt valide, adică numărul de elemente din șir să fie între 1 și 100000, elementele din șir să fie între 1 și 100000, iar intervalele să fie între 1 și 1000000.

Funcția "main()" este funcția principală care apelează celelalte funcții pentru a rezolva problema și afișează un mesaj de eroare în cazul în care datele de intrare nu sunt valide.

În final, condiția "if name == 'main':" verifică dacă codul este rulat ca script și apelează funcția principală.