Bitnami MediaWiki - User contributions [en]

15326

2024-12-13T18:16:36Z

Bonte Lucas Gabriel:

'''15326 (Andreea Bogdanovici)'''

''Determinați numerele naturale a,b,c pentru care este adevărată relația <math>\frac{37}{10}=a+\frac{1}{b+\frac{1}{c+\frac{1}{3}}}</math>.''

'''Soluție'''

Avem egalitățile <math>\frac{37}{10}=3+\frac{7}{10}=3+\frac{1/10}{7}=3+\frac{1}{1+\frac{1}{7}}=3+\frac{1}{1+\frac{1}{2+\frac{1}{3}}}</math>. Din egalitățile precedente și din <math>3<\frac{37}{10}<4, 1<\frac{10}{7}<2, 2<\frac{7}{3} < 3</math>, deducem a = 3, b = 1 și c = 2.

15326

2024-12-13T18:12:55Z

Bonte Lucas Gabriel: Created page with "'''15326 (Bonte Lucas)''' ''Determinați numerele naturale a,b,c pentru care este adevărată relația <math>\frac{37}{10}=a+\frac{1}{b+\frac{1}{c+\frac{1}{3}}}</math>.'' '''Soluție''' Avem egalitățile <math>\frac{37}{10}=3+\frac{7}{10}=3+\frac{1/10}{7}=3+\frac{1}{1+\frac{1}{7}}=3+\frac{1}{1+\frac{1}{2+\frac{1}{3}}}</math>. Din egalitățile precedente și din <math>3<\frac{37}{10}<4, 1<\frac{10}{7}<2, 2<\frac{7}{3} < 3</math>, deducem a = 3, b = 1 și c = 2."

'''15326 (Bonte Lucas)'''

''Determinați numerele naturale a,b,c pentru care este adevărată relația <math>\frac{37}{10}=a+\frac{1}{b+\frac{1}{c+\frac{1}{3}}}</math>.''

'''Soluție'''

Avem egalitățile <math>\frac{37}{10}=3+\frac{7}{10}=3+\frac{1/10}{7}=3+\frac{1}{1+\frac{1}{7}}=3+\frac{1}{1+\frac{1}{2+\frac{1}{3}}}</math>. Din egalitățile precedente și din <math>3<\frac{37}{10}<4, 1<\frac{10}{7}<2, 2<\frac{7}{3} < 3</math>, deducem a = 3, b = 1 și c = 2.

2534 - Bogdan

2024-01-03T20:37:17Z

Bonte Lucas Gabriel:

Bogdan și Ionuț au fost "bff" încă din clasa '''V''', dar acum destinele lor se cam despart…. Pentru a-l consola pe Bogdan, Ionuț i-a făcut o problema cadou. Bogdan nu vrea să-l dezamăgească pe Ionut, așa că vă cere ajutorul pentru a rezolva problema împreuna.

==Cerința==

Se dă un șir de '''n''' elemente, numere naturale. Problema constă în două operații:

'''1 i val ''': Elementul de pe poziția '''i''' se înlocuiește cu valoarea val.
'''2 i j ''': Stabiliți dacă secvența '''[i,j]''', din șirul curent, este ordonată crescător.

==Date de intrare==

Fișierul de intrare '''bogdanin.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale separate prin spații. Pe a treia linie a fișierului se afla numărul '''O''', care reprezintă numărul de operații. Pe următoarele '''O''' linii se vor afla operațiile.

==Date de ieșire==

Fișierul de ieșire '''bogdanout.txt''' va conține răspunsurile pentru operațiile de tipul '''2''', pe linie nouă fiecare.
Dacă răspunsul este afirmativ, se va afișa '''DA''', în caz contrar '''NU'''.

==Restricții și precizări==

*'''1 ≤ n ≤ 100.000'''
*'''1 ≤ O ≤ 300.000'''
*numerele fiecărui șir curent vor fi mai mici decât '''2.000.000.000'''
*Observație importantă : bff = Best Friends Forever

==Exemplul 1==

'''bogdanin.txt'''

6
22 9 2003 14 8 2003
4
2 1 6
1 1 8
2 1 3
2 4 5

'''bogdanout.txt'''

Datele de intrare corespund restrictiilor impuse
NU
DA
NU

==Exemplul 2==

'''bogdanin.txt'''

bogdan

'''bogdanout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(nr_n, string,
nr_o, fisier_out): # functia de validare a datelor de intrare
if not (1 <= nr_n <= 100000):
raise ValueError("n nu este in intervalul [1, 100000]")

if not (1 <= nr_o <= 300000):
raise ValueError("O nu este in intervalul [1, 300000]")

for numar in string:
if not (numar < 2000000000): # fiecare numar trebuie sa fie mai mic decat 2.000.000.000
raise ValueError("Un numar din sir este mai mare sau egal cu 2.000.000.000")

fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")

def rezolvare(string, exercitii, fisier_out): # functia de rezolvare
for operatie in exercitii:
if operatie[0] == 1:
string[operatie[1] - 1] = operatie[2]
elif operatie[0] == 2:
if string[operatie[1] - 1:operatie[2]] == sorted(string[operatie[1] - 1:operatie[2]]):
fisier_out.write("DA\n")
else:
fisier_out.write("NU\n")

if __name__ == '__main__':
file_in = open("bogdanin.txt", "r") # declararea fisierelor
file_out = open("bogdanout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n_str = file_in.readline().strip() # citirea numarului ca sir de caractere
try:
n = int(n_str) # incercam sa convertim sirul de caractere in numar intreg
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
file_in.close()
file_out.close()
exit(0) # iesim din program daca conversia esueaza

sir = list(map(int, file_in.readline().split()))

o = int(file_in.readline())
operatii = [list(map(int, file_in.readline().split())) for _ in range(o)]

validare(n, sir, o, file_out) # apelul functiei de validare
rezolvare(sir, operatii, file_out) # apelul functiei de rezolvare

except ValueError as ve:
file_out.write(str(ve))
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

file_in.close()
file_out.close()

</syntaxhighlight>

2217 - Map

2024-01-03T20:31:17Z

Bonte Lucas Gabriel:

Domnul Map vă pune la dispoziție un șir '''a[1]''', '''a[2]''', '''…, a[n]''' de numere naturale.

==Cerința==

Pentru fiecare '''a[i] (i=1..n)''' trebuie să spuneți de câte ori apare acest element în secvența '''a[1], a[2], …, a[i].'''

==Date de intrare==

Fișierul de intrare '''mapin.txt''' conține pe prima linie numărul '''n'''. Pe linia a doua, separate prin câte un spațiu, sunt elementele șirului.

==Date de ieșire==

În fișierul de ieșire '''mapout.txt''' se vor afișa pe primul rând '''n''' numere naturale, al '''i'''-lea număr reprezentând numărul de apariții ale lui '''a[i]''' în secvența '''a[1], a[2], …, a[i].'''

==Restricții și precizări==

*'''1 ≤ n ≤ 200 000'''
*'''0 <= a[i] <= 1018'''

==Exemplul 1:==

'''mapin.txt'''

7
1 9876543210 1 3 3 9876543210 9876543210

'''mapout.txt'''

Datele de intrare corespund restrictiilor impuse
1 1 2 1 2 2 3

==Exemplul 2:==

'''mapin.txt'''

map

'''mapout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Primul element este '''1'''. Apare o singură dată până acum.
Al doilea element este '''9876543210'''. Și el apare pentru prima dată.
Al treilea element este '''1'''. Apare a doua oară.
Al patrulea element este '''3'''. Apare prima oară.
Al cincilea element este '''3'''. Apare a doua oară.
Al șaselea element este '''9876543210'''. Apare a doua oară.
Al șaptelea element este '''9876543210'''. Apare a treia oară.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import defaultdict

def validare(nr_n, string, fisier_out): # functia de validare a datelor de intrare
if not (1 <= nr_n <= 200000):
raise ValueError("n nu este in intervalul [1, 200000]")

for numar in string:
if not (0 <= numar <= 10**18): # fiecare numar trebuie sa fie intre 0 si 10^18
raise ValueError("Un numar din sir nu este in intervalul [0, 10^18]")

fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")

def rezolvare(string, fisier_out): # functia de rezolvare
aparitii = defaultdict(int)
for numar in string:
aparitii[numar] += 1
fisier_out.write(str(aparitii[numar]) + " ")

if __name__ == '__main__':
file_in = open("mapin.txt", "r") # declararea fisierelor
file_out = open("mapout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n_str = file_in.readline().strip() # citirea numarului ca sir de caractere
try:
n = int(n_str) # incercam sa convertim sirul de caractere in numar intreg
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
file_in.close()
file_out.close()
exit(0) # iesim din program daca conversia esueaza

sir = list(map(int, file_in.readline().split()))

validare(n, sir, file_out) # apelul functiei de validare
rezolvare(sir, file_out) # apelul functiei de rezolvare

except ValueError as ve:
file_out.write(str(ve))
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

file_in.close()
file_out.close()

</syntaxhighlight>

4088 - BSTQ

2024-01-03T20:21:36Z

Bonte Lucas Gabriel:

Se consideră un șir '''A''', inițial vid. Asupra lui '''A''' se aplică '''n''' operații de două tipuri:

'''1 x''' – adaugă numărul '''x''' în '''A'''
'''2 k''' – dacă '''A''' ar fi ordonat crescător, care ar fi a '''k'''-a valoare?

==Cerința==

Să se răspundă la cele '''n''' întrebări.

==Date de intrare==

Fișierul de intrare '''bstqin.txt''' conține pe prima linie numărul '''n''', iar pe următoarele '''n''' linii se află câte o operație de tip '''1''' sau '''2'''.

==Date de ieșire==

Fișierul de ieșire '''bstqout.txt''' va conține atâtea linii câte operații de tip '''2''' sunt în fișierul de intrare.

==Restricții și precizări==

*'''1 ≤ n ≤ 200.000'''
*Numerele care se adaugă în '''A''' sunt numere întregi reprezentate pe '''32''' de biți cu semn.
*Este garantat că la orice operație '''2 k''' valoarea lui '''k''' este mai mică sau egală decât numărul de elemente din '''A'''.
*Este garantat că numerele care se introduc în '''A''' prin operația de tip '''1''' sunt generate aleator.

==Exemplul 1:==

'''bstqin.txt'''

16
1 7
1 9
1 3
1 7
2 3
2 2
1 10
1 2
2 4
2 5
1 5
2 3
1 8
1 10
1 4
1 3

'''bstqout.txt'''

Datele de intrare corespund restrictiilor impuse
7
7
7
9
5

==Exemplul 2:==

'''bstqin.txt'''

bstq

'''bstqout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

La prima întrebare, '''2 3''', deja în '''A''' sunt valorile '''3,7,7,9''', deci a treia valoare este '''7'''.
La a doua întrebare, '''2 2, A = 3,7,7,9''', deci a doua valoare este '''7'''.
La a treia întrebare, '''2 4, A = 2,3,7,7,9,10''', deci a patra valoare este '''7'''.
La a patra întrebare, '''2 5, A = 2,3,7,7,9,10''', deci a cincea valoare este '''9'''.
La a cincea întrebare, '''2 3, A = 2,3,5,7,7,9,10''', deci a treia valoare este '''5'''.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from bisect import insort_left

def validare(nr_n, operatii):
if nr_n > 200000:
raise ValueError
for operation in operatii:
if operation[0] == 1 and (operation[1] < -2147483648 or operation[1] > 2147483647):
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def process_operations(operatii, fisier_out):
a = []
for operation in operatii:
if operation[0] == 1:
insort_left(a, operation[1])
elif operation[0] == 2:
fisier_out.write(str(a[operation[1] - 1]) + '\n')

if __name__ == '__main__':
file_in = open("bstqin.txt", "r")
file_out = open("bstqout.txt", "w")
try:
n = int(file_in.readline())
operations = [list(map(int, file_in.readline().split())) for _ in range(n)]
validare(n, operations)
process_operations(operations, file_out)
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

3010 - Bst

2024-01-03T20:12:39Z

Bonte Lucas Gabriel:

Un arbore binar de căutare ('''BST – Binary Search Tree''') este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică sau egală decât valoarea memorată în orice nod din subarborele său drept.

==Cerința==

Dându-se un șir de '''n''' numere naturale, să se ordoneze crescător utilizând un '''BST'''.

==Date de intrare==

Fișierul de intrare '''bstin.txt''' 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 '''bstout.txt''' va conține pe prima linie, separate prin spațiu, cele '''n''' numere din șir, ordonate crescător.

==Restricții și precizări==

*'''1 ≤ n ≤ 100.000'''
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000.000'''
*Această problemă este destinată învățării arborilor de căutare, deci recomandarea este să memorați mai întâi numerele într-un '''BST''', apoi, cu o parcurgere în inordine să afișați șirul de numere ordonat crescător
*Se știe că există cazuri când un '''BST''' poate avea multe nivele și în consecință complexitatea sortării să fie chiar '''O(n x n).''' Un exemplu este atunci când șirul inițial este ordonat descrescător. Dar este garantat că testele au fost generate aleator, deci numărul de nivele din arbore va fi aproximativ egal cu '''log2n'''.

==Exemplul 1:==

'''bstin.txt'''

10
20 7 13 200 15 100 25 3 17 39

'''bstout.txt'''

Datele de intrare corespund restrictiilor impuse
3 7 13 15 17 20 25 39 100 200

==Exemplul 2:==

'''bstin.txt'''

bst

'''bstout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key

def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root

def inorder(root, fisier_out):
if root:
inorder(root.left, fisier_out)
fisier_out.write(str(root.val) + " ")
inorder(root.right, fisier_out)

def validare(nr):
if len(nr) > 100000:
raise ValueError
for numar in nr:
if numar < 0 or numar > 1000000000:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == '__main__':
file_in = open("bstin.txt", "r")
file_out = open("bstout.txt", "w")
try:
n = int(file_in.readline())
arr = list(map(int, file_in.readline().split()))
validare(arr)
r = Node(arr[0])
for i in range(1, n):
r = insert(r, arr[i])
inorder(r, file_out)
file_out.write('\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

3010 - Bst

2024-01-03T17:25:31Z

Bonte Lucas Gabriel:

Un arbore binar de căutare ('''BST – Binary Search Tree''') este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică sau egală decât valoarea memorată în orice nod din subarborele său drept.

==Cerința==

Dându-se un șir de '''n''' numere naturale, să se ordoneze crescător utilizând un '''BST'''.

==Date de intrare==

Fișierul de intrare '''bstin.txt''' 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 '''bstout.txt''' va conține pe prima linie, separate prin spațiu, cele '''n''' numere din șir, ordonate crescător.

==Restricții și precizări==

*'''1 ≤ n ≤ 100.000'''
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000.000'''
*Această problemă este destinată învățării arborilor de căutare, deci recomandarea este să memorați mai întâi numerele într-un '''BST''', apoi, cu o parcurgere în inordine să afișați șirul de numere ordonat crescător
*Se știe că există cazuri când un BST poate avea multe nivele și în consecință complexitatea sortării să fie chiar '''O(n x n).''' Un exemplu este atunci când șirul inițial este ordonat descrescător. Dar este garantat că testele au fost generate aleator, deci numărul de nivele din arbore va fi aproximativ egal cu '''log2n'''.

==Exemplul 1:==

bst.in

10
20 7 13 200 15 100 25 3 17 39
bst.out

3 7 13 15 17 20 25 39 100 200

class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key

def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root

def inorder(root, fisier_out):
if root:
inorder(root.left, fisier_out)
fisier_out.write(str(root.val) + " ")
inorder(root.right, fisier_out)

def validare(nr):
if len(nr) > 100000:
raise ValueError
for numar in nr:
if numar < 0 or numar > 1000000000:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == '__main__':
file_in = open("bstin.txt", "r")
file_out = open("bstout.txt", "w")
try:
n = int(file_in.readline())
arr = list(map(int, file_in.readline().split()))
validare(arr)
r = Node(arr[0])
for i in range(1, n):
r = insert(r, arr[i])
inorder(r, file_out)
file_out.write('\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

3526 - String Query

2024-01-03T17:21:32Z

Bonte Lucas Gabriel:

==Cerința==

Se dă un string '''s''' de lungime '''n''' și '''q''' query-uri de forma ('''op''', '''x''', '''y'''), unde '''op''' poate fi '''0''' sau '''1'''. Dacă '''op''' este egal cu '''1''', atunci caracterul de pe poziția '''x''' din '''s''' va deveni '''y'''. Dacă '''op''' este egal cu '''0''', se va afișa numărul de caractere distincte ale lui '''s''' din intervalul '''[x, y]'''.

==Date de intrare==

Programul citește de la tastatură '''n, s, q''' si cele '''q''' query-uri.

==Date de ieșire==

Programul va afișa pe ecran raspunsurile la query-urile de tipul '''0''', fiecare pe linie nouă.

==Restricții și precizări==

*'''1 ≤ n ≤ 5.000.000'''
*'''1 ≤ q ≤ 250.000'''
*'''s''' este format doar din litere mici ale alfabetului englez

==Exemplul 1:==

'''Intrare'''

4
aaaa
4
1 2 b
1 3 c
0 1 2
0 2 4

'''Ieșire'''

Datele de intrare corespund restrictiilor impuse.
2
3

==Exemplul 2:==

'''Intrare'''

string

'''Ieșire'''

Datele de intrare nu corespund restrictiilor impuse.

==Explicație==

După primele '''2''' operatii, '''s''' = '''"abca"'''.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def verificare_restrictii(nr_n, nr_q):
if 1 <= nr_n <= 5000000 and 1 <= nr_q <= 250000:
return True
else:
return False

def procesare_query(nr_s, nr_q, intrebare):
for i in range(nr_q):
nr_op, nr_x, nr_y = intrebare[i]
if nr_op == 1:
nr_s[nr_x - 1] = nr_y
elif nr_op == 0:
print(len(set(nr_s[nr_x - 1:nr_y])))

if __name__ == '__main__':
try:
n = int(input("Introduceti lungimea sirului: "))
s = list(input("Introduceti sirul: "))
q = int(input("Introduceti numarul de query-uri: "))
query = []
for _ in range(q):
op, x, y = input("Introduceti query-ul: ").split()
x = int(x)
if op == '1':
query.append((1, x, y))
else:
y = int(y)
query.append((0, x, y))

if verificare_restrictii(n, q):
print("Datele de intrare corespund restrictiilor impuse.")
procesare_query(s, q, query)
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

2217 - Map

2024-01-03T17:14:51Z

Bonte Lucas Gabriel: Pagină nouă: Domnul Map vă pune la dispoziție un șir a[1], a[2], …, a[n] de numere naturale. Cerința Pentru fiecare a[i] (i=1..n) trebuie să spuneți de câte ori apare acest element în secvența a[1], a[2], …, a[i]. Date de intrare Fișierul de intrare map.in conține pe prima linie numărul n. Pe linia a doua, separate prin câte un spațiu, sunt elementele șirului. Date de ieșire În fișierul de ieșire map.out se vor afișa pe primul rând n numere naturale, al i-lea n...

Domnul Map vă pune la dispoziție un șir a[1], a[2], …, a[n] de numere naturale.

Cerința
Pentru fiecare a[i] (i=1..n) trebuie să spuneți de câte ori apare acest element în secvența a[1], a[2], …, a[i].

Date de intrare
Fișierul de intrare map.in conține pe prima linie numărul n. Pe linia a doua, separate prin câte un spațiu, sunt elementele șirului.

Date de ieșire
În fișierul de ieșire map.out se vor afișa pe primul rând n numere naturale, al i-lea număr reprezentând numărul de apariții ale lui a[i] în secvența a[1], a[2], …, a[i].

Restricții și precizări
1 ≤ n ≤ 200 000
0 <= a[i] <= 1018
Exemplu:
map.in

7
1 9876543210 1 3 3 9876543210 9876543210
map.out

1 1 2 1 2 2 3
Explicație
Primul element este 1. Apare o singură dată până acum.
Al doilea element este 9876543210. Și el apare pentru prima dată.
Al treilea element este 1. Apare a doua oară.
Al patrulea element este 3. Apare prima oară.
Al cincilea element este 3. Apare a doua oară.
Al șaselea element este 9876543210. Apare a doua oară.
Al șaptelea element este 9876543210. Apare a treia oară.

from collections import defaultdict

def validare(nr_n, string, fisier_out): # functia de validare a datelor de intrare
if not (1 <= nr_n <= 200000):
raise ValueError("n nu este in intervalul [1, 200000]")

for numar in string:
if not (0 <= numar <= 10**18): # fiecare numar trebuie sa fie intre 0 si 10^18
raise ValueError("Un numar din sir nu este in intervalul [0, 10^18]")

fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")

def rezolvare(string, fisier_out): # functia de rezolvare
aparitii = defaultdict(int)
for numar in string:
aparitii[numar] += 1
fisier_out.write(str(aparitii[numar]) + " ")

if __name__ == '__main__':
file_in = open("mapin.txt", "r") # declararea fisierelor
file_out = open("mapout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n_str = file_in.readline().strip() # citirea numarului ca sir de caractere
try:
n = int(n_str) # incercam sa convertim sirul de caractere in numar intreg
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
file_in.close()
file_out.close()
exit(0) # iesim din program daca conversia esueaza

sir = list(map(int, file_in.readline().split()))

validare(n, sir, file_out) # apelul functiei de validare
rezolvare(sir, file_out) # apelul functiei de rezolvare

except ValueError as ve:
file_out.write(str(ve))
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

file_in.close()
file_out.close()

2534 - Bogdan

2024-01-03T17:08:46Z

Bonte Lucas Gabriel: Pagină nouă: Bogdan și Ionuț au fost "bff" încă din clasa V, dar acum destinele lor se cam despart…. Pentru a-l consola pe Bogdan, Ionuț i-a făcut o problema cadou. Bogdan nu vrea să-l dezamăgească pe Ionut, așa că vă cere ajutorul pentru a rezolva problema împreuna. Cerința Se dă un șir de n elemente, numere naturale. Problema constă în două operații: 1 i val : Elementul de pe poziția i se înlocuiește cu valoarea val. 2 i j : Stabiliți dacă secvența [i,j], d...

Bogdan și Ionuț au fost "bff" încă din clasa V, dar acum destinele lor se cam despart…. Pentru a-l consola pe Bogdan, Ionuț i-a făcut o problema cadou. Bogdan nu vrea să-l dezamăgească pe Ionut, așa că vă cere ajutorul pentru a rezolva problema împreuna.

Cerința
Se dă un șir de n elemente, numere naturale. Problema constă în două operații:

1 i val : Elementul de pe poziția i se înlocuiește cu valoarea val.
2 i j : Stabiliți dacă secvența [i,j], din șirul curent, este ordonată crescător.

Date de intrare
Fișierul de intrare bogdan.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații. Pe a treia linie a fișierului se afla numărul O, care reprezintă numărul de operații. Pe următoarele O linii se vor afla operațiile.

Date de ieșire
Fișierul de ieșire bogdan.out va conține răspunsurile pentru operațiile de tipul 2, pe linie nouă fiecare.
Dacă răspunsul este afirmativ, se va afișa DA, în caz contrar NU.

Restricții și precizări
1 ≤ n ≤ 100.000
1 ≤ O ≤ 300.000
numerele fiecărui șir curent vor fi mai mici decât 2.000.000.000
Observație importantă : bff = Best Friends Forever
Exemplu:
bogdan.in

6
22 9 2003 14 8 2003
4
2 1 6
1 1 8
2 1 3
2 4 5
bogdan.out

NU
DA
NU

def validare(nr_n, string,
nr_o, fisier_out): # functia de validare a datelor de intrare
if not (1 <= nr_n <= 100000):
raise ValueError("n nu este in intervalul [1, 100000]")

if not (1 <= nr_o <= 300000):
raise ValueError("O nu este in intervalul [1, 300000]")

for numar in string:
if not (numar < 2000000000): # fiecare numar trebuie sa fie mai mic decat 2.000.000.000
raise ValueError("Un numar din sir este mai mare sau egal cu 2.000.000.000")

fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")

def rezolvare(string, exercitii, fisier_out): # functia de rezolvare
for operatie in exercitii:
if operatie[0] == 1:
string[operatie[1] - 1] = operatie[2]
elif operatie[0] == 2:
if string[operatie[1] - 1:operatie[2]] == sorted(string[operatie[1] - 1:operatie[2]]):
fisier_out.write("DA\n")
else:
fisier_out.write("NU\n")

if __name__ == '__main__':
file_in = open("bogdanin.txt", "r") # declararea fisierelor
file_out = open("bogdanout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n_str = file_in.readline().strip() # citirea numarului ca sir de caractere
try:
n = int(n_str) # incercam sa convertim sirul de caractere in numar intreg
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
file_in.close()
file_out.close()
exit(0) # iesim din program daca conversia esueaza

sir = list(map(int, file_in.readline().split()))

o = int(file_in.readline())
operatii = [list(map(int, file_in.readline().split())) for _ in range(o)]

validare(n, sir, o, file_out) # apelul functiei de validare
rezolvare(sir, operatii, file_out) # apelul functiei de rezolvare

except ValueError as ve:
file_out.write(str(ve))
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

file_in.close()
file_out.close()

3526 - String Query

2024-01-03T16:36:54Z

Bonte Lucas Gabriel: Pagină nouă: Cerința Se dă un string s de lungime n și q query-uri de forma (op, x, y), unde op poate fi 0 sau 1. Dacă op este egal cu 1, atunci caracterul de pe poziția x din s va deveni y. Dacă op este egal cu 0, se va afișa numărul de caractere distincte ale lui s din intervalul [x, y]. Date de intrare Programul citește de la tastatură n, s, q si cele q query-uri. Date de ieșire Programul va afișa pe ecran raspunsurile la query-urile de tipul 0, fiecare pe linie nouă. R...

Cerința
Se dă un string s de lungime n și q query-uri de forma (op, x, y), unde op poate fi 0 sau 1. Dacă op este egal cu 1, atunci caracterul de pe poziția x din s va deveni y. Dacă op este egal cu 0, se va afișa numărul de caractere distincte ale lui s din intervalul [x, y].

Date de intrare
Programul citește de la tastatură n, s, q si cele q query-uri.

Date de ieșire
Programul va afișa pe ecran raspunsurile la query-urile de tipul 0, fiecare pe linie nouă.

Restricții și precizări
1 ≤ n ≤ 5.000.000
1 ≤ q ≤ 250.000
s este format doar din litere mici ale alfabetului englez
Exemplu:
Intrare

4
aaaa
4
1 2 b
1 3 c
0 1 2
0 2 4
Ieșire

2
3
Explicație
După primele 2 operatii, s = "abca".

def verificare_restrictii(nr_n, nr_q):
if 1 <= nr_n <= 5000000 and 1 <= nr_q <= 250000:
return True
else:
return False

def procesare_query(nr_s, nr_q, intrebare):
for i in range(nr_q):
nr_op, nr_x, nr_y = intrebare[i]
if nr_op == 1:
nr_s[nr_x - 1] = nr_y
elif nr_op == 0:
print(len(set(nr_s[nr_x - 1:nr_y])))

if __name__ == '__main__':
try:
n = int(input("Introduceti lungimea sirului: "))
s = list(input("Introduceti sirul: "))
q = int(input("Introduceti numarul de query-uri: "))
query = []
for _ in range(q):
op, x, y = input("Introduceti query-ul: ").split()
x = int(x)
if op == '1':
query.append((1, x, y))
else:
y = int(y)
query.append((0, x, y))

if verificare_restrictii(n, q):
print("Datele de intrare corespund restrictiilor impuse.")
procesare_query(s, q, query)
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")

4088 - BSTQ

2024-01-03T16:10:10Z

Bonte Lucas Gabriel: Pagină nouă: Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri: 1 x – adaugă numărul x în A 2 k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare? Cerința Să se răspundă la cele n întrebări. Date de intrare Fișierul de intrare bstq.in conține pe prima linie numărul n, iar pe următoarele n linii se află câte o operație de tip 1 sau 2. Date de ieșire Fișierul de ieșire bstq.out va conține atâtea linii câte oper...

Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri:

1 x – adaugă numărul x în A
2 k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare?
Cerința
Să se răspundă la cele n întrebări.

Date de intrare
Fișierul de intrare bstq.in conține pe prima linie numărul n, iar pe următoarele n linii se află câte o operație de tip 1 sau 2.

Date de ieșire
Fișierul de ieșire bstq.out va conține atâtea linii câte operații de tip 2 sunt în fișierul de intrare.

Restricții și precizări
1 ≤ n ≤ 200.000
Numerele care se adaugă în A sunt numere întregi reprezentate pe 32 de biți cu semn.
Este garantat că la orice operație 2 k valoarea lui k este mai mică sau egală decât numărul de elemente din A.
Este garantat că numerele care se introduc în A prin operația de tip 1 sunt generate aleator.
Exemplu:
bstq.in

16
1 7
1 9
1 3
1 7
2 3
2 2
1 10
1 2
2 4
2 5
1 5
2 3
1 8
1 10
1 4
1 3
bstq.out

7
7
7
9
5
Explicație
La prima întrebare, 2 3, deja în A sunt valorile 3,7,7,9, deci a treia valoare este 7.
La a doua întrebare, 2 2, A = 3,7,7,9, deci a doua valoare este 7.
La a treia întrebare, 2 4, A = 2,3,7,7,9,10, deci a patra valoare este 7.
La a patra întrebare, 2 5, A = 2,3,7,7,9,10, deci a cincea valoare este 9.
La a cincea întrebare, 2 3, A = 2,3,5,7,7,9,10, deci a treia valoare este 5.

from bisect import insort_left

def validare(nr_n, operatii):
if nr_n > 200000:
raise ValueError
for operation in operatii:
if operation[0] == 1 and (operation[1] < -2147483648 or operation[1] > 2147483647):
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def process_operations(operatii, fisier_out):
a = []
for operation in operatii:
if operation[0] == 1:
insort_left(a, operation[1])
elif operation[0] == 2:
fisier_out.write(str(a[operation[1] - 1]) + '\n')

if __name__ == '__main__':
file_in = open("bstqin.txt", "r")
file_out = open("bstqout.txt", "w")
try:
n = int(file_in.readline())
operations = [list(map(int, file_in.readline().split())) for _ in range(n)]
validare(n, operations)
process_operations(operations, file_out)
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

3010 - Bst

2024-01-03T16:00:56Z

Bonte Lucas Gabriel: Pagină nouă: Un arbore binar de căutare (BST – Binary Search Tree) este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică sau egală decât valoarea memorată în orice nod din subarborele său drept. Cerința Dându-se un șir de n numere naturale, să se ordoneze crescător utilizând un BST. Date de intrare Fișierul de intrare bst.in conține pe prima linie numă...

Un arbore binar de căutare (BST – Binary Search Tree) este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică sau egală decât valoarea memorată în orice nod din subarborele său drept.

Cerința
Dându-se un șir de n numere naturale, să se ordoneze crescător utilizând un BST.

Date de intrare
Fișierul de intrare bst.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 bst.out va conține pe prima linie, separate prin spațiu, cele n numere din șir, ordonate crescător.

Restricții și precizări
1 ≤ n ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
Această problemă este destinată învățării arborilor de căutare, deci recomandarea este să memorați mai întâi numerele într-un BST, apoi, cu o parcurgere în inordine să afișați șirul de numere ordonat crescător
Se știe că există cazuri când un BST poate avea multe nivele și în consecință complexitatea sortării să fie chiar O(n x n). Un exemplu este atunci când șirul inițial este ordonat descrescător. Dar este garantat că testele au fost generate aleator, deci numărul de nivele din arbore va fi aproximativ egal cu log2n.
Exemplu:
bst.in

10
20 7 13 200 15 100 25 3 17 39
bst.out

3 7 13 15 17 20 25 39 100 200

class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key

def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root

def inorder(root, fisier_out):
if root:
inorder(root.left, fisier_out)
fisier_out.write(str(root.val) + " ")
inorder(root.right, fisier_out)

def validare(nr):
if len(nr) > 100000:
raise ValueError
for numar in nr:
if numar < 0 or numar > 1000000000:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == '__main__':
file_in = open("bstin.txt", "r")
file_out = open("bstout.txt", "w")
try:
n = int(file_in.readline())
arr = list(map(int, file_in.readline().split()))
validare(arr)
r = Node(arr[0])
for i in range(1, n):
r = insert(r, arr[i])
inorder(r, file_out)
file_out.write('\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

0792 - Bi NeFrunze 1

2024-01-03T15:20:47Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în nodurile neterminale ale arborelui, în ordine descrescătoare. ==Date de intrare== Fișierul de intrare '''binefrunze1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apare valoare...

==Cerința==

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în nodurile neterminale ale arborelui, în ordine descrescătoare.

==Date de intrare==

Fișierul de intrare '''binefrunze1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apare valoarea '''0'''. Dacă un nod nu are descendent drept, în listă va apare valoarea '''0'''.

==Date de ieșire==

Fișierul de ieșire '''binefrunze1out.txt''' va conține pe prima linie valorile memorate în nodurile neterminale ale arborelui, în ordine descrescătoare, separate prin câte un spațiu.

==Restricții și precizări==

*se recomandă folosirea arborilor alocați dinamic.
*arborele nu va avea mai mult de '''5000''' de noduri neterminale

==Exemplul 1:==

'''binefrunze1in.txt'''

67 51 18 0 0 24 0 0 48 0 11 0 0

'''binefrunze1out.txt'''

Datele de intrare corespund restrictiilor impuse
67 51 48

==Exemplul 2:==

'''binefrunze1in.txt'''

binefrunze1

'''binefrunze1out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui desenat mai jos:

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

def construct_tree(data_list):
data = data_list.pop(0)
if data == 0:
return None
node = Node(data)
node.left = construct_tree(data_list)
node.right = construct_tree(data_list)
return node

def get_non_leaf_nodes(node, non_frunze):
if node is None or (node.left is None and node.right is None):
return
non_frunze.append(node.data)
get_non_leaf_nodes(node.left, non_frunze)
get_non_leaf_nodes(node.right, non_frunze)

def validare(nr):
if len(nr) > 5000:
raise ValueError
for cifra in nr:
if cifra < 0:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == '__main__':
file_in = open("binefrunze1in.txt", "r")
file_out = open("binefrunze1out.txt", "w")
try:
numar = list(map(int, file_in.readline().split()))
validare(numar)
root = construct_tree(numar)
non_leaf_nodes = []
get_non_leaf_nodes(root, non_leaf_nodes)
non_leaf_nodes.sort(reverse=True)
file_out.write(' '.join(map(str, non_leaf_nodes)))
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0791 - Bi Frunze 1

2024-01-03T15:08:43Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în nodurile terminale ale arborelui, în ordine crescătoare. ==Date de intrare== Fișierul de intrare '''bifrunze1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''...

==Cerința==

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în nodurile terminale ale arborelui, în ordine crescătoare.

==Date de intrare==

Fișierul de intrare '''bifrunze1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dacă un nod nu are descendent drept, în listă va apărea valoarea '''0'''.

==Date de ieșire==

Fișierul de ieșire '''bifrunze1out.txt''' va conține pe prima linie valorile memorate în nodurile terminale ale arborelui, în ordine crescătoare, separate prin câte un spațiu.

==Restricții și precizări==

*se recomandă folosirea arborilor alocați dinamic.
*arborele nu va avea mai mult de '''5000''' de noduri terminale

==Exemplul 1:==

'''bifrunze1in.txt'''

67 51 18 0 0 24 0 0 48 0 11 0 0

'''bifrunze1out.txt'''

Datele de intrare corespund restrictiilor impuse
11 18 24

==Exemplul 2:==

'''bifrunze1in.txt'''

bifrunze1

'''bifrunze1out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui desenat mai jos:

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

def construct_tree(data_list):
data = data_list.pop(0)
if data == 0:
return None
node = Node(data)
node.left = construct_tree(data_list)
node.right = construct_tree(data_list)
return node

def get_leaf_nodes(node, frunze):
if node is None:
return
if node.left is None and node.right is None:
frunze.append(node.data)
get_leaf_nodes(node.left, frunze)
get_leaf_nodes(node.right, frunze)

def validare(nr):
if len(nr) > 5000:
raise ValueError
for cifra in nr:
if cifra < 0:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == '__main__':
file_in = open("bifrunze1in.txt", "r")
file_out = open("bifrunze1out.txt", "w")
try:
numar = list(map(int, file_in.readline().split()))
validare(numar)
root = construct_tree(numar)
leaf_nodes = []
get_leaf_nodes(root, leaf_nodes)
leaf_nodes.sort()
file_out.write(' '.join(map(str, leaf_nodes)))
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0755 - Post Ordine 1

2023-12-19T20:42:45Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în arbore în urma parcurgerii în postordine. ==Date de intrare== Fișierul de intrare '''postordine1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dacă u...

==Cerința==

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în arbore în urma parcurgerii în postordine.

==Date de intrare==

Fișierul de intrare '''postordine1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dacă un nod nu are descendent drept, în listă va apărea valoarea '''0'''.

==Date de ieșire==

Fișierul de ieșire '''postordine1out.txt''' va conține pe prima linie valorile memorate în arbore în urma parcurgerii în postordine, separate prin exact un spațiu.

==Restricții și precizări==

*se recomandă folosirea arborilor alocați dinamic.

==Exemplul 1:==

'''postordine1in.txt'''

67 51 18 0 0 24 0 0 48 0 11 0 0

'''postordine1out.txt'''

Datele de intrare corespund restrictiilor impuse
18 24 51 11 48 67

==Exemplul 2:==

'''postordine1in.txt'''

postordine1

'''postordine1out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui desenat mai jos:

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
def __init__(self, date):
self.left = None
self.right = None
self.data = date

def construct_tree(date, index):
if index >= len(date) or int(date[index]) == 0:
return None, index + 1

radacina = Node(int(date[index]))
radacina.left, index = construct_tree(date, index + 1)
radacina.right, index = construct_tree(date, index)

return radacina, index

def postordine(radacina):
if radacina:
postordine(radacina.left)
postordine(radacina.right)
file_out.write(str(radacina.data) + " ")

def validare(date):
for num in date:
if not num.isdigit():
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == '__main__':
file_in = open("postordine1in.txt", "r")
file_out = open("postordine1out.txt", "w")

try:
data = file_in.readline().split()
validare(data)
root, _ = construct_tree(data, 0)
postordine(root)

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0754 - In Ordine 1

2023-12-19T20:28:48Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în arbore în urma parcurgerii în inordine. ==Date de intrare== Fișierul de intrare '''inordine1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dacă un no...

==Cerința==

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în arbore în urma parcurgerii în inordine.

==Date de intrare==

Fișierul de intrare '''inordine1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dacă un nod nu are descendent drept, în listă va apărea valoarea '''0'''.

==Date de ieșire==

Fișierul de ieșire '''inordine1out.txt''' va conține pe prima linie valorile memorate în arbore în urma parcurgerii în inordine, separate prin exact un spațiu.

==Restricții și precizări==

*se recomandă folosirea arborilor alocați dinamic.

==Exemplul 1:==

'''inordine1in.txt'''

67 51 18 0 0 24 0 0 48 0 11 0 0

'''inordine1out.txt'''

Datele de intrare corespund restrictiilor impuse
18 51 24 67 48 11

==Exemplul 2:==

'''inordine1in.txt'''

inordine1

'''inordine1out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui desenat mai jos:

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
def __init__(self, date):
self.left = None
self.right = None
self.data = date

def construct_tree(date, index):
if index >= len(date) or int(date[index]) == 0:
return None, index + 1

radacina = Node(int(date[index]))
radacina.left, index = construct_tree(date, index + 1)
radacina.right, index = construct_tree(date, index)

return radacina, index

def inordine(radacina):
if radacina:
inordine(radacina.left)
file_out.write(str(radacina.data) + " ")
inordine(radacina.right)

def validare(date):
for num in date:
if not num.isdigit():
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == '__main__':
file_in = open("inordine1in.txt", "r")
file_out = open("inordine1out.txt", "w")

try:
data = file_in.readline().split()
validare(data)
root, _ = construct_tree(data, 0)
inordine(root)

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0753 - Pre Ordine 1

2023-12-19T20:15:33Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în subarborele stâng al rădăcinii în urma parcurgerii în preordine. ==Date de intrare== Fișierul de intrare '''preordine1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea...

==Cerința==

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în subarborele stâng al rădăcinii în urma parcurgerii în preordine.

==Date de intrare==

Fișierul de intrare '''preordine1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dacă un nod nu are descendent drept, în listă va apare apărea '''0'''.

==Date de ieșire==

Fișierul de ieșire '''preordine1out.txt''' va conține pe prima linie valorile memorate în subarborele stâng al rădăcinii în urma parcurgerii în preordine, separate prin exact un spațiu.

==Restricții și precizări==

*se recomandă folosirea arborilor alocați dinamic.

==Exemplul 1:==

'''preordine1in.txt'''

67 51 18 0 0 24 0 0 48 0 11 0 0

'''preordine1out.txt'''

Datele de intrare corespund restrictiilor impuse
51 18 24

==Exemplul 2:==

'''preordine1in.txt'''

preordine1

'''preordine1out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui desenat mai jos:

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
def __init__(self, date):
self.left = None
self.right = None
self.data = date

def construct_tree(date, index):
if index >= len(date) or int(date[index]) == 0:
return None, index + 1

radacina = Node(int(date[index]))
radacina.left, index = construct_tree(date, index + 1)
radacina.right, index = construct_tree(date, index)

return radacina, index

def preordine(radacina):
if radacina:
file_out.write(str(radacina.data) + " ")
preordine(radacina.left)
preordine(radacina.right)

def validare(date):
if len(date) > 1000:
raise ValueError
for num in date:
if not num.isdigit():
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == '__main__':
file_in = open("preordine1in.txt", "r")
file_out = open("preordine1out.txt", "w")

try:
data = file_in.readline().split()
validare(data)
root, _ = construct_tree(data, 0)
preordine(root.left)

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

3503 - Bi Arbore 1

2023-12-13T18:19:15Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine valorile memorate în descendenții direcți ai rădăcinii arborelui. ==Date de intrare== Fișierul de intrare '''biarbore1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dac...

==Cerința==

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine valorile memorate în descendenții direcți ai rădăcinii arborelui.

==Date de intrare==

Fișierul de intrare '''biarbore1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dacă un nod nu are descendent drept, în listă va apărea valoarea '''0'''.

==Date de ieșire==

Fișierul de ieșire '''biarbore1out.txt''' va conține pe prima linie două valori '''X Y''', separate prin exact un spațiu; '''X''' reprezintă valoarea memorată în fiul stâng al rădăcinii, iar '''Y''' reprezintă valoarea memorată în fiul drept al rădăcinii. Dacă rădăcina nu are fiu stâng sau fiu drept, se va afișa corespunzător valoarea '''0'''.

==Restricții și precizări==

*se vor citi cel mult '''1.111.111''' numere
*numerele din fișierului de intrare vor fi mai mici decât '''1.111.111.111'''

==Exemplul 1:==

'''biarbore1in.txt'''

67 51 18 0 0 24 0 0 48 0 11 0 0

'''biarbore1out.txt'''

Datele de intrare corespund restrictiilor impuse
51 48

==Exemplul 2:==

'''biarbore1in.txt'''

biarbore1

'''biarbore1out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui desenat mai jos:

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data

def validare(arbori): # functia de validare a datelor de intrare
if len(arbori) > 1111111: # se vor citi cel mult 1.111.111 numere
raise ValueError

for nod in arbori:
if not nod.isdigit() or int(nod) >= 1111111111: # numerele din fișierului de intrare vor fi mai mici decât 1.111.111.111
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def biarbore(arbori): # functia de rezolvare
radacina = Node(arbori[0])
radacina.left = Node(arbori[1])
radacina.right = Node(arbori[8])
file_out.write(f"{radacina.left.data} {radacina.right.data}")

if __name__ == '__main__':
file_in = open("biarbore1in.txt", "r") # declararea fisierelor
file_out = open("biarbore1out.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
arbore = file_in.readline().split() # citirea arborelui se face ca sir de caractere

validare(arbore) # apelul functiei de validare
biarbore(arbore) # apelul functiei de rezolvare

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0752 - Bi Arbore

2023-12-13T17:51:34Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine valorile memorate în descendenții direcți ai rădăcinii arborelui. ==Date de intrare== Fișierul de intrare '''biarborein.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dac...

==Cerința==

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine valorile memorate în descendenții direcți ai rădăcinii arborelui.

==Date de intrare==

Fișierul de intrare '''biarborein.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apărea valoarea '''0'''. Dacă un nod nu are descendent drept, în listă va apărea valoarea '''0'''.

==Date de ieșire==

Fișierul de ieșire '''biarboreout.txt''' va conține pe prima linie două valori '''X Y''', separate prin exact un spațiu; '''X''' reprezintă valoarea memorată în fiul stâng al rădăcinii, iar '''Y''' reprezintă valoarea memorată în fiul drept al rădăcinii. Dacă rădăcina nu are fiu stâng sau fiu drept, se va afișa corespunzător valoarea '''0'''.

==Restricții și precizări==

*se recomandă folosirea arborilor alocați dinamic.

==Exemplul 1:==

'''biarborein.txt'''

67 51 18 0 0 24 0 0 48 0 11 0 0

'''biarboreout.txt'''

Datele de intrare corespund restrictiilor impuse
51 48

==Exemplul 2:==

'''biarborein.txt'''

biarbore

'''biarboreout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui desenat mai jos:

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data

def validare(arbori): # functia de validare a datelor de intrare
if len(arbori) > 1000:
raise ValueError

for nod in arbori:
if not nod.isdigit(): # fiecare caracter trebuie sa fie cifra
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def biarbore(arbori): # functia de rezolvare
radacina = Node(arbori[0])
radacina.left = Node(arbori[1])
radacina.right = Node(arbori[8])
file_out.write(f"{radacina.left.data} {radacina.right.data}")

if __name__ == '__main__':
file_in = open("biarborein.txt", "r") # declararea fisierelor
file_out = open("biarboreout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
arbore = file_in.readline().split() # citirea arborelui se face ca sir de caractere

validare(arbore) # apelul functiei de validare
biarbore(arbore) # apelul functiei de rezolvare

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0672 - Post Ordine

2023-12-13T17:11:20Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Considerăm un arbore binar cu '''n''' noduri în care fiecare nod este numerotat de la '''1''' la '''n''' și conține o valoare număr natural. Să se afișeze valorile din arbore în urma parcurgerii în postordine (stâng, drept, rădăcină). ==Date de intrare== Fișierul de intrare '''postordinein.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' linii contine câte '''3''' numere '''X st dr'''; linia '''i + 1''' din fi...

==Cerința==

Considerăm un arbore binar cu '''n''' noduri în care fiecare nod este numerotat de la '''1''' la '''n''' și conține o valoare număr natural. Să se afișeze valorile din arbore în urma parcurgerii în postordine (stâng, drept, rădăcină).

==Date de intrare==

Fișierul de intrare '''postordinein.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' linii contine câte '''3''' numere '''X st dr'''; linia '''i + 1''' din fișier conține informatiile despre nodul numerotat cu '''i: X''' reprezintă valoare din nod, '''st''' reprezintă numărul de ordine al descendentului stâng sau '''0''' dacă nodul '''i''' nu are descendent stâng, iar '''dr''' reprezintă numărul de ordine al descendentului drept sau '''0''' dacă nodul '''i''' nu are descendent drept.

==Date de ieșire==

Fișierul de ieșire '''postordineout.txt''' va conține pe prima linie '''n''' numere, separate prin exact un spațiu, reprezentând valorile din nodurile arborelui, obținute în urma parcurgerii în postordine.

==Restricții și precizări==

*'''1 ≤ n ≤ 1000'''
*valorile din nodurile arborelui vor fi mai mici sau egale cu '''1.000.000'''

==Exemplul 1:==

'''postordinein.txt'''

6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0

'''postordineout.txt'''

Datele de intrare corespund restrictiilor impuse
1 4 2 10 6 7

==Exemplul 2:==

'''postordinein.txt'''

postordine

'''postordineout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(nr_n, noduri):
if nr_n > 1000:
raise ValueError
for node in noduri[1:]:
if node.value > 1000000:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def postordine(node):
if node is not None:
postordine(node.left)
postordine(node.right)
file_out.write(str(node.value) + " ")

class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

if __name__ == '__main__':
file_in = open("postordinein.txt", "r")
file_out = open("postordineout.txt", "w")

try:
n = int(file_in.readline())
nodes = [None] + [Node(0) for _ in range(n)]
root = None

for i in range(1, n + 1):
X, st, dr = map(int, file_in.readline().split())
nodes[i].value = X
if st != 0:
nodes[i].left = nodes[st]
if dr != 0:
nodes[i].right = nodes[dr]
if i == 4: # nodul cu valoarea 7 este pe linia 4
root = nodes[i]

validare(n, nodes)
postordine(root)
file_out.close()

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0671 - In Ordine

2023-12-13T16:58:13Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Considerăm un arbore binar cu '''n''' noduri în care fiecare nod este numerotat de la '''1''' la '''n''' și conține o valoare număr natural. Să se afișeze valorile din arbore în urma parcurgerii în inordine (stâng, rădăcină, drept). ==Date de intrare== Fișierul de intrare '''inordinein.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' linii contine câte '''3''' numere '''X st dr'''; linia '''i + 1''' din fișie...

==Cerința==

Considerăm un arbore binar cu '''n''' noduri în care fiecare nod este numerotat de la '''1''' la '''n''' și conține o valoare număr natural. Să se afișeze valorile din arbore în urma parcurgerii în inordine (stâng, rădăcină, drept).

==Date de intrare==

Fișierul de intrare '''inordinein.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' linii contine câte '''3''' numere '''X st dr'''; linia '''i + 1''' din fișier conține informatiile despre nodul numerotat cu '''i: X''' reprezintă valoare din nod, '''st''' reprezintă numărul de ordine al descendentului stâng sau '''0''' dacă nodul '''i''' nu are descendent stâng, iar '''dr''' reprezintă numărul de ordine al descendentului drept sau '''0''' dacă nodul '''i''' nu are descendent drept.

==Date de ieșire==

Fișierul de ieșire '''inordineout.txt''' va conține pe prima linie '''n''' numere, separate prin exact un spațiu, reprezentând valorile din nodurile arborelui, obținute în urma parcurgerii în inordine.

==Restricții și precizări==

*'''1 ≤ n ≤ 1000'''
*valorile din nodurile arborelui vor fi mai mici sau egale cu '''1.000.000'''

==Exemplul 1:==

'''inordinein.txt'''

6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0

'''inordineout.txt'''

Datele de intrare corespund restrictiilor impuse
1 2 4 7 6 10

==Exemplul 2:==

'''inordinein.txt'''

inordine

'''inordineout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(nr_n, noduri):
if nr_n > 1000:
raise ValueError
for node in noduri[1:]:
if node.value > 1000000:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def inordine(node):
if node is not None:
inordine(node.left)
file_out.write(str(node.value) + " ")
inordine(node.right)

class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

if __name__ == '__main__':
file_in = open("inordinein.txt", "r")
file_out = open("inordineout.txt", "w")

try:
n = int(file_in.readline())
nodes = [None] + [Node(0) for _ in range(n)]
root = None

for i in range(1, n + 1):
X, st, dr = map(int, file_in.readline().split())
nodes[i].value = X
if st != 0:
nodes[i].left = nodes[st]
if dr != 0:
nodes[i].right = nodes[dr]
if i == 4: # nodul cu valoarea 7 este pe linia 4
root = nodes[i]

validare(n, nodes)
inordine(root)
file_out.close()

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0670 - Pre Ordine

2023-12-13T16:30:44Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Considerăm un arbore binar cu '''n''' noduri în care fiecare nod este numerotat de la '''1''' la '''n''' și conține o valoare număr natural. Să se afișeze valorile din arbore în urma parcurgerii în preordine (rădăcină, stâng, drept). ==Date de intrare== Fișierul de intrare '''preordinein.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' linii contine câte '''3''' numere '''X st dr'''; linia '''i + 1''' din fiș...

==Cerința==

Considerăm un arbore binar cu '''n''' noduri în care fiecare nod este numerotat de la '''1''' la '''n''' și conține o valoare număr natural. Să se afișeze valorile din arbore în urma parcurgerii în preordine (rădăcină, stâng, drept).

==Date de intrare==

Fișierul de intrare '''preordinein.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' linii contine câte '''3''' numere '''X st dr'''; linia '''i + 1''' din fișier conține informatiile despre nodul numerotat cu '''i: X''' reprezintă valoare din nod, st reprezintă numărul de ordine al descendentului stâng sau '''0''' dacă nodul '''i''' nu are descendent stâng, iar dr reprezintă numărul de ordine al descendentului drept sau '''0''' dacă nodul '''i''' nu are descendent drept.

==Date de ieșire==

Fișierul de ieșire '''preordineout.txt''' va conține pe prima linie '''n''' numere, separate prin exact un spațiu, reprezentând valorile din nodurile arborelui, obținute în urma parcurgerii în preordine.

==Restricții și precizări==

*'''1 ≤ n ≤ 1000'''
*valorile din nodurile arborelui vor fi mai mici sau egale cu '''1.000.000'''

==Exemplul 1:==

'''preordinein.txt'''

6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0

'''preordineout.txt'''

Datele de intrare corespund restrictiilor impuse
7 2 1 4 6 10

==Exemplul 2:==

'''preordinein.txt'''

preordine

'''preordineout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(n_noduri, arbori): # functia de validare a datelor de intrare
if n_noduri > 1000 or n_noduri < 1:
raise ValueError

for nod in arbori:
if nod[0] > 1000000 or nod[0] < 1 or nod[1] < 0 or nod[2] < 0:
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def preordine(arbori): # functia de rezolvare
def dfs(nod):
if nod == 0:
return
file_out.write(str(arbori[nod - 1][0]) + " ")
dfs(arbori[nod - 1][1])
dfs(arbori[nod - 1][2])

dfs(4) # pornim de la nodul cu numarul 4, care este radacina in exemplul tau

if __name__ == '__main__':
file_in = open("preordinein.txt", "r") # declararea fisierelor
file_out = open("preordineout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n = int(file_in.readline()) # citirea numarului de noduri
arbore = [list(map(int, file_in.readline().split())) for _ in range(n)] # citirea arborelui

validare(n, arbore) # apelul functiei de validare
preordine(arbore) # apelul functiei de rezolvare

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0867 - Generare2 cu Coada

2023-12-12T21:22:07Z

Bonte Lucas Gabriel:

Enunțul acestei probleme este identic cu cel al problemei #Generare2 . Vă recomandăm să o rezolvați folosind o structură de date de tip coadă.

==Cerința==

Se dau patru numere naturale '''n a x y'''. Să se afișeze elementele mulțimii '''M''', cu următoarele proprietăți:

*toate elementele lui '''M''' sunt numere naturale mai mici sau egale cu '''n''';
*'''a''' se află în '''M''';
*dacă '''b''' se află în '''M''', atunci '''b+x''' și '''b+y''' se află în '''M'''.

==Date de intrare==

Programul citește de la tastatură numerele '''n a x y'''.

==Date de ieșire==

Programul va afișa pe ecran elementele mulțimii '''M''', în ordine crescătoare, separate prin câte un spațiu.

==Restricții și precizări==

*'''1 ≤ n ≤ 10000'''
*'''1 ≤ x , y ≤ 10000'''
*'''0 ≤ a ≤ 10000'''

==Exemplul 1:==

;Intrare

25 3 4 11

;Ieșire

Datele de intrare corespund restrictiilor impuse.
3 7 11 14 15 18 19 22 23 25

==Exemplul 2:==

;Intrare

generare2 cu coada

;Ieșire

Datele de intrare nu corespund restrictiilor impuse.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def verificare_restrictii(nr_n, nr_a, nr_x, nr_y): # functia de verificare a datelor de intrare
if 1 <= nr_n <= 10000 and 1 <= nr_x <= 10000 and 1 <= nr_y <= 10000 and 0 <= nr_a <= 10000:
return True
else:
return False

def solve(nr_n, nr_a, nr_x, nr_y):
# Creăm o listă pentru a ține evidența numerelor pe care le-am vizitat
visited = [False] * (nr_n + 1)

# Inițializăm coada cu numărul de start 'a'
queue = deque([nr_a])

# Marcăm numărul 'a' ca vizitat
visited[nr_a] = True

# Parcurgem toate numerele din coadă
while queue:
# Scoatem numărul curent din coadă
current = queue.popleft()

# Adăugăm 'x' și 'y' la numărul curent și verificăm dacă sunt mai mici sau egale cu 'n' și dacă nu au fost vizitate încă
for i in [current + nr_x, current + nr_y]:
if i <= nr_n and not visited[i]:
# Dacă sunt, le adăugăm în coadă și le marcăm ca vizitate
queue.append(i)
visited[i] = True

# Returnăm toate numerele vizitate
return [i for i in range(nr_n + 1) if visited[i]]

if __name__ == '__main__':
try:
n = int(input("Introduceti numarul n: ")) # citirea numarului n
a = int(input("Introduceti numarul a: ")) # citirea numarului a
x = int(input("Introduceti numarul x: ")) # citirea numarului x
y = int(input("Introduceti numarul y: ")) # citirea numarului y

if verificare_restrictii(n, a, x, y): # verificam datele de intrare
print("Datele de intrare corespund restrictiilor impuse.")
print(*solve(n, a, x, y)) # apelam functia de rezolvare
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
# ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

4052 - emigrare

2023-12-12T21:12:45Z

Bonte Lucas Gabriel:

==Cerința==

Tărâmul emigranților se poate reprezenta printr-o matrice de dimensiuni '''n×m'''. O țară este formată din toate celulele care au o anumită valoare. În fiecare celulă locuiește un om. Pe tărâmul emigranților fiecare om este nemulțumit și vrea să ajungă în orice altă țară în cel mai scurt timp posibil.

Calculați pentru fiecare celulă distanța minimă până la o celulă de valoare diferită.

==Date de intrare==

Pe prima linie se află numerele '''n''' și '''m'''. Pe a '''i'''-a dintre următoarele '''n''' linii se găsește o secvență de '''m''' numere. Al '''j'''-lea număr se notează '''ai,j''' și reprezintă țara din care face parte celula '''(i,j)'''
.

==Date de ieșire==

Se vor afișa '''nm''' numere naturale reprezenând distanțele pentru fiecare om în parte. Pe a '''i'''-a dintre cele '''n''' linii se găsește o secvență de '''m''' numere. Al '''j'''-lea număr se notează '''di,j''' și reprezintă distanța minimă ce trebuie să o parcurgă omul din celula '''(i,j)''' pentru a ajunge în altă țară.

==Restricții și precizări==

*'''2≤n,m≤10^3'''
*Se garantează că există cel puțin două țări
*Celulele unei țări nu sunt neapărat conectate
*Pentru '''20''' de puncte, '''n,m≤10'''
*Pentru '''40''' de puncte, '''n,m≤40'''

==Exemplul 1:==

;Intrare

8 9
1 1 1 1 1 1 1 1 1
1 1 4 4 1 3 3 3 3
1 4 4 4 3 3 3 3 3
1 4 4 4 3 3 3 3 3
1 2 1 1 3 3 3 3 3
2 2 2 1 1 3 3 3 3
4 2 2 2 2 2 2 3 3
4 4 2 2 2 2 2 3 3

;Ieșire

Datele de intrare corespund restrictiilor impuse.
2 1 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0 0
0 0 1 0 0 1 1 1 1
0 0 0 0 0 1 2 2 2
0 0 0 0 0 1 1 2 3
0 1 0 0 0 0 0 1 2
0 0 1 0 0 0 0 0 1
1 0 0 1 1 1 0 0 1

==Exemplul 2:==

;Intrare

emigrare

;Ieșire

Datele de intrare nu corespund restrictiilor impuse.

==Explicație==

Cele '''4''' țări sunt reprezentate de valorile '''1, 2, 3, 4.'''

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def verificare_restrictii(nr_n, nr_m): # functia de verificare a datelor de intrare
if 2 <= nr_n <= 10**3 and 2 <= nr_m <= 10**3:
return True
else:
return False

def min_distance(nr_n, nr_m, matrice):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

visited = [[False] * nr_m for _ in range(nr_n)]
distanta = [[0] * nr_m for _ in range(nr_n)]

q = deque()

for i in range(nr_n):
for j in range(nr_m):
if any(matrice[i][j] != matrice[i + dx[k]][j + dy[k]] for k in range(4) if 0 <= i + dx[k] < nr_n and 0 <= j + dy[k] < nr_m):
q.append((i, j))
visited[i][j] = True

while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < nr_n and 0 <= ny < nr_m and not visited[nx][ny]:
distanta[nx][ny] = distanta[x][y] + 1
q.append((nx, ny))
visited[nx][ny] = True

return distanta

# Rularea se face in felul urmator, se scrie de la tastatura 8, apoi 9, apoi toata matricea

if __name__ == '__main__':
try:
n = int(input("Introduceti numarul de linii: "))
m = int(input("Introduceti numarul de coloane: "))

if verificare_restrictii(n, m):
print("Datele de intrare corespund restrictiilor impuse.")
matrix = [list(map(int, input().split())) for _ in range(n)]
dist = min_distance(n, m, matrix)
for row in dist:
print(*row)
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

3959 - MaxSecvK

2023-12-12T20:53:23Z

Bonte Lucas Gabriel:

==Cerința==

Se consideră un șir '''A''' de '''n''' numere întregi. Pentru fiecare subsecvență de lungimea '''k''' să se afișeze valoarea maximă.

==Date de intrare==

Fișierul de intrare '''maxsecvkin.txt''' conține pe prima linie două numere naturale nenule '''n''' și '''k''', iar pe a doua linie '''n''' numere întregi separate prin spații.

==Date de ieșire==

Fișierul de ieșire '''maxsecvkout.txt''' va conține '''n–k+1''' numere întregi ce reprezintă valoarea maximă a tuturor secvențelor de lungime '''k'''.

==Restricții și precizări==

*'''1 ≤ n ≤ 100.000'''
*'''1 ≤ k ≤ n'''
*'''-1.000.000.000 ≤ Ai ≤ -1.000.000.000'''
*prin secvență înțelegem elemente aflate pe poziții consecutive în șir

==Exemplul 1:==

'''maxsecvkin.txt'''

9 3
1 2 4 1 3 6 3 2 5

'''maxsecvkout.txt'''

Datele de intrare corespund restrictiilor impuse
4 4 4 6 6 6 5

==Exemplul 2:==

'''maxsecvkin.txt'''

maxsecvk

'''maxsecvkout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Se vor afișa '''7''' numere.
Maximul secvenței '''1 2 4''' este '''4'''
Maximul secvenței '''2 4 1''' este '''4'''
Maximul secvenței '''4 1 3''' este '''4'''
Maximul secvenței '''1 3 6''' este '''6'''
Maximul secvenței '''3 6 3''' este '''6'''
Maximul secvenței '''6 3 2''' este '''6'''
Maximul secvenței '''3 2 5''' este '''5'''

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(nr_n, nr_k, numere): # functia de validare a datelor de intrare
if nr_n < 1 or nr_n > 100000 or nr_k < 1 or nr_k > nr_n:
raise ValueError
for num in numere:
if num < -1000000000 or num > 1000000000:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def max_subsequence(numere, nr_k): # functia de rezolvare
max_values = [max(numere[i:i + nr_k]) for i in range(len(numere) - nr_k + 1)]
for value in max_values:
file_out.write(str(value) + ' ')

if __name__ == '__main__':
file_in = open('maxsecvkin.txt', 'r') # declararea fisierelor
file_out = open('maxsecvkout.txt', 'w') # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n, k = map(int, file_in.readline().split())
numbers = list(map(int, file_in.readline().split()))

validare(n, k, numbers) # apelul functiei de validare
max_subsequence(numbers, k) # apelul functiei de rezolvare

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

2638 - eval exp

2023-12-12T20:38:44Z

Bonte Lucas Gabriel:

Se consideră o expresie formată din numere naturale și operatorii '''+''', '''-''','''*'''.

==Cerința==

Să se evalueze expresia.

==Date de intrare==

Programul citește de la tastatură expresia.

==Date de ieșire==

Programul va afișa pe ecran un singur număr reprezentând valoarea expresiei.

==Restricții și precizări==

*Lungimea expresiei va fi de cel mult '''50''' de caractere
*Rezultatul final precum și rezultatele intermediare se vor încadra în tipul de date '''long long'''
*Expresia este corectă și nu conține alte caractere în afară de cifre și operatorii '''+''', '''-''', '''*'''.

==Exemplul 1:==

;Intrare

234-10+21*12

;Ieșire

Datele de intrare corespund restrictiilor impuse.
476

==Exemplul 2:==

;Intrare

eval exp

;Ieșire

Datele de intrare nu corespund restrictiilor impuse.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def verificare_restrictii(expresia): # functia de verificare a datelor de intrare
if len(expresia) <= 50 and all(c.isdigit() or c in ['+', '-', '*'] for c in expresia):
return True
else:
return False

def evalueaza_expresia(expresia):
try:
# Folosim functia eval() pentru a evalua expresia
rezultat = eval(expresia)
# Verificam daca rezultatul se incadreaza in tipul de date long long
if -9223372036854775808 <= rezultat <= 9223372036854775807:
# Returnam rezultatul
return rezultat
else:
return "Datele de intrare nu corespund restrictiilor impuse."
except Exception as excep:
# Daca apare o eroare, o returnam
return str(excep)

if __name__ == '__main__':
try:
# Citim expresia de la tastatura
expresie = input("Introduceti expresia: ")
if verificare_restrictii(expresie): # verificam datele de intrare
print("Datele de intrare corespund restrictiilor impuse.")
# Apelam functia pentru a evalua expresia si afisam rezultatul
print("Rezultatul este: ", evalueaza_expresia(expresie))
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
# ne asteptam la o eroare din cauza datelor de intrare, o tratam corespunzator
except Exception as e:
print("A aparut o eroare: ", str(e))

</syntaxhighlight>

1267 - plaja

2023-12-10T23:24:23Z

Bonte Lucas Gabriel:

==Cerința==

O plajă poate fi văzută ca o matrice cu '''n''' linii și '''m''' coloane. Elementele matricii sunt codificate cu '''0''', însemnând o poziție liberă, și '''1''', însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată.

==Date de intrare==

Fișierul de intrare '''plajain.txt''' conține pe prima linie numerele '''n''' și '''m''', iar pe următoarele '''n''' linii câte '''m''' caractere reprezentând plaja.

==Date de ieșire==

Fișierul de ieșire '''plajaout.txt''' va conține pe prima linie numărul '''S''', reprezentând aria maximă a unui dreptunghi liber.

==Restricții și precizări==

*'''1 ≤ n, m ≤ 1000'''

==Exemplul 1:==

'''plajain.txt'''

5 5
11111
11000
11100
11100
11110

'''plajaout.txt'''

Datele de intrare corespund restrictiilor impuse
6

==Exemplul 2:==

'''plajain.txt'''

plaja

'''plajaout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

1 1 1 1 1
1 1 0 '''0''' '''0'''
1 1 1 '''0''' '''0'''
1 1 1 '''0''' '''0'''
1 1 1 1 0

Suprafata dreptunghiulara de aria maxima este cea ingrosata.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(matrice, n_linii, m_coloane): # functia de validare a datelor de intrare
if not matrice:
raise ValueError("Matricea este goala")

if not (1 <= n_linii <= 1000) or not (1 <= m_coloane <= 1000):
raise ValueError("Valorile n sau m nu respecta restrictiile impuse")

for row in matrice:
if len(row) != m_coloane:
raise ValueError("Lungimea randului nu este egala cu m")

for element in row:
if not element.isdigit(): # fiecare caracter trebuie sa fie cifra
raise ValueError("Elementul matricei nu este o cifra")

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def max_rectangle(matrice): # functia de rezolvare
m_coloane = len(matrice[0])
height = [0] * (m_coloane + 1)
ans = 0

for row in matrice:
for i in range(m_coloane):
height[i] = height[i] + 1 if row[i] == '0' else 0
stack = [-1]
for i in range(m_coloane + 1):
while height[i] < height[stack[-1]]:
h = height[stack.pop()]
w = i - 1 - stack[-1]
ans = max(ans, h * w)
stack.append(i)
return ans

if __name__ == '__main__':
file_in = open('plajain.txt', 'r') # declararea fisierelor
file_out = open('plajaout.txt', 'w') # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n, m = map(int, file_in.readline().split())
matrix = [list(file_in.readline().strip()) for _ in range(n)]

validare(matrix, n, m) # apelul functiei de validare
area = max_rectangle(matrix) # apelul functiei de rezolvare
file_out.write(str(area))

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0675 - Bi Frunze

2023-12-10T23:00:19Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Considerăm un arbore binar cu '''n''' noduri în care fiecare nod este numerotat de la '''1''' la '''n''' și conține o valoare număr natural. Să se afișeze frunzele acestui arbore. ==Date de intrare== Fișierul de intrare '''bifrunzein.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' linii contine câte '''3''' numere '''X st dr'''; linia '''i + 1''' din fișier conține informatiile despre nodul numerotat cu '''i''':...

==Cerința==

Considerăm un arbore binar cu '''n''' noduri în care fiecare nod este numerotat de la '''1''' la '''n''' și conține o valoare număr natural. Să se afișeze frunzele acestui arbore.

==Date de intrare==

Fișierul de intrare '''bifrunzein.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' linii contine câte '''3''' numere '''X st dr'''; linia '''i + 1''' din fișier conține informatiile despre nodul numerotat cu '''i''': '''X''' reprezintă valoare din nod, '''st''' reprezintă numărul de ordine al descendentului stâng sau '''0''' dacă nodul '''i''' nu are descendent stâng, iar '''dr''' reprezintă numărul de ordine al descendentului drept sau '''0''' dacă nodul '''i''' nu are descendent drept.

==Date de ieșire==

Fișierul de ieșire '''bifrunzeout.txt''' va conține pe prima linie numerele de ordine ale nodurilor din arbore care sunt frunze, în ordine crescătoare, separate prin exact un spațiu.

==Restricții și precizări==

*'''1 ≤ n ≤ 1000'''
*valorile din nodurile arborelui vor fi mai mici sau egale cu '''1.000.000'''

==Exemplul 1:==

'''bifrunzein.txt'''

6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0

'''bifrunzeout.txt'''

Datele de intrare corespund restrictiilor impuse
3 5 6

==Exemplul 2:==

'''bifrunzein.txt'''

bifrunze

'''bifrunzeout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(n_noduri, copac): # functia de validare a datelor de intrare
if n_noduri > 1000 or n_noduri < 1:
raise ValueError

for nod in copac:
if len(nod) != 3 or not all(isinstance(i, int) for i in nod) or nod[1] > n_noduri or nod[2] > n_noduri:
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def frunze(n_noduri, copac): # functia de rezolvare
frunze_copac = []
for i in range(n_noduri):
if copac[i][1] == 0 and copac[i][2] == 0:
frunze_copac.append(i + 1)
return frunze_copac

if __name__ == '__main__':
file_in = open("bifrunzein.txt", "r") # declararea fisierelor
file_out = open("bifrunzeout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n = int(file_in.readline()) # citirea numarului de noduri
arbore = []
for _ in range(n):
arbore.append(list(map(int, file_in.readline().split())))

validare(n, arbore) # apelul functiei de validare
frunze = frunze(n, arbore) # apelul functiei de rezolvare
file_out.write(' '.join(map(str, frunze)))

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

==Explicație==

Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.

3277 - Lee

2023-12-10T16:38:15Z

Bonte Lucas Gabriel: Pagină nouă: Se consideră o matrice cu '''N''' linii și '''N''' coloane, numerotate de la '''1''' la '''N''', care memorează doar valori '''0''' și '''1'''. Se dau de asemenea coordonatele a trei componente din această matrice. ==Cerința== Să se determine lungimea minimă a unui drum care pleacă din poziția '''(1,1)''', trece obligatoriu prin cele trei componente date (nu contează în ce ordine) și apoi ajunge în poziția '''(N, N)''', drum care trece doar prin componente ma...

Se consideră o matrice cu '''N''' linii și '''N''' coloane, numerotate de la '''1''' la '''N''', care memorează doar valori '''0''' și '''1'''. Se dau de asemenea coordonatele a trei componente din această matrice.

==Cerința==

Să se determine lungimea minimă a unui drum care pleacă din poziția '''(1,1)''', trece obligatoriu prin cele trei componente date (nu contează în ce ordine) și apoi ajunge în poziția '''(N, N)''', drum care trece doar prin componente marcate cu '''0''' și învecinate pe linii și coloane. Un pas din drum constă din deplasarea dintr-un punct '''(i,j)''' într-unul din cele patru învecinate pe linie și coloană, adică într-unul din punctele '''(i-1,j), (i,j-1), (i+1, j), (i,j+1)'''.

==Date de intrare==

Programul citește de la tastatură numărul '''N'''. Pe fiecare din următoarele '''N''' linii și '''N''' coloane este descrisă matricea binară. Pe ultimele trei linii sunt câte două numere naturale de forma '''x y''' ce descriu coordonatele în matrice (linie și coloană) ale celor trei puncte.

==Date de ieșire==

Programul va afișa pe ecran un singur număr natural, care reprezintă lungimea minimă a drumului care pornește din '''(1, 1)''', trece prin cele trei puncte date și ajunge în punctul '''(N, N)'''.

==Restricții și precizări==

*'''3 ≤ N ≤ 100'''
*Cele trei puncte sunt distincte, diferite de pozițiile '''(1,1)''' și '''(N,N)''' și se găsesc la poziții din matrice marcate cu '''0'''. De asemenea, la pozițiile '''(1,1)''' și '''(N,N)''' se găsește mereu valoarea '''0'''.
*Pentru datele de intrare va exista mereu soluție, adică există cel puțin un drum de la '''(1,1)''' la '''(N,N)'''.

==Exemplul 1:==

'''Intrare'''

4
0 0 0 0
1 0 1 1
0 0 0 1
1 0 0 0
3 3
1 4
3 1

'''Ieșire'''

Datele de intrare corespund restrictiilor impuse.
12

==Exemplul 2:==

'''Intrare'''

lee

'''Ieșire'''

Datele de intrare nu corespund restrictiilor impuse.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from heapq import heappop, heappush
from itertools import permutations

def verificare_restrictii(n): # functia de verificare a datelor de intrare
if 3 <= n <= 100:
return True
else:
return False

def distanta_minima(matrice, start, end):
n = len(matrice)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
distante = [[float('inf')] * n for _ in range(n)]
distante[start[0]][start[1]] = 0
heap = [(0, start)]
while heap:
d, (x, y) = heappop(heap)
if (x, y) == end:
return d
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < n and matrice[nx][ny] == 0:
if d + 1 < distante[nx][ny]:
distante[nx][ny] = d + 1
heappush(heap, (d + 1, (nx, ny)))
return float('inf')

def rezolvare():
n = int(input("Introduceti dimensiunea matricei (un numar natural): "))
if not verificare_restrictii(n):
print("Datele de intrare nu corespund restrictiilor impuse.")
return
print("Datele de intrare corespund restrictiilor impuse.")
print("Introduceti matricea linie cu linie (0 sau 1 separate prin spatii): ")
matrice = [list(map(int, input().split())) for _ in range(n)]
puncte = [(0, 0)]
print("Introduceti coordonatele celor trei puncte (doua numere naturale separate prin spatii): ")
for _ in range(3):
x, y = map(int, input().split())
puncte.append((x - 1, y - 1))
puncte.append((n - 1, n - 1))
distante = [[distanta_minima(matrice, puncte[i], puncte[j]) for j in range(5)] for i in range(5)]
min_distanta = float('inf')
for perm in permutations([1, 2, 3]):
distanta = distante[0][perm[0]] + distante[perm[0]][perm[1]] + distante[perm[1]][perm[2]] + distante[perm[2]][4]
min_distanta = min(min_distanta, distanta)
print("Lungimea minima a drumului este: ", min_distanta)

if __name__ == '__main__':
try:
rezolvare()
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

==Explicație==

Cele trei puncte sunt situate în coordonatele '''(3,3), (1,4), (3,1)'''.
Drumul de lungime minimă este:

de la '''(1,1)''' la '''(1,4)''' (lungime '''3''')
de la '''(1,4)''' la '''(3,1)''' (lungime '''5''')
de la '''(3,1)''' la '''(3,3)''' (lungime '''2''')
de la '''(3,3)''' la '''(4,4)''' (lungime '''2''')
Lungime totală: '''3 + 5 + 2 + 2 = 12'''.

0868 - Acces1

2023-12-07T18:11:19Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră o clădire de formă dreptunghiulară, împărțită în '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Dintr-o cameră se poate trece în oricare dintre cele '''4''' camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut. În anumite camere se află echipe de pompieri. Pentru o intervenție cât ma...

==Cerința==

Se consideră o clădire de formă dreptunghiulară, împărțită în '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Dintr-o cameră se poate trece în oricare dintre cele '''4''' camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.

În anumite camere se află echipe de pompieri. Pentru o intervenție cât mai rapidă în cazul unui eventual incendiu apărut în una dintre camerele clădirii, este necesar să se știe, pentru fiecare cameră care este timpul minim în care o echipă de pompieri ajunge în acea cameră.

==Date de intrare==

Fișierul de intrare '''acces1in.txt''' conține pe prima linie numerele '''n m'''; următoarele '''n''' linii conțin câte '''m''' caractere, care pot fi:

*'''-''' – reprezintă o cameră liberă
*'''#''' – reprezintă o cameră închisă
*'''P''' – reprezintă o cameră în care se găsește o echipă de pompieri

==Date de ieșire==

Fișierul de ieșire '''acces1out.txt''' va conține o matrice cu '''n''' linii și '''m''' coloane, fiecare element al matricei reprezentând timpul minim necesar ca o echipă de pompieri să ajungă în camera corespunzătoare. Pentru camerele ocupate se va fișa simbolul '''#''', iar pentru cele libere în care nu va ajunge nici o echipă se va afișa '''-'''.
Matricea va fi afișată linie cu linie, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin câte un spațiu.

==Restricții și precizări==

*'''1 ≤ n,m ≤ 1000

==Exemplul 1:==

'''acces1in.txt'''

4 6
P-#-#P
--##--
--P---
-----#

'''acces1out.txt'''

Datele de intrare corespund restrictiilor impuse
0 1 # - # 0
1 2 # # 2 1
2 1 0 1 2 2
3 2 1 2 3 #

==Exemplul 2:==

'''acces1in.txt'''

acces1

'''acces1out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def validare(n_linii, m_coloane, matrice):
if n_linii > 1000 or m_coloane > 1000:
raise ValueError
for linie in matrice:
for caracter in linie:
if caracter not in ['-', '#', 'P']:
raise ValueError

def bfs(n_linii, m_coloane, matrice):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
distanta = [[-1] * m_coloane for _ in range(n_linii)]
q = deque()

for nr_i in range(n_linii):
for nr_j in range(m_coloane):
if matrice[nr_i][nr_j] == 'P':
q.append((nr_i, nr_j))
distanta[nr_i][nr_j] = 0

while q:
x, y = q.popleft()
for directie in range(4):
nx, ny = x + dx[directie], y + dy[directie]
if 0 <= nx < n_linii and 0 <= ny < m_coloane and matrice[nx][ny] != '#' and distanta[nx][ny] == -1:
distanta[nx][ny] = distanta[x][y] + 1
q.append((nx, ny))

return distanta

if __name__ == '__main__':
file_in = open("acces1in.txt", "r")
file_out = open("acces1out.txt", "w")

try:
n, m = map(int, file_in.readline().split())
mat = [list(file_in.readline().strip()) for _ in range(n)]

validare(n, m, mat)
file_out.write("Datele de intrare corespund restrictiilor impuse\n")
dist = bfs(n, m, mat)

for i in range(n):
for j in range(m):
if mat[i][j] == '#':
file_out.write('# ')
elif dist[i][j] == -1:
file_out.write('- ')
else:
file_out.write(str(dist[i][j]) + ' ')
file_out.write('\n')

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0865 - Palat

2023-12-04T21:54:06Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Ileana Cosânzeana se mărită. În consecință a dat sfoară-n țară și au venit mai mulți Feți-Frumoși, dornici să primească mâna fetei, împreună cu palatul în care locuiește. Acesta este alcătuit din '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. În anumite camere nu se poate intra, deoarece acolo se află zmei răi. În celelalte se poate intra; mai precis se poate trece dintr-o cameră în altă camer...

==Cerința==

Ileana Cosânzeana se mărită. În consecință a dat sfoară-n țară și au venit mai mulți Feți-Frumoși, dornici să primească mâna fetei, împreună cu palatul în care locuiește. Acesta este alcătuit din '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane.

În anumite camere nu se poate intra, deoarece acolo se află zmei răi. În celelalte se poate intra; mai precis se poate trece dintr-o cameră în altă cameră dacă se învecinează pe linie sau pe coloană. În una dintre camere se află Ileana Cosânzeana, iar în alte camere se afla câte un Făt-Frumos. Aceștia pot trece dintr-o cameră în alta, cu condiția să nu intre într-o cameră care conține un zmeu. Trecerea dintr-o cameră în alta a unui Făt-Frumos durează un minut.

Alegerea celui care va primi mâna Ilenei se face pe principiul '''primul venit, primul servit''' (suntem la capitolul '''Coada'''). Mai precis, se va căsători cu Ileana Cosânzeana acel Făt Frumos care ajunge primul la ea. Dacă ajung la Ileana Cosânzeana mai mulți Feți-Frumoși în același timp, deoarece este interzisă poligamia, Ileana se va căsători cu Făt-Frumos care la început era situat cât mai jos (pe o linie cu indice cât mai mare). Dacă mai mulți Feți-Frumoși situați pe aceeași linie ajung în timp minim la Ileana, aceasta se va căsători cu cel care era cât mai la dreapta (pe o coloană cu indice cât mai mare).

Aflați poziția inițială a lui Făt-Frumos care va primi mâna fetei.

==Date de intrare==

Fișierul de intrare '''palatin.txt''' conține pe prima linie numerele '''n m''', iar următoarele '''n''' linii câte '''m''' caractere, care pot fi:

*'''Z''' – reprezintă o cameră ocupată de un zmeu
*'''I''' – reprezintă camera în care se află Ileana Cosânzeana
*'''F''' – reprezinta o cameră în care se află un Făt-Frumos
*'''_''' – reprezintă o cameră liberă

==Date de ieșire==

Fișierul de ieșire '''palatout.txt''' va conține pe prima linie două numere '''i j''', separate prin exact un spațiu, reprezentând coordonatele (linie coloană) ale camerei în care se afla acel Făt-Frumos care va primi mâna Ilenei.

==Restricții și precizări==

*'''1 ≤ n ≤ 1000'''
*'''1 ≤ m ≤ 1000'''
*liniile și coloanele sunt numerotate de la '''1'''

==Exemplul 1:==

'''palatin.txt'''

4 5
ZF_ZF
_Z_Z_
_I___
_Z_ZF

'''palatout.txt'''

Datele de intrare corespund restrictiilor impuse
4 5

==Exemplul 2:==

'''palatin.txt'''

palat

'''palatout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def validare(n_linii, m_coloane, matrice): # functia de validare a datelor de intrare
if n_linii > 1000 or m_coloane > 1000:
raise ValueError

for linie in matrice:
if len(linie) != m_coloane:
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def bfs(n_linii, m_coloane, matrice, inceput): # functia de rezolvare
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
q = deque([inceput])
distanta = [[0] * m_coloane for _ in range(n_linii)]
while q:
x, y = q.popleft()
for camera_i in range(4):
nx, ny = x + dx[camera_i], y + dy[camera_i]
if 0 <= nx < n_linii and 0 <= ny < m_coloane and matrice[nx][ny] != 'Z' and not distanta[nx][ny]:
distanta[nx][ny] = distanta[x][y] + 1
q.append((nx, ny))
return distanta

if __name__ == '__main__':
file_in = open("palatin.txt", "r") # declararea fisierelor
file_out = open("palatout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
n, m = map(int, file_in.readline().split())
mat = [list(file_in.readline().strip()) for _ in range(n)]
start = None
for i in range(n):
for j in range(m):
if mat[i][j] == 'I':
start = (i, j)
break
if start:
break

validare(n, m, mat) # apelul functiei de validare
dist = bfs(n, m, mat, start) # apelul functiei de rezolvare

min_dist = min_pos = None
for i in range(n-1, -1, -1):
for j in range(m-1, -1, -1):
if mat[i][j] == 'F' and (min_dist is None or dist[i][j] < min_dist and dist[i][j] != 0):
min_dist = dist[i][j]
min_pos = (i+1, j+1)

file_out.write(f"{min_pos[0]} {min_pos[1]}\n")

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

==Explicație==

În palat se află trei Feți Frumoși. Doi dintre ei ajung la Ileana Cosânzeana în '''3''' minute, al treilea în '''4''' minute.

0883 - Traversare

2023-12-04T17:54:40Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră harta unei suprafețe deșertice, dată sub forma unei matrice cu '''n''' linii și '''m''' coloane, formată din '''n*m''' zone. Fiecare zonă poate fi accesibilă sau inaccesibilă. Dintr-o zonă accesibilă se poate trece în altă zonă accesibilă învecinată cu prima pe linie sau pe coloană. Un călător dorește să traverseze deșertul de la nord (prima linie) la sud (ultima linie). Pentru aceasta el poate sa aleagă oricare zonă accesi...

==Cerința==

Se consideră harta unei suprafețe deșertice, dată sub forma unei matrice cu '''n''' linii și '''m''' coloane, formată din '''n*m''' zone. Fiecare zonă poate fi accesibilă sau inaccesibilă. Dintr-o zonă accesibilă se poate trece în altă zonă accesibilă învecinată cu prima pe linie sau pe coloană.

Un călător dorește să traverseze deșertul de la nord (prima linie) la sud (ultima linie). Pentru aceasta el poate sa aleagă oricare zonă accesibilă de pe prima line și dorește să ajungă pe ultima linie cu număr minim de pași.

==Date de intrare==

Fișierul de intrare '''traversarein.txt''' conține pe prima linie numerele '''n m'''. Următoarele '''n''' linii conțin câte '''m''' valori '''0''' sau '''1''', separate prin câte un spațiu. Valoarea '''0''' reprezintă o zonă accesibilă, iar valoarea '''1''' reprezintă o zonă inaccesibilă.

==Date de ieșire==

Fișierul de ieșire '''traversareout.txt''' va conține pe prima linie numărul '''C''', reprezentând numărul minim de pași necesari pentru traversare.

==Restricții și precizări==

*'''1 ≤ n, m ≤ 1000'''
*în traversarea deșertului un pas este trecerea dintr-o zonă accesibilă în altă zonă accesibilă învecinată cu prima
*la determinarea numărului de pași se numără și primul pas (intrarea în matrice)
*pentru toate datele de test este posibilă traversarea deșertului

==Exemplul 1:==

'''traversarein.txt'''

6 9
1 1 0 0 1 1 1 0 0
0 0 1 0 1 0 1 1 0
1 1 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 1
1 0 1 1 0 1 0 0 0
1 0 0 0 0 0 0 1 0

'''traversareout.txt'''

Datele de intrare corespund restrictiilor impuse
8

==Exemplul 2:==

'''traversarein.txt'''

traversare

'''traversareout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def citire_matrice(n_linii, fisier):
matrix = []
for i in range(n_linii):
linie = list(map(int, fisier.readline().split()))
matrix.append(linie)
return matrix

def validare_matrice(matrix, n_linii, m_coloane, fisier_out):
if n_linii > 1000 or m_coloane > 1000:
raise ValueError
for linie in matrix:
for valoare in linie:
if valoare not in [0, 1]:
raise ValueError
fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")

def traversare_desert(matrix, n_linii, m_coloane):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
distanta = [[float('inf')] * m_coloane for _ in range(n_linii)]
q = deque()

for j in range(m_coloane):
if matrix[0][j] == 0:
distanta[0][j] = 1
q.append((0, j))

while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < n_linii and 0 <= ny < m_coloane and matrix[nx][ny] == 0:
if distanta[nx][ny] > distanta[x][y] + 1:
distanta[nx][ny] = distanta[x][y] + 1
q.append((nx, ny))

return min(distanta[-1])

if __name__ == '__main__':
file_in = open("traversarein.txt", "r")
file_out = open("traversareout.txt", "w")
try:
n, m = map(int, file_in.readline().split())
matrice = citire_matrice(n, file_in) # modificarea este aici
validare_matrice(matrice, n, m, file_out)
rezultat = traversare_desert(matrice, n, m)
file_out.write(str(rezultat))
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

==Explicație==

O traversare cu 8 pași a deșertului este următoarea:

1 1 0 0 1 1 1 0 '''0'''
0 0 1 0 1 0 1 1 '''0'''
1 1 0 0 0 0 0 '''0''' '''0'''
1 0 0 0 1 0 0 '''0''' 1
1 0 1 1 0 1 0 '''0''' '''0'''
1 0 0 0 0 0 0 1 '''0'''

0866 - Acces

2023-12-03T22:11:28Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră o clădire de formă dreptunghiulară, împărțită în '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Dintr-o cameră se poate trece în oricare dintre cele '''4''' camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut. În una dintre camere se află proprietarul clădirii, care dorește să afle...

==Cerința==

Se consideră o clădire de formă dreptunghiulară, împărțită în '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Dintr-o cameră se poate trece în oricare dintre cele '''4''' camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.

În una dintre camere se află proprietarul clădirii, care dorește să afle, pentru fiecare dintre camere care este timpul minim necesar pentru a ajunge în acea cameră.

==Date de intrare==

Fișierul de intrare '''accesin.txt''' conține pe prima linie numerele '''n m'''; următoarele '''n''' linii conțin câte '''m''' caractere, care pot fi:

*'''-''' – reprezintă o cameră liberă
*'''#''' – reprezintă o cameră închisă
*'''P''' – reprezintă camera proprietarului, care se consideră liberă

==Date de ieșire==

Fișierul de ieșire '''accesout.txt''' va conține o matrice cu '''n''' linii și '''m''' coloane, elementele matricei reprezentând timpul minim necesar ca proprietarul să ajungă în camere clădirii. Pentru camerele ocupate și pentru camerele libere în care nu se poate ajunge timpul necesar va fi '''-1'''.
Matricea va fi afișată linie cu linie, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin câte un spațiu.

==Restricții și precizări==

*'''1 ≤ n,m ≤ 1000'''

==Exemplul 1:==

'''accesin.txt'''

4 6
--#-#-
--##--
--P---
-----#

'''accesout.txt'''

Datele de intrare corespund restrictiilor impuse
4 3 -1 -1 -1 5
3 2 -1 -1 3 4
2 1 0 1 2 3
3 2 1 2 3 -1

==Exemplul 2:==

'''accesin.txt'''

acces

'''accesout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def validare(n_linii, m_coloane, matrice): # functia de validare a datelor de intrare
if n_linii > 1000 or m_coloane > 1000:
raise ValueError

for linie in matrice:
if len(linie) != m_coloane: # fiecare linie trebuie sa aiba lungimea m
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def acces(nr, nc, matrice): # functia de rezolvare
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
dist = [[-1]*nc for _ in range(nr)]
q = deque()

for i in range(nr):
for j in range(nc):
if matrice[i][j] == 'P':
q.append((i, j))
dist[i][j] = 0

while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < nr and 0 <= ny < nc and matrice[nx][ny] != '#' and dist[nx][ny] == -1:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))

for i in range(nr):
for j in range(nc):
file_out.write(str(dist[i][j]) + ' ')
file_out.write('\n')

if __name__ == '__main__':
file_in = open("accesin.txt", "r") # declararea fisierelor
file_out = open("accesout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

# din cauza datelor de intrare pot aparea 2 tipuri de erori, valueError sau IndexError pe care le tratam
try:
n, m = map(int, file_in.readline().split()) # citirea numarului de linii si coloane
mat = [list(file_in.readline().strip()) for _ in range(n)] # citirea matricei

validare(n, m, mat) # apelul functiei de validare
acces(n, m, mat) # apelul functiei de rezolvare

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

2733 - nrapp

2023-11-29T18:13:13Z

Bonte Lucas Gabriel:

==Cerința==

Se dă un număr natural '''N''' si un șir '''v''' de '''N''' numere naturale. Sa se răspundă la '''Q''' întrebări de tipul:

'''D y''': Care este cea mai mică poziție '''x''', unde '''x''' > '''y''', pentru care '''v[x] < v[y]'''? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi '''N + 1'''.
'''S y''': Care este cea mai mare poziție '''x''', unde '''x''' < '''y''', pentru care '''v[x] < v[y]'''? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi '''0'''.

==Date de intrare==

Fișierul de intrare '''nrappin.txt''' conține pe prima linie numărul natural '''N''', iar pe a doua linie '''N''' numere naturale separate prin spații. A treia linie va conține numărul natural nenul '''Q''' și apoi '''Q''' întrebări precum cele descrise anterior.

==Date de ieșire==

Fișierul de ieșire '''nrappout.txt''' va conține '''Q''' linii, anume răspunsul pentru fiecare întrebare în parte.

==Restricții și precizări==

*'''1 ≤ N ≤ 100.000'''
*'''1 ≤ v[i] ≤ 1.000.000'''

==Exemplul 1:==

;nrappin.txt

8
1 3 6 5 2 1 9 6
8
S 1
D 2
D 3
S 4
S 5
D 6
D 7
D 8

;nrappout.txt

Datele de intrare corespund restrictiilor impuse
0
5
4
2
1
9
8
9

==Exemplul 2:==

;nrappin.txt

nrapp

;nrappout.txt

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(n, sir_v, q, intrebari, file_output): # functia de validare a datelor de intrare
if not 1 <= n <= 100000:
raise ValueError
for val in sir_v:
if not 1 <= val <= 1000000: # fiecare element trebuie sa fie numar intreg intre 1 si 1.000.000
raise ValueError
if q < 1:
raise ValueError
for intrebare in intrebari:
if len(intrebare) != 2 or not isinstance(intrebare[1], int):
raise ValueError
file_output.write("Datele de intrare corespund restrictiilor impuse\n")

def solve(n, sir_v, intrebari): # functia de rezolvare
raspunsuri = []
for intrebare in intrebari:
if intrebare[0] == 'D':
y = intrebare[1]
raspuns = n + 1
for x in range(y + 1, n + 1):
if sir_v[x - 1] < sir_v[y - 1]:
raspuns = x
break
raspunsuri.append(raspuns)
elif intrebare[0] == 'S':
y = intrebare[1]
raspuns = 0
for x in range(y - 1, 0, -1):
if sir_v[x - 1] < sir_v[y - 1]:
raspuns = x
break
raspunsuri.append(raspuns)
return raspunsuri

if __name__ == '__main__':
file_in = open('nrappin.txt', 'r')
file_out = open('nrappout.txt', 'w')

try:
N = int(file_in.readline())
v = list(map(int, file_in.readline().split()))
Q = int(file_in.readline())
queries = []
for _ in range(Q):
query = file_in.readline().split()
queries.append((query[0], int(query[1])))

validare(N, v, Q, queries, file_out)
answers = solve(N, v, queries)

for answer in answers:
file_out.write(str(answer) + '\n')

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

1884 - UEMM1

2023-11-27T21:37:48Z

Bonte Lucas Gabriel:

==Cerința==

Se dă un șir cu '''n''' elemente, numere naturale. Să se afișeze, pentru fiecare element din șir, valoarea din șir aflată după acesta și mai mare decât acesta (Următorul Element Mai Mare). Dacă o asemenea valoare nu există, se va afișa '''-1'''.

==Date de intrare==

Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' elemente ale șirului.

==Date de ieșire==

Programul va afișa pe ecran cele '''n''' valori determinate, separate prin câte un spațiu.

==Restricții și precizări==

*'''1 ≤ n ≤ 100.000'''
*elementele șirului vor fi mai mai mici decât '''1.000.000'''

==Exemplul 1:==

;Intrare

5
3 4 3 5 1

;Ieșire

Datele de intrare corespund restrictiilor impuse.
4 5 5 -1 -1

==Exemplul 2:==

;Intrare

UEMM1

;Ieșire

Datele de intrare nu corespund restrictiilor impuse.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def verificare_restrictii(numere): # functia de verificare a datelor de intrare
if 1 <= numere <= 100000:
return True
else:
return False

def urmatorul_element_mai_mare(numere, string):
# Inițializăm rezultatul cu -1 pentru toate elementele
rezultat = [-1] * numere
# Inițializăm o stivă goală pentru a păstra indicii elementelor
stiva = []

# Parcurgem fiecare element din șir
for i in range(numere):
# Cât timp stiva nu este goală și elementul curent este mai mare decât elementul din vârful stivei
while stiva and string[stiva[-1]] < string[i]:
# Actualizăm rezultatul pentru indicele din vârful stivei cu valoarea actuală din șir
rezultat[stiva.pop()] = string[i]
# Adăugăm indicele elementului curent în stivă
stiva.append(i)

# Returnăm rezultatul
return rezultat

if __name__ == '__main__':
try:
# Citim numărul de elemente
n = int(input("Introduceți numărul de elemente: "))
# Citim șirul de numere
sir = list(map(int, input("Introduceți elementele șirului, separate prin spațiu: ").split()))

if verificare_restrictii(n): # verificam datele de intrare
print("Datele de intrare corespund restrictiilor impuse.")
# Apelăm funcția și afișăm rezultatul
print(urmatorul_element_mai_mare(n, sir))
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
# ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

0878 - Intervale4

2023-11-27T21:24:54Z

Bonte Lucas Gabriel:

==Cerința==

Se consideră un șir de '''n''' intervale închise întregi. Două intervale consecutive în șir care au intersecția nevidă se reunesc și se înlocuiesc în șir cu intervalul reuniune. Operația se repetă până când nu mai sunt în șir două intervale consecutive cu intersecția nevidă.

Să se determine câte intervale există în șir după realizarea acestor operații.

==Date de intrare==

Fișierul de intrare '''intervale4in.txt''' conține pe prima linie numărul '''n''', iar următoarele '''n''' linii câte două valori '''x y''', reprezentând intervalele inițiale, în ordine.

==Date de ieșire==

Fișierul de ieșire '''intervale4out.txt''' va conține pe prima linie numărul '''C''' de intervale din șir, după realizarea operațiilor.

==Restricții și precizări==

*'''1 ≤ n ≤ 100.000;'''
*pentru fiecare interval dat, '''x ≤ y''', valori întregi care se pot reprezenta pe patru octeți.

==Exemplul 1:==

'''intervale4in.txt'''

5
2 3
4 6
3 5
8 10
7 11

'''intervale4out.txt'''

Datele de intrare corespund restrictiilor impuse
2

==Exemplul 2:==

'''intervale4in.txt'''

intervale4

'''intervale4out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(numere, intervals): # functia de validare a datelor de intrare

if numere < 1 or numere > 100000:
raise ValueError

for intervall in intervals:
if len(intervall) != 2 or intervall[0] > intervall[1]:
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def solve(intervals): # functia de rezolvare
# Sortăm intervalele în ordine crescătoare
intervals.sort()

# Inițializăm lista de intervale unite cu primul interval
unite = [intervals[0]]

# Parcurgem fiecare interval
for curent in intervals:
# Obținem ultimul interval adăugat în lista de intervale unite
ultim = unite[-1]

# Dacă intervalul curent se intersectează cu ultimul interval adăugat
if curent[0] <= ultim[1]:
# Actualizăm capătul drept al ultimului interval cu valoarea maximă dintre capetele drepte ale celor două intervale
ultim[1] = max(ultim[1], curent[1])
else:
# Dacă nu se intersectează, adăugăm intervalul curent în lista de intervale unite
unite.append(curent)

# Returnăm numărul de intervale din lista de intervale unite
return len(unite)

if __name__ == '__main__':
file_in = open("intervale4in.txt", "r") # declararea fisierelor
file_out = open("intervale4out.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

# din cauza datelor de intrare pot aparea 2 tipuri de erori, valueError sau IndexError pe care le tratam
try:
n = int(file_in.readline()) # citirea numarului de intervale
intervale = []
for _ in range(n):
interval = list(map(int, file_in.readline().split()))
intervale.append(interval)

validare(n, intervale) # apelul functiei de validare
file_out.write(str(solve(intervale))) # apelul functiei de rezolvare

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

file_in.close()
file_out.close()

</syntaxhighlight>

==Explicație==

Intervalele din șirul inițial sunt: '''[2,3] [4,6] [3,5] [8,10] [7,11].'''

1.Se reunesc intervalele '''[4,6] [3,5]''' și se obține șirul '''[2,3] [3,6] [8,10] [7,11].'''
2.Se reunesc intervalele '''[2,3] [3,6]''' și se obține șirul '''[2,6] [8,10] [7,11].'''
3.Se reunesc intervalele '''[8,10] [7,11]''' și se obține șirul '''[2,6] [7,11].'''
La final în șir se află două intervale.

3266 - Sir147

2023-11-27T20:33:06Z

Bonte Lucas Gabriel:

==Cerință==

Fișierul '''sir147in.txt''' memorează cel mult '''10000''' de numere naturale cu cel mult nouă cifre. Numerele sunt ordonate strict crescător și separate prin câte un spațiu. Se consideră șirul '''1, 4, 7, ….''' definit astfel: '''f1=1, f2=4 si fn=fn−1∗2−fn−2''', pentru '''n > 2'''. Se cere să se scrie în fișierul '''sir147out.txt''' numerele din fișier care sunt termeni ai șirului. Numerele sunt afișate în ordine strict crescătoare, separate prin câte un spațiu.

==Date de intrare==

Fișierul de intrare '''sir147in.txt''' conține pe prima linie mai multe numere naturale formate din cel mult nouă cifre separate prin câte un spațiu.

==Date de ieșire==

Fișierul de ieșire '''sir147out.txt''' va conține pe prima linie numerele din fișier care sunt termeni ai șirului menționat în enunț.

==Restricții și precizări==

*numerele din fișier vor fi mai mici decât '''1.000.000.000'''
*în fișierul de intrare există cel puțin un termen al șirului menționat mai sus
*se recomandă realizarea unei soluții în care să se evite memorarea valorilor din fișier într-un tablou sau în alte structuri de date similare

==Exemplul 1==

'''sir147in.txt'''

1 2 5 7 13 17 19 30

'''sir147out.txt'''

Datele de intrare corespund restrictiilor impuse
1 7 13 19

==Exemplul 2==

'''sir147in.txt'''

sir147

'''sir147out.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(numere): # functia de validare a datelor de intrare

for number in numere:
if not isinstance(number, int) or number >= 1000000000: # fiecare număr trebuie să fie întreg și mai mic decât 1.000.000.000
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def sir147(numere): # functia de rezolvare
f1, f2 = 1, 4
current = f1

for number in numere:
while number > current:
current = f2
f1, f2 = f2, f2 * 2 - f1
if number == current:
file_out.write(str(number) + ' ')

if __name__ == '__main__':
file_in = open("sir147in.txt", "r") # declararea fisierelor
file_out = open("sir147out.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
numbers = list(map(int, file_in.readline().split())) # citirea numerelor se face ca listă de întregi

validare(numbers) # apelul functiei de validare
sir147(numbers) # apelul functiei de rezolvare

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

==Explicație==

Numerele din fișierul de intrare care sunt termeni ai șirului menționat sunt 1 7 13 19.

0876 - Coada

2023-11-17T19:11:51Z

Bonte Lucas Gabriel:

==Cerința==

Să se scrie un program care gestionează o coadă de numere întregi. Inițial coada este vidă. Programul va citi de la tastatură o listă de operații, care pot fi:

*'''push X''' – adaugă valoarea întreagă '''X''' în coadă;
*'''pop''' – elimină elementul din coadă;
*'''front''' – afișează elementul de la începutul cozii.

Programul va realiza asupra cozii operațiile citite, în ordine. Afișările se fac pe ecran, câte o valoare pe linie.

==Date de intrare==

Programul citește de la tastatură un număr '''n''', apoi cele '''n''' operații,

==Date de ieșire==

Programul va afișa pe ecran numerele rezultat ale operațiilor '''front''', câte unul pe o linie.

==Restricții și precizări==

*coada nu va conține la un moment dat mai mult de '''1000''' elemente
*elementele cozii vor fi cuprinse între '''-1.000.000''' și '''1.000.000'''
*dacă la un moment dat se aplică operația '''pop''' și coada nu conține niciun element, operația nu are efect
*dacă la un moment dat se aplică operația '''front''' și coada nu conține niciun element, operația nu are efect (nu se afișează nimic)

==Exemplul 1:==

;Intrare

12
push 5
push 4
front
push 7
push -5
pop
front
pop
front
push 11
front
pop

;Ieșire

Datele de intrare corespund restrictiilor impuse.
5
4
7
7

==Exemplul 2:==

;Intrare

0

;Ieșire

Datele de intrare nu corespund restrictiilor impuse.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

# Definim clasa Queue
class Queue:
def __init__(self):
self.queue = [] # Initializam coada ca o lista goala

# Metoda pentru adaugarea unui element in coada
def push(self, x):
if len(self.queue) < 1000 and -1000000 <= x <= 1000000: # Verificam daca coada nu este plina si daca elementul este in intervalul specificat
self.queue.append(x) # Adaugam elementul la sfarsitul cozii

# Metoda pentru eliminarea unui element din coada
def pop(self):
if self.queue: # Verificam daca coada nu este goala
self.queue.pop(0) # Eliminam primul element din coada

# Metoda pentru a obtine primul element din coada
def front(self):
if self.queue: # Verificam daca coada nu este goala
print(self.queue[0]) # Afisam primul element

def verificare_restrictii(nr_n): # functia de verificare a datelor de intrare
if 1 <= nr_n <= 1000:
return True
else:
return False

if __name__ == '__main__':
try:
# Cream o instanta a clasei Queue
queue = Queue()

# Citim numarul de operatii
n = int(input("Introduceti numarul de operatii: "))

if verificare_restrictii(n): # verificam datele de intrare
print("Datele de intrare corespund restrictiilor impuse.")
# Executam operatiile
for _ in range(n):
operation = input("Introduceti operatia: ").split() # Citim operatia
if operation[0] == 'push': # Daca operatia este 'push', adaugam elementul in coada
queue.push(int(operation[1]))
elif operation[0] == 'pop': # Daca operatia este 'pop', eliminam elementul din coada
queue.pop()
elif operation[0] == 'front': # Daca operatia este 'front', afisam primul element din coada
queue.front()
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
# ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

1598 - Coada1

2023-11-17T18:56:13Z

Bonte Lucas Gabriel:

Se consideră '''C''' o coadă de numere naturale, iniţial vidă. Se definesc două tipuri de operaţii.

Operaţia '''1''' : '''push X''', adaugă elementul '''X''' în coadă. Dacă '''X''' există deja în coadă, se scot toate elementele din coadă, pana la întâlnirea lui, inclusiv '''X'''.
Exemplu: '''C: 2 4 5 1 6'''
'''Push 5'''
'''C: 1 6 5 ( s-au scos 2, 4, 5).'''

Operaţia '''2''': '''query X''', cere afişarea poziţiei elementului '''X''' în coada '''C'''. Dacă elementul nu există în coadă, se afişează '''-1'''.
Exemplu: '''C: 2 5 1 3 7'''
'''Query 1'''
'''Răspuns: 3'''

==Cerința==

Dându-se '''M''', reprezentând numărul de operaţii şi cele '''M''' operaţii, să se răspundă la operaţiile de tip '''query'''.

==Date de intrare==

Fișierul de intrare '''coada1in.txt''' conține:

*Pe prima linie numărul natural '''M''';
*Pe următoarele '''M''' linii, câte un string şi câte un număr natural, de forma '''tip_operaţie x''', reprezentând tipul operaţiei şi numărul '''X'''.

==Date de ieșire==

Fișierul de ieșire '''coada1out.txt''' va conține:

*Răspunsurile pentru operaţiile de tip '''query''', câte unul pe linie.

==Restricții și precizări==

*'''1 ≤ M ≤ 50.000'''
*'''1 ≤ X ≤ 1.000'''

==Exemplul 1:==

;coada1in.txt

10
push 3
push 6
push 8
push 2
query 6
push 6
query 4
push 6
push 7
query 6

;coada1out.txt

Datele de intrare corespund restrictiilor impuse
2
-1
1

==Exemplul 2:==

;coada1in.txt

coada1

;coada1out.txt

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Înaintea primei întrebări, coada arată asa: '''3 6 8 2''', deci '''6''' apare pe poziţia '''2'''.
Înaintea celei de-a doua întrebări, coada arată asa: '''8 2 6''', deci '''4''' nu apare.
Înaintea ultimei întrebări, coada arată asa: '''6 7''', deci '''6''' apare pe poziţia '''1'''.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(m, operatii): # funcția de validare a datelor de intrare
if m < 1 or m > 50000:
raise ValueError
for operatie in operatii:
if operatie[0] not in ['push', 'query']:
raise ValueError
x = operatie[1]
if x < 1 or x > 1000:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def solve(operatii): # funcția de rezolvare
queue = []
output = []
for operatie in operatii:
if operatie[0] == 'push':
x = operatie[1]
if x in queue:
queue = queue[queue.index(x)+1:]
queue.append(x)
elif operatie[0] == 'query':
x = operatie[1]
if x in queue:
output.append(queue.index(x) + 1)
else:
output.append(-1)
return output

if __name__ == '__main__':
file_in = open("coada1in.txt", "r") # declararea fisierelor
file_out = open("coada1out.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
M = int(file_in.readline())
operations = []
for _ in range(M):
operation = file_in.readline().split()
operation[1] = int(operation[1])
operations.append(operation)

validare(M, operations) # apelul funcției de validare
results = solve(operations) # apelul funcției de rezolvare

for result in results:
file_out.write(str(result) + '\n')

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0864 - Roboti

2023-11-17T18:08:00Z

Bonte Lucas Gabriel:

==Cerința==

Se dă o matrice cu '''n''' linii și '''m''' coloane și elemente '''0''' sau '''1''', reprezentând planul unui teren în care '''0''' reprezintă o zonă accesibilă, iar '''1''' reprezintă o zonă inaccesibilă. O zonă a terenului are ca și coordonate linia și coloana corespunzătoare din matrice. Într-o zonă cunoscută a matricei se află un robot, iar în altă zonă, de asemenea cunoscută, se află o roboțică. Determinați numărul minim de pași prin care robotul va ajunge la roboțică. Dacă nu este posibil ca robotul să ajungă la roboțică, rezultatul va fi '''-1'''.

==Date de intrare==

Fișierul de intrare '''robotiin.txt''' conține pe prima linie numerele '''n m'''. Următoarele '''n''' linii conțin câte '''m''' valori, '''0''' sau '''1'''. Următoarele două linii conțin câte două valori, reprezentând coordonatele robotului, respectiv ale roboțicii.

==Date de ieșire==

Fișierul de ieșire '''robotiout.txt''' va conține pe prima linie valoarea cerută.

==Restricții și precizări==

*'''1 ≤ n , m ≤ 1000
*zonele pe care se află inițial cei doi roboți sunt libere și sunt diferite
*un pas reprezintă trecerea robotului din zona curentă într-o zonă vecină cu aceasta pe linie sau pe coloană, fără a părăsi matricea.

==Exemplul 1:==

;robotiin.txt

4 5
1 0 0 0 1
0 0 1 0 0
0 0 0 0 1
1 1 0 0 1
1 2
2 5

;robotiout.txt

Datele de intrare corespund restrictiilor impuse
4

==Exemplul 2:==

;robotiin.txt

robot

;robotiout.txt

Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Un traseu al robotului format din '''4''' pași este evidențiat mai jos.

1 '''0 0 0''' 1
0 0 1 '''0 0'''
0 0 0 0 1
1 1 0 0 1
Există și alte trasee posibile, dar lungimea lor este mai mare.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def validare(nr_n, nr_m, matrix, x_inceput, y_inceput, x_sfarsit, y_sfarsit, fisier_out):
if not (1 <= nr_n <= 1000 and 1 <= nr_m <= 1000):
raise ValueError
for linie in matrix:
for elem in linie:
if not isinstance(elem, int):
raise ValueError
if not (0 <= x_inceput < nr_n and 0 <= y_inceput < nr_m and 0 <= x_sfarsit < nr_n and 0 <= y_sfarsit < nr_m):
raise ValueError
if matrix[x_inceput][y_inceput] != 0 or matrix[x_sfarsit][y_sfarsit] != 0 or (x_inceput == x_sfarsit and y_inceput == y_sfarsit):
raise ValueError
fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")

def bfs(nr_n, nr_m, matrix, x_inceput, y_inceput, x_sfarsit, y_sfarsit):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
distanta = [[-1 for _ in range(nr_m)] for _ in range(nr_n)]
coada = deque()
coada.append((x_inceput, y_inceput))
distanta[x_inceput][y_inceput] = 0
while coada:
x, y = coada.popleft()
for directie in range(4):
new_x, new_y = x + dx[directie], y + dy[directie]
if 0 <= new_x < nr_n and 0 <= new_y < nr_m and matrix[new_x][new_y] == 0 and distanta[new_x][new_y] == -1:
coada.append((new_x, new_y))
distanta[new_x][new_y] = distanta[x][y] + 1
return distanta[x_sfarsit][y_sfarsit]

if __name__ == "__main__":
file_in = open('robotiin.txt', 'r')
file_out = open('robotiout.txt', 'w')
try:
n, m = map(int, file_in.readline().split())
matrice = [list(map(int, file_in.readline().split())) for _ in range(n)]
x_start, y_start = map(int, file_in.readline().split())
x_end, y_end = map(int, file_in.readline().split())
validare(n, m, matrice, x_start-1, y_start-1, x_end-1, y_end-1, file_out)
rezultat = bfs(n, m, matrice, x_start-1, y_start-1, x_end-1, y_end-1)
file_out.write(str(rezultat))
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

2088 - decodif

2023-11-17T16:59:41Z

Bonte Lucas Gabriel:

Se consideră următorul model (pattern): '''n[string]''' care este echivalent cu șirul '''(string)(string)...(string)''' ('''string''' repetat de de '''n''' ori). Pornind de la acest model orice șir de caractere poate fi codificat.

'''Exemple''' :

'''Șir codificat'''

'''1[a]'''
'''2[ab]'''
'''2[a2[b]]'''
'''3[b2[ca]]'''

'''Șir decodificat'''

'''a'''
'''abab'''
'''abbabb'''
'''bcacabcacabcaca'''

==Cerința==

Fiind dat un șir de caractere corect codificat să se afișeze decodificarea acestuia.

==Date de intrare==

Programul citește de la tastatură un șir de caractere '''S''' corect codificat.

==Date de ieșire==

Programul va afișa pe ecran un șir de caractere ce va reprezenta decodificarea șirului '''S'''.

==Restricții și precizări==

*'''3 ≤''' lungimea șirului '''S ≤ 1000'''
*lungimea șirului decodificat '''≤ 100000'''
*șirul '''S''' va conține doar caractere literă mică ale alfabetului englez

==Exemplul 1:==

;Intrare

3[a1[b2[c]]]

;Ieșire

Datele de intrare corespund restrictiilor impuse
abccabccabcc

;Intrare

3[a2[c]]2[x3[y]]

;Ieșire

Datele de intrare corespund restrictiilor impuse
accaccaccxyyyxyyy

==Exemplul 2:==

;Intrare

2024

;Ieșire

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(sir): # functia de validare a datelor de intrare
if len(sir) < 3 or len(sir) > 1000:
raise ValueError
if not sir.islower():
raise ValueError
print("Datele de intrare corespund restrictiilor impuse\n")

def decode_string(sir): # functia de rezolvare
stack = [["", 1]]
num = ""
for ch in sir:
if ch.isdigit():
num += ch
elif ch == '[':
stack.append(["", int(num)])
num = ""
elif ch == ']':
st, k = stack.pop()
stack[-1][0] += st*k
else:
stack[-1][0] += ch
return stack[0][0]

if __name__ == '__main__':
try:
s = input("Introduceți șirul codificat: ").strip()
validare(s)
result = decode_string(s)
print(result)
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse\n")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse\n")

</syntaxhighlight>

3949 - mindist

2023-11-15T19:54:30Z

Bonte Lucas Gabriel:

==Cerința==

MăcGregăr se află într-o matrice pătratică cu '''N''' linii și '''N''' coloane. Aflându-se în celula '''(i, j)''' acesta se poate deplasa printr-un pas într-una din celulele '''(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)'''. Sunt '''M''' celule distincte prin care el nu poate trece, deoarece sunt ocupate cu echipamentul lui sportiv. De asemenea, mai sunt '''K''' celule distincte, diferite de cele ocupate, în care se află proteina lui MăcGregăr. Pentru fiecare celulă din matrice din care acesta ar pleca, MăcGregăr se întreabă care este numărul minim de pași pentru a ajunge la cea mai apropiată proteină.

==Date de intrare==

Fișierul de intrare '''mindistin.txt''' conține pe prima linie numerele '''N''', '''M''' și '''K''' separate printr-un spațiu. Pe următoarele '''M''' linii se află câte două numere naturale reprezentând linia și coloana pe care se află o celulă ocupată. Pe următoarele '''K''' linii se află câte două numere naturale reprezentând linia și coloana pe care se află o proteină.

==Date de ieșire==

Fișierul de ieșire '''mindistout.txt''' va conține '''N''' linii, fiecare linie va conține '''N''' numere întregi, separate printr-un spațiu. Pe linia '''i''', a '''j'''-a valoare reprezintă numărul minim de pași pentru a ajunge din celula '''(i, j)''' la cea mai apropiată proteină, dacă un astfel de drum există, '''-1''' altfel.

==Restricții și precizări==

*'''1 ≤ M ≤ N * N'''
*'''1 ≤ K ≤ N * N'''
*Pentru 30p, avem '''1 ≤ N ≤ 50'''
*Pentru alte 30p, avem '''1 ≤ N ≤ 1000''' și '''1 ≤ K ≤ 10'''
*Pentru restul de 40p, avem '''1 ≤ N ≤ 1000'''

==Exemplul 1:==

'''mindistin.txt'''

4 5 3
4 3
2 1
4 2
4 1
3 4
3 3
2 3
1 1

'''mindistout.txt'''

Datele de intrare corespund restrictiilor impuse
0 1 1 2
-1 1 0 1
2 1 0 -1
-1 -1 -1 -1

==Exemplul 2:==

'''mindistin.txt'''

51

'''mindistout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def validare(numar_n, numar_m, numar_k): # functia de validare a datelor de intrare
if numar_n < 1 or numar_n > 1000 or numar_m < 1 or numar_m > numar_n*numar_n or numar_k < 1 or numar_k > n*n:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def mindist(numar_n, blocked, proteins): # functia de rezolvare
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
matrix = [[-1 for _ in range(numar_n)] for _ in range(numar_n)]
queue = deque()
for b in blocked:
matrix[b[0]-1][b[1]-1] = -2
for p in proteins:
queue.append((p[0]-1, p[1]-1))
matrix[p[0]-1][p[1]-1] = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < numar_n and 0 <= ny < numar_n and matrix[nx][ny] == -1:
matrix[nx][ny] = matrix[x][y] + 1
queue.append((nx, ny))
return matrix

if __name__ == '__main__':
try:
file_in = open("mindistin.txt", "r") # declararea fisierelor
file_out = open("mindistout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)
n, m, k = map(int, file_in.readline().split())
blocat = [tuple(map(int, file_in.readline().split())) for _ in range(m)]
proteine = [tuple(map(int, file_in.readline().split())) for _ in range(k)]
validare(n, m, k)
result = mindist(n, blocat, proteine)
for row in result:
file_out.write(' '.join(str(x) if x != -2 else '-1' for x in row))
file_out.write('\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")

</syntaxhighlight>

0882 - Lac

2023-11-15T18:34:54Z

Bonte Lucas Gabriel:

==Cerința==

Se dă harta unui lac de formă dreptunghiulară, împărțit în '''n*m''' zone dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Zonele pot fi acoperite cu apă, sau pot fi zone de uscat. Zonele de uscat care sunt învecinate pe linie sau pe coloană formează insule sau peninsule. Peninsule conțin cel puțin o zonă de uscat pe marginea lacului (matricei), în timp ce insulele sunt situate în întregime în interiorul lacului.

Cunoscând harta lacului, determinați numărul de insule și numărul de peninsule.

==Date de intrare==

Fișierul de intrare '''lacin.txt''' conține pe prima linie numerele '''n m'''. Următoarele '''n''' linii conțin câte '''m''' valori '''0''' sau '''1''', separate prin câte un spațiu. Valoarea '''0''' reprezintă o zonă acoperită cu apă, iar valoarea '''1''' reprezintă o zonă acoperită cu uscat.

==Date de ieșire==

Fișierul de ieșire '''lacout.txt''' va conține pe prima două numerele '''nrI nrP''', separate prin exact un spațiu, reprezentând numărul de insule, respectiv numărul de peninsule existente pe lac.

==Restricții și precizări==

*'''1 ≤ n , m ≤ 1000'''

==Exemplul 1:==

'''lacin.txt'''

6 9
1 1 0 0 1 1 1 0 0
0 0 1 0 1 0 1 0 0
1 1 0 0 0 0 0 0 0
1 0 0 0 1 1 1 0 0
1 1 1 1 0 1 0 0 0
1 0 0 0 0 0 1 1 0

'''lacout.txt'''

Datele de intrare corespund restrictiilor impuse

2 4

==Exemplul 2:==

'''lacin.txt'''

harta unui lac

'''lacout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(nr_n, nr_m, matrix): # functia de validare a datelor de intrare
if nr_n < 1 or nr_n > 1000 or nr_m < 1 or nr_m > 1000:
raise ValueError
for linie in matrix:
if len(linie) != nr_m:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def dfs(i, j, nr_n, nr_m, matrix, vizitat):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
vizitat[i][j] = True
for directie in range(4):
x_nou, y_nou = i + dx[directie], j + dy[directie]
if 0 <= x_nou < nr_n and 0 <= y_nou < nr_m and matrix[x_nou][y_nou] == 1 and not vizitat[x_nou][y_nou]:
dfs(x_nou, y_nou, n, m, matrix, vizitat)

def numara_insule_peninsule(nr_n, nr_m, matrix): # functia de rezolvare
vizitat = [[False]*nr_m for _ in range(nr_n)]
insule = peninsule = 0
for i in range(nr_n):
for j in range(nr_m):
if matrix[i][j] == 1 and not vizitat[i][j]:
if i == 0 or i == nr_n-1 or j == 0 or j == nr_m-1:
peninsule += 1
else:
insule += 1
dfs(i, j, nr_n, nr_m, matrix, vizitat)
file_out.write(f'{insule} {peninsule}\n')

if __name__ == '__main__':
try:
file_in = open('lacin.txt', 'r')
file_out = open('lacout.txt', 'w')
n, m = map(int, file_in.readline().split())
matrice = [list(map(int, file_in.readline().split())) for _ in range(n)]
validare(n, m, matrice)
numara_insule_peninsule(n, m, matrice)
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")

</syntaxhighlight>

0882 - Lac

2023-11-15T17:16:20Z

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se dă harta unui lac de formă dreptunghiulară, împărțit în '''n*m''' zone dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Zonele pot fi acoperite cu apă, sau pot fi zone de uscat. Zonele de uscat care sunt învecinate pe linie sau pe coloană formează insule sau peninsule. Peninsule conțin cel puțin o zonă de uscat pe marginea lacului (matricei), în timp ce insulele sunt situate în întregime în interiorul lacului. Cunoscând...

==Cerința==

Se dă harta unui lac de formă dreptunghiulară, împărțit în '''n*m''' zone dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Zonele pot fi acoperite cu apă, sau pot fi zone de uscat. Zonele de uscat care sunt învecinate pe linie sau pe coloană formează insule sau peninsule. Peninsule conțin cel puțin o zonă de uscat pe marginea lacului (matricei), în timp ce insulele sunt situate în întregime în interiorul lacului.

Cunoscând harta lacului, determinați numărul de insule și numărul de peninsule.

==Date de intrare==

Fișierul de intrare '''lacin.txt''' conține pe prima linie numerele '''n m'''. Următoarele '''n''' linii conțin câte '''m''' valori '''0''' sau '''1''', separate prin câte un spațiu. Valoarea '''0''' reprezintă o zonă acoperită cu apă, iar valoarea '''1''' reprezintă o zonă acoperită cu uscat.

==Date de ieșire==

Fișierul de ieșire '''lacout.txt''' va conține pe prima două numerele '''nrI nrP''', separate prin exact un spațiu, reprezentând numărul de insule, respectiv numărul de peninsule existente pe lac.

==Restricții și precizări==

*'''1 ≤ n , m ≤ 1000'''

==Exemplul 1:==

'''lac.in'''

:6 9
:1 1 0 0 1 1 1 0 0
:0 0 1 0 1 0 1 0 0
:1 1 0 0 0 0 0 0 0
:1 0 0 0 1 1 1 0 0
:1 1 1 1 0 1 0 0 0
:1 0 0 0 0 0 1 1 0

'''lac.out'''

:Datele de intrare corespund restrictiilor impuse

2 4

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(nr_n, nr_m, matrix): # functia de validare a datelor de intrare
if nr_n < 1 or nr_n > 1000 or nr_m < 1 or nr_m > 1000:
raise ValueError
for linie in matrix:
if len(linie) != nr_m:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def dfs(i, j, nr_n, nr_m, matrix, vizitat):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
vizitat[i][j] = True
for directie in range(4):
x_nou, y_nou = i + dx[directie], j + dy[directie]
if 0 <= x_nou < nr_n and 0 <= y_nou < nr_m and matrix[x_nou][y_nou] == 1 and not vizitat[x_nou][y_nou]:
dfs(x_nou, y_nou, n, m, matrix, vizitat)

def numara_insule_peninsule(nr_n, nr_m, matrix): # functia de rezolvare
vizitat = [[False]*nr_m for _ in range(nr_n)]
insule = peninsule = 0
for i in range(nr_n):
for j in range(nr_m):
if matrix[i][j] == 1 and not vizitat[i][j]:
if i == 0 or i == nr_n-1 or j == 0 or j == nr_m-1:
peninsule += 1
else:
insule += 1
dfs(i, j, nr_n, nr_m, matrix, vizitat)
file_out.write(f'{insule} {peninsule}\n')

if __name__ == '__main__':
try:
file_in = open('lacin.txt', 'r')
file_out = open('lacout.txt', 'w')
n, m = map(int, file_in.readline().split())
matrice = [list(map(int, file_in.readline().split())) for _ in range(n)]
validare(n, m, matrice)
numara_insule_peninsule(n, m, matrice)
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")

</syntaxhighlight>

2645 - minlex

2023-11-14T23:03:35Z

Bonte Lucas Gabriel:

Se consideră un cuvânt format numai din litere mici și un număr natural nenul '''K'''.

==Cerința==

Să se determine cuvântul minim lexicografic obținut prin eliminarea a exact '''K''' litere din cuvântul inițial.

==Date de intrare==

Programul citește de la tastatură numărul '''K''', apoi cuvântul.

==Date de ieșire==

Programul va afișa pe ecran cuvântul rămas după eliminarea a exact '''K''' litere, minim lexicografic.

==Restricții și precizări==

*'''3 ≤ lungimea cuvântului ≤ 1.000.000'''
*Cuvântul este format numai din litere mici ale alfabetului englez.
*'''1 ≤ K < lungimea cuvântului'''
*Literele rămase după eliminare nu-și pot schimba ordinea în cuvânt.

==Exemplul 1:==

;Intrare

:5 zyizxtnfo

;Ieșire

:Datele de intrare corespund restrictiilor impuse
:info

==Exemplul 2:==

;Intrare

:0

;Ieșire

:Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(litera_k, word): # functia de validare a datelor de intrare
if 1 > litera_k or litera_k >= len(word) or len(word) > 1000000:
raise ValueError
if not word.islower():
raise ValueError
print("Datele de intrare corespund restrictiilor impuse\n")

def elimina_litere(litera_k, word): # functia de rezolvare
stiva = []
for litera in word:
while litera_k > 0 and stiva and stiva[-1] > litera:
stiva.pop()
litera_k -= 1
stiva.append(litera)
while litera_k > 0:
stiva.pop()
litera_k -= 1
return ''.join(stiva)

if __name__ == '__main__':
try:
k, cuvant = input("Introduceți numărul K și cuvântul, separate printr-un spațiu: ").split()
k = int(k)
validare(k, cuvant)
rezultat = elimina_litere(k, cuvant)
print(str(rezultat) + '\n')
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0852 - Paranteze3

2023-11-14T22:07:58Z

Bonte Lucas Gabriel:

==Cerința==

Se dau '''n''' șiruri de paranteze rotunde sau pătrate. Să se stabilească, despre fiecare șir, dacă este corect parantezat – adică dacă parantezele se închid corect.

Un șir de paranteze '''S''' rotunde este corect parantezat dacă:

*'''S''' este șirul vid, sau
*'''S = (T)''' și '''T''' este corect parantezat, sau
*'''S = [T]''' și '''T''' este corect parantezat, sau
*'''S = AB''', iar '''A''' și '''B''' sunt corect parantezate.

==Date de intrare==

Fișierul de intrare '''paranteze3in.txt''' conține pe prima linie numărul '''n''', pe următoarele '''n''' linii câte un șir de paranteze rotunde sau pătrate.

==Date de ieșire==

Fișierul de ieșire '''paranteze3out.txt''' va conține '''n''' linii: fiecare linie va conține valoarea '''1''', dacă șirul corespunzător de paranteze este corect parantezat și '''0''' în caz contrar.

==Restricții și precizări==

*'''1 ≤ n ≤ 100'''
*fiecare șir va avea cel mult '''255''' de paranteze

==Exemplul 1:==

'''paranteze3in.txt'''

:4
:()[]
:)([]
:()[(()[])()]
([)]

'''paranteze3out.txt'''

:Datele de intrare corespund restrictiilor impuse
:1
:0
:1
:0

==Exemplul 2:==

'''paranteze3in.txt'''

:ana are mere

'''paranteze3out.txt'''

:Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(numar, strings): # functia de validare a datelor de intrare
if numar < 1 or numar > 100:
raise ValueError
for sir in strings:
if len(sir) > 255:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def verifica_paranteze(sir): # functia de rezolvare
stiva = []
for paranteza in sir:
if paranteza in "([":
stiva.append(paranteza)
else:
if not stiva:
return 0
top = stiva.pop()
if paranteza == ")" and top != "(":
return 0
elif paranteza == "]" and top != "[":
return 0
if stiva:
return 0
return 1

if __name__ == '__main__':
file_in = open('paranteze3in.txt', 'r')
file_out = open('paranteze3out.txt', 'w')

try:
n = int(file_in.readline().strip())
siruri = [file_in.readline().strip() for _ in range(n)]
validare(n, siruri)
rezultate = [verifica_paranteze(sir) for sir in siruri]
for rezultat in rezultate:
file_out.write(str(rezultat) + '\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0849 - Paranteze2

2023-11-13T22:05:06Z

Bonte Lucas Gabriel:

==Cerința==

Se dă un șir de paranteze rotunde care se închid corect (corect parantezat). Să se determine adâncimea parantezării.

Pentru un șir de paranteze închise corect '''S''', adâncimea parantezării, '''D(S)''' este definită astfel:

dacă șirul '''S''' este vid, '''D(S)=0'''
dacă '''S=(T)''', unde '''T''' este un șir de paranteze corect, '''D(S)=1+D(T)'''
dacă '''S=AB''', unde '''A''' și '''B''' sunt șiruri de paranteze corecte, '''D(S)=max{D(A),D(B)}'''

==Date de intrare==

Fișierul de intrare '''paranteze2in.txt''' conține pe prima un șir de paranteze rotunde, corect parantezat.

==Date de ieșire==

Fișierul de ieșire '''paranteze2out.txt''' va conține pe prima linie un număr '''M''', reprezentând adâncimea parantezării.

==Restricții și precizări==
*șirul va conține cel mult '''254''' de paranteze

==Exemplul 1:==

'''paranteze2in.txt'''

:1
:()((()())())

'''paranteze2out.txt'''

:Datele de intrare corespund restrictiilor impuse.
:3

==Exemplul 2:==

'''paranteze2in.txt'''

:h

'''paranteze2out.txt'''

:Datele de intrare nu corespund restrictiilor impuse.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(strings): # functia de validare a datelor de intrare
for sir in strings:
if len(sir) > 254:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def adancime_parantezare(sir): # functia de rezolvare
adancime_maxima = 0
adancime_curenta = 0
for paranteza in sir:
if paranteza == '(':
adancime_curenta += 1
if adancime_curenta > adancime_maxima:
adancime_maxima = adancime_curenta
elif paranteza == ')':
adancime_curenta -= 1
return adancime_maxima

if __name__ == '__main__':
file_in = open('paranteze2in.txt', 'r')
file_out = open('paranteze2out.txt', 'w')

try:
n = int(file_in.readline().strip())
siruri = [file_in.readline().strip() for _ in range(n)]
validare(siruri)
rezultate = [adancime_parantezare(sir) for sir in siruri]
for rezultat in rezultate:
file_out.write(str(rezultat) + '\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0848 - Paranteze1

2023-11-13T21:35:19Z

Bonte Lucas Gabriel:

==Cerința==

Se dau '''n''' șiruri de paranteze rotunde. Să se stabilească, despre fiecare șir, dacă este corect parantezat – adică dacă parantezele se închid corect.

Un șir de paranteze '''S''' rotunde este corect parantezat dacă:

*'''S''' este șirul vid, sau
*'''S = (T)''' și '''T''' este corect parantezat, sau
*'''S = AB''', iar '''A''' și '''B''' sunt corect parantezate.

==Date de intrare==

Fișierul de intrare '''paranteze1in.txt''' conține pe prima linie numărul '''n''', pe următoarele '''n''' linii câte un șir de paranteze rotunde.

==Date de ieșire==

Fișierul de ieșire '''paranteze1out.txt''' va conține '''n''' linii: fiecare linie va conține valoarea '''1''', dacă șirul corespunzător de paranteze este corect parantezat și '''0''' în caz contrar.

==Restricții și precizări==

*'''1 ≤ n ≤ 100'''
*fiecare șir va avea cel mult '''255''' de paranteze

==Exemplul 1:==

'''paranteze1in.txt'''

:4
:(())
:)(()
:()((()())())
:()(

'''paranteze1out.txt'''

:Datele de intrare corespund restrictiilor impuse.
:1
:0
:1
:0

==Exemplul 2:==

'''paranteze1in.txt'''

:2h

'''paranteze1out.txt'''

:Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def validare(numar, string): # functia de validare a datelor de intrare
if numar < 1 or numar > 100:
raise ValueError
for sir in string:
if len(sir) > 255:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def este_corect_parantezat(s): # functia de rezolvare
stiva = []
for paranteza in s:
if paranteza == '(':
stiva.append(paranteza)
elif paranteza == ')':
if len(stiva) == 0:
return 0
stiva.pop()
return 1 if len(stiva) == 0 else 0

if __name__ == '__main__':
file_in = open('paranteze1in.txt', 'r')
file_out = open('paranteze1out.txt', 'w')

try:
n = int(file_in.readline().strip())
siruri = [file_in.readline().strip() for _ in range(n)]
validare(n, siruri)
rezultate = [este_corect_parantezat(sir) for sir in siruri]
for rezultat in rezultate:
file_out.write(str(rezultat) + '\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

3410 - Submatrix Sum Max

2023-11-13T17:33:06Z

Bonte Lucas Gabriel:

Se dă o matrice de numere întregi cu '''n''' linii și '''n''' coloane.

==Cerință==

Să se determine suma maximă care se poate obține dintr-o submatrice.

==Date de intrare==

Programul citește de la tastatură numărul '''n''', iar apoi elementele matricei cu '''n''' linii și '''n''' coloane.

==Date de ieșire==

Programul va afișa pe ecran suma maximă care se poate obține dintr-o submatrice.

==Restricții de precizări==

* 1 &les; n &les; 300
* Elementele matricei sunt numere întregi din intervalul '''[-1000, 1000]'''
* O submatrice poate fi formată dintr-un singur element

==Exemplul 1==

;Intrare

:5
:2 4 -1 2 -1
:4 -7 1 -6 -1
:-9 2 4 5 -7
:1 3 -2 6 2
:1 -4 -6 -5 8

;Ieșire

:Datele introduse corespund restricțiilor impuse.

:18

==Exemplul 2==

;Intrare

:1x

;Ieșire

:Datele introduse nu corespund restricțiilor impuse.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def verificare_restrictii(numar, matrix): # functia de verificare a datelor de intrare
if 1 <= numar <= 300 and all(-1000 <= element <= 1000 for rand in matrix for element in rand):
return True
else:
return False

def suma_maxima_submatrice(numar, matrix):
# inițializăm matricea de sume prefix cu 0
prefix_sum = [[0 for _ in range(numar + 1)] for _ in range(numar + 1)]

# calculăm matricea de sume prefix
for i in range(numar):
for j in range(numar):
prefix_sum[i + 1][j + 1] = matrix[i][j] - prefix_sum[i][j] + prefix_sum[i][j + 1] + prefix_sum[i + 1][j]

max_sum = float('-inf') # inițializăm suma maximă cu -infinit
# parcurgem toate submatricile posibile
for i in range(1, numar + 1):
for j in range(1, numar + 1):
for k in range(i, numar + 1):
for lenght in range(j, numar + 1):
# calculăm suma submatricei curente folosind sumele prefix
curr_sum = prefix_sum[k][lenght] - prefix_sum[k][j - 1] - prefix_sum[i - 1][lenght] + prefix_sum[i - 1][j - 1]
max_sum = max(max_sum, curr_sum) # actualizăm suma maximă dacă este cazul

return max_sum # returnăm suma maximă

if __name__ == '__main__':
try:
n = int(input("Introduceti numarul de linii/coloane: ")) # citirea numarului de linii si coloane
matrice = [list(map(int, input().split())) for _ in range(n)] # citirea matricei

if verificare_restrictii(n, matrice): # verificam datele de intrare
print("Datele de intrare corespund restrictiilor impuse.")
print(suma_maxima_submatrice(n, matrice)) # apelam functia de rezolvare
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
# ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

==Explicație==

Submatricea de sumă maximă este:
:'''2 4 5'''
:'''3 -2 6'''