Bitnami MediaWiki - User contributions [en]

661 - Triunghiuri1

2024-01-05T19:49:04Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dau '''n''' numere naturale distincte. Determinaţi câte triunghiuri distincte pot avea lungimile laturilor printre aceste numere. == Date de intrare == Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' numere naturale. == Date de ieșire == Programul va afișa pe ecran numărul '''C''', reprezentând numărul de triunghiuri determinate. == Restricţii şi precizări == * '''1 &les; n &les; 1000''' * cele '''n''' numere citite vor...

== Cerinţa ==
Se dau '''n''' numere naturale distincte. Determinaţi câte triunghiuri distincte pot avea lungimile laturilor printre aceste numere.
== Date de intrare ==
Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' numere naturale.
== Date de ieșire ==
Programul va afișa pe ecran numărul '''C''', reprezentând numărul de triunghiuri determinate.
== Restricţii şi precizări ==
* '''1 &les; n &les; 1000'''
* cele '''n''' numere citite vor fi mai mici decât '''1.000.000'''
== Exemplul 1 ==
;'''Intrare'''
5
3 5 10 7 6
;'''Iesire'''
Datele de intrare corespund restrictiilor impuse
7
== Exemplul 2 ==
;'''Intrare'''
3
1 2 1000000000
;'''Iesire'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def numar_triunghiuri(n_val, numere_val):
numere_val.sort()
count = 0
for i in range(n_val-2):
k = i + 2
for j in range(i+1, n_val):
while k < n_val and numere_val[i] + numere_val[j] > numere_val[k]:
k += 1
if k > j:
count += k - j - 1
return count

def verifica_restrictii(n_val, numere_val):
if n_val < 1 or n_val > 1000:
return "Datele de intrare nu corespund restrictiilor impuse"
for numar in numere_val:
if numar >= 1000000:
return "Datele de intrare nu corespund restrictiilor impuse"
return "Datele de intrare corespund restrictiilor impuse"

n = int(input())
numere = list(map(int, input().split()))
print(verifica_restrictii(n, numere))
print(numar_triunghiuri(n, numere))
</syntaxhighlight>
== Explicație ==
Cele '''7''' triunghiuri au lungimile laturilor:
'''3 5 7'''
'''3 5 6'''
'''3 7 6'''
'''5 7 6'''
'''5 10 7'''
'''5 10 6'''
'''10 7 6'''

2443 - cb2

2024-01-04T23:16:01Z

Brianna Waltner: Pagină nouă: Se consideră un șir de numere naturale nenule '''a[1]''', '''a[2]''', …, '''a[n]'''. Asupra șirului se efectuează '''Q''' interogări. Fiecare interogare este dată de o pereche '''(x, s)''': care este indicele maxim '''p''' cu proprietatea că '''a[i] ≤ x''', pentru orice '''i=1..p''' și în plus '''a[1] + a[2] + ... + a[p] ≤ s'''? == Cerinţa == Trebuie să răspundeți la fiecare din cele '''Q''' întrebări. == Date de intrare == Programul citește de la tastat...

Se consideră un șir de numere naturale nenule '''a[1]''', '''a[2]''', …, '''a[n]'''. Asupra șirului se efectuează '''Q''' interogări. Fiecare interogare este dată de o pereche '''(x, s)''': care este indicele maxim '''p''' cu proprietatea că '''a[i] ≤ x''', pentru orice '''i=1..p''' și în plus '''a[1] + a[2] + ... + a[p] ≤ s'''?
== Cerinţa ==
Trebuie să răspundeți la fiecare din cele '''Q''' întrebări.
== Date de intrare ==
Programul citește de la tastatură numărul '''n''', iar apoi '''n''' numere naturale, separate prin spații, reprezentând elementele șirului. Apoi se citește valoarea '''Q''' și la final se citesc '''Q''' perechi de forma '''(x, s)''' reprezentând întrebările.
== Date de ieșire ==
Programul va afișa pe câte o linie la ecran '''Q''' valori reprezentând răspunsurile la întrebări.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* '''1 &les; Q &les; 100.000'''
* '''1 &les; a[i] &les; 1.000''' pentru orice '''i=1..n'''
* pentru fiecare întrebare, '''1 &les; x, s &les; 1.000.000.000'''
== Exemplul 1 ==
;Intrare
9
5 3 1 7 4 9 8 2 6
6
8 10
4 20
6 20
6 8
10 100
10 20
;Iesire
Datele de intrare corespund restrictiilor impuse
3
0
3
2
9
5
== Exemplul 2 ==
;Intrare
5
1 2 3 4 5000
3
10 20
20 30
30 40
;Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
n = int(input())
a = list(map(int, input().split()))
Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]

if not (1 <= n <= 100000):
print("Datele de intrare nu corespund restrictiilor impuse")
elif not all(1 <= ai <= 1000 for ai in a):
print("Datele de intrare nu corespund restrictiilor impuse")
elif not (1 <= Q <= 100000):
print("Datele de intrare nu corespund restrictiilor impuse")
elif not all(1 <= x <= 1000000000 and 1 <= s <= 1000000000 for x, s in queries):
print("Datele de intrare nu corespund restrictiilor impuse")
else:
print("Datele de intrare corespund restrictiilor impuse")

for x, s in queries:
p = 0
total = 0
while p < n and a[p] <= x and total + a[p] <= s:
total += a[p]
p += 1
print(p)

</syntaxhighlight>
== Explicatie ==
La prima întrebare, '''x=8''', '''s=10'''. Indicele maxim este '''3''' pentru că primele trei valori din șir sunt mai mici sau egale cu '''8''', iar '''5 + 3 + 1 &les; 10'''.
La a doua întrebare, răspunsul este '''0''' deoarece primul număr din șir este '''5''' care este mai mare decât '''x=4'''.
La a cincea întrebare, '''x=10''' și '''s=100'''. Răspunsul este chiar lungimea șirului.

2239 - pow2

2024-01-04T22:58:52Z

Brianna Waltner: Pagină nouă: Se consideră un șir '''a[1]''', '''a[2]''',…, '''a[n]''' de numere naturale nenule. == Cerinţa == Să se determine câte perechi de indici '''(i, j)''', '''1 &les; i < j &les; n''', există cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui '''2'''. == Date de intrare == Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' numere naturale nenule, separate prin spații. == Date de ieșire == Programul va afișa pe ecran un sing...

Se consideră un șir '''a[1]''', '''a[2]''',…, '''a[n]''' de numere naturale nenule.
== Cerinţa ==
Să se determine câte perechi de indici '''(i, j)''', '''1 &les; i < j &les; n''', există cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui '''2'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' numere naturale nenule, separate prin spații.
== Date de ieșire ==
Programul va afișa pe ecran un singur număr natural reprezentând numărul de perechi de indici distincți '''(i, j)''' cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui '''2'''.
== Restricţii şi precizări ==
* '''2 &les; n &les; 100.000'''
* '''1 &les; a[i] &les; 1.000.000.000''', pentru orice '''i = 1..n'''
* Numerele care sunt puteri ale lui '''2''' sunt '''1''', '''2''', '''4''', '''8''', '''16''', '''32''', …
== Exemplul 1 ==
;Intrare
4
3 5 3 13
;Iesire
Datele de intrare corespund restrictiilor impuse
4
== Exemplul 2 ==
;Intrare
210000
16 17 20 24 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105
;Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_power_of_two(num):
return (num != 0) and (num & (num-1) == 0)

num_elements = int(input().strip())
if not (2 <= num_elements <= 100000):
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)
a = sorted(list(map(int, input().split())))
if any(ai < 1 or ai > 1000000000 for ai in a):
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)

print("Datele de intrare corespund restrictiilor impuse")

count = 0
for i in range(num_elements):
for j in range(i+1, num_elements):
if is_power_of_two(a[i] + a[j]):
count += 1

print(count)
</syntaxhighlight>

== Explicație ==
Cele patru perechi de indici sunt: '''(1,2)''', '''(1,4)''', '''(2,3)''', '''(3,4)'''.

2276 - cb

2024-01-04T22:41:42Z

Brianna Waltner: Pagină nouă: Se consideră un șir '''a[1]''', '''a[2]''', …, '''a[n]''' de numere naturale. Se dau și '''T''' intervale închise de forma '''[x, y]''', cu '''x ≤ y'''. == Cerinţa == Pentru fiecare din cele '''T''' intervale de forma '''[x, y]''' trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului '''[x, y]'''? == Date de intrare == Programul citește de la tastatură numerele '''n''' și '''T''', apoi '''n''' numere naturale, separate prin spații,...

Se consideră un șir '''a[1]''', '''a[2]''', …, '''a[n]''' de numere naturale. Se dau și '''T''' intervale închise de forma '''[x, y]''', cu '''x ≤ y'''.
== Cerinţa ==
Pentru fiecare din cele '''T''' intervale de forma '''[x, y]''' trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului '''[x, y]'''?
== Date de intrare ==
Programul citește de la tastatură numerele '''n''' și '''T''', apoi '''n''' numere naturale, separate prin spații, '''a[1]''', '''a[2]''', …, '''a[n]'''. Pe următoarele '''T''' linii se află câte două numere naturale '''x''' și '''y''' reprezentând un interval '''[x, y]'''.
== Date de ieșire ==
Programul va afișa pe ecran '''T''' linii. Pe fiecare linie '''i''' ('''i=1..T''') se va afla un singur număr natural reprezentând răspunsul la a '''i'''-a întrebare.
== Restricţii şi precizări ==
* '''1 &les; n, T &les; 200 000'''
* '''0 &les; a[i] &les; 2 000 000 000'''
* '''0 &les; x &les; y &les; 2 000 000 000'''
== Exemplul 1 ==
;Intrare
9 7
6 1 3 5 3 3 9 20 9
4 10
0 100
0 1
500 506
3 3
10 18
3 9
;Iesire
Datele de intrare corespund restrictiilor impuse
4
9
1
0
3
0
7
== Exemplul 2 ==
;Intrare
210000 5
16 17 20 24 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105
4 10
0 100
0 1
500 506
3 3
10 18
3 9
;Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from bisect import bisect_left, bisect_right

n, T = map(int, input().strip().split())
if not (1 <= n <= 200000 and 1 <= T <= 200000):
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)
students = sorted(list(map(int, input().split())))
if any(s < 0 or s > 2000000000 for s in students):
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)
intervals = [list(map(int, input().split())) for _ in range(T)]
if any(x < 0 or y < x or y > 2000000000 for x, y in intervals):
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)

print("Datele de intrare corespund restrictiilor impuse")

for x, y in intervals:
start = bisect_left(students, x)
end = bisect_right(students, y)
print(end - start)
</syntaxhighlight>

2644 - clase

2024-01-04T22:18:36Z

Brianna Waltner: Pagină nouă: == Cerinţa == Într-o școală sunt '''n''' clase, fiecare având un număr diferit de elevi. Școală primește '''m''' pachete cu cărți, fiecare cu un număr diferit de cărți. Pentru ca o clasa să primească un pachet, numărul elevilor din acea clasa trebuie să fie egal cu numărul cărților din pachet. Să se determine câte clase primesc un pachet de cărți. == Date de intrare == Fișierul de intrare '''clasein.txt''' va avea pe prima linie numărul '''n''', iar...

== Cerinţa ==
Într-o școală sunt '''n''' clase, fiecare având un număr diferit de elevi. Școală primește '''m''' pachete cu cărți, fiecare cu un număr diferit de cărți. Pentru ca o clasa să primească un pachet, numărul elevilor din acea clasa trebuie să fie egal cu numărul cărților din pachet. Să se determine câte clase primesc un pachet de cărți.
== Date de intrare ==
Fișierul de intrare '''clasein.txt''' va avea pe prima linie numărul '''n''', iar pe următoarea linie '''n''' numere naturale ordonate crescător, separate prin spații, reprezentând numărul de elevi din fiecare clasa. Pe următoarea linie numărul '''m''', și pe următoarea linie '''m''' numere, reprezentând numărul de cărți din fiecare pachet.
== Date de ieșire ==
Fișierul de ieșire '''claseout.txt''' va conține pe prima linie numărul de clase care primesc pachete cu cărți.
== Restricţii şi precizări ==
* '''1 &les; n, m &les; 10.000'''
* într-un pachet sunt maximum '''1.000.000.000.000''' cărți.
* într-o clasă sunt maximum '''1.000.000.000.000''' elevi.
== Exemplul 1 ==
;'''clasein.txt'''
5
16 17 20 24 30
4
78 20 17 74
;'''claseout.txt'''
Datele de intrare corespund restrictiilor impuse
2
== Exemplul 2 ==
;'''clasein.txt'''
100000
16 17 20 24 30
4
78 20 17 74
;'''claseout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1

with open('clasein.txt', 'r') as fin:
n = int(fin.readline().strip())
if n < 1 or n > 10000:
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)
students = sorted(list(map(int, fin.readline().split())))
if any(s < 1 or s > 1000000000000 for s in students):
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)
m = int(fin.readline().strip())
if m < 1 or m > 10000:
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)
books = sorted(list(map(int, fin.readline().split())))
if any(b < 1 or b > 1000000000000 for b in books):
print("Datele de intrare nu corespund restrictiilor impuse")
exit(1)

print("Datele de intrare corespund restrictiilor impuse")

count = 0
for s in students:
index = binary_search(books, s)
if index != -1:
count += 1
books.pop(index)

with open('claseout.txt', 'w') as fout:
fout.write(str(count))
</syntaxhighlight>
== Explicatie ==
Doar clasa cu '''20''' de elevi și cea cu '''17''' elevi vor primi pachete cu cărți.

2006 - Mana

2024-01-04T21:06:45Z

Brianna Waltner: Pagină nouă: == Cerinţa == Înștiințat de atacul orcilor, Gandalf și-a luat măsurile de precauție. Credinciosul spion i-a adus acestuia o hartă care arată pozițiile celor '''n''' orci. Harta poate fi reprezentată ca un sistem cartezian de coordonate. Gandalf vrea să folosească o vrajă astfel încât să anihileze cel puțin '''k''' orci. De asemenea, acesta vrea să folosească cât mai puțină mana. Știind că, dacă utilizează '''r''' mana ('''r''' număr natural), și v...

== Cerinţa ==
Înștiințat de atacul orcilor, Gandalf și-a luat măsurile de precauție. Credinciosul spion i-a adus acestuia o hartă care arată pozițiile celor '''n''' orci. Harta poate fi reprezentată ca un sistem cartezian de coordonate. Gandalf vrea să folosească o vrajă astfel încât să anihileze cel puțin '''k''' orci. De asemenea, acesta vrea să folosească cât mai puțină mana. Știind că, dacă utilizează '''r''' mana ('''r''' număr natural), și vraja este folosită în punctul de coordonate '''(x,y)''', acesta anihilează toți orcii din interiorul cercului cu centrul în '''(x,y)''' de rază '''r''', aflați mana minimă necesară pentru a anihila '''k''' orci.
== Date de intrare ==
Fișierul de intrare '''manain.txt''' conține pe prima linie două numere naturale '''n''', '''k''', cu semnificațiile din enunț. Pe următoarele '''n''' linii se găsesc câte două numere întregi separate printr-un spațiu, reprezentând abscisa respectiv ordonata fiecărui orc de pe hartă.
== Date de ieșire ==
Fișierul de ieșire '''manaout.txt''' va conține pe prima linie numărul '''r''', reprezentând mana minimă pe care o poate utiliza Gandalf pentru a anihila '''k''' orci.
== Restricţii şi precizări ==
* '''1 &les; k &les; n &les; 100'''
* Numerele din fișierul de intrare sunt întregi cuprinse între '''-100000''' și '''100000'''.
== Exemplul 1 ==
;'''manain.txt'''
5 3
3 3
5 3
1 -5
-4 1
0 3
;'''manaout.txt'''
3
== Exemplul 2 ==
;'''manain.txt'''
5 3
3 3
5 3
1 -5
-4 1
1000001 3
;'''manaout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from math import sqrt, ceil

def distanta(p1, p2):
return sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

def mana_minima(n_val, k_val, orci_val):
if not (1 <= k_val <= n_val <= 100):
return "Datele de intrare nu corespund restrictiilor impuse"
if any(abs(orc[0]) > 100000 or abs(orc[1]) > 100000 for orc in orci_val):
return "Datele de intrare nu corespund restrictiilor impuse"

distante = []
for orc in orci_val:
distante_orc = sorted(distanta(orc, orc2) for orc2 in orci_val)
distante.append(distante_orc[k_val - 1])
return ceil(min(distante))

with open('manain.txt', 'r') as fin:
n, k = map(int, fin.readline().strip().split())
orci = [list(map(int, line.split())) for line in fin]
result = mana_minima(n, k, orci)

with open('manaout.txt', 'w') as fout:
fout.write(str(result))
</syntaxhighlight>
== Explicatie ==
Gandalf poate să folosească vraja în punctul de abscisă '''2,5''' și ordonată '''3'''.

508 - Cautare Binara

2024-01-04T20:36:23Z

Brianna Waltner:

== Cerinţa ==
Se dă un vector '''x''' cu '''n''' elemente numere naturale, ordonate crescător, și un vector '''y''' cu '''m''' elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului '''y''' dacă apare în '''x'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' elemente ale vectorului '''x'''. Apoi și citește '''m''' și cele '''m''' elemente ale lui '''y'''.
== Date de ieșire ==
Programul va afișa pe ecran '''m''' valori '''0''' sau '''1''', separate prin exact un spațiu. A '''j'''-a valoare afișată este '''1''', dacă al j-lea element al șirului '''y''' apare în '''x''', respectiv 0 în caz contrar.
== Restricţii şi precizări ==
* '''1 &les; n &les; 25.000'''
* '''1 &les; m &les; 200.000'''
* elementele celor '''2''' vectori vor fi mai mici decât '''1.000.000.000'''
== Exemplul 1 ==
;Intrare
7
1 2 5 6 9 10 14
8
8 14 9 14 16 15 4 2
;Iesire
0 1 1 1 0 0 0 1
== Exemplul 2 ==
;Intrare
30000
1 2 5 6 9 10 14
8
8 14 9 14 16 15 4 2
;Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def verifica_elemente():
n_val = int(input("Introduceti numarul n: "))
x_val = list(map(int, input("Introduceti elementele vectorului x: ").split()))

m_val = int(input("Introduceti numarul m: "))
y_val = list(map(int, input("Introduceti elementele vectorului y: ").split()))

if not (1 <= n_val <= 25000) or not (1 <= m_val <= 200000):
return "Datele de intrare nu corespund restrictiilor impuse"
if max(x_val) >= 1000000000 or max(y_val) >= 1000000000:
return "Datele de intrare nu corespund restrictiilor impuse"

x_set = set(x_val)

rezultat = [1 if elem in x_set else 0 for elem in y_val]

return " ".join(map(str, rezultat))

print(verifica_elemente())
</syntaxhighlight>

508 - Cautare Binara

2024-01-04T20:16:35Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă un vector '''x''' cu '''n''' elemente numere naturale, ordonate crescător, și un vector '''y''' cu '''m''' elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului '''y''' dacă apare în '''x'''. == Date de intrare == Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' elemente ale vectorului '''x'''. Apoi și citește '''m''' și cele '''m''' elemente ale lui '''y'''. == Date de ieșire == Progra...

== Cerinţa ==
Se dă un vector '''x''' cu '''n''' elemente numere naturale, ordonate crescător, și un vector '''y''' cu '''m''' elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului '''y''' dacă apare în '''x'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' elemente ale vectorului '''x'''. Apoi și citește '''m''' și cele '''m''' elemente ale lui '''y'''.
== Date de ieșire ==
Programul va afișa pe ecran '''m''' valori '''0''' sau '''1''', separate prin exact un spațiu. A '''j'''-a valoare afișată este '''1''', dacă al j-lea element al șirului '''y''' apare în '''x''', respectiv 0 în caz contrar.
== Restricţii şi precizări ==
* '''1 ≤ n ≤ 25.000'''
* '''1 ≤ m ≤ 200.000'''
* elementele celor '''2''' vectori vor fi mai mici decât '''1.000.000.000'''
== Exemplul 1 ==
;Intrare
7
1 2 5 6 9 10 14
8
8 14 9 14 16 15 4 2
;Iesire
0 1 1 1 0 0 0 1
== Exemplul 2 ==
;Intrare
30000
1 2 5 6 9 10 14
8
8 14 9 14 16 15 4 2
;Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def verifica_elemente():
n_val = int(input("Introduceti numarul n: "))
x_val = list(map(int, input("Introduceti elementele vectorului x: ").split()))

m_val = int(input("Introduceti numarul m: "))
y_val = list(map(int, input("Introduceti elementele vectorului y: ").split()))

if not (1 <= n_val <= 25000) or not (1 <= m_val <= 200000):
return "Datele de intrare nu corespund restrictiilor impuse"
if max(x_val) >= 1000000000 or max(y_val) >= 1000000000:
return "Datele de intrare nu corespund restrictiilor impuse"

x_set = set(x_val)

rezultat = [1 if elem in x_set else 0 for elem in y_val]

return " ".join(map(str, rezultat))

print(verifica_elemente())
</syntaxhighlight>

0543 - Bipartit 2

2024-01-04T14:21:17Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă lista muchiilor unui graf neorientat conex cu '''n''' vârfuri, etichetate de la '''1''' la '''n'''. Să se verifice dacă graful este bipartit. == Date de intrare == Fişierul de intrare '''bipartit2in.txt''' conţine pe prima linie numerele '''n''' și '''m''', reprezentând numărul de vârfuri ale grafului și numărul de muchii. Fiecare dintre următoarele '''m''' linii conține câte o pereche de numere '''i j''', cu semnificația că există muchi...

== Cerinţa ==
Se dă lista muchiilor unui graf neorientat conex cu '''n''' vârfuri, etichetate de la '''1''' la '''n'''. Să se verifice dacă graful este bipartit.
== Date de intrare ==
Fişierul de intrare '''bipartit2in.txt''' conţine pe prima linie numerele '''n''' și '''m''', reprezentând numărul de vârfuri ale grafului și numărul de muchii. Fiecare dintre următoarele '''m''' linii conține câte o pereche de numere '''i j''', cu semnificația că există muchie între '''i''' și '''j'''.
== Date de ieșire ==
Fişierul de ieşire '''bipartit2out.txt''' va conţine pe prima linie mesajul '''DA''', dacă graful este bipartit, respectiv '''NU''' în caz contrar.

Dacă mesajul este '''DA''', următoarele două linii vor conţine două mulţimi care formează partiţia vârfurilor. Elementele fiecărei mulţimi vor fi afişate în ordine crescătoare, separate prin exact un spaţiu. Prima mulţime va fi cea care conţine vârful '''1'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100'''
* '''1 &les; i , j &les; n'''
== Exemplul 1 ==
;'''bipartit2in.txt'''
7 6
1 4
1 6
6 5
3 2
3 5
3 7
;'''bipartit2out.txt'''
Datele de intrare corespund resprictiilor impuse
DA
1 2 5 7
3 4 6
== Exemplul 2 ==
;'''bipartit2in.txt'''
0 6
1 4
1 6
6 5
3 2
3 5
3 7
;'''bipartit2out.txt'''
Datele de intrare nu corespund resprictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict

def is_bipartite():
with open('bipartit2in.txt', 'r') as fin:
n, m = map(int, fin.readline().split())
if n <= 1 or n > 100:
return "Datele de intrare nu corespund resprictiilor impuse", [], []
edges = [tuple(map(int, line.split())) for line in fin.readlines()]
for u, v in edges:
if u < 1 or u > n or v < 1 or v > n:
return "Datele de intrare nu corespund resprictiilor impuse", [], []

print("Datele de intrare corespund resprictiilor impuse")

graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)

color = defaultdict(int)
partition = defaultdict(list)
for node in range(1, n+1):
if node not in color:
stack = [(node, 1)]
while stack:
node, c = stack.pop()
color[node] = c
partition[c].append(node)
for neighbour in graph[node]:
if neighbour not in color:
stack.append((neighbour, -c))
elif color[neighbour] == color[node]:
return 'NU', [], []
return 'DA', sorted(partition[1]), sorted(partition[-1])

result, group1, group2 = is_bipartite()
with open('bipartit2out.txt', 'w') as fout:
fout.write(result + '\n')
if result == 'DA':
fout.write(' '.join(map(str, group1)) + '\n')
fout.write(' '.join(map(str, group2)) + '\n')
</syntaxhighlight>

4290 - Gaseste Ciclu

2024-01-03T23:39:33Z

Brianna Waltner: Pagină nouă: == Cerinţa == Gigel are un graf cu '''n''' noduri și '''m''' muchii, care nu este conex. El dorește să afle răspunsul la două întrebări: 1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex? 2) Dacă costul adăugării unei muchii între nodurile '''a''' și b este '''a + b''', care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex? == Date de intrare == Fișierul de intra...

== Cerinţa ==
Gigel are un graf cu '''n''' noduri și '''m''' muchii, care nu este conex. El dorește să afle răspunsul la două întrebări:

1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex?

2) Dacă costul adăugării unei muchii între nodurile '''a''' și b este '''a + b''', care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?
== Date de intrare ==
Fișierul de intrare '''unirein.txt''' conține pe prima linie numerele '''n''' și '''m''', pe a doua linie conține numărul '''c''', reprezentând numărul cerinței '''1 &les; c &les; 2''', iar pe următoarele '''m''' linii se află muchiile grafului '''a b''', '''1 &les; a, b &les; n''', '''a ≠ b'''.
== Date de ieșire ==
Fișierul de ieșire '''unireout.txt''' va conține pe prima linie numărul '''S''', reprezentând răspunsul cerut de Gigel.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100000, 0 &les; m &les; n-1'''
* Pentru teste în valoare de '''30''' de puncte, cerința va fi '''1'''.
* Pentru teste în valoare de '''40''' de puncte, '''1 &les; n &les; 1000'''.
== Exemplul 1 ==
;'''unirein.txt'''
6 3
1
1 2
3 4
5 6
;'''unireout.txt'''
Datele de intrare corespund restrictiilor impuse
2
== Exemplul 2 ==
;'''unirein.txt'''
100001 1
1
1 2
;'''unireout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
import heapq

def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):
xroot = find(parent, x)
yroot = find(parent, y)

if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1

def solve(n, c, edges):
parent = [i for i in range(n+1)]
rank = [0] * (n+1)

for a, b in edges:
union(parent, rank, a, b)

sets = [find(parent, i) for i in range(1, n+1)]
unique_sets = list(set(sets))

if c == 1:
return len(unique_sets) - 1
else:
costs = [i for i in unique_sets]
heapq.heapify(costs)
total_cost = 0

while len(costs) > 1:
cost1 = heapq.heappop(costs)
cost2 = heapq.heappop(costs)
total_cost += cost1 + cost2
heapq.heappush(costs, cost1 + cost2)

return total_cost

def main():
with open('unirein.txt', 'r') as f:
n, _ = map(int, f.readline().split())
c = int(f.readline())
edges = [list(map(int, line.split())) for line in f]

if not (1 <= n <= 100000):
print("Datele de intrare nu corespund restrictiilor impuse")
return

result = solve(n, c, edges)

with open('unireout.txt', 'w') as f:
f.write(str(result))

print("Datele de intrare corespund restrictiilor impuse")

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicaţie ==
Se vor uni nodurile '''1''' și '''3''', respectiv nodurile '''1'''și '''5''', s-au folosit '''2''' muchii, iar costul total va fi '''1 + 3 + 1 + 5 = 10'''.

0541 - Lant 1

2024-01-03T22:59:22Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă lista muchiilor unui graf neorientat și trei vârfuri '''p q r''' . Să se determine un lanț cu extremitățile '''p q''' care conține vârful '''r'''. == Date de intrare == Fişierul de intrare '''lant1in.txt''' conţine pe prima linie numerele '''n p q r''', reprezentând numărul de vârfuri ale grafului și cele trei vârfuri date. Fiecare dintre următoarele linii conține câte o pereche de numere '''i j''', cu semnificația că există muchie...

== Cerinţa ==
Se dă lista muchiilor unui graf neorientat și trei vârfuri '''p q r''' . Să se determine un lanț cu extremitățile '''p q''' care conține vârful '''r'''.
== Date de intrare ==
Fişierul de intrare '''lant1in.txt''' conţine pe prima linie numerele '''n p q r''', reprezentând numărul de vârfuri ale grafului și cele trei vârfuri date. Fiecare dintre următoarele linii conține câte o pereche de numere '''i j''', cu semnificația că există muchie între '''i''' și '''j'''.
== Date de ieșire ==
Fişierul de ieşire '''lant1out.txt''' va conţine pe prima linie numărul de vârfuri din lanțul determinat. A doua linie va conține vârfurile din acest lanț, separate prin exact un spațiu.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100'''
* '''1 &les; i , j &les; n'''
* în fișierul de intrare muchiile se pot repeta;
* orice lanț cu extremitățile '''p q''' care conține vârful '''r''' și are lungimea mai mică decât '''2*n''' este acceptat; lanțul nu trebuie să fie elementar
* pentru toate datele de test există cel puțin un lanț care respectă cerința;
== Exemplul 1 ==
;'''lant1in.txt'''
8 5 7 3
1 2
1 3
1 5
2 3
2 5
2 7
3 6
4 6
4 7
5 7
6 8
7 8
;'''lant1out.txt'''
Datele de intrare corespund restrictiilor impuse
5
5 1 3 2 7
== Exemplu 2 ==
;'''lant1in.txt'''
5 1 2 3
1 2
2 3
3 4
4 5
5 1
1 1000001
;'''lant1out.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict

def bfs(graf, start):
vizitat = [False] * (len(graf) + 1)
coada = [start]
vizitat[start] = True
parinte = [-1] * (len(graf) + 1)

while coada:
nod = coada.pop(0)
for vecin in graf[nod]:
if not vizitat[vecin]:
coada.append(vecin)
vizitat[vecin] = True
parinte[vecin] = nod

return parinte

def construieste_lant(parinte, start, end):
lant = []
nod = end
while nod != start:
lant.append(nod)
nod = parinte[nod]
lant.append(start)
return lant[::-1]

def main():
with open('lant1in.txt', 'r') as f:
n, p, q, r = map(int, f.readline().split())
graf = defaultdict(list)
muchii = []
for _ in range(n-1):
x, y = map(int, f.readline().split())
muchii.append((x, y))
graf[x-1].append(y-1)
graf[y-1].append(x-1)

m = len(muchii)
if 1 <= n <= 100000 and 0 <= m <= n*(n-1)//2:
print("Datele de intrare corespund restrictiilor impuse")
parinte = bfs(graf, p-1)
lant = construieste_lant(parinte, p-1, r-1)
parinte = bfs(graf, r-1)
lant += construieste_lant(parinte, r-1, q-1)[1:]
with open('lant1out.txt', 'w') as f:
f.write(str(len(lant)) + "\n")
f.write(' '.join(map(str, [i+1 for i in lant])) + "\n")
else:
print("Datele de intrare nu corespund restrictiilor impuse")

if __name__ == "__main__":
main()
</syntaxhighlight>

4204 - Este Arbore

2024-01-03T22:01:29Z

Brianna Waltner: Pagină nouă: == Cerinţa == Verificați dacă un graf este arbore sau nu. == Date de intrare == Fișierul de intrare '''estearborein.txt''' conține pe prima linie numărul de noduri '''n''', iar pe următoarele linii perechi de numere '''x y''', separate printr-un spațiu, cu semnificația că există muchie de la nodul '''x''' la nodul '''y'''. == Date de ieșire == Fișierul de ieșire '''estearboreout.txt''' va conține pe prima linie cuvântul '''DA''' dacă graful poate fi arbore, s...

== Cerinţa ==
Verificați dacă un graf este arbore sau nu.
== Date de intrare ==
Fișierul de intrare '''estearborein.txt''' conține pe prima linie numărul de noduri '''n''', iar pe următoarele linii perechi de numere '''x y''', separate printr-un spațiu, cu semnificația că există muchie de la nodul '''x''' la nodul '''y'''.
== Date de ieșire ==
Fișierul de ieșire '''estearboreout.txt''' va conține pe prima linie cuvântul '''DA''' dacă graful poate fi arbore, sau cuvântul '''NU''' dacă graful nu este arbore.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100'''
* '''1 &les; x, y &les; n'''
* muchiile se pot repeta
== Exemplul 1 ==
;'''estearborein.txt'''
5
1 3
2 4
3 1
3 5
4 2
4 5
;'''estearboreout.txt'''
Datele de intrare corespund restrictiilor impuse
DA
== Exemplul 1 ==
;'''estearborein.txt'''
5
1 2
2 3
3 4
4 105
5 1
;'''estearboreout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict

def este_arbore(numar_noduri, lista_muchii):
vizitat = [False] * (numar_noduri + 1)
graf = defaultdict(list)

for nod_x, nod_y in lista_muchii:
graf[nod_x].append(nod_y)
graf[nod_y].append(nod_x)

if este_ciclu(1, -1, graf, vizitat):
return False

for i in range(1, numar_noduri + 1):
if not vizitat[i]:
return False

return True

def este_ciclu(nod, parinte, graf, vizitat):
vizitat[nod] = True

for i in graf[nod]:
if not vizitat[i]:
if este_ciclu(i, nod, graf, vizitat):
return True
elif i != parinte:
return True

return False

def main():
with open('estearborein.txt', 'r') as f:
n = int(f.readline())
muchii = []
for _ in range(n):
x, y = map(int, f.readline().split())
muchii.append((x, y))

if 1 <= n <= 100 and all(1 <= x <= n and 1 <= y <= n for x, y in muchii):
print("Datele de intrare corespund restrictiilor impuse")
with open('estearboreout.txt', 'w') as f:
if este_arbore(n, muchii):
f.write("NU\n")
else:
f.write("DA\n")
else:
print("Datele de intrare nu corespund restrictiilor impuse")

if __name__ == "__main__":
main()
</syntaxhighlight>
== Explicatie ==
Graful poate fi arbore.

0756 - Nr Nod

2024-01-03T19:10:10Z

Brianna Waltner:

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine câte noduri din arbore au un singur descendent direct.
== Date de intrare ==
Fișierul de intrare '''nrnodin.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 '''nrnodout.txt''' va conține pe prima linie un singur număr '''C''', reprezentând numărul de noduri din arbore care au un singur descendent direct.
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
== Exemplul 1 ==
; '''nrnodin.txt'''
67 51 18 0 0 24 0 0 48 0 11 0 0
; '''nrnodout.txt'''
Datele de intrare corespund restrictiilor impuse
1
== Exemplul 2 ==
; '''nrnodin.txt'''
1000001 2 3 4 5 6 7 8 9 10
; '''nrnodout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def count_single_child_nodes(node):
if node is None:
return 0
count = count_single_child_nodes(node.left) + count_single_child_nodes(node.right)
if (node.left is not None and node.right is None) or (node.left is None and node.right is not None):
count += 1
return count

def main():
with open('nrnodin.txt', 'r') as fin:
values = map(int, fin.readline().split())
root = build_tree(iter(values))
count = count_single_child_nodes(root)
with open('nrnodout.txt', 'w') as fout:
fout.write(str(count))
if not all(1 <= value <= 1000000 for value in values if value != 0):
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")

if __name__ == "__main__":
main()
</syntaxhighlight>

0550 - Mere

2024-01-03T18:19:11Z

Brianna Waltner: Pagină nouă: == Cerinţa == Țăranul Ion are în livada sa '''N''' pomi, fiecare cu '''v[i]''' mere. Între pomi există N-1 cărări, astfel încât între oricare doi pomi să existe un singur drum, alcătuit eventual din mai multe cărări. Pentru că nu și-a plătit ratele la bancă, el este nevoit să vândă o parte dintre pomi. El vrea să adune merele din livadă, dar pentru că nu are foarte mult timp, el va aduna merele doar dintr-o parte din pomi. Ion pornește din pomul lui...

== Cerinţa ==
Țăranul Ion are în livada sa '''N''' pomi, fiecare cu '''v[i]''' mere. Între pomi există N-1 cărări, astfel încât între oricare doi pomi să existe un singur drum, alcătuit eventual din mai multe cărări. Pentru că nu și-a plătit ratele la bancă, el este nevoit să vândă o parte dintre pomi. El vrea să adune merele din livadă, dar pentru că nu are foarte mult timp, el va aduna merele doar dintr-o parte din pomi.

Ion pornește din pomul lui preferat, pomul '''1''', și se deplasează spre unul din vecinii lui. Pentru că nu este foarte inteligent, atunci când Ion se află la un pom, el se va deplasa către pomul vecin care are cele mai multe mere, fără să ia în calcul ceilalți meri din livadă. Dacă doi pomi au același număr de mere, atunci Ion se va deplasa spre pomul cu numărul de ordine mai mic.

Ajutați-l pe Ion să afle câte mere va aduna folosind metoda sa!
== Date de intrare ==
Pe prima linie a fișierului de intrare '''merein.txt''' se află un număr natural '''N''', reprezentând numărul de pomi din livadă; pe linia a doua se află '''N''' valori '''v[i]''', reprezentând numărul de mere din pomul '''i'''. Pe următoarele '''N-1''' linii se află câte o pereche de numere '''x y''', cu semnificația că există o cărare de la pomul '''x''' la pomul '''y'''.
== Date de ieșire ==
Fișierul de ieșire '''mereout.txt''' va conține pe prima linie numărul '''S''', reprezentând numărul total de mere culese.
== Restricţii şi precizări ==
* '''1 &les; n &les; 1000'''
* '''1 &les; v[i] &les; 10000'''
== Exemplul 1 ==
;'''merein.txt'''
6
3 1 2 3 2 1
1 2
1 3
2 4
2 5
2 6
;'''mereout.txt'''
Datele de intrare corespund restrictiilor impuse
5
== Exemplul 2 ==
;'''merein.txt'''
65000
3 1 2 3 2 1
1 2
1 3
2 4
2 5
2 6
;'''mereout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict

def dfs(node, parent):
global ans, maxv, idx, visit, g, apple
visit[node] = True
for neighbour in g[node]:
if neighbour != parent and not visit[neighbour]:
dfs(neighbour, node)
if apple[neighbour] > maxv[node]:
maxv[node] = apple[neighbour]
idx[node] = neighbour

def solve():
global ans, maxv, idx, visit, g, apple
dfs(1, 0)
node = 1
while node:
ans += apple[node]
node = idx[node]

if __name__ == "__main__":
g = defaultdict(list)
ans = 0

with open('merein.txt', 'r') as fin:
N = int(fin.readline().strip())
if N < 1 or N > 1000:
with open('mereout.txt', 'w') as fout:
fout.write("Datele de intrare nu corespund restrictiilor impuse")
exit(0)
apple = [0] + list(map(int, fin.readline().split()))
maxv = [0]*(N+1)
idx = [0]*(N+1)
visit = [False]*(N+1)

for _ in range(N-1):
u, v = map(int, fin.readline().split())
g[u].append(v)
g[v].append(u)

solve()

with open('mereout.txt', 'w') as fout:
fout.write(str(ans) if ans else "Datele de intrare corespund restrictiilor impuse")
</syntaxhighlight>

== Explicatie ==
Ion va culege merele din pomii '''1 3''', obținând '''3+2=5''' mere.

1707 - Retea

2024-01-03T17:24:57Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se consideră o rețea formată din '''n''' servere, numerotate de la '''1''' la '''n'''. În rețea există m perechi de servere '''x y''' cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere. Stabiliți pentru fiecare dintre cele '''n''' servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere r...

== Cerinţa ==
Se consideră o rețea formată din '''n''' servere, numerotate de la '''1''' la '''n'''. În rețea există m perechi de servere '''x y''' cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere.

Stabiliți pentru fiecare dintre cele '''n''' servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere rămase.
== Date de intrare ==
Fișierul de intrare '''reteain.txt''' conține pe prima linie numerele '''n''' si '''m'''. Pe următoarele '''m''' linii se vor afla câte două numere naturale '''x y''', reprezentând perechi de servere între care există legături directe.
== Date de ieșire ==
Fișierul de ieșire '''reteaout.txt''' va conține pe prima linie '''n''' numere naturale '''0''' sau '''1''':
* al '''i'''-lea număr va fi '''0''' dacă prin eliminarea serverului cu numărul i rămân legături între oricare două servere rămase
* al '''i'''-lea număr va fi '''1''' dacă prin eliminarea sa se pierde legătura între cel puțin două servere rămase.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100'''
* '''1 &les; x,y &les; n'''
== Exemplul 1 ==
;'''reteain.txt'''
5 5
1 2
2 3
1 3
3 4
4 5
;'''reteaout.txt'''
Datele de intrare corespund restrictiilor impuse
0 0 1 1 0
== Exemplul 2 ==
;'''reteain.txt'''
101 1
1 2
;'''reteaout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict

def dfs(v, visited, graph):
visited[v] = True
for u in graph[v]:
if not visited[u]:
dfs(u, visited, graph)

def main():
with open('reteain.txt', 'r') as fin:
n, m = map(int, fin.readline().split())
edges = [list(map(int, fin.readline().split())) for _ in range(m)]
if not (1 <= n <= 100) or not all(1 <= x <= n and 1 <= y <= n for x, y in edges):
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")
graph = defaultdict(list)
for x, y in edges:
graph[x].append(y)
graph[y].append(x)
result = []
for i in range(1, n+1):
visited = [False] * (n+1)
visited[i] = True
dfs((i % n) + 1, visited, graph)
result.append('0' if all(visited[1:n+1]) else '1')
with open('reteaout.txt', 'w') as fout:
fout.write(' '.join(result))

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicaţie ==
Serverul '''1''' daca este eliminat nu întrerupe legătura deoarece exista lanțul de legături '''2 - 3 - 4 - 5''' pe care nu îl afectează.
Serverul '''2''' dacă este eliminat nu întrerupe legătura deoarece exista lanțul de legături '''1 - 3 - 4 - 5''' pe care nu îl afectează.
Serverul '''3''' dacă este eliminat, serverele '''1''' și '''2''' nu mai pot comunica cu serverele '''4''' și '''5'''.
Serverul '''4''' daca este eliminat, serverele '''1''', '''2''' și '''3''' nu mai pot comunica cu serverul '''5'''.
Serverul '''5''' dacă este eliminat nu întrerupe legătura deoarece serverele '''1''', '''2''', '''3''', '''4''' sunt legate intre ele.

0760 - k Nivel 1

2024-01-03T16:11:08Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se consideră un arbore binar în care nodurile memorează numere naturale nenule și un număr '''k'''. În arbore rădăcina se află pe nivelul '''0''', fii rădăcinii pe nivelul '''1''', fii fiilor rădăcinii pe nivelul '''2''', etc. Să se determine suma valorilor din nodurile aflate pe nivelul '''k'''. == Date de intrare == Fișierul de intrare '''knivel1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urm...

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule și un număr '''k'''. În arbore rădăcina se află pe nivelul '''0''', fii rădăcinii pe nivelul '''1''', fii fiilor rădăcinii pe nivelul '''2''', etc. Să se determine suma valorilor din nodurile aflate pe nivelul '''k'''.
== Date de intrare ==
Fișierul de intrare '''knivel1in.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'''.

Linia a doua a fișierului conține numărul '''k'''.
== Date de ieșire ==
Fișierul de ieșire '''knivel1out.txt''' va conține pe prima linie un singur număr '''S''', reprezentând suma cerută
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
== Exemplul 1 ==
; '''knivel1in.txt'''
67 51 18 0 0 24 0 0 48 0 11 0 0
1
;'''knivel1out.txt'''
Datele de intrare corespund restrictiilor impuse
99
== Exemplul 2 ==
; '''knivel1in.txt'''
1 0 0
1
; '''knivel1out.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def sum_at_level(node, k):
if node is None:
return 0
if k == 0:
return node.value
return sum_at_level(node.left, k-1) + sum_at_level(node.right, k-1)

def main():
with open('knivel1in.txt', 'r') as fin:
values = list(map(int, fin.readline().split()))
k = int(fin.readline())
root = build_tree(iter(values))
if root is None or root.left is None or root.right is None:
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")
s = sum_at_level(root, k)
with open('knivel1out.txt', 'w') as fout:
fout.write(str(s))

if __name__ == "__main__":
main()
</syntaxhighlight>

0761 - Inaltime 1

2024-01-03T16:03:25Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine înălțimea arborelui. Înălțimea unui arbore este egală cu numărul de noduri de pe cel mai lung lanț elementar care unește rădăcina cu un nod terminal. == Date de intrare == Fișierul de intrare '''inaltime1in.txt''' conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stân...

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine înălțimea arborelui.

Înălțimea unui arbore este egală cu numărul de noduri de pe cel mai lung lanț elementar care unește rădăcina cu un nod terminal.
== Date de intrare ==
Fișierul de intrare '''inaltime1in.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 '''inaltime1out.txt''' va conține pe prima linie o valoare '''H''', reprezentând înălțimea arborelui.
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
== Exemplul 1 ==
; '''inaltime1in.txt'''
67 51 18 0 0 24 0 0 48 0 11 0 0
; '''inaltime1out.txt'''
Datele de intrare corespund restrictiilor impuse
3
== Exemplul 2 ==
; '''inaltime1in.txt'''
1 0 0
; '''inaltime1out.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def height(node):
if node is None:
return 0
return max(height(node.left), height(node.right)) + 1

def main():
with open('inaltime1in.txt', 'r') as fin:
values = list(map(int, fin.readline().split()))
root = build_tree(iter(values))
if root is None or root.left is None or root.right is None:
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")
h = height(root)
with open('inaltime1out.txt', 'w') as fout:
fout.write(str(h))

if __name__ == "__main__":
main()
</syntaxhighlight>

0759 - Bi Latime

2024-01-03T15:57:37Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile din arbore în urma parcurgerii în lățime, pornind din rădăcină. == Date de intrare == Fișierul de intrare '''bilatimein.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''...

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile din arbore în urma parcurgerii în lățime, pornind din rădăcină.
== Date de intrare ==
Fișierul de intrare '''bilatimein.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 '''bilatimeout.txt''' va conține pe prima linie valorile din arbore în urma parcurgerii în lățime, pornind din rădăcină, separate prin câte un spațiu.
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
* la parcurgerea în lățime, după vizitarea unui nod, se va vizita fiul stâng, apoi fiul drept.
== Exemplul 1 ==
; '''bilatimein.txt'''
67 51 18 0 0 24 0 0 48 0 11 0 0
; '''bilatimeout.txt'''
Datele de intrare corespund restrictiilor impuse
67 51 48 18 24 11
== Exemplul 2 ==
; '''bilatimein.txt'''
1 0 0
; '''bilatimeout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def breadth_first_search(root):
queue = [root]
values = []
while queue:
node = queue.pop(0)
if node is not None:
values.append(node.value)
queue.append(node.left)
queue.append(node.right)
return values

def main():
with open('bilatimein.txt', 'r') as fin:
values = list(map(int, fin.readline().split()))
root = build_tree(iter(values))
if root is None or root.left is None or root.right is None:
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")
bfs_values = breadth_first_search(root)
with open('bilatimeout.txt', 'w') as fout:
fout.write(' '.join(map(str, bfs_values)))

if __name__ == "__main__":
main()
</syntaxhighlight>

0758 - Bi Min Prim

2024-01-03T15:49:19Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine cele mai mici valori număr prim din subarborii stâng și drept ai rădăcinii. == Date de intrare == Fișierul de intrare '''biminprimin.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 '''...

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine cele mai mici valori număr prim din subarborii stâng și drept ai rădăcinii.
== Date de intrare ==
Fișierul de intrare '''biminprimin.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 '''biminprimout.txt''' va conține pe prima linie două valori '''X''' '''Y''', reprezentând cea mai mică valoare număr prim din subarborele stâng, respectiv cea mai mică valoare număr prim din subarborele drept. Dacă unul dintre subarbori nu conține numere prime, se va afișa '''-1'''.
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
* se garantează că rădăcina are doi descendenți direcți
== Exemplul 1 ==
; '''biminprimin.txt'''
67 53 17 0 0 24 0 0 48 0 12 0 0
; '''biminprimout.txt'''
Datele de intrare corespund restrictiilor impuse
17 -1
== Exemplul 2 ==
; '''biminprimin.txt'''
1 0 0
; '''biminprimout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True

def find_min_prime(node):
if node is None:
return float('inf')
left = find_min_prime(node.left)
right = find_min_prime(node.right)
current = node.value if is_prime(node.value) else float('inf')
return min(left, right, current)

def main():
with open('biminprimin.txt', 'r') as fin:
values = list(map(int, fin.readline().split()))
root = build_tree(iter(values))
if root is None or root.left is None or root.right is None:
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")
left_min_prime = find_min_prime(root.left)
right_min_prime = find_min_prime(root.right)
left_min_prime = -1 if left_min_prime == float('inf') else left_min_prime
right_min_prime = -1 if right_min_prime == float('inf') else right_min_prime
with open('biminprimout.txt', 'w') as fout:
fout.write(f"{left_min_prime} {right_min_prime}")

if __name__ == "__main__":
main()
</syntaxhighlight>

0757 - Bi Max

2024-01-03T15:37:16Z

Brianna Waltner:

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine valorile maxime din subarborii stâng și drept ai rădăcinii.
== Date de intrare ==
Fișierul de intrare '''bimaxin.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 '''bimaxout.txt''' va conține pe prima linie două valori '''X''' '''Y''', reprezentând valoarea maximă din subarborele stâng, respectiv valoarea maximă din subarborele drept.
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
* se garantează că rădăcina are doi descendenți direcți
== Exemplul 1 ==
'''bimaxin.txt'''
67 51 18 0 0 24 0 0 48 0 11 0 0
'''bimaxout.txt'''
Datele de intrare corespund restrictiilor impuse
51 48
== Exemplul 2 ==
'''bimaxin.txt'''
1 0 0
'''bimaxout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def find_max(node):
if node is None:
return 0
return max(node.value, find_max(node.left), find_max(node.right))

def main():
with open('bimaxin.txt', 'r') as fin:
values = list(map(int, fin.readline().split()))
root = build_tree(iter(values))
if root is None or root.left is None or root.right is None:
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")
left_max = find_max(root.left)
right_max = find_max(root.right)
with open('bimaxout.txt', 'w') as fout:
fout.write(f"{left_max} {right_max}")

if __name__ == "__main__":
main()
</syntaxhighlight>

0756 - Nr Nod

2024-01-03T15:36:10Z

Brianna Waltner:

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine câte noduri din arbore au un singur descendent direct.
== Date de intrare ==
Fișierul de intrare '''nrnodin.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 '''nrnodout.txt''' va conține pe prima linie un singur număr '''C''', reprezentând numărul de noduri din arbore care au un singur descendent direct.
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
== Exemplul 1 ==
; '''nrnodin.txt'''
67 51 18 0 0 24 0 0 48 0 11 0 0
; '''nrnodout.txt'''
Datele de intrare corespund restrictiilor impuse
1
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def count_single_child_nodes(node):
if node is None:
return 0
count = count_single_child_nodes(node.left) + count_single_child_nodes(node.right)
if (node.left is not None and node.right is None) or (node.left is None and node.right is not None):
count += 1
return count

def main():
with open('nrnodin.txt', 'r') as fin:
values = map(int, fin.readline().split())
root = build_tree(iter(values))
count = count_single_child_nodes(root)
with open('nrnodout.txt', 'w') as fout:
fout.write(str(count))
if not all(1 <= value <= 1000000 for value in values if value != 0):
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")

if __name__ == "__main__":
main()
</syntaxhighlight>

0757 - Bi Max

2024-01-03T15:35:00Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine valorile maxime din subarborii stâng și drept ai rădăcinii. == Date de intrare == Fișierul de intrare '''bimaxin.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...

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine valorile maxime din subarborii stâng și drept ai rădăcinii.
== Date de intrare ==
Fișierul de intrare '''bimaxin.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 '''bimaxout.txt''' va conține pe prima linie două valori '''X''' '''Y''', reprezentând valoarea maximă din subarborele stâng, respectiv valoarea maximă din subarborele drept.
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
* se garantează că rădăcina are doi descendenți direcți
== Exemplul 1 ==
'''bimaxin.txt'''
Datele de intrare corespund restrictiilor impuse
67 51 18 0 0 24 0 0 48 0 11 0 0
'''bimaxout.txt'''
51 48
== Exemplul 2 ==
'''bimaxin.txt'''
1 0 0
'''bimaxout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def find_max(node):
if node is None:
return 0
return max(node.value, find_max(node.left), find_max(node.right))

def main():
with open('bimaxin.txt', 'r') as fin:
values = list(map(int, fin.readline().split()))
root = build_tree(iter(values))
if root is None or root.left is None or root.right is None:
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")
left_max = find_max(root.left)
right_max = find_max(root.right)
with open('bimaxout.txt', 'w') as fout:
fout.write(f"{left_max} {right_max}")

if __name__ == "__main__":
main()
</syntaxhighlight>

0756 - Nr Nod

2024-01-03T15:25:50Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine câte noduri din arbore au un singur descendent direct. == Date de intrare == Fișierul de intrare '''nrnodin.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 d...

== Cerinţa ==
Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine câte noduri din arbore au un singur descendent direct.
== Date de intrare ==
Fișierul de intrare '''nrnodin.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 '''nrnodout.txt''' va conține pe prima linie un singur număr '''C''', reprezentând numărul de noduri din arbore care au un singur descendent direct.
== Restricţii şi precizări ==
* se recomandă folosirea arborilor alocați dinamic.
== Exemplul 1 ==
; '''nrnodin.txt'''
67 51 18 0 0 24 0 0 48 0 11 0 0
; '''nrnodout.txt'''
1
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def build_tree(values):
value = next(values)
if value == 0:
return None
node = Node(value)
node.left = build_tree(values)
node.right = build_tree(values)
return node

def count_single_child_nodes(node):
if node is None:
return 0
count = count_single_child_nodes(node.left) + count_single_child_nodes(node.right)
if (node.left is not None and node.right is None) or (node.left is None and node.right is not None):
count += 1
return count

def main():
with open('nrnodin.txt', 'r') as fin:
values = map(int, fin.readline().split())
root = build_tree(iter(values))
count = count_single_child_nodes(root)
with open('nrnodout.txt', 'w') as fout:
fout.write(str(count))
if not all(1 <= value <= 1000000 for value in values if value != 0):
print("Datele de intrare nu corespund restrictiilor impuse")
return
print("Datele de intrare corespund restrictiilor impuse")

if __name__ == "__main__":
main()
</syntaxhighlight>

2198 – Elimin Prime

2024-01-03T15:01:02Z

Brianna Waltner:

Se consideră un șir de n numere întregi, cu n număr natural nenul. Se elimină primul element din șir și toate elementele șirului aflate pe poziții care reprezintă numere prime, în ordinea crescătoare a pozițiilor. Operația de eliminare se repetă cu elementele rămase în șir, repoziționate după eliminarea celorlalte, până când este eliminat și ultimul element rămas.
== Cerinţa ==
Să se scrie un program care afișează elementele șirului inițial, în ordinea în care au fost eliminate conform algoritmului descris mai sus.
== Date de intrare ==
Fișierul de intrare '''elimin_primein.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere întregi separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''elimin_primeout.txt''' va conține pe prima linie, separate prin spațiu, numerele din fișierul de intrare în ordinea eliminării acestora.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* numerele de pe a doua linie a fișierului de intrare sun cuprinse în intervalul '''[-1.000.000.000, 1.000.000.000]'''
* elementele șirului sunt indexate de la '''1''' la '''n'''.

== Exemplul 1 ==
; elimin_primein.txt
10
1 2 3 4 5 6 7 8 9 10
; elimin_primeout.txt
Datele de intrare corespund restrictiilor impuse
1 2 3 5 7 4 6 8 10 9

== Exemplu 2 ==
; elimin_primein.txt
100001
1 2 3 4 5 6 7 8 9 10 ... 1000001
; elimin_primeout.txt
Datele de intrare nu corespund restrictiilor impuse

== Atentie! ==
Programele vor folosi doar instrucțiunile de bază ale limbajului de programare ales, inclusiv cele de intrare/ieșire, dar nu și alte funcții din biblioteci specializate ('''algorithm''', '''string''',…).

== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open('elimin_primein.txt', 'r') as fin, open('elimin_primeout.txt', 'w') as fout:
n = int(fin.readline().strip())
if n < 1 or n > 100000:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
numbers = list(map(int, fin.readline().strip().split()))
if any(x < -1000000000 or x > 1000000000 for x in numbers):
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
fout.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == "__main__":
main()
</syntaxhighlight>

2198 – Elimin Prime

2024-01-03T15:00:31Z

Brianna Waltner:

Se consideră un șir de n numere întregi, cu n număr natural nenul. Se elimină primul element din șir și toate elementele șirului aflate pe poziții care reprezintă numere prime, în ordinea crescătoare a pozițiilor. Operația de eliminare se repetă cu elementele rămase în șir, repoziționate după eliminarea celorlalte, până când este eliminat și ultimul element rămas.
== Cerinţa ==
Să se scrie un program care afișează elementele șirului inițial, în ordinea în care au fost eliminate conform algoritmului descris mai sus.
== Date de intrare ==
Fișierul de intrare '''elimin_primein.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere întregi separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''elimin_primeout.txt''' va conține pe prima linie, separate prin spațiu, numerele din fișierul de intrare în ordinea eliminării acestora.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* numerele de pe a doua linie a fișierului de intrare sun cuprinse în intervalul '''[-1.000.000.000, 1.000.000.000]'''
* elementele șirului sunt indexate de la '''1''' la '''n'''.

== Exemplul 1 ==
; elimin_primein.txt
10
1 2 3 4 5 6 7 8 9 10
; elimin_primeout.txt
Datele de intrare corespund restrictiilor impuse
1 2 3 5 7 4 6 8 10 9

== Exemplu 2 ==
; elimin_primein.txt
100001
1 2 3 4 5 6 7 8 9 10 ... 1000001
; elimin_primeout.txt
Datele de intrare nu corespund restrictiilor impuse

== Atentie! ==
Programele vor folosi doar instrucțiunile de bază ale limbajului de programare ales, inclusiv cele de intrare/ieșire, dar nu și alte funcții din biblioteci specializate ('''algorithm''', '''string''',…).

== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open('elimin_primein.txt', 'r') as fin, open('elimin_primeout.txt', 'w') as fout:
n = int(fin.readline().strip())
if n < 1 or n > 100000:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
numbers = list(map(int, fin.readline().strip().split()))
if any(x < -1000000000 or x > 1000000000 for x in numbers):
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
fout.write("Datele de intrare corespund restrictiilor impuse\n")
# TODO: Implement the algorithm to eliminate the numbers
# and write the eliminated numbers to fout

if __name__ == "__main__":
main()
</syntaxhighlight>

2847 – List

2024-01-03T14:54:52Z

Brianna Waltner:

== Cerinţa ==
Se dă o listă simplu înlănțuită care conține '''n''' perechi de numere naturale '''(a,b)'''. Fiecare pereche este stocată în câte un nod al listei; notăm cu '''a''' primul număr stocat într-un nod și cu '''b''' al doilea număr stocat în acel nod.

Se cere să se insereze în listă astfel:

Dacă pentru nodul curent:

* '''a''' este par și '''b''' este impar se inserează după nodul curent un nou nod, care conține dublul sumei lor pe prima poziție a nodului inserat iar pe a doua poziție diferența dintre dublul sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este par se inserează înaintea nodului curent un nou nod, care conține dublul sumei lor pe a doua poziție a nodului inserat și pe prima poziție diferența dintre dublul sumei numerelor din nodul curent și a primului număr din nodul curent;
* '''a''' este par, '''b''' este par se inserează după nodul curent un nou nod, care conține jumătatea sumei lor pe prima poziție a nodului inserat iar pe a doua poziție suma dintre jumătatea sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este impar se inserează înaintea nodului curent un nou nod, care conține jumătatea sumei lor pe a doua poziție a nodului inserat și pe prima poziție suma dintre jumătatea sumei numerelor din nodul curent și a primului număr din nodul curent.
== Date de intrare ==
Fișierul de intrare '''listin.txt''' conține pe prima linie numărul '''n''', iar pe următoarele '''n''' linii '''n''' perechi de numere naturale separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''listout.txt''' va conține pe câte o linie numerele fiecărui nod al listei separate prin spații, după realizarea inserărilor.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* '''1 &les; a &les; b &les; 100'''
* se recomandă utilizarea unei liste alocate dinamic
== Exemplul 1 ==
; listin.txt
5
1 2
2 4
1 1
2 6
7 4
; listout.txt
Datele de intrare corespund restrictiilor impuse
5 6
1 2
2 4
3 7
2 1
1 1
2 6
4 10
15 22
7 4
== Exemplul 2 ==
; listin.txt
100001
1 2
2 3
3 4
...
100000 100001
; listout.txt
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, a, b, next_node=None):
self.a = a
self.b = b
self.next_node = next_node

def insert_after(node, a, b):
new_node = Node(a, b, node.next_node)
node.next_node = new_node

def insert_before(head, prev_node, node, a, b):
new_node = Node(a, b, node)
if prev_node is None:
return new_node
else:
prev_node.next_node = new_node
return head

def main():
with open('listin.txt', 'r') as fin, open('listout.txt', 'w') as fout:
n = int(fin.readline().strip())
if n < 1 or n > 100000:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
a, b = map(int, fin.readline().strip().split())
if a < 1 or a > 100 or b < 1 or b > 100:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
head = Node(a, b)
node = head
for _ in range(n-1):
a, b = map(int, fin.readline().strip().split())
if a < 1 or a > 100 or b < 1 or b > 100:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
node.next_node = Node(a, b)
node = node.next_node
fout.write("Datele de intrare corespund restrictiilor impuse\n")
prev = None
node = head
while node is not None:
if node.a % 2 == 0 and node.b % 2 == 1:
insert_after(node, 2*(node.a+node.b), 2*(node.a+node.b)-node.b)
elif node.a % 2 == 1 and node.b % 2 == 0:
head = insert_before(head, prev, node, 2*(node.a+node.b)-node.a, 2*(node.a+node.b))
elif node.a % 2 == 0 and node.b % 2 == 0:
insert_after(node, (node.a+node.b)//2, (node.a+node.b)//2+node.b)
elif node.a % 2 == 1 and node.b % 2 == 1:
head = insert_before(head, prev, node, (node.a+node.b)//2+node.a, (node.a+node.b)//2)
prev = node
node = node.next_node
node = head
while node is not None:
fout.write(str(node.a) + ' ' + str(node.b) + '\n')
node = node.next_node

if __name__ == "__main__":
main()
</syntaxhighlight>

0676 - Count Prim Sub

2024-01-03T14:00:57Z

Brianna Waltner: 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. Se dau '''k''' noduri din arbore și se cere determinarea, pentru fiecare nod, a numărului de noduri din subarborele cu rădăcina în acel nod care conțin valori prime. == Date de intrare == Fișierul de intrare '''countprimsubin.txt''' conține pe prima linie numărul '''n'''. Fiecare dintre următoarele '''n''' l...

== 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. Se dau '''k''' noduri din arbore și se cere determinarea, pentru fiecare nod, a numărului de noduri din subarborele cu rădăcina în acel nod care conțin valori prime.
== Date de intrare ==
Fișierul de intrare '''countprimsubin.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.

Pe următoarea linie se află numărul '''k''', iar pe fiecare dintre următoarele'''k''' linii se află câte un număr natural cuprins între '''1''' și '''n''', reprezentând nodul curent.
== Date de ieșire ==
Fișierul de ieșire '''countprimsubout.txt''' va conține '''k''' linii; fiecare linie va conține numărul de noduri din subarborele cu rădăcina în nodul corespunzător.
== Restricţii şi precizări ==
* '''1 ≤ n ≤ 1000'''
* valorile din nodurile arborelui vor fi mai mici sau egale cu '''1.000.000'''
* '''1 ≤ k ≤ 1000'''
== Exemplul 1 ==
; '''countprimsubin.txt'''
6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
4
1
2
4
2
; '''countprimsubout.txt'''
Datele de intrare corespund restrictiilor impuse
1
0
2
0
== Exemplul 2 ==
; '''countprimsubin.txt'''
1002
2 0 0
3 0 0
5 0 0
7 0 0
1000001 0 0
2
1
5
; '''countprimsubout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
tree = []
prime_count = []

def is_prime(n):
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
w = 2
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True

def dfs(node):
global tree, prime_count
prime_count[node] = is_prime(tree[node][0])
if tree[node][1] != 0:
prime_count[node] += dfs(tree[node][1])
if tree[node][2] != 0:
prime_count[node] += dfs(tree[node][2])
return prime_count[node]

def main():
global tree, prime_count
with open('countprimsubin.txt', 'r') as fin, open('countprimsubout.txt', 'w') as fout:
n = int(fin.readline().strip())
tree = [[0, 0, 0] for _ in range(n+1)]
prime_count = [0 for _ in range(n+1)]
for i in range(1, n+1):
x, st, dr = map(int, fin.readline().strip().split())
tree[i] = [x, st, dr]
k = int(fin.readline().strip())
nodes = [int(fin.readline().strip()) for _ in range(k)]
if n < 1 or n > 1000 or any(x < 1 or x > 1000000 for x, _, _ in tree[1:]) or k < 1 or k > 1000:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
fout.write("Datele de intrare corespund restrictiilor impuse\n")
for node in nodes:
fout.write(str(dfs(node)) + '\n')

if __name__ == "__main__":
main()
</syntaxhighlight>

1163 - CowboysAndAliens

2024-01-03T12:59:28Z

Brianna Waltner:

== Cerinţa ==
Cei '''m''' cowboys și cei '''n''' aliens s-au întâlnit în vestul sălbatic și, păstrând tradiția locului, s-au așezat în șir indian. Cum cowboys erau gazde primitoare și în special foarte precaute, s-au gândit că între doi cowboys consecutivi ar fi bine să fie cel mult un alien (din motive de securitate). De asemenea primul și ultimul din șir să fie cawboys. Dilema care s-a ivit a fost numărul de moduri în care s-ar putea așeza în șir indian ținând cont de condițiile de securitate impuse.
== Date de intrare ==
Fișierul de intrare '''cowboysandaliensin.txt''' conține pe prima linie numerele naturale '''m''' și '''n'''.
== Date de ieșire ==
Fișierul de ieșire '''cowboysandaliensout.txt''' va conține pe prima linie numărul '''S''', reprezentând numărul de moduri modulo '''555557''', în care s-ar putea așeza în șir indian.
== Restricţii şi precizări ==
* '''1 &les; n &les; m &les; 500.000
* reprezentările în baza '''10''' ale lui '''x''', '''y''' şi suma lor nu depăşesc '''2 000 000 000'''

== Exemplul 1 ==
; '''cowboysandaliensin.txt'''
3 1
; '''cowboysandaliensout.txt'''
Datele de intrare corespund restrictiilor impuse
12

== Exemplu 2 ==
; '''cowboysandaliensin.txt'''
2 2
; '''cowboysandaliensout.txt'''
Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
MOD = 555557

def main():
with open('cowboysandaliensin.txt', 'r') as fin, open('cowboysandaliensout.txt', 'w') as fout:
m, n = map(int, fin.readline().strip().split())
if n > m or m > 2 * n + 2:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
dp[0][0] = 1
for i in range(1, m+1):
dp[i][0] = 1
for j in range(1, min(i, n)+1):
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD
if j < i:
dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD
fout.write("Datele de intrare corespund restrictiilor impuse\n")
fout.write(str(dp[m][n]) + '\n')

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
Dacă cei trei cawboys ar fi Jake, Percy și Roy pe care-i vom nota J, P, R iar alien ar fi Bronc, notat B, atunci ei s-ar putea așeza în șir indian în următoarele moduri: '''JBPR''' , '''JPBR''' , '''JBRP''' , '''JRBP''' , '''PBJR''' , '''PJBR''' , '''PBRJ''' , '''PRBJ''' , '''RBPJ''' , '''RPBJ''' , '''RBJP''' , '''RJBP'''. În total avem 12 moduri.

1003 - Baze1

2024-01-03T12:34:56Z

Brianna Waltner:

== Cerinţa ==
Se dau două numere '''b1 b2''', reprezentând două baze de numeraţie şi două şiruri de cifre '''x y''', reprezentând două numere: '''x''' în baza '''b1''', '''y''' în baza '''b2'''. Determinaţi suma numerelor '''x''' şi '''y''' în baza '''10'''.
== Date de intrare ==
Fișierul de intrare '''baze1in.txt''' conține pe prima linie numerele '''b1 b2''', iar pe a doua linie cele două şiruri de cifre cu semnificaţia de mai sus.
== Date de ieșire ==
Fișierul de ieșire '''baze1out.txt''' va conține pe prima linie numărul '''S''', reprezentând suma dintre '''x''' şi '''y'''.
== Restricţii şi precizări ==
* '''2 &les; b1,b2 &les; 10'''
* reprezentările în baza '''10''' ale lui '''x''', '''y''' şi suma lor nu depăşesc '''2 000 000 000'''

== Exemplul 1 ==
; baze1in.txt
2 5
110 213
; baze1out.txt
Datele de intrare corespund restrictiilor impuse
64

== Exemplu 2 ==
; baze1in.txt
2 5
110 213333333333333333333
; baze1out.txt
Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open('baze1in.txt', 'r') as fin, open('baze1out.txt', 'w') as fout:
b1, b2 = map(int, fin.readline().strip().split())
x, y = fin.readline().strip().split()

if any(len(numar) > 10 for numar in [x, y]):
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return

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

x_10 = int(x, b1)
y_10 = int(y, b2)

suma_10 = x_10 + y_10

fout.write(str(suma_10) + '\n')

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
'''110(2) = 6'''
'''213(5) = 58'''
'''6 + 58 = 64'''

1003 - Baze1

2024-01-02T22:24:38Z

Brianna Waltner:

== Cerinţa ==
Se dau două numere '''b1 b2''', reprezentând două baze de numeraţie şi două şiruri de cifre '''x y''', reprezentând două numere: '''x''' în baza '''b1''', '''y''' în baza '''b2'''. Determinaţi suma numerelor '''x''' şi '''y''' în baza '''10'''.
== Date de intrare ==
Fișierul de intrare '''baze1in.txt''' conține pe prima linie numerele '''b1 b2''', iar pe a doua linie cele două şiruri de cifre cu semnificaţia de mai sus.
== Date de ieșire ==
Fișierul de ieșire '''baze1out.txt''' va conține pe prima linie numărul '''S''', reprezentând suma dintre '''x''' şi '''y'''.
== Restricţii şi precizări ==
* '''2 &les; b1,b2 &les; 10'''
* reprezentările în baza '''10''' ale lui '''x''', '''y''' şi suma lor nu depăşesc '''2 000 000 000'''

== Exemplul 1 ==
; baze1in.txt
2 5
110 213
; baze1out.txt
Datele de intrare corespund restrictiilor impuse
64

== Exemplu 2 ==
; baze1in.txt
2 5
110 213333333333333333333
; baze1out.txt
Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open('baze1in.txt', 'r') as fin, open('baze1out.txt', 'w') as fout:
# Citirea bazelor și a numerelor din fișierul de intrare
b1, b2 = map(int, fin.readline().strip().split())
x, y = fin.readline().strip().split()

if any(len(numar) > 10 for numar in [x, y]):
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return

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

x_10 = int(x, b1)
y_10 = int(y, b2)

suma_10 = x_10 + y_10

fout.write(str(suma_10) + '\n')

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
'''110(2) = 6'''
'''213(5) = 58'''
'''6 + 58 = 64'''

1003 - Baze1

2024-01-02T22:23:45Z

Brianna Waltner:

== Cerinţa ==
Se dau două numere '''b1 b2''', reprezentând două baze de numeraţie şi două şiruri de cifre '''x y''', reprezentând două numere: '''x''' în baza '''b1''', '''y''' în baza '''b2'''. Determinaţi suma numerelor '''x''' şi '''y''' în baza '''10'''.
== Date de intrare ==
Fișierul de intrare '''baze1in.txt''' conține pe prima linie numerele '''b1 b2''', iar pe a doua linie cele două şiruri de cifre cu semnificaţia de mai sus.
== Date de ieșire ==
Fișierul de ieșire '''baze1out.txt''' va conține pe prima linie numărul '''S''', reprezentând suma dintre '''x''' şi '''y'''.
== Restricţii şi precizări ==
* '''2 &les; b1,b2 &les; 10'''
* reprezentările în baza '''10''' ale lui '''x''', '''y''' şi suma lor nu depăşesc '''2 000 000 000'''

== Exemplul 1 ==
; baze1in.txt
2 5
110 213
; baze1out.txt
Datele de intrare corespund restrictiilor impuse
64

== Exemplu 2 ==
; baze1in.txt
2 5
110 213333333333333333333
; baze1out.txt
Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open('baze1in.txt', 'r') as fin, open('baze1out.txt', 'w') as fout:
# Citirea bazelor și a numerelor din fișierul de intrare
b1, b2 = map(int, fin.readline().strip().split())
x, y = fin.readline().strip().split()

if any(len(numar) > 10 for numar in [x, y]):
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return

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

x_10 = int(x, b1)
y_10 = int(y, b2)

suma_10 = x_10 + y_10

fout.write(str(suma_10) + '\n')

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
'''110(2) = 6'''
'''213(5) = 58'''
'''6 + 58 = 64'''

1016 - imparpar

2024-01-02T22:23:04Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă '''n''' un număr natural. Să se afle în câte moduri putem aranja numerele de la '''1''' la '''n''' astfel încât numerele pare să fie situate pe poziții impare iar cele impare pe poziții pare ? == Date de intrare == Programul citește de la tastatură numărul natural '''n'''. == Date de ieșire == Programul va afișa pe ecran numărul de moduri în care putem aranja numerele de la '''1''' la '''n''' astfel încât numerele pare să fie situate p...

== Cerinţa ==
Se dă '''n''' un număr natural. Să se afle în câte moduri putem aranja numerele de la '''1''' la '''n''' astfel încât numerele pare să fie situate pe poziții impare iar cele impare pe poziții pare ?
== Date de intrare ==
Programul citește de la tastatură numărul natural '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran numărul de moduri în care putem aranja numerele de la '''1''' la '''n''' astfel încât numerele pare să fie situate pe poziții impare iar cele impare pe poziții pare.
== Restricţii şi precizări ==
* '''1 &les; n &les; 20'''
== Exemplul 1 ==
; Intrare
4
; Iesire
Datele de intrare corespund restrictiilor impuse
4

== Exemplu 2 ==
; Intrare
25
; Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from math import factorial

def compute_arrangements(n):
even_positions = n // 2
odd_positions = n - even_positions

even_numbers = n // 2
odd_numbers = n - even_numbers

if even_positions < even_numbers or odd_positions < odd_numbers:
return 0
else:
return factorial(even_positions) * factorial(odd_positions)

def main():
n = int(input())

if n > 20:
print("Datele de intrare nu corespund restrictiilor impuse")
return

arrangements = compute_arrangements(n)
print("Datele de intrare corespund restrictiilor impuse")
print(arrangements)

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
Numerele de la '''1''' la '''4''' se pot aranja astfel : '''(2,1,4,3)''', '''(2,3,4,1)''', '''(4,1,2,3)''', '''(4,3,2,1)''' astfel încât numerele pare sunt pe poziții impare și numerele impare sunt pe poziții pare. Avem '''4''' moduri de aranjare.

2215 - cifre002

2024-01-02T22:13:29Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă un număr natural '''n''' format cu cifre distincte nenule. Să se afle câte numere pare se pot obţine din '''n''', prin rearanjarea cifrelor sale. == Date de intrare == Programul citește de la tastatură numărul '''n'''. == Date de ieșire == Programul va afișa pe ecran numărul numerelor pare care se pot obţine prin rearanjarea cifrelor lui '''n'''. == Restricţii şi precizări == * '''1 &les; n &les; 2.000.000.000''' == Exemplul 1 == ; Intrare...

== Cerinţa ==
Se dă un număr natural '''n''' format cu cifre distincte nenule. Să se afle câte numere pare se pot obţine din '''n''', prin rearanjarea cifrelor sale.
== Date de intrare ==
Programul citește de la tastatură numărul '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran numărul numerelor pare care se pot obţine prin rearanjarea cifrelor lui '''n'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 2.000.000.000'''
== Exemplul 1 ==
; Intrare
324
; Iesire
Datele de intrare corespund restrictiilor impuse
4
== Exemplu 2 ==
; Intrare
2000000001
; Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from math import factorial

def compute_even_numbers(n):
digits = [int(d) for d in str(n)]
even_digits = [d for d in digits if d % 2 == 0]
if not even_digits:
return 0
digits.sort()
count = 0
for ed in even_digits:
temp = digits[:]
temp.remove(ed)
count += factorial(len(temp)) * (len(temp) ** (len(temp) - 1))
return count

def main():
n = int(input())

if n > 2000000000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

even_numbers = compute_even_numbers(n)
print("Datele de intrare corespund restrictiilor impuse")
print(even_numbers)

if __name__ == "__main__":
main()
</syntaxhighlight>
== Explicatie ==
Numerele pare ce se pot obţine prin rearanjarea cifrelor lui '''n''' sunt: '''324,342,234,432'''

1163 - CowboysAndAliens

2024-01-02T22:07:06Z

Brianna Waltner: Pagină nouă: == Cerinţa == Cei '''m''' cowboys și cei '''n''' aliens s-au întâlnit în vestul sălbatic și, păstrând tradiția locului, s-au așezat în șir indian. Cum cowboys erau gazde primitoare și în special foarte precaute, s-au gândit că între doi cowboys consecutivi ar fi bine să fie cel mult un alien (din motive de securitate). De asemenea primul și ultimul din șir să fie cawboys. Dilema care s-a ivit a fost numărul de moduri în care s-ar putea așeza în șir...

== Cerinţa ==
Cei '''m''' cowboys și cei '''n''' aliens s-au întâlnit în vestul sălbatic și, păstrând tradiția locului, s-au așezat în șir indian. Cum cowboys erau gazde primitoare și în special foarte precaute, s-au gândit că între doi cowboys consecutivi ar fi bine să fie cel mult un alien (din motive de securitate). De asemenea primul și ultimul din șir să fie cawboys. Dilema care s-a ivit a fost numărul de moduri în care s-ar putea așeza în șir indian ținând cont de condițiile de securitate impuse.
== Date de intrare ==
Fișierul de intrare '''cowboysandaliensin.txt''' conține pe prima linie numerele naturale '''m''' și '''n'''.
== Date de ieșire ==
Fișierul de ieșire '''cowboysandaliensout.txt''' va conține pe prima linie numărul '''S''', reprezentând numărul de moduri modulo '''555557''', în care s-ar putea așeza în șir indian.
== Restricţii şi precizări ==
* '''1 &les; n &les; m &les; 500.000
* reprezentările în baza '''10''' ale lui '''x''', '''y''' şi suma lor nu depăşesc '''2 000 000 000'''

== Exemplul 1 ==
; '''cowboysandaliensin.txt'''
3 1
; '''cowboysandaliensout.txt'''
Datele de intrare corespund restrictiilor impuse
12

== Exemplu 2 ==
; '''cowboysandaliensin.txt'''
2 2
; '''cowboysandaliensout.txt'''
Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
def compute_ways(m, n):
mod = 555557
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
dp[1][0] = 1
dp[2][0] = 2
dp[2][1] = 2
for i in range(3, m+1):
dp[i][0] = dp[i-1][0] + dp[i-2][0]
for j in range(1, min(i, n+1)):
dp[i][j] = dp[i-1][j] + dp[i-2][j] + dp[i-1][j-1] + dp[i-2][j-1]
return sum(dp[m]) % mod

def main():
m, n = map(int, input().split())

if m > 500000 or n >= m:
print("Datele de intrare nu corespund restrictiilor impuse")
return

ways = compute_ways(m, n)
print("Datele de intrare corespund restrictiilor impuse")
print(ways)

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
Dacă cei trei cawboys ar fi Jake, Percy și Roy pe care-i vom nota J, P, R iar alien ar fi Bronc, notat B, atunci ei s-ar putea așeza în șir indian în următoarele moduri: '''JBPR''' , '''JPBR''' , '''JBRP''' , '''JRBP''' , '''PBJR''' , '''PJBR''' , '''PBRJ''' , '''PRBJ''' , '''RBPJ''' , '''RPBJ''' , '''RBJP''' , '''RJBP'''. În total avem 12 moduri.

3623 - insule01

2024-01-02T21:51:16Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă '''n''' un număr natural. Într-un şir de lungime '''n''', format cu cifrele '''0''' şi '''1''', numim '''insulă''' o secvenţă maximă de cifre egale. Să se afle câte '''insule''' se află în toate şirurile de lungime '''n''', formate cu cifrele '''0''' şi '''1'''. == Date de intrare == Programul citește de la tastatură numărul '''n'''. == Date de ieșire == Programul va afișa pe ecran numărul '''insulelor''' care se află în toate şiru...

== Cerinţa ==
Se dă '''n''' un număr natural. Într-un şir de lungime '''n''', format cu cifrele '''0''' şi '''1''', numim '''insulă''' o secvenţă maximă de cifre egale. Să se afle câte '''insule''' se află în toate şirurile de lungime '''n''', formate cu cifrele '''0''' şi '''1'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran numărul '''insulelor''' care se află în toate şirurile de lungime '''n''', formate cu cifrele '''0''' şi '''1'''. Deoarece acest număr este prea mare, se va afişa modulo '''1.000.000.007'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 1.000.000.000'''

== Exemplul 1 ==
; Intrare
2
; Iesire
Datele de intrare corespund restrictiilor impuse
6

== Exemplu 2 ==
; Intrare
1000000001
; Iesire
Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
def compute_islands(n):
mod = 1000000007
dp = [0] * (n+1)
dp[1] = 2
dp[2] = 6
for i in range(3, n+1):
dp[i] = (dp[i-1] * 2 + dp[i-2] * 2) % mod
return dp[n]

def main():
n = int(input())

if n > pow(10, 9):
print("Datele de intrare nu corespund restrictiilor impuse")
return

islands = compute_islands(n)
print("Datele de intrare corespund restrictiilor impuse")
print(islands)

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
Şirurile de lungime '''2''' formate cu cifrele '''0''' şi '''1''' sunt '''00''', '''01''', '''10''', '''11''', acestea conţinând '''1''', '''2''', '''2''', respectiv '''1''' insule. În total sunt '''6''' insule.

3336 - acadele

2024-01-02T21:39:23Z

Brianna Waltner:

== Cerinţa ==
Candyman are acadele de trei feluri: cu căpşuni, cu vişine şi cu zmeură, oricâte acadele din fiecare fel. Cei '''n''' copii de la grupa pregătitoare şi-au ales fiecare câte o acadea astfel încât cel mult doi copii şi-au ales cu vişine. Dacă notăm cu '''m''' numărul de moduri în care puteau să-şi aleagă fiecare câte o acadea, să se afle restul împărţirii lui '''m''' la '''2020'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran restul împărţirii lui '''m''' la '''2020'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 1018'''
== Exemplul 1 ==
; Intrare
2
; Iesire
Datele de intrare corespund restrictiilor impuse
9
== Exemplu 2 ==
; Intrare
10000000000000000000
; Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def compute_ways(n):
mod = 2020
if n == 1:
return 3 % mod
elif n == 2:
return 9 % mod
else:
return (3 * 3 * pow(2, n-2, mod)) % mod

def main():
n = int(input())

if n > pow(10, 18):
print("Datele de intrare nu corespund restrictiilor impuse")
return

ways = compute_ways(n)
print("Datele de intrare corespund restrictiilor impuse")
print(ways)

if __name__ == "__main__":
main()
</syntaxhighlight>
== Explicatie ==
Cei doi copii puteau să-şi aleagă acadelele astfel: (c,c), (z,z), (v,v), (c,v), (v,c), (c,z), (z,c), (v,z), (z,v).

3630 - codred

2024-01-02T21:38:57Z

Brianna Waltner:

== Cerinţa ==
Se dă '''n''' un număr natural. Să se calculeze suma '''∑nk=1(k!⋅(k2+k+1))'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran valoarea sumei, modulo '''1.000.000.007'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 10.000.000'''
== Exemplul 1 ==
; Intrare
3
; Iesire
Datele de intrare corespund restrictiilor impuse
95
== Exemplu 2 ==
; Intrare
100000000
; Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def factorial(n, mod):
fact = 1
for i in range(1, n + 1):
fact = (fact * i) % mod
return fact

def compute_sum(n):
mod = 1000000007
suma = 0
for k in range(1, n + 1):
term = (factorial(k, mod) * (k*k + k + 1)) % mod
suma = (suma + term) % mod
return suma

def main():
n = int(input())

if n > 10000000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

suma = compute_sum(n)
print("Datele de intrare corespund restrictiilor impuse")
print(suma)

if __name__ == "__main__":
main()
</syntaxhighlight>
== Explicatie ==
Suma este '''1!⋅3+2!⋅7+3!⋅13=3+14+78=95'''.

2198 – Elimin Prime

2024-01-02T21:38:06Z

Brianna Waltner:

Se consideră un șir de n numere întregi, cu n număr natural nenul. Se elimină primul element din șir și toate elementele șirului aflate pe poziții care reprezintă numere prime, în ordinea crescătoare a pozițiilor. Operația de eliminare se repetă cu elementele rămase în șir, repoziționate după eliminarea celorlalte, până când este eliminat și ultimul element rămas.
== Cerinţa ==
Să se scrie un program care afișează elementele șirului inițial, în ordinea în care au fost eliminate conform algoritmului descris mai sus.
== Date de intrare ==
Fișierul de intrare '''elimin_primein.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere întregi separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''elimin_primeout.txt''' va conține pe prima linie, separate prin spațiu, numerele din fișierul de intrare în ordinea eliminării acestora.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* numerele de pe a doua linie a fișierului de intrare sun cuprinse în intervalul '''[-1.000.000.000, 1.000.000.000]'''
* elementele șirului sunt indexate de la '''1''' la '''n'''.

== Exemplul 1 ==
; elimin_primein.txt
10
1 2 3 4 5 6 7 8 9 10
; elimin_primeout.txt
Datele de intrare corespund restrictiilor impuse
1 2 3 5 7 4 6 8 10 9

== Exemplu 2 ==
; elimin_primein.txt
100001
2 3 4 5 6 7 8 9 10 4 23 16 -7 89 115 23 11 15 2 -8 -9 21 0 75 23 32 -1 4 5 ...
; elimin_primeout.txt
Datele de intrare nu corespund restrictiilor impuse

== Atentie! ==
Programele vor folosi doar instrucțiunile de bază ale limbajului de programare ales, inclusiv cele de intrare/ieșire, dar nu și alte funcții din biblioteci specializate ('''algorithm''', '''string''',…).

== Rezolvare ==
<syntaxhighlight lang="python" line>
def este_prim(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
p = 3
while p * p <= n:
if n % p == 0:
return False
p += 2
return True

def main():
sir = list(map(int, input().split()))

if len(sir) > 100000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

eliminat = []

while sir:
eliminat.append(sir.pop(0))
i = 1
while i < len(sir):
if este_prim(i+1):
eliminat.append(sir.pop(i))
else:
i += 1

print("Datele de intrare corespund restrictiilor impuse")
print(' '.join(map(str, eliminat)))

if __name__ == "__main__":
main()
</syntaxhighlight>

2847 – List

2024-01-02T21:33:25Z

Brianna Waltner:

== Cerinţa ==
Se dă o listă simplu înlănțuită care conține '''n''' perechi de numere naturale '''(a,b)'''. Fiecare pereche este stocată în câte un nod al listei; notăm cu '''a''' primul număr stocat într-un nod și cu '''b''' al doilea număr stocat în acel nod.

Se cere să se insereze în listă astfel:

Dacă pentru nodul curent:

* '''a''' este par și '''b''' este impar se inserează după nodul curent un nou nod, care conține dublul sumei lor pe prima poziție a nodului inserat iar pe a doua poziție diferența dintre dublul sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este par se inserează înaintea nodului curent un nou nod, care conține dublul sumei lor pe a doua poziție a nodului inserat și pe prima poziție diferența dintre dublul sumei numerelor din nodul curent și a primului număr din nodul curent;
* '''a''' este par, '''b''' este par se inserează după nodul curent un nou nod, care conține jumătatea sumei lor pe prima poziție a nodului inserat iar pe a doua poziție suma dintre jumătatea sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este impar se inserează înaintea nodului curent un nou nod, care conține jumătatea sumei lor pe a doua poziție a nodului inserat și pe prima poziție suma dintre jumătatea sumei numerelor din nodul curent și a primului număr din nodul curent.
== Date de intrare ==
Fișierul de intrare '''listin.txt''' conține pe prima linie numărul '''n''', iar pe următoarele '''n''' linii '''n''' perechi de numere naturale separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''listout.txt''' va conține pe câte o linie numerele fiecărui nod al listei separate prin spații, după realizarea inserărilor.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* '''1 &les; a &les; b &les; 100'''
* se recomandă utilizarea unei liste alocate dinamic
== Exemplul 1 ==
; listin.txt
5
1 2
2 4
1 1
2 6
7 4
; listout.txt
Datele de intrare corespund restrictiilor impuse
5 6
1 2
2 4
3 7
2 1
1 1
2 6
4 10
15 22
7 4
== Exemplul 2 ==
; listin.txt
100001
1 2
2 3
3 4
...
100000 100001
; listout.txt
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, a, b):
self.a = a
self.b = b
self.next = None

def insert_after(node, a, b):
new_node = Node(a, b)
new_node.next = node.next
node.next = new_node

def insert_before(head, node, a, b):
new_node = Node(a, b)
if head == node:
new_node.next = head
return new_node
else:
prev = head
while prev.next != node:
prev = prev.next
prev.next = new_node
new_node.next = node
return head

def main():
n = int(input())
sir = [list(map(int, input().split())) for _ in range(n)]

if len(sir) > 100000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

head = Node(sir[0][0], sir[0][1])
node = head
for i in range(1, n):
node.next = Node(sir[i][0], sir[i][1])
node = node.next

node = head
while node:
a, b = node.a, node.b
if a % 2 == 0 and b % 2 == 1:
insert_after(node, 2*(a+b), 2*(a+b)-b)
node = node.next
elif a % 2 == 1 and b % 2 == 0:
head = insert_before(head, node, 2*(a+b)-a, 2*(a+b))
elif a % 2 == 0 and b % 2 == 0:
insert_after(node, (a+b)//2, (a+b)//2+b)
node = node.next
elif a % 2 == 1 and b % 2 == 1:
head = insert_before(head, node, (a+b)//2+a, (a+b)//2)
node = node.next

print("Datele de intrare corespund restrictiilor impuse")
node = head
while node:
print(node.a, node.b)
node = node.next

if __name__ == "__main__":
main()
</syntaxhighlight>

2847 – List

2024-01-02T21:33:09Z

Brianna Waltner:

== Cerinţa ==
Se dă o listă simplu înlănțuită care conține '''n''' perechi de numere naturale '''(a,b)'''. Fiecare pereche este stocată în câte un nod al listei; notăm cu '''a''' primul număr stocat într-un nod și cu '''b''' al doilea număr stocat în acel nod.

Se cere să se insereze în listă astfel:

Dacă pentru nodul curent:

* '''a''' este par și '''b''' este impar se inserează după nodul curent un nou nod, care conține dublul sumei lor pe prima poziție a nodului inserat iar pe a doua poziție diferența dintre dublul sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este par se inserează înaintea nodului curent un nou nod, care conține dublul sumei lor pe a doua poziție a nodului inserat și pe prima poziție diferența dintre dublul sumei numerelor din nodul curent și a primului număr din nodul curent;
* '''a''' este par, '''b''' este par se inserează după nodul curent un nou nod, care conține jumătatea sumei lor pe prima poziție a nodului inserat iar pe a doua poziție suma dintre jumătatea sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este impar se inserează înaintea nodului curent un nou nod, care conține jumătatea sumei lor pe a doua poziție a nodului inserat și pe prima poziție suma dintre jumătatea sumei numerelor din nodul curent și a primului număr din nodul curent.
== Date de intrare ==
Fișierul de intrare '''listin.txt''' conține pe prima linie numărul '''n''', iar pe următoarele '''n''' linii '''n''' perechi de numere naturale separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''listout.txt''' va conține pe câte o linie numerele fiecărui nod al listei separate prin spații, după realizarea inserărilor.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* '''1 &les; a &les; b &les; 100'''
* se recomandă utilizarea unei liste alocate dinamic
== Exemplul 1 ==
; listin.txt
5
1 2
2 4
1 1
2 6
7 4
; listout.txt
Datele de intrare nu corespund restrictiilor impuse
5 6
1 2
2 4
3 7
2 1
1 1
2 6
4 10
15 22
7 4
== Exemplul 2 ==
; listin.txt
100001
1 2
2 3
3 4
...
100000 100001
; listout.txt
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, a, b):
self.a = a
self.b = b
self.next = None

def insert_after(node, a, b):
new_node = Node(a, b)
new_node.next = node.next
node.next = new_node

def insert_before(head, node, a, b):
new_node = Node(a, b)
if head == node:
new_node.next = head
return new_node
else:
prev = head
while prev.next != node:
prev = prev.next
prev.next = new_node
new_node.next = node
return head

def main():
n = int(input())
sir = [list(map(int, input().split())) for _ in range(n)]

if len(sir) > 100000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

head = Node(sir[0][0], sir[0][1])
node = head
for i in range(1, n):
node.next = Node(sir[i][0], sir[i][1])
node = node.next

node = head
while node:
a, b = node.a, node.b
if a % 2 == 0 and b % 2 == 1:
insert_after(node, 2*(a+b), 2*(a+b)-b)
node = node.next
elif a % 2 == 1 and b % 2 == 0:
head = insert_before(head, node, 2*(a+b)-a, 2*(a+b))
elif a % 2 == 0 and b % 2 == 0:
insert_after(node, (a+b)//2, (a+b)//2+b)
node = node.next
elif a % 2 == 1 and b % 2 == 1:
head = insert_before(head, node, (a+b)//2+a, (a+b)//2)
node = node.next

print("Datele de intrare corespund restrictiilor impuse")
node = head
while node:
print(node.a, node.b)
node = node.next

if __name__ == "__main__":
main()
</syntaxhighlight>

2847 – List

2024-01-02T21:31:28Z

Brianna Waltner:

== Cerinţa ==
Se dă o listă simplu înlănțuită care conține '''n''' perechi de numere naturale '''(a,b)'''. Fiecare pereche este stocată în câte un nod al listei; notăm cu '''a''' primul număr stocat într-un nod și cu '''b''' al doilea număr stocat în acel nod.

Se cere să se insereze în listă astfel:

Dacă pentru nodul curent:

* '''a''' este par și '''b''' este impar se inserează după nodul curent un nou nod, care conține dublul sumei lor pe prima poziție a nodului inserat iar pe a doua poziție diferența dintre dublul sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este par se inserează înaintea nodului curent un nou nod, care conține dublul sumei lor pe a doua poziție a nodului inserat și pe prima poziție diferența dintre dublul sumei numerelor din nodul curent și a primului număr din nodul curent;
* '''a''' este par, '''b''' este par se inserează după nodul curent un nou nod, care conține jumătatea sumei lor pe prima poziție a nodului inserat iar pe a doua poziție suma dintre jumătatea sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este impar se inserează înaintea nodului curent un nou nod, care conține jumătatea sumei lor pe a doua poziție a nodului inserat și pe prima poziție suma dintre jumătatea sumei numerelor din nodul curent și a primului număr din nodul curent.
== Date de intrare ==
Fișierul de intrare '''listin.txt''' conține pe prima linie numărul '''n''', iar pe următoarele '''n''' linii '''n''' perechi de numere naturale separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''listout.txt''' va conține pe câte o linie numerele fiecărui nod al listei separate prin spații, după realizarea inserărilor.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* '''1 &les; a &les; b &les; 100'''
* se recomandă utilizarea unei liste alocate dinamic
== Exemplul 1 ==
; listin.txt
5
1 2
2 4
1 1
2 6
7 4
; listout.txt
5 6
1 2
2 4
3 7
2 1
1 1
2 6
4 10
15 22
7 4
== Exemplul 2 ==
; listin.txt
100001
1 2
2 3
3 4
...
100000 100001
; listout.txt
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, a, b):
self.a = a
self.b = b
self.next = None

def insert_after(node, a, b):
new_node = Node(a, b)
new_node.next = node.next
node.next = new_node

def insert_before(head, node, a, b):
new_node = Node(a, b)
if head == node:
new_node.next = head
return new_node
else:
prev = head
while prev.next != node:
prev = prev.next
prev.next = new_node
new_node.next = node
return head

def main():
n = int(input())
sir = [list(map(int, input().split())) for _ in range(n)]

if len(sir) > 100000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

head = Node(sir[0][0], sir[0][1])
node = head
for i in range(1, n):
node.next = Node(sir[i][0], sir[i][1])
node = node.next

node = head
while node:
a, b = node.a, node.b
if a % 2 == 0 and b % 2 == 1:
insert_after(node, 2*(a+b), 2*(a+b)-b)
node = node.next
elif a % 2 == 1 and b % 2 == 0:
head = insert_before(head, node, 2*(a+b)-a, 2*(a+b))
elif a % 2 == 0 and b % 2 == 0:
insert_after(node, (a+b)//2, (a+b)//2+b)
node = node.next
elif a % 2 == 1 and b % 2 == 1:
head = insert_before(head, node, (a+b)//2+a, (a+b)//2)
node = node.next

print("Datele de intrare corespund restrictiilor impuse")
node = head
while node:
print(node.a, node.b)
node = node.next

if __name__ == "__main__":
main()
</syntaxhighlight>

2847 – List

2024-01-02T21:27:40Z

Brianna Waltner:

== Cerinţa ==
Se dă o listă simplu înlănțuită care conține '''n''' perechi de numere naturale '''(a,b)'''. Fiecare pereche este stocată în câte un nod al listei; notăm cu '''a''' primul număr stocat într-un nod și cu '''b''' al doilea număr stocat în acel nod.

Se cere să se insereze în listă astfel:

Dacă pentru nodul curent:

* '''a''' este par și '''b''' este impar se inserează după nodul curent un nou nod, care conține dublul sumei lor pe prima poziție a nodului inserat iar pe a doua poziție diferența dintre dublul sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este par se inserează înaintea nodului curent un nou nod, care conține dublul sumei lor pe a doua poziție a nodului inserat și pe prima poziție diferența dintre dublul sumei numerelor din nodul curent și a primului număr din nodul curent;
* '''a''' este par, '''b''' este par se inserează după nodul curent un nou nod, care conține jumătatea sumei lor pe prima poziție a nodului inserat iar pe a doua poziție suma dintre jumătatea sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este impar se inserează înaintea nodului curent un nou nod, care conține jumătatea sumei lor pe a doua poziție a nodului inserat și pe prima poziție suma dintre jumătatea sumei numerelor din nodul curent și a primului număr din nodul curent.
== Date de intrare ==
Fișierul de intrare '''listin.txt''' conține pe prima linie numărul '''n''', iar pe următoarele '''n''' linii '''n''' perechi de numere naturale separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''listout.txt''' va conține pe câte o linie numerele fiecărui nod al listei separate prin spații, după realizarea inserărilor.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* '''1 &les; a &les; b &les; 100'''
* se recomandă utilizarea unei liste alocate dinamic
== Exemplul ==
; listin.txt
5
1 2
2 4
1 1
2 6
7 4
; listout.txt
5 6
1 2
2 4
3 7
2 1
1 1
2 6
4 10
15 22
7 4
== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, a, b):
self.a = a
self.b = b
self.next = None

def insert_after(node, a, b):
new_node = Node(a, b)
new_node.next = node.next
node.next = new_node

def insert_before(head, node, a, b):
new_node = Node(a, b)
if head == node:
new_node.next = head
return new_node
else:
prev = head
while prev.next != node:
prev = prev.next
prev.next = new_node
new_node.next = node
return head

def main():
n = int(input())
sir = [list(map(int, input().split())) for _ in range(n)]

if len(sir) > 100000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

head = Node(sir[0][0], sir[0][1])
node = head
for i in range(1, n):
node.next = Node(sir[i][0], sir[i][1])
node = node.next

node = head
while node:
a, b = node.a, node.b
if a % 2 == 0 and b % 2 == 1:
insert_after(node, 2*(a+b), 2*(a+b)-b)
node = node.next
elif a % 2 == 1 and b % 2 == 0:
head = insert_before(head, node, 2*(a+b)-a, 2*(a+b))
elif a % 2 == 0 and b % 2 == 0:
insert_after(node, (a+b)//2, (a+b)//2+b)
node = node.next
elif a % 2 == 1 and b % 2 == 1:
head = insert_before(head, node, (a+b)//2+a, (a+b)//2)
node = node.next

print("Datele de intrare corespund restrictiilor impuse")
node = head
while node:
print(node.a, node.b)
node = node.next

if __name__ == "__main__":
main()
</syntaxhighlight>

3336 - acadele

2024-01-02T21:27:07Z

Brianna Waltner:

== Cerinţa ==
Candyman are acadele de trei feluri: cu căpşuni, cu vişine şi cu zmeură, oricâte acadele din fiecare fel. Cei '''n''' copii de la grupa pregătitoare şi-au ales fiecare câte o acadea astfel încât cel mult doi copii şi-au ales cu vişine. Dacă notăm cu '''m''' numărul de moduri în care puteau să-şi aleagă fiecare câte o acadea, să se afle restul împărţirii lui '''m''' la '''2020'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran restul împărţirii lui '''m''' la '''2020'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 1018'''
== Exemplul 1 ==
; Intrare
2
; Iesire
9
== Exemplu 2 ==
; Intrare
10000000000000000000
; Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def compute_ways(n):
mod = 2020
if n == 1:
return 3 % mod
elif n == 2:
return 9 % mod
else:
return (3 * 3 * pow(2, n-2, mod)) % mod

def main():
n = int(input())

if n > pow(10, 18):
print("Datele de intrare nu corespund restrictiilor impuse")
return

ways = compute_ways(n)
print("Datele de intrare corespund restrictiilor impuse")
print(ways)

if __name__ == "__main__":
main()
</syntaxhighlight>
== Explicatie ==
Cei doi copii puteau să-şi aleagă acadelele astfel: (c,c), (z,z), (v,v), (c,v), (v,c), (c,z), (z,c), (v,z), (z,v).

3630 - codred

2024-01-02T21:26:37Z

Brianna Waltner:

== Cerinţa ==
Se dă '''n''' un număr natural. Să se calculeze suma '''∑nk=1(k!⋅(k2+k+1))'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran valoarea sumei, modulo '''1.000.000.007'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 10.000.000'''
== Exemplul 1 ==
; Intrare
3
; Iesire
95
== Exemplu 2 ==
; Intrare
100000000
; Iesire
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def factorial(n, mod):
fact = 1
for i in range(1, n + 1):
fact = (fact * i) % mod
return fact

def compute_sum(n):
mod = 1000000007
suma = 0
for k in range(1, n + 1):
term = (factorial(k, mod) * (k*k + k + 1)) % mod
suma = (suma + term) % mod
return suma

def main():
n = int(input())

if n > 10000000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

suma = compute_sum(n)
print("Datele de intrare corespund restrictiilor impuse")
print(suma)

if __name__ == "__main__":
main()
</syntaxhighlight>
== Explicatie ==
Suma este '''1!⋅3+2!⋅7+3!⋅13=3+14+78=95'''.

3336 - acadele

2024-01-02T21:21:02Z

Brianna Waltner: Pagină nouă: == Cerinţa == Candyman are acadele de trei feluri: cu căpşuni, cu vişine şi cu zmeură, oricâte acadele din fiecare fel. Cei '''n''' copii de la grupa pregătitoare şi-au ales fiecare câte o acadea astfel încât cel mult doi copii şi-au ales cu vişine. Dacă notăm cu '''m''' numărul de moduri în care puteau să-şi aleagă fiecare câte o acadea, să se afle restul împărţirii lui '''m''' la '''2020'''. == Date de intrare == Programul citește de la tastatură...

== Cerinţa ==
Candyman are acadele de trei feluri: cu căpşuni, cu vişine şi cu zmeură, oricâte acadele din fiecare fel. Cei '''n''' copii de la grupa pregătitoare şi-au ales fiecare câte o acadea astfel încât cel mult doi copii şi-au ales cu vişine. Dacă notăm cu '''m''' numărul de moduri în care puteau să-şi aleagă fiecare câte o acadea, să se afle restul împărţirii lui '''m''' la '''2020'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran restul împărţirii lui '''m''' la '''2020'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 1018'''

== Exemplul 1 ==
; Intrare
2
; Iesire
9

== Exemplu 2 ==
; Intrare
10000000000000000000
; Iesire
Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
def compute_ways(n):
mod = 2020
if n == 1:
return 3 % mod
elif n == 2:
return 9 % mod
else:
return (3 * 3 * pow(2, n-2, mod)) % mod

def main():
n = int(input())

if n > pow(10, 18):
print("Datele de intrare nu corespund restrictiilor impuse")
return

ways = compute_ways(n)
print("Datele de intrare corespund restrictiilor impuse")
print(ways)

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
Cei doi copii puteau să-şi aleagă acadelele astfel: (c,c), (z,z), (v,v), (c,v), (v,c), (c,z), (z,c), (v,z), (z,v).

3630 - codred

2024-01-02T21:10:32Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă '''n''' un număr natural. Să se calculeze suma '''∑nk=1(k!⋅(k2+k+1))'''. == Date de intrare == Programul citește de la tastatură numărul '''n'''. == Date de ieșire == Programul va afișa pe ecran valoarea sumei, modulo '''1.000.000.007'''. == Restricţii şi precizări == * '''1 &les; n &les; 10.000.000''' == Exemplul 1 == ; Intrare 3 ; Iesire 95 == Exemplu 2 == ; Intrare 100000000 ; Iesire Datele de intrare nu corespund restrictiilor imp...

== Cerinţa ==
Se dă '''n''' un număr natural. Să se calculeze suma '''∑nk=1(k!⋅(k2+k+1))'''.
== Date de intrare ==
Programul citește de la tastatură numărul '''n'''.
== Date de ieșire ==
Programul va afișa pe ecran valoarea sumei, modulo '''1.000.000.007'''.
== Restricţii şi precizări ==
* '''1 &les; n &les; 10.000.000'''

== Exemplul 1 ==
; Intrare
3
; Iesire
95

== Exemplu 2 ==
; Intrare
100000000
; Iesire
Datele de intrare nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
def factorial(n, mod):
fact = 1
for i in range(1, n + 1):
fact = (fact * i) % mod
return fact

def compute_sum(n):
mod = 1000000007
suma = 0
for k in range(1, n + 1):
term = (factorial(k, mod) * (k*k + k + 1)) % mod
suma = (suma + term) % mod
return suma

def main():
n = int(input())

if n > 10000000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

suma = compute_sum(n)
print("Datele de intrare corespund restrictiilor impuse")
print(suma)

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
Suma este '''1!⋅3+2!⋅7+3!⋅13=3+14+78=95'''.

3387 - Veverita

2024-01-02T21:03:16Z

Brianna Waltner: Ștergerea conținutului paginii

3387 - Veverita

2024-01-02T20:47:35Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă o matrice cu '''n''' linii și '''m''' coloane cu valori de '''0''' și '''1'''. Numim '''dreptunghi de extrem''' un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă. == Date de intrare == Fișierul de intrare '''colturi_drin.txt''' conține pe prima linie numărul '''n''' de linii,...

== Cerinţa ==
Se dă o matrice cu '''n''' linii și '''m''' coloane cu valori de '''0''' și '''1'''. Numim '''dreptunghi de extrem''' un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă.
== Date de intrare ==
Fișierul de intrare '''colturi_drin.txt''' conține pe prima linie numărul '''n''' de linii, numărul '''m''' de coloane, iar pe următoarele linii se află cele '''n * m''' numere naturale.
== Date de ieșire ==
Fișierul de ieșire '''colturi_dr.out''' va conține pe prima linie numerele '''nr''', '''A''' si '''cnt''' reprezentând cele trei numere specificate în cerință.
== Restricţii şi precizări ==
* '''1 &les; n, m &les; 100'''
* numărul de dreptunghiuri de extrem cu vârfuri de 1 este diferit de numărul de dreptunghiuri de extrem cu vârfuri de '''0'''.
* un '''dreptunghi de extrem''' are cel puțin două linii și două coloane

== Exemplul 1 ==
; colturi_drin.txt
5 5
1 0 1 0 1
1 1 1 1 0
0 1 1 0 1
0 1 0 0 1
1 0 1 0 1
; colturi_dr.out
11 25 9

== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_extreme_rectangles(matrix):
n = len(matrix)
m = len(matrix[0])
cnt = [0, 0]
max_area = [0, 0]
max_area_cnt = [0, 0]

for i in range(n):
for j in range(m):
for k in range(i+1, n):
for o in range(j+1, m):
if matrix[i][j] == matrix[k][o] == matrix[i][o] == matrix[k][j]:
cnt[matrix[i][j]] += 1
area = (k-i+1) * (o-j+1)
if area > max_area[matrix[i][j]]:
max_area[matrix[i][j]] = area
max_area_cnt[matrix[i][j]] = 1
elif area == max_area[matrix[i][j]]:
max_area_cnt[matrix[i][j]] += 1

if max_area[0] > max_area[1]:
return cnt[0], max_area[0], max_area_cnt[0]
else:
return cnt[1], max_area[1], max_area_cnt[1]

def main():
n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]

if n > 100 or m > 100:
print("Datele de intrare nu corespund restrictiilor impuse")
return

nr, A, cnt = count_extreme_rectangles(matrix)
print("Datele de intrare corespund restrictiilor impuse")
print(nr, A, cnt)

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==
Sunt '''9''' dreptunghiuri de extrem a cărui vârfuri sunt '''1''', respectiv '''2''' ale cărui vârfuri sunt '''0'''. Dreptunghiul de extrem de arie maximă are colțul stânga sus la '''(0,0)''' și colțul dreapta jos la '''(5,5)'''.

2847 – List

2024-01-02T20:27:31Z

Brianna Waltner: Pagină nouă: == Cerinţa == Se dă o listă simplu înlănțuită care conține '''n''' perechi de numere naturale '''(a,b)'''. Fiecare pereche este stocată în câte un nod al listei; notăm cu '''a''' primul număr stocat într-un nod și cu '''b''' al doilea număr stocat în acel nod. Se cere să se insereze în listă astfel: Dacă pentru nodul curent: * '''a''' este par și '''b''' este impar se inserează după nodul curent un nou nod, care conține dublul sumei lor pe prima po...

== Cerinţa ==
Se dă o listă simplu înlănțuită care conține '''n''' perechi de numere naturale '''(a,b)'''. Fiecare pereche este stocată în câte un nod al listei; notăm cu '''a''' primul număr stocat într-un nod și cu '''b''' al doilea număr stocat în acel nod.

Se cere să se insereze în listă astfel:

Dacă pentru nodul curent:

* '''a''' este par și '''b''' este impar se inserează după nodul curent un nou nod, care conține dublul sumei lor pe prima poziție a nodului inserat iar pe a doua poziție diferența dintre dublul sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este par se inserează înaintea nodului curent un nou nod, care conține dublul sumei lor pe a doua poziție a nodului inserat și pe prima poziție diferența dintre dublul sumei numerelor din nodul curent și a primului număr din nodul curent;
* '''a''' este par, '''b''' este par se inserează după nodul curent un nou nod, care conține jumătatea sumei lor pe prima poziție a nodului inserat iar pe a doua poziție suma dintre jumătatea sumei numerelor din nodul curent și al doilea număr din nodul curent;
* '''a''' este impar, '''b''' este impar se inserează înaintea nodului curent un nou nod, care conține jumătatea sumei lor pe a doua poziție a nodului inserat și pe prima poziție suma dintre jumătatea sumei numerelor din nodul curent și a primului număr din nodul curent.
== Date de intrare ==
Fișierul de intrare '''listin.txt''' conține pe prima linie numărul '''n''', iar pe următoarele '''n''' linii '''n''' perechi de numere naturale separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''listout.txt''' va conține pe câte o linie numerele fiecărui nod al listei separate prin spații, după realizarea inserărilor.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* '''1 &les; a &les; b &les; 100'''
* se recomandă utilizarea unei liste alocate dinamic

== Exemplul ==
; listin.txt
5
1 2
2 4
1 1
2 6
7 4
; listout.txt
5 6
1 2
2 4
3 7
2 1
1 1
2 6
4 10
15 22
7 4

== Rezolvare ==
<syntaxhighlight lang="python" line>
class Node:
def __init__(self, a, b):
self.a = a
self.b = b
self.next = None

def insert_after(node, a, b):
new_node = Node(a, b)
new_node.next = node.next
node.next = new_node

def insert_before(head, node, a, b):
new_node = Node(a, b)
if head == node:
new_node.next = head
return new_node
else:
prev = head
while prev.next != node:
prev = prev.next
prev.next = new_node
new_node.next = node
return head

def main():
n = int(input())
sir = [list(map(int, input().split())) for _ in range(n)]

if len(sir) > 100000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

head = Node(sir[0][0], sir[0][1])
node = head
for i in range(1, n):
node.next = Node(sir[i][0], sir[i][1])
node = node.next

node = head
while node:
a, b = node.a, node.b
if a % 2 == 0 and b % 2 == 1:
insert_after(node, 2*(a+b), 2*(a+b)-b)
node = node.next
elif a % 2 == 1 and b % 2 == 0:
head = insert_before(head, node, 2*(a+b)-a, 2*(a+b))
elif a % 2 == 0 and b % 2 == 0:
insert_after(node, (a+b)//2, (a+b)//2+b)
node = node.next
elif a % 2 == 1 and b % 2 == 1:
head = insert_before(head, node, (a+b)//2+a, (a+b)//2)
node = node.next

print("Datele de intrare corespund restrictiilor impuse")
node = head
while node:
print(node.a, node.b)
node = node.next

if __name__ == "__main__":
main()
</syntaxhighlight>

2198 – Elimin Prime

2024-01-02T20:13:22Z

Brianna Waltner: Pagină nouă: Se consideră un șir de n numere întregi, cu n număr natural nenul. Se elimină primul element din șir și toate elementele șirului aflate pe poziții care reprezintă numere prime, în ordinea crescătoare a pozițiilor. Operația de eliminare se repetă cu elementele rămase în șir, repoziționate după eliminarea celorlalte, până când este eliminat și ultimul element rămas. == Cerinţa == Să se scrie un program care afișează elementele șirului inițial, în...

Se consideră un șir de n numere întregi, cu n număr natural nenul. Se elimină primul element din șir și toate elementele șirului aflate pe poziții care reprezintă numere prime, în ordinea crescătoare a pozițiilor. Operația de eliminare se repetă cu elementele rămase în șir, repoziționate după eliminarea celorlalte, până când este eliminat și ultimul element rămas.
== Cerinţa ==
Să se scrie un program care afișează elementele șirului inițial, în ordinea în care au fost eliminate conform algoritmului descris mai sus.
== Date de intrare ==
Fișierul de intrare '''elimin_primein.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere întregi separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''elimin_primeout.txt''' va conține pe prima linie, separate prin spațiu, numerele din fișierul de intrare în ordinea eliminării acestora.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* numerele de pe a doua linie a fișierului de intrare sun cuprinse în intervalul '''[-1.000.000.000, 1.000.000.000]'''
* elementele șirului sunt indexate de la '''1''' la '''n'''.

== Exemplul 1 ==
; elimin_primein.txt
10
1 2 3 4 5 6 7 8 9 10
; elimin_primeout.txt
1 2 3 5 7 4 6 8 10 9

== Exemplu 2 ==
; elimin_primein.txt
20
4 23 16 -7 89 115 23 11 15 2 -8 -9 21 0 75 23 32 -1 4 5
; elimin_primeout.txt
4 23 16 89 23 -8 21 32 4 -7 115 11 2 0 5 15 -9 75 -1 23

== Atentie! ==
Programele vor folosi doar instrucțiunile de bază ale limbajului de programare ales, inclusiv cele de intrare/ieșire, dar nu și alte funcții din biblioteci specializate ('''algorithm''', '''string''',…).

== Rezolvare ==
<syntaxhighlight lang="python" line>
def este_prim(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
p = 3
while p * p <= n:
if n % p == 0:
return False
p += 2
return True

def main():
sir = list(map(int, input().split()))

if len(sir) > 100000:
print("Datele de intrare nu corespund restrictiilor impuse")
return

eliminat = []

while sir:
eliminat.append(sir.pop(0))
i = 1
while i < len(sir):
if este_prim(i+1):
eliminat.append(sir.pop(i))
else:
i += 1

print("Datele de intrare corespund restrictiilor impuse")
print(' '.join(map(str, eliminat)))

if __name__ == "__main__":
main()
</syntaxhighlight>