Bitnami MediaWiki - User contributions [en]

1962 - Vecini Buni

2024-06-03T17:41:01Z

AjM: Pagină nouă: == Enunt == Se consideră matricea A ale cărei elemente pot avea doar valorile 0 sau 1 și în care numerotarea liniilor și numerotarea coloanelor începe de la 1. Pentru un element oarecare al matricei, definim noţiunea de vecin ca fiind acele elementele din matrice aflate în imediata sa apropiere, pe una dintre direcțiile orizontală, verticală sau pe cele două diagonale. Un vecin bun al elementului A[i][j] este un vecin care are aceeaşi valoare cu A[i][j]. == Cerin...

== Enunt ==
Se consideră matricea A ale cărei elemente pot avea doar valorile 0 sau 1 și în care numerotarea liniilor și numerotarea coloanelor începe de la 1. Pentru un element oarecare al matricei, definim noţiunea de vecin ca fiind acele elementele din matrice aflate în imediata sa apropiere, pe una dintre direcțiile orizontală, verticală sau pe cele două diagonale. Un vecin bun al elementului A[i][j] este un vecin care are aceeaşi valoare cu A[i][j].
== Cerinţa ==
Dându-se matricea A, să se determine numărul maxim de vecini buni pe care îi are unul dintre elementele matricei precum și numărul de elemente care au acest număr maxim de vecini buni.
== Date de intrare ==
Fișierul de intrare vecini_buni.in conține pe prima linie trei valori naturale m, n și k reprezentând numărul de linii, numărul de coloane și numărul de valori egale cu 1 din matricea A. Pe fiecare dintre următoarele k linii ale fișierului se află două valori i și j cu semnificaţia A[i][j] este egal cu 1. Aceste valori sunt date în ordinea parcurgerii matricei pe linii de la linia 1 la linia m.
== Date de ieșire ==
Fișierul de ieșire vecini_buni.out va conține pe prima linie două numere naturale x și y separate printr-un singur spaţiu: x va reprezenta numărul maxim de vecini buni pe care îi are unul dintre elementele matricei date iar y va reprezenta numărul de elemente din matricea dată care au acest număr maxim de vecini buni.
== Restricţii şi precizări ==
* 2 ≤ m,n ≤ 1000
* 0 ≤ k ≤ n*m
* pentru 30% dintre teste, 2 ≤ m,n ≤ 200
== Exemplul 1 ==
; vecini_buni.in
3 4 7
1 3
2 1
2 4
3 1
3 4
3 3
3 2
; vecini_buni.out
3 6
 

== Explicație ==
Matricea A este următoarea:

0 0 1 0
1 0 0 1
1 1 1 1
Numărul maxim de vecini buni pe care îl întâlnim pentru elementele matricei este 3. Sunt 6 elemente care au acest număr maxim de vecini buni, cele situate în poziţiile: 1,2; 2,2; 2,3; 2,4; 3,2; 3,3 (cele care sunt subliniate în reprezentarea de mai sus a matricei).
== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_good_neighbors(matrix):
m = len(matrix)
n = len(matrix[0])
max_good_neighbors = 0
max_good_neighbors_count = 0

for i in range(m):
for j in range(n):
if matrix[i][j] == 1:
good_neighbors = 0
for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
if 0 <= i + di < m and 0 <= j + dj < n and matrix[i + di][j + dj] == 1:
good_neighbors += 1
good_neighbors -= 1 # Exclude the element itself
if good_neighbors > max_good_neighbors:
max_good_neighbors = good_neighbors
max_good_neighbors_count = 1
elif good_neighbors == max_good_neighbors:
max_good_neighbors_count += 1

return max_good_neighbors, max_good_neighbors_count

def main():
# Read input
with open("vecini_buni.in", "r") as fin:
m, n, k = map(int, fin.readline().split())
matrix = [[0] * n for _ in range(m)]
for _ in range(k):
i, j = map(int, fin.readline().split())
matrix[i - 1][j - 1] = 1

# Count good neighbors
max_good_neighbors, max_good_neighbors_count = count_good_neighbors(matrix)

# Write output
with open("vecini_buni.out", "w") as fout:
fout.write(f"{max_good_neighbors} {max_good_neighbors_count}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2170 - Dreptc

2024-06-03T17:39:19Z

AjM: Pagină nouă: == Enunt == Se consideră n puncte colorate dispuse în plan. Ele sunt identificate prin coordonatele lor întregi, pe axele OX și OY. Fiecare punct are asociat un număr natural între 1 și C reprezentând codul culorii lui. Un dreptunghi se numește corect dacă îndeplinește simultan următoare condiții: * toate cele patru vârfuri se regăsesc printre cele n puncte date; * are laturile paralele cu axele OX, OY; * are vârfurile colorate în aceeași culoare. == Cerin...

== Enunt ==
Se consideră n puncte colorate dispuse în plan. Ele sunt identificate prin coordonatele lor întregi, pe axele OX și OY. Fiecare punct are asociat un număr natural între 1 și C reprezentând codul culorii lui. Un dreptunghi se numește corect dacă îndeplinește simultan următoare condiții:
* toate cele patru vârfuri se regăsesc printre cele n puncte date;
* are laturile paralele cu axele OX, OY;
* are vârfurile colorate în aceeași culoare.
== Cerinţa ==
Să se determine numărul maxim de dreptunghiuri corecte care se pot forma cu cele n puncte din plan.
== Date de intrare ==
Pe prima linie a fișierului text dreptc.in se găsesc două numere n maxc reprezentând numărul de puncte din plan și numărul de culori asociate punctelor. Pe următoarele n linii se citesc câte trei numere x y c reprezentând în ordine coordonata pe axa OX (abscisa), coordonata pe axa OY (ordonata) și codul culorii asociate punctului. Nu există două puncte cu aceleași coordonate.
== Date de ieșire ==
Fișierul de ieșire dreptc.out va conține un singur număr reprezentând numărul maxim de dreptunghiuri corecte.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 1000
* 1 ≤ C ≤ 5
* -1000 ≤ x , y ≤ 1000
* 40% din teste vor avea N ≤ 100
== Exemplu ==
; dreptc.in
9 2
3 10 1
3 8 2
3 6 1
3 4 1
3 0 1
6 0 1
6 4 1
6 8 2
6 10 1
; dreptc.out
3
 

== Explicație ==
Vârfurile celor trei dreptunghiuri corecte sunt:
(3,0) (3,4) (6,4) (6,0)
(3,0) (3,10) (6,10) (6,0)
(3,6) (3,10) (6,10) (6,4).
== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_rectangles(points):
n = len(points)
rectangles = 0

# Generate all possible rectangles
for i in range(n):
for j in range(i + 1, n):
# Check if the other two points of the potential rectangle exist and have the same color
x1, y1, c1 = points[i]
x2, y2, c2 = points[j]
if (x1, y2, c1) in points and (x2, y1, c1) in points and c1 == c2:
rectangles += 1

return rectangles // 2 # Each rectangle is counted twice, so we divide by 2

def main():
# Read input
with open("dreptc.in", "r") as fin:
n, maxc = map(int, fin.readline().split())
points = [tuple(map(int, fin.readline().split())) for _ in range(n)]

# Count rectangles
result = count_rectangles(points)

# Write output
with open("dreptc.out", "w") as fout:
fout.write(str(result) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1228 - SSK

2024-06-03T17:35:50Z

AjM: Pagină nouă: == Enunt == Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător. Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, iden...

== Enunt ==
Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.

Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, identificată prin colțul stânga-sus (x1,y1) şi colţul dreapta-jos (x2,y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1≤i≤x2 şi y1≤j≤y2. Suma unui subtablou este suma tuturor elementelor sale.
== Cerinţa ==
Scrieţi un program care, cunoscând valorile elementelor matricei A, determină al K-lea termen din șirul ordonat al sumelor tuturor subtablourilor matricei A.
== Date de intrare ==
Fișierul de intrare ssk.in conţine pe prima linie numerele naturale N M K separate prin câte un spațiu, având semnificația din enunț. Pe următoarele N linii se află câte M numere naturale separate prin spaţii, reprezentând elementele matricei A.
== Date de ieșire ==
Fişierul de ieşire ssk.out va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerinţă.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 150
* 1 ≤ M ≤ 150
* 1 ≤ K ≤ numărul de termeni din şirul ordonat
* 0 ≤ A[i][j] ≤ 1000 unde 1 ≤ i ≤ N și 1 ≤ j ≤ M
Numerotarea termenilor din şirul ordonat al sumelor tuturor subtablourilor se va face începând de la 1.
== Exemplu ==
; ssk.in
2 3 14
3 2 7
4 1 0
; ssk.out
9
 

== Explicație ==
Șirul ordonat al tuturor sumelor subtablourilor matricei este

0 1 1 2 3 3 4 5 5 5 7 7 7 9 10 10 12 17

A patrusprezecea sumă este 9.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def calculate_subtable_sums(matrix):
n = len(matrix)
m = len(matrix[0])

# Initialize the cumulative sum matrix
cumulative_sum = [[0] * (m + 1) for _ in range(n + 1)]

# Calculate cumulative sum matrix
for i in range(1, n + 1):
for j in range(1, m + 1):
cumulative_sum[i][j] = matrix[i - 1][j - 1] + cumulative_sum[i - 1][j] + cumulative_sum[i][j - 1] - cumulative_sum[i - 1][j - 1]

# Calculate the sum of each subtable and store it in a list
subtable_sums = []
for i1 in range(1, n + 1):
for j1 in range(1, m + 1):
for i2 in range(i1, n + 1):
for j2 in range(j1, m + 1):
subtable_sum = cumulative_sum[i2][j2] - cumulative_sum[i2][j1 - 1] - cumulative_sum[i1 - 1][j2] + cumulative_sum[i1 - 1][j1 - 1]
subtable_sums.append(subtable_sum)

# Sort the list of subtable sums
subtable_sums.sort()

return subtable_sums

def main():
with open("ssk.in", "r") as fin:
N, M, K = map(int, fin.readline().split())
matrix = [list(map(int, fin.readline().split())) for _ in range(N)]

# Calculate subtable sums
subtable_sums = calculate_subtable_sums(matrix)

# Retrieve the K-th term
kth_term = subtable_sums[K - 1]

# Write the result to the output file
with open("ssk.out", "w") as fout:
fout.write(str(kth_term) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1190 - Sipet

2024-06-03T17:33:57Z

AjM: Pagină nouă: == Enunt == Un arheolog a găsit un sipet interesant. După ce l-a deschis cu grijă, a constatat cu surprindere că sipetul conține bănuți de aur. Uitându-se mai atent a mai găsit ceva: un pergament ascuns într-un compartiment secret al sipetului, cu un text scris într-o limbă antică, pe care, din fericire, arheologul o cunoștea. Din text a reieșit că un grup de negustori foarte bogați a vrut să ascundă în mare secret averea breslei lor, formată din monede d...

== Enunt ==
Un arheolog a găsit un sipet interesant. După ce l-a deschis cu grijă, a constatat cu surprindere că sipetul conține bănuți de aur. Uitându-se mai atent a mai găsit ceva: un pergament ascuns într-un compartiment secret al sipetului, cu un text scris într-o limbă antică, pe care, din fericire, arheologul o cunoștea. Din text a reieșit că un grup de negustori foarte bogați a vrut să ascundă în mare secret averea breslei lor, formată din monede de aur, deoarece se prevestea un război cumplit. Negustorii știau că există șanse ca această comoară să fie găsită și confiscată de dușmani, deci s-au sfătuit cum e mai bine să procedeze, cum să ascundă comoara. Arheologul a reușit să deducă din text următoarele:

a) Cele N monede, care formau averea breslei, au fost împărțite în maximum trei feluri de grămezi, formate din p1, p2 și p3 bănuți, p1, p2 și p3 fiind numere prime consecutive, p1<p2<p3. Fiecare grămadă a fost pusă în întregime într-un sipet.
b) Este posibil să existe 0 (zero) grămezi formate din p1 sau p2 sau p3 monede, scopul fiind să se obțină o împărțire în care numărul monedelor rămase nedistribuite să fie minim, iar dacă există mai multe posibilități, se alege aceea pentru care numărul de grămezi este mai mare. Dacă există mai multe astfel de soluții, se consideră corectă oricare dintre ele.
c) Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.
== Cerinţa ==
Scrieți un program care determină numărul maxim S de sipete și numărul sipetelor cu p1, p2 respectiv p3 monede, precum și suma donată bisericii.
== Date de intrare ==
Fișierul de intrare sipet.in conține pe prima linie numărul natural T, iar pe următoarele T linii câte două numerele naturale N și p1, despărțite printr-un singur spațiu.
== Date de ieșire ==
Fișierul de ieșire sipet.out va conține pe prima linie pe primele T linii câte 5 numere naturale, separate prin câte un spațiu: S, x, y, z și r, reprezentând numărul maxim S de sipete, numărul x de sipete cu p1 monede, numărul y de sipete cu p2 monede, respectiv numărul z de sipete cu p3 monede și numărul r de monede donate bisericii, corespunzătoare datelor de intrare de pe linia T+1 a fișierului sipet.in. Dacă există mai multe soluții corecte, este acceptată oricare dintre ele.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 10.000.000
* 2 ≤ p1 < p2 < p3 ≤ N
* 1 ≤ T ≤ 10 – în fișierul de intrare nu vor fi mai mult de 10 perechi de numere N p1
== Exemplu ==
; sipet.in
3
15 5
10 3
41 11
; sipet.out
3 3 0 0 0
2 1 0 1 0
3 1 1 1 0
 

== Explicație ==
* numărul maxim de sipete este 3, toate cu câte 3 monede;
* sau: 2 0 2 0 0 (1*3+1*7=2*5=10); (ambele soluții sunt corecte!)
* numărul maxim de sipete este 3; 1 sipet cu 11, unul cu 13 și unul cu 17 monede.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True

def next_prime(num):
while True:
num += 1
if is_prime(num):
return num

def main():
with open("sipet.in", "r") as fin:
T = int(fin.readline())
queries = [tuple(map(int, line.split())) for line in fin]

primes = [2, 3, 5]
results = []

for N, p1 in queries:
p2 = next_prime(p1)
p3 = next_prime(p2)

remaining_coins = N - p1 - p2 - p3

# Calculate the number of coins for each pile
x = (remaining_coins // p1) + 1
y = (remaining_coins // p2) + 1
z = (remaining_coins // p3) + 1

# Calculate the number of satchels
S = min(x, y, z)

# Calculate the remaining coins after distributing them into piles
remaining_coins -= (S - 1) * min(p1, p2, p3)

# Calculate the number of coins donated to the church
r = max(remaining_coins, 0)

results.append((S, x, y, z, r))

with open("sipet.out", "w") as fout:
for result in results:
fout.write(" ".join(map(str, result)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1206 - Placa

2024-06-03T17:30:27Z

AjM: Pagină nouă: == Enunt == Un gard este format din mai multe plăci dreptunghiulare. Fiecare placă este, la rândul ei, construită din NxM cărămizi. Una dintre plăci ridică o problemă, deoarece este deteriorată. Placa este reprezentată pe hârtie cu ajutorul unei matrice cu N linii și M coloane, numerotate de la 1 la N, respectiv de la 1 la M. Matricea conține doar valori 0 și 1, și respectă următoarele reguli: * un element egal cu 1 indică prezența în aceea poziție a un...

== Enunt ==
Un gard este format din mai multe plăci dreptunghiulare. Fiecare placă este, la rândul ei, construită din NxM cărămizi. Una dintre plăci ridică o problemă, deoarece este deteriorată. Placa este reprezentată pe hârtie cu ajutorul unei matrice cu N linii și M coloane, numerotate de la 1 la N, respectiv de la 1 la M. Matricea conține doar valori 0 și 1, și respectă următoarele reguli:

* un element egal cu 1 indică prezența în aceea poziție a unei cărămizi, iar un element egal cu 0 indică absența ei;
* linia 1 și linia N conțin numai valori egale cu 1, pentru că marginea de sus și cea de jos a plăcii este intactă;
* din orice element egal cu 1, situat în interiorul matricei, se poate ajunge pe linia 1 sau pe linia N sau pe amândouă, mergând doar în sus sau doar în jos, parcurgând numai valorile egale cu 1;
* există cel puțin o coloană stabilă (formată numai din elemente egale cu 1).
Se dorește modificarea plăcii și pentru aceasta se pot șterge din matrice maximum K coloane alăturate. După ștergere se alipesc coloanele rămase și se deplasează pe verticală partea de sus a plăcii spre cea de jos, până când se va forma o coloană stabilă.
== Cerinţa ==
Să se determine înălțimea minimă Hmin pe care o poate avea placa ștergând cel mult K coloane alăturate. Identificați numărul minim de coloane alăturate care trebuie șterse pentru a obține înălțimea Hmin.
== Date de intrare ==
Din fișierul placa.in se citesc de pe prima linie 3 numere naturale N, M, K separate prin câte un spațiu, având semnificația din enunț. Pe fiecare dintre următoarele M linii ale fișierului se găsesc perechi de numere naturale N1, N2, separate printr-un spațiu. Astfel pe linia i+1 a fișierului de intrare numărul N1 reprezintă numărul de elemente de 1 situate pe coloana i, începând cu linia 1, deplasându-ne în „jos” până la întâlnirea unei valori egale cu 0, sau până se ajunge pe linia N; numărul N2 reprezintă numărul de elemente de 1 situate pe coloana i, începând cu linia N, deplasându-ne în „sus” până la întâlnirea unei valori egale cu 0, sau până se ajunge pe linia 1.
== Date de ieșire ==
În fișierul placa.out se va scrie pe prima linie înălțimea minimă cerută Hmin, iar pe a doua linie numărul minim de coloane ce trebuie eliminate pentru a obține înălțimea Hmin.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100.000; 1 ≤ M ≤ 100.000; 1 ≤ K < M;
* se garantează că pe liniile ce conțin informații referitoare la cele M coloane ale matricei există cel puțin o linie pe care se află valoarea N de 2 ori, în rest suma celor două valori este strict mai mică decât N;
* toate valorile din fișier sunt strict pozitive;
== Exemplu ==
; placa.in
5 6 3
1 1
2 1
1 2
5 5
1 3
1 1
; placa.out
3
2
 

== Explicație ==
Matricea inițială:

1 1 1 1 1 1
0 1 0 1 0 0
0 0 0 1 1 0
0 0 1 1 1 0
1 1 1 1 1 1
Înălțimea minimă este 3 și se poate obține eliminând, de exemplu, coloanele 3, 4, 5 rezultând matricea:

1 1 1
0 1 0
1 1 1
O altă modalitate de a obține aceeași înălțime dar prin ștergerea unui număr minim de coloane (4 și 5) conduce la:

1 1 1 1
0 1 1 0
1 1 1 1
== Rezolvare ==
<syntaxhighlight lang="python" line>
def can_obtain_height(board, k, height):
n, m = len(board), len(board[0])

# Numărăm coloanele consecutive cu 0 de la început și sfârșit
zeros_left = [0] * m
zeros_right = [0] * m

for j in range(m):
for i in range(n):
if board[i][j] == 1:
break
zeros_left[j] += 1

for i in range(n - 1, -1, -1):
if board[i][j] == 1:
break
zeros_right[j] += 1

# Verificăm dacă putem elimina cel mult k coloane pentru a obține înălțimea height
for j in range(1, m):
if zeros_left[j] + zeros_right[j] >= height:
continue
removed = 0
for jj in range(j, min(j + k, m)):
removed += min(zeros_left[jj], height - zeros_right[jj])
if removed > k:
break
if removed <= k:
return True
return False

def min_height(board, k):
low, high = 2, len(board)
while low < high:
mid = (low + high) // 2
if can_obtain_height(board, k, mid):
high = mid
else:
low = mid + 1
return low

def main():
with open("placa.in", "r") as fin:
N, M, K = map(int, fin.readline().split())
board = [list(map(int, fin.readline().split())) for _ in range(M)]

min_h = min_height(board, K)

removed_cols = min(K, max(0, min_h - 2))

with open("placa.out", "w") as fout:
fout.write(f"{min_h}\n")
fout.write(f"{removed_cols}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1104 - Qvect

2024-06-03T17:27:38Z

AjM: Pagină nouă: == Enunt == Se consideră N vectori cu elemente întregi, numerotați de la 1 la N, sortați crescător, fiecare vector având un număr precizat de elemente. == Cerinţa == Să se răspundă la Q întrebări de tipul: a) 1 i j, cu semnificaţia: care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu i, iar cel de al doilea element aparținând vectorului numerotat cu j ? b) 2 i j, cu semnificația: care e...

== Enunt ==
Se consideră N vectori cu elemente întregi, numerotați de la 1 la N, sortați crescător, fiecare vector având un număr precizat de elemente.
== Cerinţa ==
Să se răspundă la Q întrebări de tipul:
a) 1 i j, cu semnificaţia: care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu i, iar cel de al doilea element aparținând vectorului numerotat cu j ?
b) 2 i j, cu semnificația: care este valoarea ce se găsește pe poziția mediană în vectorul obținut prin interclasarea vectorilor având numerele de ordine i,i+1,…,j (i<j).
== Date de intrare ==
Fişierul de intrare qvect.in conţine pe prima linie două numerele naturale N Q, separate printr-un spațiu, ce reprezintă numărul de vectori, respectiv numărul de întrebări.

Pe fiecare dintre următoarele N linii se găsește descrierea unui vector sub forma: k a1 a2 … ak, unde k reprezintă numărul de elemente, iar a1 a2 … ak reprezintă elementele vectorului, separate prin câte un spațiu.

Pe fiecare dintre următoarele Q linii se găsește descrierea unei întrebări sub forma unui triplet de numere naturale: t i j, separate prin câte un spațiu, unde t reprezintă tipul întrebării şi poate lua numai valorile 1 sau 2, iar i și j au semnificația precizată în cerinţă.
== Date de ieșire ==
Fişierul de ieşire qvect.out va conţine Q numere întregi, câte unul pe linie, reprezentând în ordine, răspunsurile la cele Q întrebări.
== Restricţii şi precizări ==
* 1 ≤ N, i, j ≤ 100
* 1 ≤ Q ≤ 1000
* 1 ≤ t ≤ 2
* 1 ≤ k ≤ 5000
* -1 000 000 000 ≤ ap ≤ 1 000 000 000
* Prin valoarea aflată pe poziția mediană a unui vector a cu k elemente se înțelege valoarea elementului situat pe poziţia [k/2], adică partea întreagă a lui k / 2.
* 15% dintre teste vor conține numai întrebări de tipul 1
* 15% dintre teste vor conține numai întrebări de tipul 2
== Exemplu ==
; qvect.in
3 3
7 1 4 5 8 11 18 19
6 2 4 5 10 21 29
4 13 14 15 15
2 2 3
1 2 3
2 1 3
; qvect.out
13
3
10
 

== Explicație ==
Prima întrebare este de tipul 2. Vectorul nou obținut prin interclasarea vectorilor numerotați cu 2 și cu 3 este următorul: 2,4,5,10,13,14,15,15,21,29 și conține 6+4=10 elemente, valoarea elementului median este 13

A doua întrebare este de tipul 1. Diferența minimă se obține pentru perechea (10,13), unde valoarea 10 aparține vectorului numerotat cu 2, iar valoarea 13 aparține vectorului numerotat cu 3.

A treia întrebare este de tipul 2. Poziția mediană în vectorul nou obținut prin interclasare este (7+6+4)/2 = 8, deci valoarea ce se găsește pe poziția mediană este 10.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def find_min_difference(vector1, vector2):
min_diff = float('inf')
i, j = 0, 0
while i < len(vector1) and j < len(vector2):
diff = abs(vector1[i] - vector2[j])
min_diff = min(min_diff, diff)
if vector1[i] < vector2[j]:
i += 1
else:
j += 1
return min_diff

def merge_and_find_median(vector1, vector2):
merged_vector = []
i, j = 0, 0
while i < len(vector1) and j < len(vector2):
if vector1[i] < vector2[j]:
merged_vector.append(vector1[i])
i += 1
else:
merged_vector.append(vector2[j])
j += 1
merged_vector.extend(vector1[i:])
merged_vector.extend(vector2[j:])
median_index = len(merged_vector) // 2
return merged_vector[median_index]

def main():
with open("qvect.in", "r") as fin:
N, Q = map(int, fin.readline().split())
vectors = [list(map(int, fin.readline().split()))[1:] for _ in range(N)]
queries = [tuple(map(int, fin.readline().split())) for _ in range(Q)]

with open("qvect.out", "w") as fout:
for query in queries:
t, i, j = query
if t == 1:
min_diff = find_min_difference(vectors[i-1], vectors[j-1])
fout.write(f"{min_diff}\n")
elif t == 2:
median = merge_and_find_median(vectors[i-1], vectors[j-1])
fout.write(f"{median}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3562 - Momente

2024-06-03T17:23:07Z

AjM: /* Rezolvare */

== Enunt ==
G are un ceas digital care afișează ora printr-o valoare între 0 și 23 sub forma unui număr de una sau două
cifre, minutul printr-o valoare între 0 și 59 sub forma unui număr de exact două cifre (prima cifră este 0 dacă numărul de minute care trebuie afișat este mai mic decât 10) și secunda printr-o valoare între 0 și 59 sub forma unui număr de exact două cifre (dacă numărul de secunde care trebuie afișat este mai mic decât 10, atunci prima cifră este 0). Aceste informaţii apar în ordinea: numărul de ore, numărul de minute, numărul de secunde şi sunt separate prin câte un spaţiu. Exemple: 23 39 17(pentru ora 23, 39 minute şi 17 secunde), 1 00 01(pentru ora 1, 0 minute şi o secundă) sau 0 02 02(pentru ora 0, 2 minute şi 2 secunde).

G observă că dacă alătură aceste trei valori poate construi un număr natural. Asfel, pentru exemplele de mai
sus obține numerele 233917, 10001 și respectiv 202 (Atenție! Numărul rezultat nu începe cu 0 – eventualele cifre nule aflate la începutul lui sunt eliminate!). G mai observă că există momente de timp, când numărul astfel format este un palindrom, cum este cazul celui de-al doilea şi celui de-al treilea exemplu. G denumește aceste momente de timp momente palindromice și dorește să afle câte astfel de momente sunt într-un interval de timp dat.

Un interval de timp este situat pe parcursul anului 2013 fiind precizat prin data și ora exactă când începe și
data și ora exactă când se termină. Data este precizată prin două numere care reprezintă luna și ziua, iar ora exactă sub forma afișată de ceasul digital al lui G.
== Cerinţa ==
Determinați câte momente palidromice au loc în k intervale de timp date.
== Date de intrare ==
Fișierul de intrare momente.in conține pe prima linie numărul natural k cu semnificația din enunț.

Pe fiecare dintre următoarele k linii se află câte 10 valori naturale separate prin câte un spațiu. Primele cinci numere reprezintă luna, ziua, ora, minutul și secunda când începe intervalul de timp dat. Următoarele cinci numere reprezintă luna, ziua, ora, minutul și secunda când se termină intervalul de timp dat.
== Date de ieșire ==
Fișierul de ieșire momente.out va conține pe prima linie numărul S, reprezentând suma numerelor de pe a doua linie a fișierului de intrare.
== Restricţii şi precizări ==
* k ≤ 100.000
* data de început precede data de sfârşit pentru fiecare interval de timp;
* în anul 2013 luna februarie are 28 zile;
* pentru 50% dintre teste vom avea k = 1;
* se numeşte palindrom un număr care citit de la stânga la dreapta sau de la dreapta la stânga are aceeaşi valoare;
* dacă intervalul de timp considerat începe sau se termină cu un moment palindromic, acesta este numărat.
== Exemplu ==
; momente.in
1
2 28 23 44 32 3 1 0 02 02
; momente.out
24
 

== Explicație ==
Fişierul de intrare conţine un singur interval de timp, între 28 februarie ora 23, 44 minute şi 32 secunde şi 1 martie ora 0, 2 minute şi 2 secunde. În acest interval de timp sunt 24 momente palindomice după cum urmeaza:
- în data de 28 februarie la orele 23 44 32 şi 23 55 32
- în data de 1 martie la orele 0 00 00, 0 00 01, 0 00 02, 0 00 03, 0 00 04, 0 00 05, 0 00 06, 0 00 07, 0 00 08, 0 00 09, 0 00 11, 0 00 22, 0 00 33, 0 00 44, 0 00 55, 0 01 01, 0 01 11, 0 01 21, 0 01 31, 0 01 41, 0 01 51 şi 0 02 02.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_palindrome(num):
# Convertim numărul în șir de caractere
num_str = str(num)
# Verificăm dacă șirul de caractere este egal cu oglinditul său
return num_str == num_str[::-1]

def count_palindromic_moments(start_month, start_day, start_hour, start_minute, start_second,
end_month, end_day, end_hour, end_minute, end_second):
# Inițializăm numărul de momente palindromice
count = 0

# Parcurgem intervalul de timp și numărăm momentele palindromice
for hour in range(start_hour, end_hour + 1):
for minute in range(start_minute, end_minute + 1):
for second in range(start_second, end_second + 1):
# Verificăm dacă momentul curent este palindromic
if is_palindrome(int(str(hour) + str(minute).zfill(2) + str(second).zfill(2))):
count += 1

return count

def main():
# Citim datele de intrare din fișier
with open("momente.in", "r") as fin:
k = int(fin.readline())
intervals = [tuple(map(int, fin.readline().split())) for _ in range(k)]

# Inițializăm suma momentelor palindromice
total_palindromic_moments = 0

# Calculăm numărul de momente palindromice pentru fiecare interval de timp
for interval in intervals:
total_palindromic_moments += count_palindromic_moments(*interval)

# Scriem rezultatul în fișierul de ieșire
with open("momente.out", "w") as fout:
fout.write(str(total_palindromic_moments) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3562 - Momente

2024-06-03T17:22:46Z

AjM: Pagină nouă: == Enunt == G are un ceas digital care afișează ora printr-o valoare între 0 și 23 sub forma unui număr de una sau două cifre, minutul printr-o valoare între 0 și 59 sub forma unui număr de exact două cifre (prima cifră este 0 dacă numărul de minute care trebuie afișat este mai mic decât 10) și secunda printr-o valoare între 0 și 59 sub forma unui număr de exact două cifre (dacă numărul de secunde care trebuie afișat este mai mic decât 10, atunci prima...

1781 - Intersectii

2024-06-03T17:20:52Z

AjM: Pagină nouă: == Enunt == Dreptunghiul ABCD are laturile de lungimi w şi h, numere naturale pare. Acest dreptunghi este desenat pe o foaie de matematică şi este descompus în w ∙ h pătrate de latură 1. Vârfurile A, B, C şi D sunt plasate în colţurile unor pătrate de latură 1. Se alege un punct P din interiorul dreptunghiului ABCD, situat în colţul unui pătrat de latură 1 şi se uneşte prin segmente de dreaptă cu cele patru colţuri ale dreptunghiului. Unele segmente inte...

== Enunt ==
Dreptunghiul ABCD are laturile de lungimi w şi h, numere naturale pare. Acest dreptunghi este desenat pe o foaie de matematică şi este descompus în w ∙ h pătrate de latură 1. Vârfurile A, B, C şi D sunt plasate în colţurile unor pătrate de latură 1. Se alege un punct P din interiorul dreptunghiului ABCD, situat în colţul unui pătrat de latură 1 şi se uneşte prin segmente de dreaptă cu cele patru colţuri ale dreptunghiului. Unele segmente intersectează pătrate de latură 1 în exact două puncte distincte, altele într-un singur punct.
Numim pătrat 2-intersectat, un pătrat de latură 1 intersectat de un segment în exact 2 puncte distincte.
== Cerinţa ==
Se dau două numere naturale w şi h reprezentând lungimile laturilor dreptunghiului ABCD, un număr natural n şi n numere naturale x1, x2,… xn cu propietatea din enunt. Punctul P se plasează, pe rând, în toate punctele interioare dreptunghiului ABCD care sunt colţuri ale unor pătrate de latură 1. Pentru fiecare valoare x[i] (1 ≤ i ≤ n), determinaţi numărul de segmente distincte care trec prin exact x[i] pătrate 2-intersectate.
== Date de intrare ==
Fişierul de intrare intersectii.in conţine pe prima linie trei numere naturale w, h (reprezentând dimensiunile dreptunghiului) şi n. Următoarele n linii conţin câte un număr natural x[i] cu semnificaţia de mai sus.
== Date de ieșire ==
Fişierul de ieşire intersectii.out va conţine n linii. Pe fiecare linie i va fi scris numărul de segmente care trec prin exact x[i] pătrate 2-intersectate, obţinute după plasarea punctului P în fiecare colţ al unui pătrat de latură 1 din interiorul dreptunghiului ABCD.
== Restricţii şi precizări ==
* 2 ≤ w , h ≤ 2000 numere naturale pare;
* 2 ≤ n ≤ 100000;
* punctul P se alege doar în interiorul dreptunghiului;
* pentru 40% din teste 2 ≤ w, n, h ≤ 500.
== Exemplul 1 ==
; intersectii.in
4 6 2
3
5
; intersectii.out
12
4
 

== Explicație ==
Se pot obţine 12 segmente care trec prin exact 3 pătrate 2-intersectate şi 4 segmente care trec prin exact 3 pătrate 2-intersectate.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_intersected_squares(w, h):
# Calculăm numărul de pătrate 2-intersectate pentru fiecare punct P
return (w - 1) * (h - 1) * 2

def main():
# Citim datele de intrare din fișier
with open("intersectii.in", "r") as fin:
w, h, n = map(int, fin.readline().split())
x_values = [int(fin.readline()) for _ in range(n)]

# Calculăm numărul de pătrate 2-intersectate pentru dreptunghi
num_intersected_squares = count_intersected_squares(w, h)

# Calculăm numărul de segmente care trec prin fiecare x[i] pătrate 2-intersectate
results = [x * num_intersected_squares for x in x_values]

# Scriem rezultatele în fișierul de ieșire
with open("intersectii.out", "w") as fout:
fout.write("\n".join(map(str, results)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1758 - Bile 3

2024-06-03T17:17:40Z

AjM: Pagină nouă: == Enunt == Matei a inventat un nou joc cu bile. Terenul de joc este o tablă dreptunghiulară aşezată vertical. Tabla este împărţită în m*n celule, aşezate în m linii şi n coloane. În unele dintre celule se află obstacole. De sus, din celulele aflate pe prima linie, sunt lăsate să cadă bile. Bilele cad vertical până la întâlnirea unui obstacol sau până în celula cea mai de jos din coloana pe care se află. Prima bilă care loveşte un obstacol se depla...

== Enunt ==
Matei a inventat un nou joc cu bile. Terenul de joc este o tablă dreptunghiulară aşezată vertical. Tabla este împărţită în m*n celule, aşezate în m linii şi n coloane. În unele dintre celule se află obstacole.

De sus, din celulele aflate pe prima linie, sunt lăsate să cadă bile. Bilele cad vertical până la întâlnirea unui obstacol sau până în celula cea mai de jos din coloana pe care se află. Prima bilă care loveşte un obstacol se deplasează pe orizontală în coloana alăturată din stânga, apoi îşi continuă căderea. Fiecare dintre celelalte bile care lovesc acelaşi obstacol se deplasează pe orizontală, în coloana alăturată, dar în direcţie opusă faţă de bila care a lovit acest obstacol exact înaintea lor, apoi îşi continuă căderea.
== Cerinţa ==
Cunoscând numărul de bile lăsate să cadă de pe fiecare celulă a primei linii şi poziţia obstacolelor, determinaţi numărul de bile ajunse în fiecare celulă a ultimei linii. Poziţiile obstacolelor sunt indicate prin linia şi coloana lor (colţul din stânga sus corespunde liniei 1 şi coloanei 1).
== Date de intrare ==
Fişierul bile.in conţine pe prima linie, separate prin câte un spaţiu, numerele naturale m, n şi p (numărul de linii, numărul de coloane şi numărul de obstacole). Următoarele p linii conţin câte două numere, separate de câte un spaţiu, reprezentând poziţiile celor p obstacole. Ultimele n linii conţin câte un număr natural, reprezentând numărul bilelor lansate din fiecare celulă a primei linii (începând cu prima celulă de pe linie).
== Date de ieșire ==
Fişierul de ieşire bile.out va conţine n linii cu câte un număr, acesta reprezentând numărul de bile din fiecare celulă a ultimei linii (începând cu prima celulă de pe această linie).
== Restricţii şi precizări ==
* 2 ≤ m,n ≤ 2000
* 0 ≤ p ≤ 10.000
* Se lansează maximum 1000 de bile din fiecare celulă;
* Pe prima şi ultima linie, respectiv prima şi ultima coloană, nu există obstacole;
* Nu există două obstacole alăturate pe linie, coloană sau diagonală.
== Exemplu ==
; bile.in
6 7 5
2 3
2 5
4 2
4 4
5 6
4
6
4
5
8
3
5
; bile.out
8
0
10
0
9
0
8
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def simulate_balls(m, n, p, obstacles, balls):
# Inițializăm matricea pentru terenul de joc
board = [[0] * n for _ in range(m)]

# Adăugăm obstacolele pe tablă
for obstacle in obstacles:
x, y = obstacle
board[x - 1][y - 1] = 1

# Inițializăm vectorul pentru bilele lăsate să cadă de pe prima linie
first_row_balls = balls

# Iterăm prin fiecare coloană, de la stânga la dreapta
for j in range(n):
# Numărăm câte bile au ajuns în fiecare celulă de pe ultima linie
for i in range(m):
if i == m - 1:
# Dacă suntem pe ultima linie, adăugăm numărul de bile lăsate să cadă din coloana j
board[i][j] += first_row_balls[j]
else:
# Dacă nu suntem pe ultima linie, simulăm căderea bilelor
if board[i][j] > 0:
# Bila va cădea în jos până întâlnește un obstacol sau ajunge pe ultima linie
k = i + 1
while k < m and board[k][j] == 0:
k += 1
# Dacă am întâlnit un obstacol, bilele se vor deplasa pe orizontală
if k < m:
if j > 0 and board[k][j - 1] == 1:
board[k][j - 1] += board[i][j]
if j < n - 1 and board[k][j + 1] == 1:
board[k][j + 1] += board[i][j]
else:
# Dacă am ajuns pe ultima linie, adăugăm bilele în acea celulă
board[k - 1][j] += board[i][j]

# Extragem numărul de bile din fiecare celulă de pe ultima linie
last_row_balls = board[-1]

return last_row_balls

def main():
# Citim datele de intrare din fișier
with open("bile.in", "r") as fin:
m, n, p = map(int, fin.readline().split())
obstacles = [tuple(map(int, fin.readline().split())) for _ in range(p)]
balls = [int(fin.readline()) for _ in range(n)]

# Simulăm căderea bilelor
last_row_balls = simulate_balls(m, n, p, obstacles, balls)

# Scriem rezultatul în fișierul de ieșire
with open("bile.out", "w") as fout:
fout.write("\n".join(map(str, last_row_balls)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3577 - Origami 1

2024-06-03T17:14:03Z

AjM: Pagină nouă: == Enunt == Costel este pasionat de arta orientală a confecţionării obiectelor de hârtie, origami, dar este abia la început şi trebuie să se familiarizeze cu operaţiile de îndoire corectă a hârtiei. El are la dispoziţie o foaie de hârtie pătrată, ruptă dintr-un caiet de matematică, având dimensiunea de exact N x N pătrăţele. Îndoiturile trebuie realizate exact pe o linie orizontală sau verticală. Sunt permise două tipuri de îndoituri: îndoitura de...

== Enunt ==
Costel este pasionat de arta orientală a confecţionării obiectelor de hârtie, origami, dar este abia la început şi trebuie să se familiarizeze cu operaţiile de îndoire corectă a hârtiei. El are la dispoziţie o foaie de hârtie pătrată, ruptă dintr-un caiet de matematică, având dimensiunea de exact N x N pătrăţele. Îndoiturile trebuie realizate exact pe o linie orizontală sau verticală.
Sunt permise două tipuri de îndoituri:

îndoitura de tipul 1, îndoitură verticală executată la X pătrăţele faţă de marginea stângă a foii: partea din stânga a foii se pliază către dreapta, de-a lungul liniei verticale aflate la distanţa de X pătrăţele faţă de marginea stângă;
îndoitura de tipul 2, îndoitură orizontală executată la X pătrăţele faţă de marginea superioară a foii: partea de sus a foii se pliază în jos, de-a lungul liniei aflate la distanţa de X pătrăţele faţă de marginea de sus a hârtiei.

În urma realizării unei succesiuni de îndoituri, din foaia iniţială de hârtie se va obţine un obiect, care va avea o formă dreptunghiulară, cu înălţimea H, lăţimea M şi având grosimea egală cu numărul maxim de foi care se suprapun în cadrul obiectului obţinut.
== Cerinţa ==
Dată fiind o succesiune de îndoituri aplicată unei foi de dimensiune N x N, scrieţi un program care să determine înălţimea, lăţimea şi grosimea obiectului obţinut.
== Date de intrare ==
Fişierul de intrare origami1.in are următoarea structură :

* prima linie a fişierului conţine un număr natural N, reprezentând dimensiunea iniţială a hârtiei;
a doua linie conţine un număr natural K, reprezentând numărul îndoiturilor;
* pe următoarele K linii se găsesc perechi de numere naturale nenule, A B, separate printr-un spaţiu, reprezentând tipul îndoiturii ( A este 1 dacă se realizează o îndoitură verticală sau A este 2 dacă se realizează o îndoitură orizontală), respectiv la ce distanţă se realizează îndoitura;
== Date de ieșire ==
Fişierul de ieşire origami1.out va conţine, pe o singură linie, trei numere naturale nenule H, L, G, separate prin câte un spaţiu, reprezentând înălţimea, lăţimea şi respectiv grosimea obiectului obţinut.
== Restricţii şi precizări ==
* 2 ≤ N ≤ 170
* 1 ≤ K ≤ 2N-2
* A = 1 sau A = 2
* 1 ≤ B < înălţimea sau lăţimea hârtiei la momentul respectiv (funcţie de tipul îndoiturii)
== Exemplu ==
; origami1.in
4
3
1 3
2 3
1 1
; origami1.out
3 2 6
 

== Explicație ==
Hârtia are 4 unităţi înălţime şi 4 unităţi lăţime. Prima îndoitură se realizează de la stânga la dreapta, de-a lungul celei de-a treia linii verticale faţă de marginea stângă a foii. Se obţine o foaie de înălţime 4, lăţime 3 şi grosime 2. A doua îndoitură se realizează îndoind partea superioară a foii, în jos, de-a lungul celei de-a treia linii orizontale faţă se marginea de sus a foii. Se obţine un obiect de înălţime 3, lăţime 3 şi grosime 4. După a treia îndoitură se obţine obiectul final, având înălţimea 3, lăţimea 2 şi grosimea 6.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def fold_paper(N, K, folds):
height = N
width = N
thickness = 1

for fold_type, position in folds:
if fold_type == 1:
# Îndoitură verticală
width = min(position, N - position)
thickness *= 2
elif fold_type == 2:
# Îndoitură orizontală
height = min(position, N - position)
thickness *= 2

return height, width, thickness

def main():
with open("origami1.in", "r") as fin:
N = int(fin.readline())
K = int(fin.readline())
folds = [list(map(int, fin.readline().split())) for _ in range(K)]

height, width, thickness = fold_paper(N, K, folds)

with open("origami1.out", "w") as fout:
fout.write(f"{height} {width} {thickness}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3573 - Joc 11

2024-06-03T17:10:19Z

AjM: Pagină nouă: == Enunt == Pentru un concurs de design de jocuri, Gigel vrea să construiască un joc. La joc participă n concurenţi numerotaţi de la 1 la n. Fiecare concurent are la dispoziţie câte un şir de m încăperi, numerotate de la 1 la m. Scopul jocului este de a găsi o comoară ascunsă în una din aceste încăperi. Fiecare încăpere conţine un cod, număr natural, fie egal cu 0, fie având cel puţin 2 cifre. Ultima cifră indică numărul de etape de penalizare, adică...

== Enunt ==
Pentru un concurs de design de jocuri, Gigel vrea să construiască un joc. La joc participă n concurenţi numerotaţi de la 1 la n. Fiecare concurent are la dispoziţie câte un şir de m încăperi, numerotate de la 1 la m. Scopul jocului este de a găsi o comoară ascunsă în una din aceste încăperi. Fiecare încăpere conţine un cod, număr natural, fie egal cu 0, fie având cel puţin 2 cifre. Ultima cifră indică numărul de etape de penalizare, adică numărul de etape în care concurentul nu are voie să părăsească încăperea. Numărul obţinut prin eliminarea ultimei cifre a codului indică numărul încăperii în care se va deplasa acesta la următoarea etapă sau la expirarea penalizării.

Există două excepţii de la regula de definire a codului: numărul 9999 codifică o încăpere conţinând o comoară, iar numărul 0 o încăpere conţinând o capcana.

În etapa 1 fiecare jucător intră în încăperea 1 din şirul său de încăperi. În funcţie de codul găsit în încăpere sunt posibile următoarele situaţii:

* codul găsit este 9999 ceea ce înseamnă că jucătorul este câştigător şi jocul se încheie la finalul acestei etape;
* codul găsit este 0 ceea ce duce la eliminarea sa din joc;
* pentru celelalte coduri, după efectuarea etapelor de penalizare, jucătorul efectuează o deplasare în încăperea indicată de cod. De exemplu la întâlnirea codul 157, după efectuarea celor 7 etape de penalizare jucătorul se va deplasa în camera 15.
Trecerea de la o etapă la alta se realizează simultan pentru toţi concurenţii.
== Cerinţa ==
Fiind dat numărul n de concurenţi, numărul m de încăperi alocate fiecărui concurent, şi codurile din cele n×m încăperi să se determine câştigătorul jocului, numărul încăperii în care a găsit comoara, numărul de etape parcurse până când câştigătorul găseşte comoara precum şi numărul de concurenţi eliminaţi din joc până la etapa respectivă (inclusiv).
== Date de intrare ==
Prima linie a fişierului de intrare joc11.in conţine două numere naturale n şi m, separate printr-un spaţiu, reprezentând numărul concurenţilor, respectiv numărul încăperilor. Următoarele n linii conţin câte m numere naturale, separate prin câte un spaţiu, reprezentând codurile din fiecare încăpere.
== Date de ieșire ==
Prima linie a fişierului de ieşire joc11.out va conţine patru numere naturale separate prin câte un spaţiu, reprezentând indicele câştigătorului, numărul încăperii unde a găsit comoara, numărul etapei în care a câştigat şi respectiv numărul de concurenţi eliminaţi din joc.
== Restricţii şi precizări ==
* 1 ≤ n ≤ 400
* 1 ≤ m ≤ 900
* Pentru toate testele de intrare se garantează că există exact un câştigător.
== Exemplu ==
; joc11.in
4 8
0 9999 41 50 61 70 80 30
30 80 60 60 9999 21 40 50
20 30 40 50 61 71 81 9999
20 30 50 0 61 71 9999 41
; joc11.out
2 5 7 1
 

== Explicație ==
Câştigă jucătorul al 2-lea, după 7 etape, iar încăperea în care a găsit comoara este încăperea 5. În cele 7 etape a fost eliminat un singur concurent şi anume primul concurent.
Încăperile prin care trece jucătorul câştigător până la final sunt: 1->3->6->2->8->5
== Rezolvare ==
<syntaxhighlight lang="python" line>
def simulate_game(n, m, rooms):
winner = None
room_number = None
steps = 0
eliminated = 0

# Cream o listă de seturi pentru a memora concurenții eliminați în fiecare etapă
eliminated_each_step = [set() for _ in range(m)]

for step in range(m):
next_rooms = [0] * n # Inițializăm lista cu următoarele încăperi pentru fiecare concurent
for i in range(n):
if i in eliminated_each_step[step]:
continue # Dacă concurentul este deja eliminat în această etapă, nu facem nimic cu el

code = rooms[i][step] # Codul din încăperea curentă a concurentului

if code == 9999:
winner = i + 1
room_number = step + 1
steps = step + 1
return winner, room_number, steps, eliminated

if code == 0:
eliminated += 1
eliminated_each_step[step].add(i)
else:
next_room = int(str(code)[:-1]) # Obținem numărul următoarei încăperi
next_rooms[next_room - 1] += 1

# Actualizăm seturile de concurenți eliminați pentru etapele următoare
for i in range(n):
if next_rooms[i] > 1:
eliminated_each_step[step + 1].add(i)

return winner, room_number, steps, eliminated

def main():
with open("joc11.in", "r") as fin:
n, m = map(int, fin.readline().split())
rooms = [list(map(int, fin.readline().split())) for _ in range(n)]

winner, room_number, steps, eliminated = simulate_game(n, m, rooms)

with open("joc11.out", "w") as fout:
fout.write(f"{winner} {room_number} {steps} {eliminated}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3578 - Palind

2024-06-03T17:07:49Z

AjM: Pagină nouă: == Enunt == Ana a descoperit că are o adevărată pasiune pentru palindromuri. Un şir de numere este palindrom dacă se citeşte la fel de la stânga la dreapta şi de la dreapta la stânga (primul număr este egal cu ultimul, al doilea cu penultimul etc). Ea are un şir cu N numere naturale şi vrea ca orice subsecvenţă de lungime impară a şirului să fie palindrom. Pentru a-şi îndeplini dorinţa ea poate efectua asupra şirului mai multe operaţii. O operaţie const...

== Enunt ==
Ana a descoperit că are o adevărată pasiune pentru palindromuri. Un şir de numere este palindrom dacă se citeşte la fel de la stânga la dreapta şi de la dreapta la stânga (primul număr este egal cu ultimul, al doilea cu penultimul etc). Ea are un şir cu N numere naturale şi vrea ca orice subsecvenţă de lungime impară a şirului să fie palindrom. Pentru a-şi îndeplini dorinţa ea poate efectua asupra şirului mai multe operaţii. O operaţie constă în alegerea unui element din şir şi incrementarea sau decrementarea lui cu o unitate. Bineînţeles, Ana doreşte să utilizeze un număr minim de operaţii pentru ca şirul obţinut să respecte proprietatea amintită mai sus (orice subsecvenţă de lungime impară să fie palindrom).
== Cerinţa ==
Determinaţi pentru Ana numărul minim de operaţii pe care trebuie să-l efectueze pentru ca orice subsecvenţă de lungime impară a şirului obţinut în urma efectuării operaţiilor să fie palindrom. De asemenea aflaţi şi numărul de şiruri finale distincte pe care le poate obţine efectuând acest numar minim de operaţii.
== Date de intrare ==
Fişierul de intrare palind.in va conţine pe prima linie numărul T, reprezentând numărul de seturi de date de intrare care urmează. În continuare urmează seturile de date de intrare, fiecare pe câte două linii. Pe prima linie a unui set de date se află numărul N, având semnificaţia din enunţ. Pe următoarea linie se află elementele şirului iniţial, separate prin câte un spaţiu.
== Date de ieșire ==
Fişierul de ieşire palind.out va conţine T linii, pe linia i aflându-se două numere, reprezentând raspunsul pentru al i-lea set de date de intrare. Primul numar este numarul minim de operaţii, iar al doilea numărul de şiruri distincte finale care se pot obţine efectuând numărul minim de operaţii.
== Restricţii şi precizări ==
* 1 ≤ T ≤ 20
* 1 ≤ N ≤ 10.000
* Elementele şirului sunt numere naturale din intervalul [1, 7.000]
* subsecvenţă a unui şir este un subşir de numere care apar pe poziţii consecutive
* Toate testele folosite la corectare vor avea T = 20
* Pentru 20% din teste 1 ≤ N ≤ 100
* Pentru 20% din teste valoarea maximă din oricare şir este cel mult 500 şi N ≥ 101
== Exemplu ==
; palind.in
2
3
1 2 3
1
3
; palind.out
2 3
0 1
 

== Explicație ==
entru primul test, cele trei șiruri posibile sunt: 1 2 1, 2 2 2 și 3 2 3. Pentru al doilea test, singurul șir posibil este format din elementul 3.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def min_operations_and_unique_sequences(N, sequence):
min_operations = 0
unique_sequences = set()

for i in range(N // 2):
diff = abs(sequence[i] - sequence[N - i - 1])
min_operations += diff

# Actualizăm numărul de șiruri unice posibile
unique_sequences.add(sequence[i] + min_operations)
unique_sequences.add(sequence[N - i - 1] + min_operations)

if N % 2 == 1:
# Dacă lungimea șirului este impară, trebuie să tratăm mijlocul separat
middle_number = sequence[N // 2]
unique_sequences.add(middle_number + min_operations)

return min_operations, len(unique_sequences)

def main():
with open("palind.in", "r") as fin:
T = int(fin.readline())
results = []

for _ in range(T):
N = int(fin.readline())
sequence = list(map(int, fin.readline().split()))

min_ops, unique_seqs = min_operations_and_unique_sequences(N, sequence)
results.append((min_ops, unique_seqs))

with open("palind.out", "w") as fout:
for min_ops, unique_seqs in results:
fout.write(f"{min_ops} {unique_seqs}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2250 - Fact

2024-06-03T17:05:53Z

AjM: Pagină nouă: == Enunt == Pentru un număr natural nenul, definim factorialul său ca fiind produsul tuturor numerelor naturale nenule mai mici sau egale decât el şi îl notăm N! (adică N! = 1*2*…*N). Pentru o bază de numeraţie B şi un număr natural nenul N, se cere determinarea ultimei cifre nenule a scrierii în baza B a lui N!. == Cerinţa == Se citesc 5 perechi de forma (Ni, Bi), unde 1 ≤ i ≤ 5. Pentru fiecare din cele 5 perechi citite, aflați ultima cifră nenulă a scr...

== Enunt ==
Pentru un număr natural nenul, definim factorialul său ca fiind produsul tuturor numerelor naturale nenule mai mici sau egale decât el şi îl notăm N! (adică N! = 1*2*…*N). Pentru o bază de numeraţie B şi un număr natural nenul N, se cere determinarea ultimei cifre nenule a scrierii în baza B a lui N!.
== Cerinţa ==
Se citesc 5 perechi de forma (Ni, Bi), unde 1 ≤ i ≤ 5. Pentru fiecare din cele 5 perechi citite, aflați ultima cifră nenulă a scrierii în baza Bi a factorialului numărului Ni.
== Date de intrare ==
Fișierul de intrare fact.in conţine 5 linii, pe fiecare dintre ele fiind scrise câte două numere naturale nenule Ni şi Bi, scrise în baza 10, despărţite printr-un spaţiu.
== Date de ieșire ==
Fișierul de ieșire fact.out va conţine 5 linii. Pe linia i se va afla cifra corespunzătoare unei perechi (Ni, Bi), citită de pe linia i din fişierul de intrare.
== Restricţii şi precizări ==
* 1 ≤ Ni ≤ 1.000.000, pentru 1 ≤ i ≤ 5
* 2 ≤ Bi ≤ 36, pentru 1 ≤ i ≤ 5;
* în cazul în care Bi > 10, cifrele mai mari decât 9 vor fi reprezentate prin litere mari ale alfabetului englez (10='A', 11='B', …, 35='Z');
* un test va fi punctat doar dacă toate cele cinci rezultate cerute sunt corecte.
== Exemplu ==
; fact.in
5 10
7 10
7 20
8 16
9 8
; fact.out
2
4
C
8
6
 

== Explicație ==
5!=120, în baza 10, deci ultima cifră nenulă este 2
7!=5040, în baza 10, deci ultima cifră nenulă este 4
7!=CC0, în baza 20, deci ultima cifră nenulă este C
8!= 9D80, în baza 16, deci ultima cifră nenulă este 8
9!=1304600, în baza 8, deci ultima cifră nenulă este 6
== Rezolvare ==
<syntaxhighlight lang="python" line>
def last_nonzero_digit_factorial(N, B):
# Calculează factorialul lui N
factorial = 1
for i in range(2, N + 1):
factorial *= i

# Convertim factorialul în baza B
factorial_base_B = ""
while factorial > 0:
remainder = factorial % B
if remainder >= 10:
factorial_base_B = chr(ord('A') + remainder - 10) + factorial_base_B
else:
factorial_base_B = str(remainder) + factorial_base_B
factorial //= B

# Găsim ultima cifră nenulă
for digit in reversed(factorial_base_B):
if digit != '0':
return digit

def main():
# Citim datele de intrare
with open("fact.in", "r") as fin:
pairs = [list(map(int, line.split())) for line in fin.readlines()]

# Determinăm ultima cifră nenulă pentru fiecare pereche
results = [last_nonzero_digit_factorial(N, B) for N, B in pairs]

# Scriem rezultatele în fișierul de ieșire
with open("fact.out", "w") as fout:
for result in results:
fout.write(str(result) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1811 - Aritma

2024-06-03T17:03:34Z

AjM: Pagină nouă: == Cerinţa == Shaka, regele zuluşilor, a dat ordin să se realizeze un sistem de comunicaţii bazat pe tobe (tamtam)care să acopere întreaga ţară. Pentru aceasta el a dispus instruirea celor ce vor urma să transmită mesajele. Problema intervenită este aceea că o parte din cursanţi nu pot face distincţie între sunete şi nu pot reda cu fidelitate succesiunea de sunete pe hârtie. S-a făcut următoarea convenţie de notare: un sunet lung va fi reprezentat prin +,...

== Cerinţa ==
Shaka, regele zuluşilor, a dat ordin să se realizeze un sistem de comunicaţii bazat pe tobe (tamtam)care să acopere întreaga ţară. Pentru aceasta el a dispus instruirea celor ce vor urma să transmită mesajele. Problema intervenită este aceea că o parte din cursanţi nu pot face distincţie între sunete şi nu pot reda cu fidelitate succesiunea de sunete pe hârtie. S-a făcut următoarea convenţie de notare: un sunet lung va fi reprezentat prin +, unul scurt prin -, iar unul nedecis (receptorul nu e sigur de lungimea sunetului) prin *.

Spre finalul stagiului Shaka a mers să verifice nivelul de pregătire al cursanţilor. Pentru aceasta el a adunat n cursanţi pe care i-a pus să recepţioneze şi să noteze un mesaj format din m sunete. După transmiterea mesajului s-a constatat că mulţi dintre cursanţi au scris şiruri foarte diferite, ceea ce ducea la o alterare semnificativă a mesajului original, chiar dacă nici cel mai slab pregătit cursant nu a fost indecis la mai mult de jumătate din sunete. Supărat Shaka l-a chemat pe instructorul şef şi, ca să-l pedepsească, i-a cerut ca să determine câte mesaje distincte se pot forma din şirurile scrise de cursanţi.

Scrieţi un program care determină numărul de mesaje distincte rezultate.
== Date de intrare ==
Fişierul aritma.in conţine pe prima sa linie numerele n şi m separate prin spaţiu, iar pe următoarele n linii şiruri de caractere de lungime m formate numai din simbolurile +, - sau *.
== Date de ieșire ==
Pe prima linie a fişierului aritma.out se va scrie numărul de mesaje distincte.
== Restricţii şi precizări ==
* 1 < n < 25
* 1 < m < 19
== Exemplu ==
; aritma.in
3 3
+-*
+*+
-*+
; aritma.out
5
 

== Explicație ==
Mesajele rezultate sunt: +--, +-+, +++, +-+, --+, -++. Primele două mesaje sunt rezultate din prima identificare, următoarele două sunt din a doua identificare şi ultimele două din ultimul şir; numai cinci sunt distincte.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def distinct_messages(strings):
def backtrack(index):
if index == len(strings[0]):
messages.add("".join(message))
return

# Dacă sunetul este cunoscut, îl adăugăm în mesaj
if all(s[index] != '*' for s in strings):
message.append(strings[0][index])
backtrack(index + 1)
message.pop()

# Dacă sunetul este incert, încercăm toate posibilitățile
elif any(s[index] == '*' for s in strings):
for sound in ['+', '-', '*']:
message.append(sound)
backtrack(index + 1)
message.pop()

messages = set()
message = []
backtrack(0)
return len(messages)

def main():
# Citim datele de intrare
with open("aritma.in", "r") as fin:
n, m = map(int, fin.readline().split())
strings = [fin.readline().strip() for _ in range(n)]

# Determinăm numărul de mesaje distincte
result = distinct_messages(strings)

# Scriem rezultatul în fișierul de ieșire
with open("aritma.out", "w") as fout:
fout.write(str(result) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1704 - Cercetasi

2024-06-03T17:02:01Z

AjM: Pagină nouă: == Enunt == Un grup de N cercetași, numerotați de la 1 la N, se află în tabără la munte. Pentru ei, organizatorii au pregătit N scaune, de asemenea numerotate de la 1 la N, așezate în cerc, astfel încât fiecare cercetaș să aibă locul său (locul cercetașului i este pe scaunul i, 1≤i≤N). Pentru desfășurarea următoarei activități, organizatorii au decis ca M dintre cercetași să prezinte diferite exerciții. Numărul M este egal cu cea mai mare putere...

== Enunt ==
Un grup de N cercetași, numerotați de la 1 la N, se află în tabără la munte. Pentru ei, organizatorii au pregătit N scaune, de asemenea numerotate de la 1 la N, așezate în cerc, astfel încât fiecare cercetaș să aibă locul său (locul cercetașului i este pe scaunul i, 1≤i≤N).

Pentru desfășurarea următoarei activități, organizatorii au decis ca M dintre cercetași să prezinte diferite exerciții. Numărul M este egal cu cea mai mare putere a lui 2 cu proprietatea că numărul N de cercetași aflați în tabără se poate scrie ca sumă de M numere consecutive în mulțimea numerelor impare. Cei M cercetași care vor prezenta sunt cei numerotați cu numerele impare consecutive a căror sumă este N. De exemplu, dacă N=8, atunci M este 2, iar exercițiile vor fi prezentate de cercetașii numerotați cu 3, respectiv cu 5.

Din joacă, micii cercetași s-au așezat pe scaune la întâmplare. Organizatorii au nevoie pentru a desfășura activitatea ca cel puțin cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor. Pentru aceasta, o parte dintre cercetași trebuie să-și schimbe locul și organizatorii invită micii cercetași să participe la jocul numit ”Mutare”. Acest joc se desfășoară astfel: unul dintre cercetașii care nu se află pe locul lor se ridică și merge în interiorul cercului. Cercetașul numerotat cu numărul scaunului rămas liber își va ocupa locul, iar locul ocupat de el anterior rămâne astfel liber. Jocul continuă până când scaunul cercetașului aflat în interiorul cercului se eliberează și el se așază pe locul său.
== Cerinţa ==
Fiind dat numărul N, precum și ordinea în care s-au așezat cercetașii pe scaunele numerotate de la 1 la N, scrieți un program care să determine:

* numărul M de cercetaşi care vor prezenta exerciţii în cadrul activităţii;
* numerele de identificare ale celor M cercetaşi care vor prezenta exerciţiile, în ordine strict crescătoare;
* numărul minim de cercetași care își vor schimba locul, astfel încât toţi cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor.
== Date de intrare ==
Fișierul de intrare cercetasi.in conține pe prima linie numărul natural N cu semnificația din enunț. Pe a doua linie, se află N numere naturale distincte din mulțimea {1, 2, ..., N}, separate prin spaţii, reprezentând ordinea în care s-au așezat cei N cercetași pe scaunele numerotate de la 1 la N.
== Date de ieșire ==
Fișierul de ieșire cercetasi.out va conține 3 linii. Pe prima linie se va scrie un singur număr natural reprezentând numărul M de cercetași care vor prezenta exercițiile. Pe a doua linie se vor scrie M numere naturale, în ordine strict crescătoare, separate prin câte un spaţiu, reprezentând cercetașii care vor prezenta exercițiile. Pe a treia linie se va scrie un număr natural, reprezentând numărul minim de cercetași care își vor schimba locul.
== Restricţii şi precizări ==
* 0 < N ≤ 10000 şi N∉ {x ∈ ℕ | x=4*k+2, k∈ ℕ}
* Un joc ”Mutare” odată început, se va încheia doar atunci când cercetașul din interiorul cercului se așază pe locul său.
== Exemplu ==
; cercetasi.in
8
2 3 4 1 5 8 6 7
; cercetasi.out
2
3 5
4
 

== Explicație ==
Dacă N=8, atunci M este 2, iar exercițiile vor fi prezentate de cercetașii numerotați cu 3, respectiv cu 5.

Cercetașul cu numărul 3 nu se află pe locul său și va trece în interiorul cercului, astfel scaunul cu numărul 2 rămâne liber. Cercetașul cu numărul 2 își ocupă locul și rămâne liber scaunul cu numărul 1. Cercetașul cu numărul 1 își ocupă locul și rămâne liber scaunul cu numărul 4. Cercetașul cu numărul 4 își ocupă locul și rămâne liber scaunul cu numărul 3 și astfel cercetașul aflat în interiorul cercului se poate așeza pe locul său. In cadrul acestui joc ”Mutare” și-au schimbat locul 4 cercetași. Cum cercetașul cu numărul 5 se află deja pe locul său, numărul de cercetași care își schimbă locul rămâne 4.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def find_presenters(N, seats):
# Cautăm cel mai mare M astfel încât suma primelor M numere impare să fie mai mică sau egală cu N
M = 1
while M * (M + 1) <= 2 * N:
M += 2

# Identificăm cercetașii care vor prezenta exercițiile
presenters = [i for i in range(1, N + 1) if i % 2 != 0]

# Numărăm câți dintre aceștia sunt deja pe locurile lor
presenters_on_seats = sum(1 for i, s in enumerate(seats) if s == presenters[i])

# Calculăm câți cercetași trebuie să își schimbe locul
moves = 0
for i in range(N):
if seats[i] != presenters[i]:
moves += 1

return M // 2, presenters, moves

def main():
# Citim datele de intrare
with open("cercetasi.in", "r") as fin:
N = int(fin.readline())
seats = list(map(int, fin.readline().split()))

# Găsim prezentatorii și numărul minim de mutări necesare
M, presenters, moves = find_presenters(N, seats)

# Scriem rezultatele în fișierul de ieșire
with open("cercetasi.out", "w") as fout:
fout.write(f"{M}\n")
fout.write(" ".join(map(str, presenters)) + "\n")
fout.write(f"{moves}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3015 - Fibo Interval

2024-06-03T16:58:48Z

AjM: Pagină nouă: == Cerinţa == Se dă șirul lui Fibonacci: f1=1, f2=1, f3=2, f4=3, f5=5, …, definit astfel fk+2 = fk+1 + fk, k>2. Se dau Q query-uri de forma ab. Se cere să se afișeze pentru fiecare query fa, fb și suma elementelor fk din șirul lui Fibonacci cu a≤k≤b. == Date de intrare == Fișierul de intrare fibointerval.in conține pe prima linie numerele n si Q, iar pe următoarele Q linii câte două numere a si b reprezentând query-urile. == Date de ieșire == Fișierul de...

== Cerinţa ==
Se dă șirul lui Fibonacci: f1=1, f2=1, f3=2, f4=3, f5=5, …, definit astfel fk+2 = fk+1 + fk, k>2.

Se dau Q query-uri de forma ab. Se cere să se afișeze pentru fiecare query fa, fb și suma elementelor fk din șirul lui Fibonacci cu a≤k≤b.
== Date de intrare ==
Fișierul de intrare fibointerval.in conține pe prima linie numerele n si Q, iar pe următoarele Q linii câte două numere a si b reprezentând query-urile.
== Date de ieșire ==
Fișierul de ieșire fibointerval.out va conține pe fiecare linie, în ordine, rezultatul celor Q query-uri, cele 3 valori care trebuie afișate fiind separate prin câte un spațiu.
== Restricţii şi precizări ==
* 1 ≤ n ≤ 1000
* 1 ≤ Q ≤ 10000
* 1 ≤ a ≤ b ≤ n
== Exemplu ==
; fibointerval.in
10 3
1 3
3 5
2 8
; fibointerval.out
1 2 4
2 5 10
1 21 53
 

== Explicație ==
n=10 și Q=3.
Primul query: a=1, b=3, rezultă că f1=1, f3=2, iar suma elementelor cu indici cuprinși intre a și b este 4.Al doilea query: a=3, b=5, rezultă că f3=2, f5=5, iar suma elementelor cu indici cuprinși intre a și b este 10.Al treilea query: a=2, b=8, rezultă că f2=1, f8=21, iar suma elementelor cu indici cuprinși intre a și b este 53.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def generate_fibonacci(n):
fibonacci = [1, 1]

for i in range(2, n):
fibonacci.append(fibonacci[i-1] + fibonacci[i-2])

return fibonacci

def main():
with open("fibointerval.in", "r") as fin:
n, Q = map(int, fin.readline().split())
queries = [tuple(map(int, fin.readline().split())) for _ in range(Q)]

fibonacci = generate_fibonacci(n)

with open("fibointerval.out", "w") as fout:
for a, b in queries:
fa = fibonacci[a - 1]
fb = fibonacci[b - 1]
fib_sum = sum(fibonacci[a - 1:b])
fout.write(f"{fa} {fb} {fib_sum}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2458 - Hobby

2024-06-03T16:55:45Z

AjM: Pagină nouă: == Enunt == În școala lui Gigel copiii se pregătesc pentru vacanță. Ei vor să-și petreacă timpul liber în mod diferit în funcție de hobby-urile pe care le au. În concluzie, urmează să formeze grupuri, pe baza preferințelor. Totuși, a apărut o problemă. Unii sunt dispuși să renunțe la propriul hobby și preferă să facă parte dintr-un grup din care face parte și un anumit prieten al lor. În școala lui Gigel sunt n copii, numerotați de la 1 la n. == C...

== Enunt ==
În școala lui Gigel copiii se pregătesc pentru vacanță. Ei vor să-și petreacă timpul liber în mod diferit în funcție de hobby-urile pe care le au. În concluzie, urmează să formeze grupuri, pe baza preferințelor. Totuși, a apărut o problemă. Unii sunt dispuși să renunțe la propriul hobby și preferă să facă parte dintr-un grup din care face parte și un anumit prieten al lor. În școala lui Gigel sunt n copii, numerotați de la 1 la n.
== Cerinţa ==
Cunoscând prietenul preferat și hobby-ul fiecărui copil, scrieți un program care determină numărul grupurilor care se vor forma și numărul grupurilor formate din copii care au hobby-uri identice; doi copii vor face parte din același grup, dacă cel puțin unul din cei doi l-a numit pe celălalt ca prieten.
== Date de intrare ==
Pe prima linie a fișierului de intrare hobby1.in se află un număr natural n, reprezentând numărul copiilor. Pe fiecare din următoarele n linii se află câte o pereche de numere naturale, unde primul număr reprezintă numărul de ordine al copilului având ca prieten preferat copilul identificat cu cel de al doilea număr. Pe următoarele n linii se află, pe fiecare, câte un șir de caractere format din litere mici ale alfabetului englez, reprezentând hobby-urile copiilor în ordinea în care sunt numerotați copiii.
== Date de ieșire ==
Pe prima linie a fișierului de ieșire hobby1.out veți scrie numărul gr al grupurilor de copii. Pe următoarea linie veți afișa numărul grupurilor în care toți copiii au același hobby.
== Restricţii şi precizări ==
* 1 ≤ n ≤ 700.
* 1 ≤ lungime_denumire_hobby ≤ 10.
* 1 ≤ gr ≤ 400.
* numărul de ordine al fiecărui copil apare o singură dată pe prima poziție a unei perechi.
* un copil poate fi prietenul mai multor copii.
* numărul maxim al hobby-urilor: 20.
* La concurs s-au dat 10 puncte din oficiu, aici sunt date pe exemplu.
== Exemplu ==
; hobby.in
8
1 2
3 4
5 6
7 7
8 3
2 1
4 3
6 2
baschet
baschet
tenis
fotbal
baschet
baschet
muzica
tenis
; hobby.out
3
2
 

== Explicație ==
Avem 3 grupuri:
1: 1 2 5 6
2: 7
3: 3 4 8
Toți copiii din primul grup (cu numerele de ordine 1 2 5 6) au ca hobby baschetul, copilul 7 este singur, iar în al treilea grup hobby-urile diferă. Deci avem 2 grupuri în care copiii au același hobby.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def form_groups(n, preferences, hobbies):
groups = {} # Dicționar pentru a înregistra grupurile

for i in range(1, n+1):
friend = preferences[i]
hobby = hobbies[i]

# Verificăm dacă prietenul preferat este deja într-un grup
if friend in groups:
# Adăugăm copilul curent în grupul prietenului său
groups[friend].append(i)
groups[i] = groups[friend] # Actualizăm grupul pentru copilul curent
else:
# Creăm un nou grup pentru ei
groups[i] = [i]

return groups

def count_same_hobbies(groups, hobbies):
same_hobby_groups = 0

for group in groups.values():
# Verificăm dacă toți copiii din grup au același hobby
same_hobby = all(hobbies[child] == hobbies[group[0]] for child in group)
if same_hobby:
same_hobby_groups += 1

return same_hobby_groups

def main():
with open("hobby.in", "r") as fin:
n = int(fin.readline())
preferences = {}
hobbies = {}

for _ in range(n):
child, friend = map(int, fin.readline().split())
preferences[child] = friend

for _ in range(n):
hobbies[i] = fin.readline().strip()

# Formăm grupurile
groups = form_groups(n, preferences, hobbies)

# Numărăm grupurile cu aceleași hobby-uri
same_hobby_groups = count_same_hobbies(groups, hobbies)

# Scriem rezultatul în fișierul de ieșire
with open("hobby.out", "w") as fout:
fout.write(str(len(groups)) + "\n")
fout.write(str(same_hobby_groups) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1119 - Permutare 1

2024-06-03T16:51:05Z

AjM: Pagină nouă: == Enunt == Se dă o matrice cu m linii şi n coloane, fiecare linie reprezentând o permutare. Se ştie că liniile de la 2 la m sunt permutări circulare ale primei linii. Unei linii x (1 ≤ x ≤ m) i se pot aplica următoarele operaţii: * o permutare circulară la stânga: elementul de pe poziţia i (1 < i ≤ n) se mută pe poziţia i-1, mai puţin primul primul element, care devine ultimul; * o permutare circulară la dreapta: elementul de pe pozitia i (1 ≤ i < n)...

== Enunt ==
Se dă o matrice cu m linii şi n coloane, fiecare linie reprezentând o permutare. Se ştie că liniile de la 2 la m sunt permutări circulare ale primei linii. Unei linii x (1 ≤ x ≤ m) i se pot aplica următoarele operaţii:

* o permutare circulară la stânga: elementul de pe poziţia i (1 < i ≤ n) se mută pe poziţia i-1, mai puţin primul primul element, care devine ultimul;
* o permutare circulară la dreapta: elementul de pe pozitia i (1 ≤ i < n) se mută pe poziţia i+1, mai puţin ultimul element care devine primul.
Scopul este să permutăm circular liniile, la stânga sau la dreapta, astfel încât în final toate liniile să fie egale, folosind un număr minim de operaţii.
== Cerinţa ==
Dându-se o matrice cu proprietatea din enunţ se cere să se determine numărul minim de operaţii necesare pentru a ajunge la o matrice în care toate liniile sunt egale.
== Date de intrare ==
Fișierul de intrare permutare1.in conține pe prima linie două numere naturale m şi n, reprezentând numărul de linii şi numărul de coloane ale matricei. Pe a doua linie a fişierului de intrare se află n numere naturale, reprezentând permutarea de pe prima linie a matricei. Pe următoarele m-1 linii, se află câte un număr natural cuprins între 0 şi n-1. Al i-lea (0 < i < m) dintre aceste numere reprezintă numărul de poziţii cu care este permutată circular la dreapta a (i+1) -a linie faţă de linia 1.
== Date de ieșire ==
Fișierul de ieșire permutare1.out va conține pe prima linie un singur număr natural reprezentând numărul minim de operaţii necesare.
== Restricţii şi precizări ==
* 1 ≤ n, m ≤ 100 000
* Două linii dintr-un tablou sunt egale dacă elementele aflate pe aceeaşi coloană sunt egale.
== Exemplu ==
; permutare1.in
pre.6 5
3 1 4 2 6 5
1
1
3
3
; permutare1.out
5
 

== Explicație ==
Matricea va fi:

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

Dacă permutăm circular la dreapta prima linie cu o poziţie, iar liniile 4 şi 5 le permutăm la stânga cu două poziţii, vom obţine din 5 operaţii o matrice cu toate liniile egale între ele. Liniile vor fi determinate de permutarea: 5 3 1 4 2 6.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def min_operations_to_equalize_first_row(matrix, n):
first_row = matrix[0]
min_operations = n
for i in range(n):
operations = 0
for j in range(n):
if matrix[i][j] != first_row[j]:
operations += 1
min_operations = min(min_operations, operations)
return min_operations

def main():
with open("permutare1.in", "r") as fin:
m, n = map(int, fin.readline().split())
matrix = [list(map(int, fin.readline().split())) for _ in range(m-1)]

min_ops = min_operations_to_equalize_first_row(matrix, n)

with open("permutare1.out", "w") as fout:
fout.write(str(min_ops) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1692 - Calafat

2024-06-03T16:48:28Z

AjM: Pagină nouă: == Enunt == Această problemă se numește Calafat pentru că a fost compusă în timpul excursiei la Calafat de mâine. == Cerinţa == Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între doi indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st, dr], se cere să se calculeze suma distanțelor corespunzătoa...

== Enunt ==
Această problemă se numește Calafat pentru că a fost compusă în timpul excursiei la Calafat de mâine.
== Cerinţa ==
Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între doi indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st, dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.
== Date de intrare ==
Fișierul de intrare calafat.in conține pe prima linie două numere natural N și M. Pe a doua linie se vor afla cele N numere din șirul dat. Pe următoarele M linii se vor afla câte două numere st și dr, cu semnificația că vrem să calculăm suma menționată mai sus pentru subsecvența [st,dr].
== Date de ieșire ==
Fișierul de ieșire calafat.out va conține M numere naturale, câte unul pe fiecare linie, reprezentând cele M sume cerute.
== Restricţii şi precizări ==
* 1 ≤ N, M ≤ 200000
* 1 ≤ st ≤ dr ≤ N
* Valorile din șir se vor afla în intervalul [1, N]
* Pentru 20% din teste se garantează că N, M ≤ 1000
* Pentru alte 25% din teste se garantează că N, M ≤ 35 000 iar numărul de elemente distincte din șir este maxim 100.
* Pentru alte 25% din teste se garantează că N, M ≤ 70 000
== Exemplu ==
; calafat.in
7 3
1 3 1 2 2 1 3
2 4
2 7
3 6
; calafat.out
0
9
4
 

== Explicație ==
În prima subsecvență fiecare valoare apare o singură dată, deci suma diferențelor este 0.

În a doua subsecvență:

* Valoarea 3 apare la indicii 2 și 7 rezultând diferența 7-2=5
* Valoarea 1 apare la indicii 3 și 6 => diferența 6–3=3
* Valoarea 2 apare la indicii 4 și 5 => diferența 5-4=1
Suma diferențelor este 9.

În a treia subsecvență:

* Valoarea 1 apare la indicii 3 și 6 => diferența 6–3=3
* Valoarea 2 apare la indicii 4 și 5 => diferența 5-4=1
Suma diferențelor este 4.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open("calafat.in", "r") as fin:
N, M = map(int, fin.readline().split())
sequence = list(map(int, fin.readline().split()))
queries = [tuple(map(int, line.split())) for line in fin.readlines()]

with open("calafat.out", "w") as fout:
for query in queries:
st, dr = query
subsequence = sequence[st-1:dr]
distinct_values = set(subsequence)
result = calculate_distances(subsequence, distinct_values)
fout.write(str(result) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4087 - vecine

2024-06-03T16:43:08Z

AjM: Pagină nouă: == Enunt == Se dă un șir de n cifre c1, c2, …, cn, adică 0 ≤ ci ≤ 9. Dintr-un șir de cifre se poate obține un șir de 1 ≤ m ≤ n numere a1, a2, …, am astfel: * Inițial considerăm fiecare cifră un număr și obținem șirul de n numere ai = c1 * Un număr nou poate fi obținut prin lipirea unei secvențe de două sau mai multe numere vecine din șirul original. Două elemente dintr-un șir se numesc vecine dacă acestea se regăsesc în șir pe poziții al...

== Enunt ==
Se dă un șir de n cifre c1, c2, …, cn, adică 0 ≤ ci ≤ 9. Dintr-un șir de cifre se poate obține un șir de 1 ≤ m ≤ n numere a1, a2, …, am astfel:

* Inițial considerăm fiecare cifră un număr și obținem șirul de n numere ai = c1
* Un număr nou poate fi obținut prin lipirea unei secvențe de două sau mai multe numere vecine din șirul original. Două elemente dintr-un șir se numesc vecine dacă acestea se regăsesc în șir pe poziții alăturate.
* Operația de lipire de două sau mai multe numere se poate realiza de oricâte ori atât timp cât numărul obținut este mai mic sau egal cu 2.000.000.000, nu începe cu cifra 0 și există cel puțin două numere în șir.
* De exemplu șirul [3, 5, 0, 2, 7, 3] poate deveni [35, 0, 2, 73] prin lipirea numerelor 3, 5 → 35 și 7, 3 → 73, care ulterior poate deveni [3502, 73] prin lipirea numerelor 35, 0, 2 → 3502. Dar nu putem crea șirul [35, 02, 73], deoarece am avea un număr care începe cu 0.
Două numere vecine sunt consecutive dacă primul este cu 1 mai mic decât al doilea.
== Cerinţa ==
Cunoscându-se șirul de cifre inițial, să se obțină următoarele rezultate:

* Presupunând că nu se face nici o lipire de cifre, fiecare cifră devenind un număr în șir, adică ai = c1, să se determine câte perechi de numere vecine consecutive există în șir;
* Să se determine o modalitate de lipire a cifrelor astfel încât să se obțină cele mai mari două numere vecine consecutive și să se afișeze primul dintre aceste numere.
== Date de intrare ==
Fișierul de intrare vecine.in conține pe prima linie două numere p și n, p reprezentând cerința 1 sau 2, iar pe linia următoare cele n cifre, despărțite prin câte un spațiu.
== Date de ieșire ==
În fișierul de ieșire vecine.out se va afla un singur număr natural. Dacă p = 1, acesta va reprezenta răspunsul pentru cerința 1. Dacă p = 2, acesta va reprezenta răspunsul pentru cerința 2.
== Restricţii şi precizări ==
* Pentru cerința 2 se garantează că numerele ce se pot obține nu vor depăși valoarea 2.000.000.000
* Tot pentru cerința 2 se garantează existența a cel puțin o pereche de numere vecine consecutive
* Cifra 0 poate forma singură doar numărul 0.
* Două numere vecine sunt consecutive dacă primul este cu 1 mai mic decât al doilea.
* Pentru 20 de puncte p = 1 și 3 ≤ n ≤ 100.000
* Pentru 80 de puncte p = 2 și 3 ≤ n ≤ 100.000
== Exemplul 1 ==
; vecine.in
1 18
3 2 1 2 1 0 6 3 0 5 6 3 0 6 9 2 9 3
; vecine.out
2
 

== Explicație ==
Există două perechi de numere vecine consecutive formate dintr-o singură cifră: 1, 2 și 5, 6
== Exemplul 2 ==
; vecine.in
2 18
3 2 1 2 1 0 6 3 0 5 6 3 0 6 9 2 9 3
; vecine.out
6305
 

== Explicație ==
Perechea cu cele mai mari două numere vecine consecutive este 6305 și 6306. Conform cerinței s-a scris în fișier doar primul număr din pereche.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_consecutive_pairs(arr):
count = 0
for i in range(len(arr) - 1):
if abs(arr[i] - arr[i+1]) == 1:
count += 1
return count

def find_largest_consecutive_pair(arr):
max_num = arr[0]
second_max_num = arr[1]

for i in range(1, len(arr) - 1):
if abs(arr[i] - arr[i+1]) == 1:
if arr[i] > max_num:
second_max_num = max_num
max_num = arr[i]
elif arr[i] > second_max_num:
second_max_num = arr[i]

return max_num

def main():
p, n = map(int, input().split())
digits = list(map(int, input().split()))

if p == 1:
result = count_consecutive_pairs(digits)
print(result)
elif p == 2:
result = find_largest_consecutive_pair(digits)
print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3860 - consecutive1

2024-06-03T16:40:02Z

AjM: Pagină nouă: == Enunt == Se dă un șir (a[1], a[2], ..., a[n]) de numere naturale cuprinse între 1 și n. Se dau de asemenea Q interogări, fiecare prin două numere x, y: dacă s-ar ordona a[x], a[x+1], ..., a[y], se obține sau nu o secvență de numere consecutive? (De exemplu, 5,3,6,4 dacă e ordonată se obține 3,4,5,6, care este o secvență de numere consecutive). == Cerinţa == Dându-se Q întrebări, să se răspundă la acestea. La fiecare interogare, dacă prin sortare se o...

== Enunt ==
Se dă un șir (a[1], a[2], ..., a[n]) de numere naturale cuprinse între 1 și n. Se dau de asemenea Q interogări, fiecare prin două numere x, y: dacă s-ar ordona a[x], a[x+1], ..., a[y], se obține sau nu o secvență de numere consecutive? (De exemplu, 5,3,6,4 dacă e ordonată se obține 3,4,5,6, care este o secvență de numere consecutive).
== Cerinţa ==
Dându-se Q întrebări, să se răspundă la acestea. La fiecare interogare, dacă prin sortare se obține o secvență de numere consecutive veți afișa valoarea 1, iar în caz contrar veți afișa valoarea 0.
== Date de intrare ==
De la tastatură, de pe prima linie se citește numărul natural n. Pe linia a doua se află n numere naturale reprezentând elementele șirului. Pe a treia linie se află numărul Q, iar pe următoarele Q linii se găsesc câte două numere naturale x și y, 1 ≤ x ≤ y ≤ n, reprezentând câte o interogare.
== Date de ieșire ==
La ecran se vor afișa pe o singură linie, fără spații, Q cifre din mulțimea {0, 1} reprezentând răspunsurile la fiecare întrebare.
== Restricţii şi precizări ==
* Pentru 10 puncte, 3 ≤ n ≤ 50, 1 ≤ Q ≤ 100
* Pentru 30 puncte, n ≤ 300, Q ≤ 10.000
* Pentru 60 puncte, 10.000 ≤ n ≤ 100.000, Q ≤ 200.000
== Exemplu ==
; Intrare
9
4 1 3 4 2 1 6 5 4
5
1 4
3 5
3 6
5 9
7 9
; Ieșire
01101
 

== Explicație ==
Sunt 5 interogări.
Întrebarea 1: 4 1 3 4 nu obține o secvență de numere consecutive, deci răspunsul este 0.
Întrebarea 2: 3 4 2 obține o secvență de numere consecutive, deci răspunsul este 1.
Întrebarea 3: 3 4 2 1 obține o secvență de numere consecutive, deci răspunsul este 1.
Întrebarea 4: 2 1 6 5 4 nu obține o secvență de numere consecutive, deci răspunsul este 0.
Întrebarea 5: 6 5 4 obține o secvență de numere consecutive, deci răspunsul este 1.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def can_form_consecutive_sequence(arr, x, y):
sorted_arr = sorted(arr[x-1:y])
for i in range(1, len(sorted_arr)):
if sorted_arr[i] != sorted_arr[i-1] + 1:
return False
return True

def main():
n = int(input())
arr = list(map(int, input().split()))
Q = int(input())

result = ""
for _ in range(Q):
x, y = map(int, input().split())
result += "1" if can_form_consecutive_sequence(arr, x, y) else "0"

print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3778 - Pian

2024-06-03T16:38:04Z

AjM: Pagină nouă: == Enunt == Ian este un copil pasionat de muzică, așa că părinții săi i-au cumpărat de ziua lui un pian. Pianul lui Ian este mai special, acesta are N clape. Întrucât pianul nu este nou, clapele se mișcă mai greu, astfel apăsarea celei de-a i-a clape durează t[i] secunde. Deoarece Ian este foarte nerăbdător, s-a hotarât să repare clapele pianului pentru ca apăsarea unei clape să fie cât mai rapidă. Acesta poate selecta două clape vecine i și i+1 ce nec...

== Enunt ==
Ian este un copil pasionat de muzică, așa că părinții săi i-au cumpărat de ziua lui un pian. Pianul lui Ian este mai special, acesta are N clape. Întrucât pianul nu este nou, clapele se mișcă mai greu, astfel apăsarea celei de-a i-a clape durează t[i] secunde.

Deoarece Ian este foarte nerăbdător, s-a hotarât să repare clapele pianului pentru ca apăsarea unei clape să fie cât mai rapidă. Acesta poate selecta două clape vecine i și i+1 ce necesită t[i], respectiv t[i+1] secunde pentru a fi apăsate și le lustruiește. În urma lustruirii, cele două clape vor necesita doar cmmdc(t[i],t[i+1]) secunde pentru apăsarea fiecăreia. Practic, o operație va efectua următoarea transformare asupra clapelor: t[i] = t[i + 1] = cmmdc(t[i], t[i+1]).

Ian consideră ca pianul este lustruit dacă timpul de apăsare al fiecărei clape este minim posibil.
== Cerinţa ==
* Cerința 1: Ian vrea să facă un riff (adică să apese fiecare clapă o singură dată) și vrea să știe care ar fi durata de timp a unui riff pe pianul lustruit.
* Cerința 2: Pentru că Ian nu are timp de pierdut cu lustruitul, acesta vrea o listă de instrucțiuni de lungime minimă asfel încât dupa efectuarea instrucțiunilor pianul să fie lustruit.
== Date de intrare ==
Fișierul de intrare pian.in conține pe prima linie numărul C ce reprezintă cerința care trebuie rezolvată. Pe următoarea linie se află N, numărul de clape ale pianului. Pe următoarea linie se vor afla N numere separate prin câte un spațiu, al i-lea număr reprezentând durata inițială t[i] necesară pentru apăsarea clapei cu indicele i.
== Date de ieșire ==
În fișierul pian.out se vor afișa în funcție de cerință următoarele:

* Dacă C = 1, atunci fișierul va conține o singură linie cu un singur număr S, ce reprezintă răspunsul pentru prima cerință.
* Dacă C = 2, atunci fișierul va conține pe prima linie un număr M care reprezintă numarul minim de operații pe care Ian trebuie să le facă, iar pe următoarea linie M numere separate prin câte un spatiu, al i-lea număr x[i], reprezentând faptul că a i-a operație de lustruire a clapelor se va face între clapele cu indicii x[i] și x[i]+1.
== Restricţii şi precizări ==
* C ∈ {1, 2}
* 1 ≤ N ≤ 100.000
* 1 ≤ v[i] ≤ 1.000.000, pentru orice i ∈ {1, 2, ..., N}
* 1 ≤ x[j] < N, pentru orice j ∈ {1, 2, ..., M}
* Daca pentru cerința 2 există mai multe soluții cu număr minim de operații se acceptă oricare.
== Exemplul 1 ==
; pian.in
1
5
2 4 6 8 10
; pian.out
10
 

== Explicație ==
Ian poate lustrui pianul în doar 2 instrucțiuni în următorul mod:

* Aplicăm operația pe clapele 2 și 3. Obținem șirul 2 2 2 8 10
* Aplicăm operația pe clapele 4 și 5. Obținem șirul 2 2 2 2 2
În final se va obține șirul de clape: 2 2 2 2 2. Astfel, durata unui riff va fi de 10 secunde.
== Exemplul 2 ==
; pian.in
2
5
2 4 6 8 10
; pian.out
2
2 4
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
from math import gcd

def main():
C = int(input())
N = int(input())
times = list(map(int, input().split()))

if C == 1:
# Cerința 1
total_time = 0
for i in range(N):
total_time += gcd(times[i], times[i + 1]) if i < N - 1 else times[i]
print(total_time)
elif C == 2:
# Cerința 2
operations = []
for i in range(N):
if gcd(times[i], times[i + 1]) < times[i] or gcd(times[i], times[i + 1]) < times[i + 1]:
operations.append(i + 1)
print(len(operations))
print(*operations)

if __name__ == "__main__":
main()

</syntaxhighlight>

3759 - Cartita

2024-06-03T16:34:34Z

AjM: Pagină nouă: == Enunt == În grădina lui Macarie există un șir de N morcovi, numerotați de la 1 la N. Ca să știe unde sunt plantați, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov și a notat înălțimea fiecăreia exprimată în centimetri. Astfel morcovul i are în dreptul său o grămăjoară de pământ cu înălțimea de h[i] centimetri. O cârtiță neastâmpărată sapă galerii subterane pe sub morcovii lui Macarie. Când sapă o galerie c...

== Enunt ==
În grădina lui Macarie există un șir de N morcovi, numerotați de la 1 la N. Ca să știe unde sunt plantați, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov și a notat înălțimea fiecăreia exprimată în centimetri. Astfel morcovul i are în dreptul său o grămăjoară de pământ cu înălțimea de h[i] centimetri.

O cârtiță neastâmpărată sapă galerii subterane pe sub morcovii lui Macarie. Când sapă o galerie către un morcov, tot pământul rezultat îl scoate afară modificând astfel înălțimea grămăjoarei corespunzătoare acelui morcov, dar și ale celorlalți morcovi din grădină.

Dacă în urma săpării unei galerii către morcovul de pe poziția pos înălțimea grămăjoarei lui a crescut cu x centimetri, atunci înălțimile grămăjoarelor tuturor morcovilor se modifică după următoarea regulă ce depinde de un număr K:

* înălțimea grămăjoarei morcovului pos - 1 se modifică cu x - K centimetri iar a morcovului pos + 1 cu x + K centimetri,
* înălțimile gramăjoarelor morcovilor pos - 2 și pos + 2 se modifică cu x - 2 * K respectiv x + 2 * K centimetri
* În caz general, înălțimea se modifică după următoarele reguli pentru fiecare morcov din grădină:
- Înălțimea h[pos - i] devine h[pos - i] + x - i * K, pentru fiecare i, 1 ≤ i ≤ pos-1
- Înălțimea h[pos + i] devine h[pos + i] + x + i * K, pentru fiecare i, 1 ≤ i ≤ N-pos
== Cerinţa ==
Se cunosc înălțimile inițiale ale tuturor celor N grămăjoare și cele U modificări făcute de cârtiță asupra înălțimilor grămăjoarelor de pământ ale morcovilor. Știm că în cadrul unei secvențe continue de morcovi cel mai tentant pentru cârtiță este morcovul cu cea mai mică înălțime a grămăjoarei de pământ. Ajutați-l pe Macarie să identifice înălțimea grămăjoarei celui mai tentant morcov, pentru mai multe intervale date, după efectuarea tuturor modificărilor realizate de cârtiță.
== Date de intrare ==
Fișierul de intrare cartita.in conţine pe prima linie un număr natural N având semnificația din enunț.

Pe următoarea linie se află N numere naturale despărțite prin câte un spațiu, reprezentând în ordine, înălțimile grămăjoarelor de pământ, al i-lea număr reprezentând înălțimea inițială h[i], a grămăjoarei din dreptul morcovului i.

Pe a treia linie se află un număr natural U reprezentând numărul de morcovi către care cărtița a săpat galerii.

Pe următoarele U linii se află câte un triplet de numere naturale pos, x, K, separate între ele prin câte un spațiu, cu semnificația că în urma săpării unei galerii către morcovul pos înălțimea grămăjoarei lui a crescut cu x centimetri, iar celelalte înălțimi se modifică, după regula descrisă în enunț.

Pe următoarea linie se găsește numărul Q reprezentând numărul de intervale unde se dorește identificarea înălțimii minime a unei grămăjoare corespunzătoare celui mai tentant morcov.

Pe următoarele Q linii sunt câte două numere naturale L, R, separate între ele printr-un spațiu, reprezentând capetele intervalului de morcovi investigat.
== Date de ieșire ==
Fişierul de ieşire cartita.out va conţine Q linii, pe fiecare găsindu-se, în ordine, răspunsul la intervalele investigate.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100.000
* 1 ≤ U ≤ 300.000
* 1 ≤ Q ≤ 200.000
* 1 ≤ L ≤ R ≤ N
* Inițial 1 ≤ h[i] ≤ N, pentru fiecare i, 1 ≤ i ≤ N
* 1 ≤ pos ≤ N, 1 ≤ x ≤ 400 și -21 ≤ K ≤ 21, K ≠ 0
== Exemplu ==
; cartita.in
6
1 6 2 4 3 4
3
4 5 2
2 4 1
4 2 8
3
1 6
2 4
4 4
; cartita.in
-19
-3
17
 

== Explicație ==
* După prima galerie săpată către morcovul 4, șirul înălțimilor celor N=6 grămăjoare a devenit (0, 7, 5, 9, 10, 13).
* După a doua galerie săpată către morcovul 2, șirul înălțimilor celor N=6 grămăjoare a devenit (3, 11, 10, 15, 17, 21).
* După a treia galerie săpată către morcovul 4, șirul înălțimilor celor N=6 grămăjoare a devenit (-19, -3, 4, 17, 27, 39)
* Pe intervalul [1,6], înălțimea minimă este -19, pe intervalul [2,4], înălțimea minimă este -3, iar pentru ultimul interval investigat [4,4] înălțimea minimă este 17.
== Rezolvare ==
<syntaxhighlight lang="python" line>
from math import inf

class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self.construct_segment_tree(arr, 0, self.n - 1, 0)

def construct_segment_tree(self, arr, start, end, idx):
if start == end:
self.tree[idx] = arr[start]
return
mid = (start + end) // 2
self.construct_segment_tree(arr, start, mid, 2 * idx + 1)
self.construct_segment_tree(arr, mid + 1, end, 2 * idx + 2)
self.tree[idx] = min(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

def update(self, pos, val, start, end, idx):
if start == end:
self.tree[idx] += val
return
mid = (start + end) // 2
if pos <= mid:
self.update(pos, val, start, mid, 2 * idx + 1)
else:
self.update(pos, val, mid + 1, end, 2 * idx + 2)
self.tree[idx] = min(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

def query(self, left, right, start, end, idx):
if left > end or right < start:
return inf
if left <= start and right >= end:
return self.tree[idx]
mid = (start + end) // 2
return min(self.query(left, right, start, mid, 2 * idx + 1),
self.query(left, right, mid + 1, end, 2 * idx + 2))

def main():
N = int(input())
heights = list(map(int, input().split()))
U = int(input())
changes = []
for _ in range(U):
pos, x, K = map(int, input().split())
changes.append((pos, x, K))

tree = SegmentTree(heights)

Q = int(input())
for _ in range(Q):
L, R = map(int, input().split())
min_height = inf
for pos, x, K in changes:
min_height = min(min_height, tree.query(L - 1, R - 1, 0, N - 1, 0) + x - abs(L - pos) * K)
print(min_height)

if __name__ == "__main__":
main()

</syntaxhighlight>

3729 - Exclusiv

2024-06-03T16:31:19Z

AjM: Pagină nouă: == Enunt == Se consideră doi vectori care conțin numere naturale: s cu M elemente și v cu N elemente. Numim secvență i-exclusivă o secvență a vectorului s care nu conține niciuna dintre valorile v[1], v[2], …, v[i]. == Cerinţa == Scrieți un program care să determine, pentru orice 1 ≤ i ≤ N, lungimea maximă a unei secvențe i-exclusive. == Date de intrare == Fișierul de intrare exclusiv.in conține pe prima linie numerele naturale M și N. Pe linia a doua s...

== Enunt ==
Se consideră doi vectori care conțin numere naturale: s cu M elemente și v cu N elemente. Numim secvență i-exclusivă o secvență a vectorului s care nu conține niciuna dintre valorile v[1], v[2], …, v[i].
== Cerinţa ==
Scrieți un program care să determine, pentru orice 1 ≤ i ≤ N, lungimea maximă a unei secvențe i-exclusive.
== Date de intrare ==
Fișierul de intrare exclusiv.in conține pe prima linie numerele naturale M și N. Pe linia a doua se află M numere naturale reprezentând elementele vectorului s, iar pe linia a treia N numere naturale reprezentând elementele vectorului v. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.
== Date de ieșire ==
Fișierul de ieșire exclusiv.out va conține N linii. Pe linia i (1 ≤ i ≤ N) va fi scris un număr natural care reprezintă lungimea maximă a unei secvențe i-exclusive.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 2.000
* 3 ≤ M ≤ 100.000
* Vectorii s și v conțin numere naturale mai mici sau egale cu 2.000.000.000, memorate începând cu poziția 1
* Valorile din fiecare vector nu sunt obligatoriu distincte două câte două.
* O subsecvență nevidă în s este formată din elemente situate pe poziții consecutive (s[i], s[i + 1], …, s[j]), i ≤ j. O subsecvență i-exclusivă poate fi și vidă, lungimea ei fiind 0.
== Exemplu ==
; exclusiv.in
20 6
11 5 11 7 2 10 11 9 2 77 88 88 88 2 7 2 2 77 2 11
11 5 7 9 5 2
; exclusiv.out
12
12
7
6
6
4
 

== Explicație ==
Cea mai lungă secvență 1-exclusivă (care nu conține valoarea 11) este 9 2 77 88 88 88 2 7 2 2 77 2 și are lungimea 12.
Cea mai lungă secvență 2-exclusivă (care nu conține valorile 11 și 5) este 9 2 77 88 88 88 2 7 2 2 77 2 și are lungimea 12.
Cea mai lungă secvență 3-exclusivă (care nu conține valorile 11, 5 și 7) este 9 2 77 88 88 88 2 și are lungimea 7.
Cea mai lungă secvență 4-exclusivă (care nu conține valorile 11, 5, 7 și 9) este 2 77 88 88 88 2 și are
lungimea 6.
Cea mai lungă secvență 5-exclusivă (care nu conține valorile 11, 5 7, 9 și 5) este 2 77 88 88 88 2 și are lungimea 6.
Cea mai lungă secvență 6-exclusivă (care nu conține valorile 11, 5, 7, 9, 5 și 2) este 77 88 88 88 și are lungimea 4.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def longest_exclusive_sequence(s, v):
last_position = {value: -1 for value in v}
longest_sequence = 0
current_sequence = 0

for value in s:
if value in last_position:
current_sequence = min(current_sequence + 1, 1 + last_position[value])
else:
current_sequence += 1
last_position[value] = current_sequence
longest_sequence = max(longest_sequence, current_sequence)

return longest_sequence

def main():
M, N = map(int, input().split())
s = list(map(int, input().split()))
v = list(map(int, input().split()))

result = []
for i in range(N):
result.append(longest_exclusive_sequence(s, v[:i+1]))

for length in result:
print(length)

if __name__ == "__main__":
main()

</syntaxhighlight>

3695 - iziStack

2024-06-03T16:29:11Z

AjM: Pagină nouă: == Enunt == Se dă o stivă vidă. Elementele stivei sunt numerotate incepand cu 1 de la bază înspre vârf. Avem de procesat T comenzi de tipurile: * 0 x – elementul x se va adăuga în vârful stivei * 1 x y add – tuturor elementelor din intervalul x y le va fi adăugată valoarea add * 2 – eliminarea elementului din vârf == Cerinţa == Afisați dupa fiecare operație elementul din vârful stivei. Se garantează: 1. că nu se va efectua operația de tip 2 dacă nu...

== Enunt ==
Se dă o stivă vidă. Elementele stivei sunt numerotate incepand cu 1 de la bază înspre vârf. Avem de procesat T comenzi de tipurile:

* 0 x – elementul x se va adăuga în vârful stivei
* 1 x y add – tuturor elementelor din intervalul x y le va fi adăugată valoarea add
* 2 – eliminarea elementului din vârf
== Cerinţa ==
Afisați dupa fiecare operație elementul din vârful stivei.
Se garantează:
1. că nu se va efectua operația de tip 2 dacă nu există cel puțin două elemente în stivă;
2. că prima operatie va fi de tipul 0
== Date de intrare ==
Fișierul de intrare izi.in conține pe prima linie un număr natural T, iar pe următoarele T linii operațiile efectuate asupra stivei.
== Date de ieșire ==
Fișierul de ieșire izi.out va conține T linii, reprezentând elementele din vârful stivei dupa fiecare operație.
== Restricţii şi precizări ==
* 1 ≤ T ≤ 1.000.000
* -1000 ≤ add ≤ 1000
* Pentru operațiile de tip 1, -1000 ≤ x ≤ 1000, iar pentru operatiile de tip 2 numărul elementelor aflate în stivă este mai mare ca y
* Pentru 36 puncte: 1 ≤ T ≤ 1000
* Pentru alte 33 puncte: Toate operatiile de tip 2 se vor afla la finalul fișierului de intrare
== Exemplu ==
; izi.in
7
0 1
1 1 1 2
0 2
1 1 2 3
2
0 4
2
; izi.out
1
3
2
5
6
4
6
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
class Stack:
def __init__(self):
self.stack = []

def push(self, x):
self.stack.append(x)

def pop(self):
if self.is_empty():
return None
return self.stack.pop()

def top(self):
if self.is_empty():
return None
return self.stack[-1]

def is_empty(self):
return len(self.stack) == 0

def process_operations(T, operations):
stack = Stack()
for op in operations:
if op[0] == 0:
stack.push(op[1])
elif op[0] == 1:
x, y, add = op[1], op[2], op[3]
for i in range(x - 1, y):
stack.stack[i] += add
elif op[0] == 2:
stack.pop()
if not stack.is_empty():
print(stack.top())

def main():
T = int(input())
operations = []
for _ in range(T):
operation = list(map(int, input().split()))
operations.append(operation)
process_operations(T, operations)

if __name__ == "__main__":
main()

</syntaxhighlight>

3436 - Wind

2024-06-03T16:26:06Z

AjM: Pagină nouă: == Enunt == Domnul Vânt a pus pe marginea unei șosele N centrale eoliene, dintre care unele produc energie electrică, iar altele, deocamdată, doar consumă energie. El a etichetat centralele cu numerele naturale distincte de la 1 la N, în ordinea poziționării lor pe șosea. Fiecare centrală eoliană are la bază un ecran pe care este afișat un număr întreg, reprezentând cantitatea de energie pe care o produce (dacă numărul este pozitiv) sau pe care o consumă (d...

== Enunt ==
Domnul Vânt a pus pe marginea unei șosele N centrale eoliene, dintre care unele produc energie electrică, iar altele, deocamdată, doar consumă energie. El a etichetat centralele cu numerele naturale distincte de la 1 la N, în ordinea poziționării lor pe șosea. Fiecare centrală eoliană are la bază un ecran pe care este afișat un număr întreg, reprezentând cantitatea de energie pe care o produce (dacă numărul este pozitiv) sau pe care o consumă (dacă numărul este negativ).

Pentru a construi corect k orașe de-a lungul acestei șosele, un arhitect trebuie să aibă în vedere că:

* fiecărui oraș îi va fi atribuit câte un grup format din centrale eoliene vecine pe șosea, toate grupurile având același număr de centrale;
* cantitatea de energie repartizată unui oraș este egală cu suma numerelor afișate pe ecranele centralelor
eoliene din grupul atribuit; uneori este posibil ca, deocamdată, suma obținută să fie negativă;
* fiecare dintre cele N centrale eoliene trebuie să fie atribuită unui oraș;
* factorul de dezechilibru, notat cu P(k), este valoarea maximă a diferenței dintre energiile repartizate oricăror două orașe diferite, dintre cele k.
== Cerinţa ==
Scrieți un program care citește numărul N, valorile afișate pe cele N ecrane ale centralelor eoliene și rezolvă următoarele două cerinţe:

* afișează numărul M de moduri în care se pot grupa cele N centrale pentru construcția corectă de orașe;
* afișează numărul maxim X de orașe ce pot fi construite corect, dintre cele care au factorul de dezechilibru minim, precum și eticheta E a primei centrale eoliene atribuită orașului cu cea mai mare cantitate de energie repartizată, dintre cele X orașe; dacă sunt mai multe astfel de orașe, se ia în considerare cel care are atribuite centrale etichetate cu numere mai mari.
== Date de intrare ==
Fișierul de intrare wind.in conține pe prima linie un număr natural C reprezentând cerința care trebuie rezolvată (1 sau 2). A doua linie a fișierului conține un număr natural N, cu semnificația din enunț. A treia linie din fișier conține N numere întregi, separate prin câte un spațiu, reprezentând valorile afișate pe cele N ecrane ale centralelor eoliene, în ordinea poziționării acestora pe șosea.
== Date de ieșire ==
Fișierul de ieșire wind.out va conține pe prima linie:

* dacă C=1, numărul natural M, reprezentând răspunsul la cerința 1;
* dacă C=2, cele două numere naturale X și E, în această ordine, separate printr-un singur spațiu,
reprezentând răspunsul la cerința 2.
== Restricţii şi precizări ==
* 2 ≤ N ≤ 100000, N număr natural;
* Numerele afișate pe ecranele centralelor sunt numere întregi formate din cel mult nouă cifre;
* Se vor construi minimum 2 orașe;
* În concurs, pentru rezolvarea cerinței 1 s-au acordat 20 de puncte, pentru rezolvarea cerinței 2 s-au acordat 70 de puncte. Pe site se acordă 10 puncte pentru exemple.
== Exemplul 1 ==
; wind.in
1
12
2 4 -5 12 3 5 -6 4 5 7 -8 2
; wind.out
5
 

== Explicație ==
Cerința este 1. Centralele eoliene se pot grupa câte 1, câte 2, câte 3, câte 4 sau câte 6.
== Exemplul 2 ==
; wind.in
2
12
2 4 -5 12 3 5 -6 4 5 7 -8 2
; wind.out
3 1
 

== Explicație ==
Cerința este 2. Posibilitățile de grupare:

* câte 1 centrală/oraș (sumele sunt 2, 4, -5, …, 2; P(12)=20=12-(-8));
* câte 2 centrale/oraș (sumele sunt: 6, 7, 8, -2, 12, -6; P(6)=18=12-(-6));
* câte 3 centrale/oraș (sumele sunt: 1, 20, 3, 1; P(4)=19=20-1);
* câte 4 centrale/oraș (sumele sunt: 13, 6, 6; P(3)=7=13-6);
* câte 6 centrale/oraș (sumele sunt: 21 si 4; P(2)=17=21-4).
Astfel, factorul de dezechilibru minim este P(3)=7, deci X=3. Pentru această grupare a centralelor, orașul cu cantitatea maximă de energie (13) corespunde primului grup, care începe cu centrala etichetată cu E=1.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def calculate_divisors(n):
divisors = []
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n // i)
return divisors

def imbalance_factor(groups):
max_energy = max(sum(group) for group in groups)
min_energy = min(sum(group) for group in groups)
return max_energy - min_energy

def main():
task = int(input())
N = int(input())
energies = list(map(int, input().split()))

if task == 1:
divisors = calculate_divisors(N)
print(len(divisors))
elif task == 2:
divisors = calculate_divisors(N)
min_imbalance = float('inf')
max_cities = 0
best_start = 0

for divisor in divisors:
groups = [energies[i:i + divisor] for i in range(0, N, divisor)]
imbalance = imbalance_factor(groups)
if imbalance < min_imbalance:
min_imbalance = imbalance
max_cities = len(groups)
best_start = sum(groups[0])

print(max_cities, best_start)

if __name__ == "__main__":
main()

</syntaxhighlight>

3085 - fsecv

2024-06-03T16:22:24Z

AjM: Pagină nouă: == Enunt == Se consideră un șir A format din N numere întregi, numerotate de la 1 la N. Numim secvență a șirului A orice succesiune de elemente consecutive din șir de forma A[i], A[i+1], …, A[j], cu 0 < i < j ≤ N. == Cerinţa == Fiind dat șirul A cu N numere întregi se cere să se răspundă la Q întrebări de forma: i j k (0 < i < j ≤ N). Pentru fiecare întrebare se cere să se determine câte numere din secvența A[i], …, A[j] au frecvența de apariții e...

== Enunt ==
Se consideră un șir A format din N numere întregi, numerotate de la 1 la N. Numim secvență a șirului A orice succesiune de elemente consecutive din șir de forma A[i], A[i+1], …, A[j], cu 0 < i < j ≤ N.
== Cerinţa ==
Fiind dat șirul A cu N numere întregi se cere să se răspundă la Q întrebări de forma: i j k (0 < i < j ≤ N). Pentru fiecare întrebare se cere să se determine câte numere din secvența A[i], …, A[j] au frecvența de apariții egală cu k.
== Date de intrare ==
Fișierul de intrare fsecv.in conține pe prima linie numerele naturale nenule N și Q cu semnificația din enunț. Pe următoarea linie se găsesc N numere întregi ce reprezintă valorile șirului A. Pe următoarele linii se află descrierea celor Q întrebări, câte una pe linie, în formatul precizat i j k.
== Date de ieșire ==
Fișierul de ieșire fsecv.out va conține Q linii. Pe fiecare linie se va găsi răspunsul întrebării i, cu 1 ≤ i ≤ Q.
== Restricţii şi precizări ==
* 2 < N ≤ 100.000
* 1 < Q ≤ 100.000
* 0 < k ≤ N
* -100.000 ≤ A[i] ≤ 100.000; 1 ≤ i ≤ N
== Exemplu ==
; fsecv.in
11 3
1 2 4 3 2 5 6 4 5 2 1
1 6 2
2 7 3
4 11 1
; fsecv.out
1
0
4
 

== Explicație ==
Secvența la care se referă prima întrebare este 1,2,4,3,2,5, iar răspunsul este egal cu 1.
Secvența la care se referă a doua întrebare este 2,4,3,2,5,6, iar răspunsul este egal cu 0.
Secvența la care se referă a treia întrebare este 3,2,5,6,4,5,2,1, iar răspunsul este egal cu 4.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_elements_with_frequency(sequence, k):
frequency = {}
for num in sequence:
if num in frequency:
frequency[num] += 1
else:
frequency[num] = 1

count = 0
for num in sequence:
if frequency[num] == k:
count += 1

return count

def main():
# Citirea datelor de intrare
N, Q = map(int, input().split())
sequence = list(map(int, input().split()))

# Procesarea întrebărilor
answers = []
for _ in range(Q):
i, j, k = map(int, input().split())
count = count_elements_with_frequency(sequence[i-1:j], k)
answers.append(count)

# Afisarea rezultatului
for count in answers:
print(count)

if __name__ == "__main__":
main()

</syntaxhighlight>

4169 - Switch Letters

2024-06-03T16:19:35Z

AjM: Pagină nouă: == Enunt == Se dă un șir s = s0, s1,…, sn-1 de n litere mici. Prin s[i..j] se înțelege secvența si, si+1, …, sj. Asupra șirului se efectuează de mai multe ori operația switch(i,j,c1,c2), care în secvența s[i..j] modifică orice apariție a literei c1 în litera c2. De exemplu, dacă s=abcdaabcdaaab, atunci switch(0,5,'a','z') face ca șirul să devină s=zbcdzzbcdaaab. == Cerinţa == Dându-se șirul s și m operații switch, să se afișeze șirul s după efect...

== Enunt ==
Se dă un șir s = s0, s1,…, sn-1 de n litere mici. Prin s[i..j] se înțelege secvența si, si+1, …, sj. Asupra șirului se efectuează de mai multe ori operația switch(i,j,c1,c2), care în secvența s[i..j] modifică orice apariție a literei c1 în litera c2. De exemplu, dacă s=abcdaabcdaaab, atunci switch(0,5,'a','z') face ca șirul să devină s=zbcdzzbcdaaab.
== Cerinţa ==
Dându-se șirul s și m operații switch, să se afișeze șirul s după efectuarea celor m operații.
== Date de intrare ==
Fișierul de intrare switchletters.in conține pe prima linie șirul s, pe a doua linie numărul natural m, iar pe următoarele m linii se află câte două numere naturale și două litere mici ale alfabetului englez, separate prin câte un spațiu i j c1 c2, reprezentând operația switch(i,j,c1,c2).
== Date de ieșire ==
Fișierul de ieșire switchletters.out va conține șirul s după efectuarea celor m operații.
== Restricţii şi precizări ==
* Șirul s conține cel mult 1.000.000 litere mici: 1 ≤ n ≤ 1.000.000.
* Șirul s nu conține alte caractere în afară de litere mici.
* Într-o operație switch(i,j,c1,c2), întotdeauna 0 ≤ i ≤ j < n, iar c1 ≠ c2.
* 1 ≤ m ≤ 217.
== Exemplul 1 ==
; switchletters.in
aaaabbbbcccc
3
0 2 a y
5 9 b c
1 3 a z
; switchletters.out
yyyzbccccccc
 

== Explicație ==
Pentru primul exemplu, După operația switch(0,2,’a’,’y’), s=yyyabbbbcccc.
După operația switch(5,9,’b’,’c’), s=yyyabccccccc.
După operația switch(1,3,’a’,’z’), s=yyyzbccccccc
== Exemplul 2 ==
; switchletters.in
anaaremere
2
3 6 z y
2 7 o x
; switchletters.out
anaaremere
 

== Explicație ==
s rămâne neschimbat, deoarece literele z și o nu apar în șir.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def switch_letters(s, operations):
for op in operations:
i, j, c1, c2 = op
for k in range(i, j+1):
if s[k] == c1:
s[k] = c2

def main():
# Citirea datelor de intrare
s = list(input().strip())
m = int(input().strip())
operations = [list(input().split()) for _ in range(m)]

# Conversia indicele și literelor la valorile numerice corespunzătoare
for i in range(m):
operations[i][0] = int(operations[i][0])
operations[i][1] = int(operations[i][1])

# Aplicarea operațiilor switch
switch_letters(s, operations)

# Afisarea rezultatului
print("".join(s))

if __name__ == "__main__":
main()

</syntaxhighlight>

3772 - Joc Cu Lasere

2024-06-03T16:16:07Z

AjM: Pagină nouă: == Cerinţa == RAU-Gigel testează un joc cu trageri și premii. Jocul constă într-o serie de acțiuni care au loc la anumite momente de timp. Acțiunile pot fi: (1) aparițiile unor premii sau (2) trageri. Premiile apar la anumite înălțimi, pentru un interval de timp bine definit. Tragerile au loc la anumite momente de timp și se propagă în spațiu instantaneu. RAU-Gigel câștigă câte un punct pentru fiecare premiu ochit. Din păcate, RAU-Gigel nu și-a calibrat...

== Cerinţa ==
RAU-Gigel testează un joc cu trageri și premii. Jocul constă într-o serie de acțiuni care au loc la anumite momente de timp. Acțiunile pot fi: (1) aparițiile unor premii sau (2) trageri. Premiile apar la anumite înălțimi, pentru un interval de timp bine definit. Tragerile au loc la anumite momente de timp și se propagă în spațiu instantaneu. RAU-Gigel câștigă câte un punct pentru fiecare premiu ochit.

Din păcate, RAU-Gigel nu și-a calibrat bine trăgătorul, astfel încât fiecare tragere devine activă numai între două înălțimi date: [h1, h2], interval numit rază de acțiune. Așadar, RAU-Gigel nu va câștiga puncte decât pentru premiile aflate în raza de acțiune a fiecărei trageri.

Dacă o tragere are loc exact în același moment în care apare un premiu în raza ei de acțiune, acesta se consideră ”ochit”. Similar, dacă un premiu este programat să dispară la un moment de timp în care are loc o tragere, iar el se află în raza de acțiune a tragerii, atunci punctul se consideră câștigat. Un premiu ochit rămâne în joc și poate genera și alte puncte, până la momentul la care este programat să dispară. Nu pot avea loc două trageri în același moment, dar pot exista mai multe premii la aceeași înălțime în același timp și toate sunt generatoare de puncte.

Dându-se numărul N de operații de tipul 1 sau 2, unde:

Operația 1 t d h – reprezintă un premiu: t este momentul în care apare, d este numărul de unități de timp cât este programat să existe, iar h este înălțimea la care apare;
Operația 2 t h1 h2 – reprezintă o tragere, t este momentul în care are loc, iar h1 și h2 reprezintă înălțimile în care tragerea este activă (raza de acțiune).
Să se afle câte puncte câștigă RAU-Gigel la fiecare tragere și care este punctajul cu care termină jocul?
== Date de intrare ==
Fișierul de intrare lasere.in conține pe prima linie un număr natural N. Pe următoarele N linii se află operațiile, în ordine crescătoare a momentului t de începere a acțiunii, de tipul 1 și 2, de forma:

* 1 t d h , unde t, d, h sunt 3 numere naturale separate cu un spațiu, cu semnificația de mai sus, reprezintă o operație de tipul 1;
* 2 t h1 h2 , unde t, h1, h2 sunt 3 numere naturale separate cu un spațiu, cu semnificația de mai sus, reprezintă o operație de tipul 2.
== Date de ieșire ==
Fișierul de ieșire lasere.out va conține răspunsurile, în ordinea solicitării, pentru operațiile de tip 2, câte unul pe linie, iar pe ultimul rând, punctajul lui RAU-Gigel la sfârșitul jocului.
== Restricţii şi precizări ==
* 2 ≤ N ≤ 100.000
* 1 ≤ t, d, h, h1, h2 ≤ 1.000.000.000, h1<h2
== Exemplul 1 ==
; lasere.in
4
1 2 8 4
2 3 5 10
1 5 6 7
2 8 3 8
; lasere.out
0
2
2
 

== Explicație ==
Sunt 4 acțiuni, dintre care 2 trageri (tipul 2). La prima tragere RAU-Gigel nu nimerește singurul premiu existent în momentul tragerii (momentul 3), pentru că aceasta nu este în raza sa de acțiune.

La a doua tragere, din momentul 8, RAU-Gigel nimerește ambele premii.

Total: 0+2=2.
== Exemplul 2 ==
; lasere.in
6
2 2 4 5
1 2 8 4
2 3 5 10
1 5 6 7
2 10 4 8
1 10 3 7
; lasere.out
1
0
3
4
 

== Explicație ==
Sunt 6 acțiuni, dintre care 3 trageri. În momentul 2 au loc 2 acțiuni: o tragere și apariția unui premiu. Pentru că premiul, aflat la înălțimea 4, este în raza de acțiune a acestei trageri și anume în intervalul [4-5], RAU-Gigel câștigă un punct.

La a doua tragere, nu nimerește nimic, singurul premiu existent în acel moment nefiind în raza sa de acțiune.

La a treia tragere, RAU-Gigel mai câștigă 3 puncte, acele premii fiind în raza de acțiune a tragerii (intervalul 4-8). Se numără inclusiv primul premiu, planificat să existe până în momentul 10, care este și momentul tragerii. De asemenea, se numără și ultimul premiu, apărut chiar în momentul tragerii.

Total: 1+0+3=4.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
n = int(input())
actions = []
for _ in range(n):
action = list(map(int, input().split()))
actions.append(action)

# Dicționar pentru stocarea premiilor și tragerilor
prizes = {}
shots = []

# Parcurgem toate acțiunile și le salvăm în dicționarul corespunzător
for action in actions:
if action[0] == 1: # Dacă este o acțiune de tip premiu
start_time = action[1]
end_time = action[1] + action[2] # Momentul în care premiul va dispărea
height = action[3]
prizes[start_time] = (end_time, height)
elif action[0] == 2: # Dacă este o acțiune de tip tragere
time = action[1]
height1 = action[2]
height2 = action[3]
shots.append((time, height1, height2))

# Parcurgem fiecare tragere și numărăm câte premii sunt în raza de acțiune
for shot in shots:
time = shot[0]
height1 = shot[1]
height2 = shot[2]
points = 0
for prize_time, prize_info in prizes.items():
if time >= prize_time and time <= prize_info[0] and prize_info[1] >= height1 and prize_info[1] <= height2:
points += 1
print(points)

if __name__ == "__main__":
main()

</syntaxhighlight>

0935 - Punct In Poligon Simplu

2024-06-03T16:13:22Z

AjM: /* Exemplu */

== Cerinţa ==
Se dau coordonatele în plan pentru n puncte care determină un poligon. Se mai dau coordonatele altor m puncte. Să se verifice, pentru fiecare dintre cele m puncte, dacă se găsește sau nu în interiorul (sau pe marginea) poligonului.
== Date de intrare ==
Fișierul de intrare punctinpoligonsimplu.in conține pe prima linie două numere separate prin spațiu: n și m, reprezentând respectiv, numărul de vârfuri ale poligonului și numărul de puncte de testat. Pe următoarele n linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui vârf al poligonului. Acestea sunt date între-un sens de parcurgere a laturilor poligonului. Pe următoarele m linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui punct care trebuie testat.
== Date de ieșire ==
Fișierul de ieșire punctinpoligonsimplu.out va conține m linii și pe fiecare dintre ele sa află mesajul DA sau NU după cum punctul corespunzător este sau nu în interiorul
== Restricţii şi precizări ==
1 ≤ n , m ≤ 100
Numerele din fișierul de intrare sunt întregi cuprinse între -1001 și 1001.
Poligonul nu este neapărat convex dar nu se autointersectează.
În primele două teste poligonul este convex.
== Exemplu ==
; punctinpoligonsimplu.in
8 9
-4 -1
-3 2
-1 3
2 3
4 1
4 -2
1 -4
-2 -4
0 0
-3 -2
3 -2
-1 2
2 2
-4 0
-2 3
0 -20
20 0
; punctinpoligonsimplu.out
DA
DA
DA
DA
DA
NU
NU
NU
NU

 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_point_in_polygon(n, vertices, point):
x, y = point
inside = False

p1x, p1y = vertices[0]
for i in range(n + 1):
p2x, p2y = vertices[i % n]
if y > min(p1y, p2y):
if y <= max(p1y, p2y):
if x <= max(p1x, p2x):
if p1y != p2y:
xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x, p1y = p2x, p2y

return inside

def read_input_file(filename):
with open(filename, 'r') as file:
data = file.readlines()
n, m = map(int, data[0].strip().split())
vertices = [tuple(map(int, line.strip().split())) for line in data[1:n+1]]
points = [tuple(map(int, line.strip().split())) for line in data[n+1:]]
return n, m, vertices, points

def write_output_file(filename, results):
with open(filename, 'w') as file:
for result in results:
file.write(result + "\n")

def main():
n, m, vertices, points = read_input_file('punctinpoligonsimplu.in')
results = []

for point in points:
if is_point_in_polygon(n, vertices, point):
results.append('DA')
else:
results.append('NU')

write_output_file('punctinpoligonsimplu.out', results)

if __name__ == "__main__":
main()

</syntaxhighlight>

0935 - Punct In Poligon Simplu

2024-06-03T16:11:32Z

AjM: /* Exemplu */

== Cerinţa ==
Se dau coordonatele în plan pentru n puncte care determină un poligon. Se mai dau coordonatele altor m puncte. Să se verifice, pentru fiecare dintre cele m puncte, dacă se găsește sau nu în interiorul (sau pe marginea) poligonului.
== Date de intrare ==
Fișierul de intrare punctinpoligonsimplu.in conține pe prima linie două numere separate prin spațiu: n și m, reprezentând respectiv, numărul de vârfuri ale poligonului și numărul de puncte de testat. Pe următoarele n linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui vârf al poligonului. Acestea sunt date între-un sens de parcurgere a laturilor poligonului. Pe următoarele m linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui punct care trebuie testat.
== Date de ieșire ==
Fișierul de ieșire punctinpoligonsimplu.out va conține m linii și pe fiecare dintre ele sa află mesajul DA sau NU după cum punctul corespunzător este sau nu în interiorul
== Restricţii şi precizări ==
1 ≤ n , m ≤ 100
Numerele din fișierul de intrare sunt întregi cuprinse între -1001 și 1001.
Poligonul nu este neapărat convex dar nu se autointersectează.
În primele două teste poligonul este convex.
== Exemplu ==
<nowiki>;</nowiki> punctinpoligonsimplu.in

8 9

-4 -1

-3 2

-1 3

2 3

4 1

4 -2

1 -4

-2 -4

0 0

-3 -2

3 -2

-1 2

2 2

-4 0

-2 3

0 -20

20 0

<nowiki>;</nowiki> punctinpoligonsimplu.out

DA

DA

DA

DA

DA

NU

NU

NU

NU

<nowiki> </nowiki>
== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_point_in_polygon(n, vertices, point):
x, y = point
inside = False

p1x, p1y = vertices[0]
for i in range(n + 1):
p2x, p2y = vertices[i % n]
if y > min(p1y, p2y):
if y <= max(p1y, p2y):
if x <= max(p1x, p2x):
if p1y != p2y:
xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x, p1y = p2x, p2y

return inside

def read_input_file(filename):
with open(filename, 'r') as file:
data = file.readlines()
n, m = map(int, data[0].strip().split())
vertices = [tuple(map(int, line.strip().split())) for line in data[1:n+1]]
points = [tuple(map(int, line.strip().split())) for line in data[n+1:]]
return n, m, vertices, points

def write_output_file(filename, results):
with open(filename, 'w') as file:
for result in results:
file.write(result + "\n")

def main():
n, m, vertices, points = read_input_file('punctinpoligonsimplu.in')
results = []

for point in points:
if is_point_in_polygon(n, vertices, point):
results.append('DA')
else:
results.append('NU')

write_output_file('punctinpoligonsimplu.out', results)

if __name__ == "__main__":
main()

</syntaxhighlight>

3683 - Predictor Machine

2024-06-03T16:09:58Z

AjM: Pagină nouă: == Cerinţa == După ce a văzut câti oameni au vrut să știe ce rating vor avea în viitor pe Codeforces, Ștefan s-a decis să își folosească abilitățile sale de programator pentru a găsi punctele importante din graficele ratingurilor de pe Codeforces. Pentru că nu are timp să adauge toate tehnicile sale, el se va ocupa doar de punctele de interes. Astfel, el primește un vector de n numere, indexat de la 1 și o funcție continuă, astfel încât v[i] = f(i), un...

== Cerinţa ==
După ce a văzut câti oameni au vrut să știe ce rating vor avea în viitor pe Codeforces, Ștefan s-a decis să își folosească abilitățile sale de programator pentru a găsi punctele importante din graficele ratingurilor de pe Codeforces. Pentru că nu are timp să adauge toate tehnicile sale, el se va ocupa doar de punctele de interes.

Astfel, el primește un vector de n numere, indexat de la 1 și o funcție continuă, astfel încât v[i] = f(i), unde v[i] e ratingul utilizatorului dupa i concursuri. Pentru că funcția e continuă, pentru fiecare linie dintre cele două puncte, graficul funcției va atinge toate punctele de coordonate întregi dintre valori.

De exemplu, daca f(1) = 3 și f(2) = 9, linia va atinge punctele de pe coordonatele întregi 3, 4, 5, 6, 7, 8 și 9.

De asemenea ni se dau q query-uri, unde la un query vom schimba valoarea unui punct din vector și după fiecare query, va trebui să afișăm punctul de interes al vectorului, care este punctul atins de cel mai mare număr de ori de către graficul funcției. De asemenea, trebuie afișat și numărul de ori în care este atins.

Dacă avem mai multe puncte de acest fel, vom afișa punctul cu cea mai mică valoare dintre ele.

Se garantează că cele n valori vor fi distincte atât la început, cât și de-a lungul actualizărilor.
== Date de intrare ==
Programul citește de la tastatură pe prima linie numărul n. Pe următoarea linie, programul va citi cele n numere naturale, reprezentând valorile inițiale ale vectorului v.

Pe linia a treia, programul va citi numărul q, iar pe următoarele q linii, programul va citi câte două numere, pos și val, reprezentând poziția schimbată și valoarea nouă.
== Date de ieșire ==
Programul va afișa pe ecran q linii, pe fiecare din cele q linii regăsindu-se cele două valori cerute de problemă, și anume punctul cu valoare minimă care este atins de numărul maxim de ori, precum și numărul de ori în care este atins.
== Restricţii şi precizări ==
* 1 ≤ pos ≤ n ≤ 100 000
* 1 ≤ q ≤ 200 000
* 1 ≤ v[i], val ≤ 200 000
* Pentru teste în valoare de 30 de puncte, 1 ≤ n, q ≤ 1000
== Exemplu ==
; Intrare
5
4 2 6 1 7
5
1 3
4 4
2 1
5 2
3 5
; Ieșire
3 4
5 3
5 3
2 3
2 3
 

== Explicație ==
După ce s-au efectuat toate actualizăriile, vectorul va arăta astfel: 3 1 5 4 2.

Valoarea 2 e atinsă de 3 ori, între pozițiile 1 și 2, între pozițiile 2 și 3 precum și între pozițiile 4 și 5.
== Rezolvare ==
<syntaxhighlight lang="python" line>
class SegmentTree:
def __init__(self, n):
self.tree = [0] * (4 * n)

def update(self, node, start, end, idx, val):
if start == end:
if start == idx:
self.tree[node] = val
return
mid = (start + end) // 2
if idx <= mid:
self.update(2 * node, start, mid, idx, val)
else:
self.update(2 * node + 1, mid + 1, end, idx, val)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

def query(self, node, start, end, left, right):
if start > right or end < left:
return 0
if left <= start and end <= right:
return self.tree[node]
mid = (start + end) // 2
return self.query(2 * node, start, mid, left, right) + self.query(2 * node + 1, mid + 1, end, left, right)

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

# Construim arborele de segmente
seg_tree = SegmentTree(n)
for i in range(n):
seg_tree.update(1, 1, n, v[i], 1)

q = int(input())
for _ in range(q):
pos, val = map(int, input().split())
# Actualizăm arborele de segmente
seg_tree.update(1, 1, n, v[pos - 1], 0)
seg_tree.update(1, 1, n, val, seg_tree.query(1, 1, n, val, val) + 1)
v[pos - 1] = val

# Căutăm punctul de interes
left = 1
right = n
while left < right:
mid = (left + right) // 2
if seg_tree.query(1, 1, n, left, mid) >= seg_tree.query(1, 1, n, mid + 1, right):
right = mid
else:
left = mid + 1
print(left, seg_tree.query(1, 1, n, left, left))

if __name__ == "__main__":
main()

</syntaxhighlight>

3230 - Cambridge

2024-06-03T16:07:19Z

AjM: Pagină nouă: == Enunt == Interviul de admitere la prestigioasa Universitate Cambridge constă în N probleme, numerotate de la 1 la N. Alex este în momentul acesta acolo, așteptând să susțină interviul. Takahiro Wong, care tocmai a ieșit din examen, a rezolvat toate problemele, problema i rezolvând-o după Di secunde de la începerea interviului. Cunoscând ca poate rezolva fiecare problema i în Ti secunde, Alex, panicat din fire, își pune M întrebări de forma: x y. Pentru fi...

== Enunt ==
Interviul de admitere la prestigioasa Universitate Cambridge constă în N probleme, numerotate de la 1 la N. Alex este în momentul acesta acolo, așteptând să susțină interviul. Takahiro Wong, care tocmai a ieșit din examen, a rezolvat toate problemele, problema i rezolvând-o după Di secunde de la începerea interviului.
Cunoscând ca poate rezolva fiecare problema i în Ti secunde, Alex, panicat din fire, își pune M întrebări de forma: x y. Pentru fiecare întrebare, Alex vrea să afle dacă poate rezolva fiecare problemă din intervalul [x;y] înaintea lui Takahiro Wong (Alex poate rezolva problemele din intervalul [x;y] în ce ordine dorește).
De exemplu, să considerăm că Alex rezolvă problemele a și b (în această ordine). El va termina problema a după Ta secunde, și problema b după Ta + Tb secunde. Alex va rezolva ambele probleme înaintea lui Takahiro Wong dacă Ta < Da și Ta + Tb < Db. Atât interviul lui Takahiro Wong, cât și cel al lui Alex încep de la secunda 0.
== Cerinţa ==
Ajutați-l pe Alex să răspundă corect la cele M întrebări pentru a nu intra panicat la interviu.
== Date de intrare ==
Pe prima linie se vor citi de la tastatura N și M, separate prin câte un spațiu. N – numărul de probleme, M – numărul de întrebări.

Pe următoarele N linii se vor citi de la tastatura Ti și Di, separate prin câte un spațiu. Ti – timpul necesar lui Alex sa rezolve problema i. Di – timpul (de la începerea interviului) după care Takahiro Wong rezolv[ problema i.

Pe următoarele M linii se vor citi de la tastatură x și y, separate prin câte un spațiu. x – capătul din stânga al intervalului. y – capătul din dreapta al intervalului.
== Date de ieșire ==
Se vor afișa pe ecran M linii – răspunsurile la cele M întrebări. Linia cu numărul i va conține răspunsul pentru întrebarea cu numărul i: 1, dacă Alex poate găsi o ordine în care să rezolve toate problemele din intervalul [x;y], astfel încât să termine fiecare problema înaintea lui Takahiro Wong, sau 0, altfel.
== Restricţii şi precizări ==
* 1 ≤ N, M ≤ 100.000
* 1 ≤ Ti, Di ≤ 1.000.000.000
* Valorile Di nu sunt distincte două câte două (o valoarea poate apărea de mai multe ori)
* Alex nu poate rezolva două probleme în același timp, însă Takahiro Wong poate (valorile Di nu sunt distincte două câte două).
== Exemplul 1 ==
; Intrare
4 3
1 10
14 18
2 7
10 12
3 4
2 4
1 3
; Ieșire
0
0
1
 

== Explicație ==
Sunt 4 probleme, numerotate de la 1 la 4:
* problema numărul 1: T1 = 1, D1 = 10;
* problema numărul 2: T2 = 14, D2 = 18;
* problema numărul 3: T3 = 2, D3 = 7;
* problema numărul 4: T4 = 10, D4 = 12;
* Prima întrebare se referă la intervalul [3,4]: – Dacă rezolvăm problemele în ordinea (3,4) trebuie să avem T3 < D3 și T3 + T4 < D4. Observăm că a doua relație este falsă. – Dacă rezolvăm problemele în ordinea (4,3) trebuie să avem T4 < D4 și T4 + T3 < D3. Observăm, din nou, că a doua relație este falsă. – Nu există nicio altă ordine în care putem rezolva problemele, deci răspunsul este 0.
* A doua întrebare se referă la intervalul [2,4]: – Exista șase modalități de a rezolva problemele: (2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2). – În niciuna din cele șase modalități nu sunt toate relațiile respectate, deci răspunsul este 0.
* A treia întrebare se referă la intervalul [1,3]: – Exista șase modalități de a rezolva problemele: (1,2,3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). – Dacă rezolvăm problemele în ordinea (1,3,2) trebuie să avem T1 < D1, T1 + T3 < D3 și T1 + T3 + T2 < D2. * Observăm că toate sunt adevărate. – Deoarece am găsit o ordine de a rezolva problemele, pentru care toate relațiile sunt adevărate, răspunsul este 1.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def can_solve_in_time_interval(N, problems, x, y):
max_time_ending_here = 0
for i in range(x - 1, y):
max_time_ending_here = max(max_time_ending_here, problems[i][0]) + problems[i][1]
if max_time_ending_here > problems[i][2]:
return False
return True

def main():
N, M = map(int, input().split())

problems = []
for _ in range(N):
T, D = map(int, input().split())
problems.append((T, D, T + D))

for _ in range(M):
x, y = map(int, input().split())
if can_solve_in_time_interval(N, problems, x, y):
print(1)
else:
print(0)

if __name__ == "__main__":
main()

</syntaxhighlight>

3225 - Simple

2024-06-03T16:02:55Z

AjM: Pagină nouă: == Enunt == Se dă un șir de N numere și Q operații de tipul: * 0 a b val : se va aduna valoarea val la toate numerele din intervalul [a, b]. * 1 a b : se va afișa elementul minim par și elementul maxim impar din intervalul [a, b]; în cazul în care unul dintre aceste numere nu există, se va afișa -1 în locul său. == Cerinţa == Răspundeți corect la toate operațiile de tip 1. == Date de intrare == Programul citește de la tastatură numărul N. Pe a doua linie s...

== Enunt ==
Se dă un șir de N numere și Q operații de tipul:

* 0 a b val : se va aduna valoarea val la toate numerele din intervalul [a, b].
* 1 a b : se va afișa elementul minim par și elementul maxim impar din intervalul [a, b]; în cazul în care unul dintre aceste numere nu există, se va afișa -1 în locul său.
== Cerinţa ==
Răspundeți corect la toate operațiile de tip 1.
== Date de intrare ==
Programul citește de la tastatură numărul N. Pe a doua linie se vor afla N numere reprezentând elementele din sir. Pe linia a treia se va afla numărul Q, iar pe următoarele Q linii se vor afla Q operații sub forma descrisa în enunț.
== Date de ieșire ==
Se vor afișa pe ecran răspunsurile la operațiile de tip 1, câte unul pe linie.
== Restricţii şi precizări ==
* N, Q <= 200.000
* Numerele din sir sunt cuprinse intre 1 și 2.000.000.000.
* Valorile val din operațiile de tip 0 sunt cuprinse intre 1 și 2.000.000.000.
* ATENȚIE! În cazul în care unul din cele două răspunsuri la o operație de tip 1 nu poate fi calculat, se va afișa -1
== Exemplu ==
; Intrare
7
5 6 3 1 9 8 5
10
1 2 5
0 2 3 2
1 2 4
0 2 7 3
1 2 4
1 4 7
0 5 7 1
1 1 6
1 1 2
1 3 4
; Ieșire
6 9
8 5
4 11
4 11
4 13
-1 11
4 -1
 

== Explicație ==
Șirul inițial este: 5 6 3 1 9 8 5.
Operația 1 2 5: Se vor afișa cele doua valori cerute pe intervalul [2; 5].
Operația 0 2 3 2: Șirul nou format va fi 5 8 5 1 9 8 5.
Operația 1 2 4 : Se vor afișa cele doua valori cerute pe intervalul [2; 4].
Operația 0 2 7 3 : Șirul nou format va fi 5 11 8 4 12 11 8.
Operația 1 2 4 : Se vor afișa cele doua valori cerute pe intervalul [2; 4].
Operația 1 4 7 : Se vor afișa cele doua valori cerute pe intervalul [4; 7].
Operația 0 5 7 1 : Șirul nou format va fi 5 11 8 4 13 12 9.
Operația 1 1 6 : Se vor afișa cele doua valori cerute pe intervalul [1; 6].
Operația 1 1 2 : Se vor afișa cele doua valori cerute pe intervalul [1; 2].
Operația 1 3 4 : Se vor afișa cele doua valori cerute pe intervalul [3; 4].
== Rezolvare ==
<syntaxhighlight lang="python" line>
def apply_operation_0(arr, a, b, val):
for i in range(a - 1, b):
arr[i] += val

def find_min_par_and_max_odd(arr, a, b):
min_par = float('inf')
max_odd = float('-inf')
for i in range(a - 1, b):
if arr[i] % 2 == 0:
min_par = min(min_par, arr[i])
else:
max_odd = max(max_odd, arr[i])
if min_par == float('inf'):
min_par = -1
if max_odd == float('-inf'):
max_odd = -1
return min_par, max_odd

def main():
N = int(input())
arr = list(map(int, input().split()))
Q = int(input())

for _ in range(Q):
query = input().split()
op = int(query[0])
a = int(query[1])
b = int(query[2])

if op == 0:
val = int(query[3])
apply_operation_0(arr, a, b, val)
elif op == 1:
min_par, max_odd = find_min_par_and_max_odd(arr, a, b)
print(min_par, max_odd)

if __name__ == "__main__":
main()

</syntaxhighlight>

3059 - Lexicografic

2024-06-03T16:00:40Z

AjM: Pagină nouă: == Enunt == Se dă un șir v format din N elemente naturale nenule nu neapărat distincte. Asupra șirului putem aplica un singur tip de operație: interschimbarea a două elemente aflate pe poziții consecutive. == Cerinţa == Dându-se un număr natural K, se cere șirul minim lexicografic ce se poate obține prin aplicarea a cel mult K interschimbări de elemente de pe poziții consecutive. == Date de intrare == În fișierul lexicografic.in se află pe prima linie T, rep...

== Enunt ==

Se dă un șir v format din N elemente naturale nenule nu neapărat distincte. Asupra șirului putem aplica un singur tip de operație: interschimbarea a două elemente aflate pe poziții consecutive.
== Cerinţa ==
Dându-se un număr natural K, se cere șirul minim lexicografic ce se poate obține prin aplicarea a cel mult K interschimbări de elemente de pe poziții consecutive.
== Date de intrare ==
În fișierul lexicografic.in se află pe prima linie T, reprezentând numărul de teste. Urmează cele T teste, fiecare pe câte două linii. Pe prima linie din cadrul unui test se află două numere N și K separate prin spațiu. Pe linia a doua din cadrul unui test se află cele N elemente ale șirului v separate prin spații.
== Date de ieșire ==
În fișierul lexicografic.out se vor afișa cele T linii, câte una corespunzătoare răspunsului pe fiecare test. Linia corespunzătoare unui test va conține cele N elemente separate prin spații ale șirului minim lexicografic ce s-a obținut din șirul inițial, după aplicarea a cel mult K interschimbări de elemente de pe poziții consecutive.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 250.000;
* T ≤ 2500;
* într-un fișier de intrare suma totală a lungimilor șirurilor corespunzătoare celor T teste nu va depăși 250.000;
* 1 ≤ K ≤ N*(N-1)/2;
* 1 ≤ v[i] ≤ N, pentru 1 ≤ i ≤ N;
* Vă rugăm să acordați atenție tipului de date necesar pentru a citi valoarea lui K;
* Pentru acordarea punctajului pe un fișier de test este necesară rezolvarea corectă a tuturor celor T teste;
* Pentru teste în valoare de 5 puncte se garantează K = N * (N – 1) / 2;
* Pentru alte teste în valoare de 7 puncte se garantează K = 1;
* Pentru alte teste în valoare de 23 de puncte se garantează T ≤ 10, N ≤ 50;
* Pentru alte teste în valoare de 4 puncte se garantează T ≤ 10, N ≤ 100;
* Pentru alte teste în valoare de 12 puncte se garantează T ≤ 10, N ≤ 500;
* Pentru alte teste în valoare de 24 de puncte se garantează T ≤ 10, N ≤ 2000;
* Un șir a1, a2, …, an este mai mic lexicografic decât un alt șir b1, b2, …, bn dacă există un număr întreg P mai mic sau egal cu N astfel * încât: a1 = b1, a2 = b2, … , aP-1 = bP-1, iar aP < bP.
== Exemplul 1 ==
; lexicografic.in
3
5 2
4 2 3 1 1
4 3
2 1 3 4
6 4
5 3 5 3 4 6
; lexicografic.out
2 3 4 1 1
1 2 3 4
3 3 5 4 5 6
 

== Explicație ==
Pentru primul test: Șirul este format din N = 5 elemente, și anume v=(4,2,3,1,1). Putem efectua K=2 interschimbări. Interschimbând elementele v[1] și v[2] obținem șirul (2,4,3,1,1), apoi după interschimbarea elementelor v[3] și v[2] se obține șirul minim lexicografic (2,3,4,1,1).
== Rezolvare ==
<syntaxhighlight lang="python" line>
def min_lexicographic_sequence(N, K, v):
for _ in range(min(K, N)):
for i in range(N - 1):
if v[i] > v[i + 1]:
v[i], v[i + 1] = v[i + 1], v[i]

return v

def main():
with open("lexicografic.in", "r") as fin, open("lexicografic.out", "w") as fout:
T = int(fin.readline())
for _ in range(T):
N, K = map(int, fin.readline().split())
v = list(map(int, fin.readline().split()))
min_lex_seq = min_lexicographic_sequence(N, K, v)
fout.write(" ".join(map(str, min_lex_seq)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4019 - Pikachu

2024-06-03T15:57:52Z

AjM: Pagină nouă: == Enunt == Miruna şi partenerul ei de aventură, Pikachu, sunt în faţa unei noi provocări. Cele două personaje au ajuns lângă un lanţ muntos format din N vârfuri aşezate în linie dreaptă unul după altul. Pentru fiecare vârf muntos se cunoaşte înălţimea lui. Folosindu-se de puterile sale extraordinare, Pikachu este capabil sa scadă sau să crească înălţimea unui vârf muntos cu o unitate într-o secundă. Din motive necunoscute muritorilor de rând, cei...

== Enunt ==
Miruna şi partenerul ei de aventură, Pikachu, sunt în faţa unei noi provocări. Cele două personaje au ajuns lângă un lanţ muntos format din N vârfuri aşezate în linie dreaptă unul după altul. Pentru fiecare vârf muntos se cunoaşte înălţimea lui. Folosindu-se de puterile sale extraordinare, Pikachu este capabil sa scadă sau să crească înălţimea unui vârf muntos cu o unitate într-o secundă. Din motive necunoscute muritorilor de rând, cei doi prieteni vor să obţină cel puţin K vârfuri montane consecutive care au aceeaşi înălţime, într-un timp cât mai scurt.
== Cerinţa ==
Determinaţi timpul minim în care Pikachu poate îndeplini această sarcină.
== Date de intrare ==
Fișierul de intrare pikachu.in conține pe prima linie două numere N şi K având semnificaţia din enunţ. Pe cea de a doua linie se vor găsi N numere naturale reprezentând înălţimile vârfurilor muntoase.
== Date de ieșire ==
Fișierul de ieșire pikachu.out va conţine un singur număr natural T, reprezentând timpul minim necesar pentru a obţine cel puţin K vârfuri consecutive cu aceeaşi înălţime.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100.000
* 1 ≤ K ≤ N
* Înălţimile munţilor sunt numere pozitive care se pot reprezenta pe întregi de 32 de biţi cu semn
* 20% din teste au 1 ≤ N, K ≤ 100, iar înălţimile aparţin intervalului [1, 100]
* Alte 20% din teste au 1 ≤ N, K ≤ 5000
* Rezultatul se poate reprezenta pe un întreg de 64 biţi cu semn
== Exemplu ==
; pikachu.in
5 3
5 2 4 3 7
; pikachu.out
2
 

== Explicație ==
În prima secundă se creşte înălţimea muntelui de pe poziţia a doua, iar în a doua secundă se scade înălţimea muntelui de pe poziţia a treia. În urma acestor operaţii subsevenţa care începe pe a doua poziţie şi se termină pe a patra poziţie va conţine doar vârfuri de înălţime 3.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def min_time_to_consecutive_height(N, K, heights):
min_time = float('inf')
counter = {}
start, end = 0, 0

while end < N:
height = heights[end]
counter[height] = counter.get(height, 0) + 1
end += 1

while len(counter) > 1 or (len(counter) == 1 and max(counter.values()) < K):
start_height = heights[start]
counter[start_height] -= 1
if counter[start_height] == 0:
del counter[start_height]
start += 1

if len(counter) == 1 and max(counter.values()) >= K:
min_time = min(min_time, end - start)

return min_time

def main():
with open("pikachu.in", "r") as fin, open("pikachu.out", "w") as fout:
N, K = map(int, fin.readline().split())
heights = list(map(int, fin.readline().split()))
min_time = min_time_to_consecutive_height(N, K, heights)
fout.write(str(min_time) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2092 - Actualizare Element, Produs Interval, Matrice

2024-06-03T15:54:40Z

AjM: Pagină nouă: == Enunt == Se dă un șir de matrice pătratice asupra căruia se pot face două tipuri de operații: actualizare a unui element (se înlocuiește matricea de pe acea poziție cu alta) și interogarea unui interval de indici (determinarea produsului matricelor memorate între cei doi indici, inclusiv). == Cerinţa == Afișați răspunsul la fiecare interogare. == Date de intrare == Prima linie a fisierului aepim.in conține două numere: N, ce reprezintă lungimea șirului d...

== Enunt ==
Se dă un șir de matrice pătratice asupra căruia se pot face două tipuri de operații: actualizare a unui element (se înlocuiește matricea de pe acea poziție cu alta) și interogarea unui interval de indici (determinarea produsului matricelor memorate între cei doi indici, inclusiv).
== Cerinţa ==
Afișați răspunsul la fiecare interogare.
== Date de intrare ==
Prima linie a fisierului aepim.in conține două numere: N, ce reprezintă lungimea șirului dat și K ce reprezintă dimensiunea matricelor pătratice. Linia a doua, conține, separate prin câte un spațiu, matricele din șirului dat. Atât matricele date în șirul inițial cât și cele de la actualizări conțin doar 1 și 2 și sunt date la intrare codificat, ca un șir de K*K caractere, conform parcurgerii crescător după linii și apoi crescător după coloane (fără spații). De exemplu, matricea:
1 2 2
1 1 1
1 2 1
se codifică prin 122111121.
Codificările matricelor de pe a doua linie se separă prin câte un spațiu.
Pe linia a treia e află un număr M ce reprezintă numărul de operații ce se efectuează asupra șirului dat. Pe fiecare din următoarele M linii se găsesc câte 3 numere naturale separate prin câte un spațiu: T A B. Dacă T = 1 operația este de interogare iar A și B sunt capetele inrervalului. Dacă T = 2 operația este de actualizare cu semnificația: elementul de pe poziția A devine B (B reprezintă codificarea unei matrice).
== Date de ieșire ==
Fișierul aepim.out conține pe câte o linie răspunsul la căte o operațe de tip 1, în ordinea în care acestea apar în datele de intrare. Elementele matricelor rezultat se scriu modulo 9901, se afișează, ca ordine, după aceeași regulă ca la codificarea din datele de intrare și se separă prin câte un spațiu.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100000
* 1 ≤ M ≤ 100000
* 1 ≤ A ≤ B ≤ N
* 2 ≤ K ≤ 3
* elementele șirului dat sunt indexate de la 1
== Exemplul 1 ==
; aepim.in
4 2
1121 1221 1121 1121
3
1 2 4
2 2 2112
1 2 4
; aepim.out
11 8 10 7
10 7 11 8
 

== Explicație ==
Matricele sunt de ordin 2. Pe prima linie a fișierului deieșire este codifictă matricea
11 8
10 7
== Rezolvare ==
<syntaxhighlight lang="python" line>

</syntaxhighlight>

2091 - Actualizare Interval, Minim Interval

2024-06-03T15:50:37Z

AjM: Pagină nouă: == Enunt == Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui interval (schimbarea valorii tuturor elementelor aflate între două poziții date) și interogarea unui interval (determinarea celei mai mici valori aflate între două poziții date). == Cerinţa == Afișați răspunsurile la fiecare interogare. == Date de intrare == Prima linie a fisierului aimi.in conține un număr N, ce reprezintă lungimea șirului dat. Linia a...

== Enunt ==
Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui interval (schimbarea valorii tuturor elementelor aflate între două poziții date) și interogarea unui interval (determinarea celei mai mici valori aflate între două poziții date).
== Cerinţa ==
Afișați răspunsurile la fiecare interogare.
== Date de intrare ==
Prima linie a fisierului aimi.in conține un număr N, ce reprezintă lungimea șirului dat. Linia a doua, conține, separate prin câte un spațiu elementele șirului dat. Pe linia a treia se află un număr M ce reprezintă numărul de operații ce se efectuează asupra șirului dat. Pe fiecare din următoarele M linii se află descrierea câte unei operații astfel: interogările sub forma 1 A B, cerându-se minimul elementelor aflate între pozițiile A și B inclusiv, sau 2 A B X, semnificând faptul că toate elementele de pe poziții de la A la B inclusiv primesc valoarea X.
== Date de ieșire ==
Fișierul aimi.out conține pe câte o linie răspunsul la căte o operațe de tip 1, în ordinea în care acestea apar în datele de intrare.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100000
* 1 ≤ M ≤ 100000
* 1 ≤ A ≤ B ≤ N
* elementele șirului dat sunt indexate de la 1
* elementele șirului dat precum și valorile X sunt de tip int, pozitive
== Exemplu ==
; aimi.in
5
1 6 4 3 9
3
1 2 4
2 2 3 2
1 2 4
; aimi.out
3
2
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
class SegmentTree:
def __init__(self, nums):
self.n = len(nums)
self.tree = [float('inf')] * (4 * self.n)
self.build(nums, 0, 0, self.n - 1)

def build(self, nums, idx, left, right):
if left == right:
self.tree[idx] = nums[left]
return
mid = (left + right) // 2
self.build(nums, 2 * idx + 1, left, mid)
self.build(nums, 2 * idx + 2, mid + 1, right)
self.tree[idx] = min(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

def update(self, idx, left, right, pos, val):
if left == right == pos:
self.tree[idx] = val
return
mid = (left + right) // 2
if pos <= mid:
self.update(2 * idx + 1, left, mid, pos, val)
else:
self.update(2 * idx + 2, mid + 1, right, pos, val)
self.tree[idx] = min(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

def query(self, idx, left, right, q_left, q_right):
if q_left <= left and right <= q_right:
return self.tree[idx]
if q_right < left or right < q_left:
return float('inf')
mid = (left + right) // 2
left_min = self.query(2 * idx + 1, left, mid, q_left, q_right)
right_min = self.query(2 * idx + 2, mid + 1, right, q_left, q_right)
return min(left_min, right_min)

def main():
with open("aimi.in", "r") as fin, open("aimi.out", "w") as fout:
N = int(fin.readline())
nums = list(map(int, fin.readline().split()))
tree = SegmentTree(nums)

M = int(fin.readline())
for _ in range(M):
op = list(map(int, fin.readline().split()))
if op[0] == 1:
left, right = op[1] - 1, op[2] - 1
min_val = tree.query(0, 0, N - 1, left, right)
fout.write(f"{min_val}\n")
else:
pos, val = op[1], op[2]
tree.update(0, 0, N - 1, pos - 1, val)

if __name__ == "__main__":
main()

</syntaxhighlight>

2093 - Actualizare Element, Stergere Minim

2024-06-03T15:48:07Z

AjM: Pagină nouă: == Enunt == Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui element (schimbarea valorii sale) și determinarea, urmată de ștergerea, elementului minim. Dacă valoarea minimă apare de mai multe ori în șir, se elimină prima sa apariție. Se consideră că elementele aflate în dreapta celui eliminat se deplasează o poziție la stânga (acoperă golul lăsat). == Cerinţa == Afișați, după fiecare operație de ștergere,...

== Enunt ==
Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui element (schimbarea valorii sale) și determinarea, urmată de ștergerea, elementului minim. Dacă valoarea minimă apare de mai multe ori în șir, se elimină prima sa apariție. Se consideră că elementele aflate în dreapta celui eliminat se deplasează o poziție la stânga (acoperă golul lăsat).
== Cerinţa ==
Afișați, după fiecare operație de ștergere, valoarea eliminată.
== Date de intrare ==
Prima linie a fisierului aesm.in conține un număr N, ce reprezintă lungimea șirului dat. Linia a doua, conține, separate prin câte un spațiu, elementele șirului. Pe linia a treia e află un număr M ce reprezintă numărul de operații ce se efectuează asupra șirului. Pe fiecare din următoarele M linii se găsește descrierea unei operații, astfel: fie se găsește pe linie doar numărul 1, fie se găsește numărul 2, urmat de un număr p și de un număr x, separate prin câte un spațiu. Dacă operația este de tip 1, se va determina valoarea minimă din șir și apoi se va șterge prima sa apariție. Dacă operația este de tip 2, elementul aflat în șir pe poziția p va primi valoarea x. Se garantează că la apariția fiecărei astfel de operații șirul conține cel puțin p numere.
== Date de ieșire ==
Fișierul aesm.out conține valorile minime din momentul apariției operațiilor de tip 1, câte una pe linie, în ordinea apariției în fișierul de intrare.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100.000
* 1 ≤ M ≤ 100.000
* elementele șirului dat sunt indexate de la 1
* elementele șirului dat precum și valoriile x sunt pozitive ≤ 2.000.000.000
* se garantează că numărul de operații de tip 1 este ≤ N
== Exemplu ==
; aesm.in
7
1 6 3 9 3 7 2
5
1
2 4 2
1
2 5 8
1
; aesm.out
1
2
3
 

== Explicatie ==
Minimul din șir este 1, aflat pe poziția 1, acesta se afișează și se șterge. Șirul rămâne 6 3 9 3 7 2. După prima operație de tip 2, șirul devine: 6 3 9 2 7 2. Se obține minimul 2 și se șterge acesta, șirul devenind 6 3 9 7 2. A doua operație de tip 2 transformă acum șirul în 6 3 9 7 8. Ultima dată se tipărește și se șterge 3.
== Rezolvare ==
<syntaxhighlight lang="python" line>
import heapq

def remove_min(nums, heap):
min_val = nums[heap[0]]
nums[heap[0]] = None
heapq.heapify(heap)
return min_val

def main():
with open("aesm.in", "r") as fin, open("aesm.out", "w") as fout:
N = int(fin.readline())
nums = list(map(int, fin.readline().split()))
heap = [(num, idx) for idx, num in enumerate(nums) if num is not None]
heapq.heapify(heap)

M = int(fin.readline())
for _ in range(M):
op = fin.readline().split()
if op[0] == '1':
min_val = remove_min(nums, heap)
fout.write(f"{min_val}\n")
else:
p, x = map(int, op[1:])
nums[p - 1] = x
heapq.heapify(heap)

if __name__ == "__main__":
main()

</syntaxhighlight>

2095 - Descompunere in Intervale

2024-06-03T15:45:49Z

AjM: Pagină nouă: == Enunt == Se dau numerele N și M și apoi M perechi de numere X, Y ambele valori fiind cuprinse între 1 și N. În această problemă numim interval o mulțime de numere naturale consecutive. Notăm [A, B] cu A <= B ca fiind intervalul format din numerele A, A+1, A+2, ... B-1, B. Numim descompunere în intervale a unei perechi de numere X, Y ca fiind o mulțime de intervale care acoperă complet mulțimea (fiecare număr dintre X și Y, inclusiv, este conținut de exact u...

== Enunt ==
Se dau numerele N și M și apoi M perechi de numere X, Y ambele valori fiind cuprinse între 1 și N. În această problemă numim interval o mulțime de numere naturale consecutive. Notăm [A, B] cu A <= B ca fiind intervalul format din numerele A, A+1, A+2, ... B-1, B. Numim descompunere în intervale a unei perechi de numere X, Y ca fiind o mulțime de intervale care acoperă complet mulțimea (fiecare număr dintre X și Y, inclusiv, este conținut de exact un interval din descompunere). De exemplu, pentru perechea 5,10, o descompunere în intervale este [5,5], [6,8],[9,10]. Dorim să realizăm o descompunere în intervale a tuturor celor M perechi de numere date, astfel încât să se îndeplinească condițiile următoare (notăm L = 1 + [log2N]).
fiecare pereche să aibă în descompunere maxim 2*L intervale.
numărul total de intervale distincte cu mai mult de un element care apar în descompuneri să nu depășească valoarea N.
== Cerinţa ==
Afișați descompunerea fiecărei perechi din fișierul de intrare.
== Date de intrare ==
Pe prima linie a fisierului di.in se află două numere N și M, separate prin spațiu, cu semnificația de mai sus. Pe fiecare din următoarele M linii se găsesc câte 2 numere naturale separate prin câte un spațiu, X Y ce reprezintă câte o pereche ce trebuie descompusă.
== Date de ieșire ==
Fișierul di.out conține M linii, pe fiecare aflându-se descompunerea unei perechi date în fișierul de intrare, în ordine. Primul element al unei linii reprezintă numărul de intervale ale unei descompuneri, notat K. Urmează apoi K+1 elemente în ordine strict crescătoare, E1, E2, ... Ek+1. Primul interval este [E1, E2], al doilea este [E2+1, E3] ... Ultimul interval este [Ek+1 ,E k+1 ].
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100000
* 1 ≤ M ≤ 200000
* 1 ≤ X ≤ Y ≤ N
* X ≤ Y
== Exemplul 1 ==
; di.in
7 10
1 4
1 5
1 6
1 7
2 5
2 6
2 7
3 6
3 7
4 7
; di.out
1 1 4
2 1 4 5
2 1 4 6
1 1 7
3 2 2 4 5
3 2 2 4 6
3 2 2 4 7
2 3 4 6
3 3 4 6 7
2 4 4 7
 

== Explicatie ==
Pentru perechea 2,7 codificarea descompunerii este 2 2 4 7 reprezentând intervalele [2,2], [3,4], [5,7].
== Rezolvare ==
<syntaxhighlight lang="python" line>
import math

def decompose_interval(X, Y, N):
L = 1 + math.floor(math.log2(N))
intervals = []
while Y - X + 1 > 2 * L:
intervals.append((X, X + L - 1))
X += L
intervals.append((X, Y))
return intervals

def main():
with open("di.in", "r") as fin, open("di.out", "w") as fout:
N, M = map(int, fin.readline().split())
for _ in range(M):
X, Y = map(int, fin.readline().split())
intervals = decompose_interval(X, Y, N)
fout.write(f"{len(intervals)} {' '.join(str(i) for interval in intervals for i in interval)}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2094 - Actualizare Element, CMMDC Interval

2024-06-03T15:42:33Z

AjM: Pagină nouă: == Enunt == Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui element (schimbarea valorii sale) și interogarea unui interval de indici (determinarea celui mai mare divizor comun pentru valorile aflate între cei doi indici, inclusiv). == Cerinţa == Afișați răspunsul la fiecare interogare. == Date de intrare == Prima linie a fisierului aecmmdci.in conține un număr N, ce reprezintă lungimea șirului dat. Linia a doua conț...

== Enunt ==
Se dă un șir de numere asupra căruia se pot face două tipuri de operații: actualizare a unui element (schimbarea valorii sale) și interogarea unui interval de indici (determinarea celui mai mare divizor comun pentru valorile aflate între cei doi indici, inclusiv).
== Cerinţa ==
Afișați răspunsul la fiecare interogare.
== Date de intrare ==
Prima linie a fisierului aecmmdci.in conține un număr N, ce reprezintă lungimea șirului dat. Linia a doua conține, separate prin câte un spațiu, elementele șirului dat. Pe linia a treia se află un număr M ce reprezintă numărul de operații ce se efectuează asupra șirului dat. Pe fiecare din următoarele M linii se găsesc câte 3 numere naturale separate prin câte un spațiu: T A B. Dacă T = 1 operația este de interogare iar A și B sunt capetele inrervalului. Dacă T = 2 operația este de actualizare cu semnificația: elementul de pe poziția A devine B.
== Date de ieșire ==
Fișierul aecmmdci.out conține pe câte o linie răspunsul la căte o operațe de tip 1, în ordinea în care acestea apar în datele de intrare.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100000
* 1 ≤ M ≤ 100000
* 1 ≤ A ≤ B ≤ N
* elementele șirului dat sunt indexate de la 1
* elementele șirului dat, precum și cele de la operațiile de actualizare, sunt strict pozitive <= 2000000000
== Exemplu ==
; aecmmdci.in
5
2 12 6 9 8
3
1 2 4
2 4 2
1 2 4
; aecmmdci.out
3
2
 
== Rezolvare ==
<syntaxhighlight lang="python" line>
def gcd(a, b):
while b:
a, b = b, a % b
return a

def main():
with open("aecmmdci.in", "r") as fin, open("aecmmdci.out", "w") as fout:
n = int(fin.readline())
arr = list(map(int, fin.readline().split()))
last_update = {i + 1: val for i, val in enumerate(arr)}

m = int(fin.readline())
for _ in range(m):
op, a, b = map(int, fin.readline().split())
if op == 1:
result = gcd(last_update[a], last_update[b])
fout.write(f"{result}\n")
elif op == 2:
last_update[a] = b

if __name__ == "__main__":
main()

</syntaxhighlight>

3526 - StringQuery

2024-06-03T15:38:34Z

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

== Cerinţa ==
Se dă un string s de lungime n și q query-uri de forma (op, x, y), unde op poate fi 0 sau 1. Dacă op este egal cu 1, atunci caracterul de pe poziția x din s va deveni y. Dacă op este egal cu 0, se va afișa numărul de caractere distincte ale lui s din intervalul [x, y].
== Date de intrare ==
Programul citește de la tastatură n, s, q si cele q query-uri.
== Date de ieșire ==
Programul va afișa pe ecran raspunsurile la query-urile de tipul 0, fiecare pe linie nouă.
== Restricţii şi precizări ==
* 1 ≤ n ≤ 5.000.000
* 1 ≤ q ≤ 250.000
* s este format doar din litere mici ale alfabetului englez
== Exemplu ==
; Intrare
4
aaaa
4
1 2 b
1 3 c
0 1 2
0 2 4
; Ieșire
2
3
 

== Explicatie ==
După primele 2 operatii, s = "abca".
== Rezolvare ==
<syntaxhighlight lang="python" line>
def distinct_characters_in_range(s, x, y):
count = {}
for i in range(x - 1, y):
if s[i] not in count:
count[s[i]] = 1
return len(count)

def main():
n = int(input("Introduceți lungimea șirului: "))
s = input("Introduceți șirul: ")
q = int(input("Introduceți numărul de query-uri: "))

for _ in range(q):
op, x, y = map(int, input().split())
if op == 1:
s = s[:x - 1] + chr(y) + s[x:]
elif op == 0:
result = distinct_characters_in_range(s, x, y)
print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3600 - Numbers Tree

2024-06-03T15:33:40Z

AjM: Pagină nouă: == Cerinţa == Se dă un șir a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații: * 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val; * 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori); * 3 st dr – se cere să se afișeze lu...

== Cerinţa ==
Se dă un șir a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații:
* 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val;
* 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori);
* 3 st dr – se cere să se afișeze lungimea cele mai lungi secvențe de numere prime alcătuită exclusiv din elemente ale șirului care au indicii aflați în intervalul [st, dr](o secvență a unui șir este alcătuită din elemente aflate poziții consecutive).
Dându-se Q operații, să se raspundă în ordine la cele de tip 2 și 3.
== Date de intrare ==
Fișierul de intrare numbers_tree.in conține pe prima linie numerele n și Q, reprezentând numărul de elemente ale șirului a, respectiv numărul de operații, pe a doua linie n numere naturale separate prin spații reprezentând elementele șirului inițial, iar pe următoarele Q linii sunt descrise operațiile.
== Date de ieșire ==
Fișierul de ieșire numbers_tree.out va conține pe câte o linie răspunsurile la operațiile de tip 2 și 3 în ordinea în care acestea apar în fișierul de intrare.
== Restricţii şi precizări ==
* 1 ≤ n, Q ≤ 100.000
* 2 ≤ a[i], val ≤ 1.000.000
* 1 ≤ st ≤ dr ≤ n
== Exemplu ==
; numbers_tree.in
7 7
2 3 4 5 6 7 8
2 1 7
3 1 7
1 2 5 4
2 2 5
3 2 5
1 2 4 3
3 1 6
; numbers_tree.out
3
2
4
0
4
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(filename):
with open(filename, 'r') as f:
n, Q = map(int, f.readline().split())
a = list(map(int, f.readline().split()))
operations = [list(map(int, line.split())) for line in f.readlines()]
return n, a, operations

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

def apply_operation_2(a, st, dr):
count_composite = 0
for i in range(st - 1, dr):
if a[i] > 1 and not is_prime(a[i]):
count_composite += 1
return count_composite

def apply_operation_3(a, st, dr):
max_prime_sequence = 0
current_prime_sequence = 0
for i in range(st - 1, dr):
if is_prime(a[i]):
current_prime_sequence += 1
max_prime_sequence = max(max_prime_sequence, current_prime_sequence)
else:
current_prime_sequence = 0
return max_prime_sequence

def process_operations(n, a, operations):
result = []
for op in operations:
if op[0] == 2:
count_composite = apply_operation_2(a, op[1], op[2])
result.append(count_composite)
elif op[0] == 3:
max_prime_sequence = apply_operation_3(a, op[1], op[2])
result.append(max_prime_sequence)
return result

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

def main():
input_file = "numbers_tree.in"
output_file = "numbers_tree.out"
n, a, operations = read_input(input_file)
result = process_operations(n, a, operations)
write_output(output_file, result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3386 - Serbare 3

2024-06-03T15:28:13Z

AjM: Pagină nouă: == Enunt == Am o prietenă educatoare. Anul acesta are grupa mică și trebuie să organizeze serbarea de Crăciun. Ea s-a gândit să așeze copiii sub forma unui brad (cam așa ∆). Va împărți copiii în trei categorii: prima categorie va fi formată din primii X cei mai scunzi copii, a doua categorie este formată din copiii cu înălțimea maximă și restul Y de copii în a treia categorie. Copiii din prima categorie vor fi așezați în ordinea crescătoare a înăl...

== Enunt ==
Am o prietenă educatoare. Anul acesta are grupa mică și trebuie să organizeze serbarea de Crăciun. Ea s-a gândit să așeze copiii sub forma unui brad (cam așa ∆). Va împărți copiii în trei categorii: prima categorie va fi formată din primii X cei mai scunzi copii, a doua categorie este formată din copiii cu înălțimea maximă și restul Y de copii în a treia categorie. Copiii din prima categorie vor fi așezați în ordinea crescătoare a înălțimilor, iar cei din a treia categorie în ordinea descrescătoare a înălțimilor. Prietena mea vrea ca toți copiii cu aceeași înălțime să stea unul lângă altul, iar dacă numărul de copii din prima categorie nu poate fi egal cu cel din a treia, vrea ca prima categorie să fie mai numeroasă (X ≥ Y). Prietena mea știe N, numărul de elevi din grupă, prenumele copiilor și înălțimea lor în centimetri. Ea încearcă de câteva zile să îi așeze. Oare cum ar rezolva un elev olimpic la informatică această problemă?
== Cerinţa ==
Scrieţi un program care să determine:
1. Numărul maxim de copii cu aceeași înălțime.
2. O posibilă distribuire a înălțimilor sub forma unui brad.
3. Lista cu prenumele copiilor conform distribuirii înălțimilor determinată anterior.
== Date de intrare ==
Fișierul de intrare serbare.in conține pe prima linie cerința (1, 2 sau 3). Linia următoare conține un număr natural N reprezentând numărul de copii. Pe următoarele N linii conține câte o pereche de forma prenume înălțime, reprezentând prenumele și înălțimea corespunzătoare fiecărui copil din grupă.
== Date de ieșire ==
Fișierul de ieșire serbare.out va conține, dacă cerința este 1, o singură linie pe care va fi scris un număr natural determinat conform cerinței, dacă cerința este 2 va conține o linie pe care vor fi scrise N numere naturale determinate conform cerinței, dacă cerința este 3 va conține o linie pe care vor fi scrise prenumele copiilor conform distribuirii înălțimilor afișate la cerința 2.
== Restricţii şi precizări ==
* 0 < N, X, Y < 101; X ≥ Y
* 0 < înălțime < 151, numere naturale.
* prenumele este un cuvânt cu cel mult 50 de caractere alfabetice.
* NU există doi copii cu același prenume.
* Dacă sunt mai multe soluții se va afișa prima din punct de vedere lexicografic.
== Exemplul 1 ==
; serbare.in
1
5
Ionel 96
Vasile 88
Gigel 66
Mara 77
Ana 77
; serbare.out
2
 

== Explicație ==
Sunt 2 copii cu aceeași înălțime (77), acesta fiind numărul maxim de apariții a aceleiași înălțimi.
== Exemplul 2 ==
; serbare.in
2
5
Ionel 96
Vasile 88
Gigel 66
Mara 77
Ana 77
; serbare.out
66 77 77 96 88
 

== Explicație ==
Așezăm copiii în ordinea crescătoare a înălțimilor și apoi în ordinea descrescătoare a înălțimilor.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(filename):
with open(filename, 'r') as f:
request = int(f.readline().strip())
N = int(f.readline().strip())
children = []
for _ in range(N):
name, height = f.readline().strip().split()
children.append((name, int(height)))
return request, children

def write_output(filename, output):
with open(filename, 'w') as f:
if isinstance(output, int):
f.write(str(output))
elif isinstance(output, list):
f.write(' '.join(map(str, output)))
elif isinstance(output, tuple):
f.write(' '.join(output))

def max_same_height(children):
heights = {}
for _, height in children:
if height in heights:
heights[height] += 1
else:
heights[height] = 1
return max(heights.values())

def arrange_children(children, max_height_count):
sorted_children = sorted(children, key=lambda x: x[1])
ascending = sorted_children[:max_height_count]
descending = sorted_children[max_height_count:]
descending.reverse()
arranged_children = [child[1] for child in ascending] + [child[1] for child in descending]
return arranged_children

def main():
input_file = "serbare.in"
output_file = "serbare.out"
request, children = read_input(input_file)

if request == 1:
max_same = max_same_height(children)
write_output(output_file, max_same)
elif request == 2:
max_same = max_same_height(children)
arranged_children = arrange_children(children, max_same)
write_output(output_file, arranged_children)

if __name__ == "__main__":
main()

</syntaxhighlight>

2054 - Joc 7

2024-06-03T15:22:20Z

AjM: Pagină nouă: == Enunt == Inspirați de clasicul joc Tic-Tac-Toe (X și 0), Teodora și Ștefan își propun să joace ceva asemănător, adăugând jocului clasic câteva reguli noi: tabla de joc este un pătrat de latură N, care este împărțit în N*N celule, așezate pe N linii și N coloane; celulele pătratului sunt numerotate de la 1 la N^2 parcurgând liniile de sus în jos, și coloanele de la stânga la dreapta; Teodora va marca celulele cu X (litera X), iar Ștefan cu 0 (cifr...

== Enunt ==
Inspirați de clasicul joc Tic-Tac-Toe (X și 0), Teodora și Ștefan își propun să joace ceva asemănător, adăugând jocului clasic câteva reguli noi:

tabla de joc este un pătrat de latură N, care este împărțit în N*N celule, așezate pe N linii și N coloane; celulele pătratului sunt numerotate de la 1 la N^2 parcurgând liniile de sus în jos, și coloanele de la stânga la dreapta;
Teodora va marca celulele cu X (litera X), iar Ștefan cu 0 (cifra 0);
în cadrul unei runde, copiii marchează alternativ câte o celulă din pătrat, nemarcată anterior;
o rundă a jocului este descrisă printr-un șir format din exact N^2 numere naturale reprezentând celulele pătratului, în ordinea în care au fost marcate succesiv de cei doi copii;
jocul are K runde; prima este începută de Teodora, a doua de Ștefan, a treia Teodora, a patra Ștefan și așa mai departe;
o rundă este câștigată de jucătorul care reușește primul să marcheze complet o linie, o coloană, diagonala principală sau una din cele două semidiagonale paralele și alăturate cu aceasta, diagonala secundară sau una din cele două semidiagonale paralele și alăturate acesteia;
o rundă se încheie fără un câștigător dacă după marcarea celor N^2 celule nu există pe tabla de joc nicio linie, coloană, diagonală sau semidiagonală marcate cu același simbol.
== Cerinţa ==
Cunoscând numerele N, K și cele K șiruri de numere care reprezintă rundele jucate, scrieți un program care să rezolve una dintre următoarele două cerințe:

Să se determine câte runde a câștigat fiecare copil.
Să se determine care este cel mai mare număr de marcări efectuate până la câștigarea unei runde.
== Date de intrare ==
Fișierul de intrare joc7.in conține pe prima linie un număr natural C. Pentru toate testele, C poate lua numai valorile 1 sau 2. Pe a doua linie se află două numere naturale N și K, separate prin câte un spațiu, reprezentând dimensiunea tablei de joc și respectiv numărul de runde jucate. Pe următoarele K linii sunt descrise rundele de joc, câte o rundă pe câte o linie a fișierului. În cadrul liniilor, numerele sunt separate prin câte un spațiu.
== Date de ieșire ==
Dacă valoarea lui C este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fișierul de ieșire joc7.out va conține pe prima linie două numere naturale t și s, separate printr-un spațiu, unde t reprezintă numărul de runde câștigate de Teodora, iar s numărul rundelor câștigate de Ștefan.

Dacă valoarea lui C este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fișierul de ieșire joc7.out va conține pe prima linie numărul cel mai mare de marcări efectuate până la câștigarea unei runde.
== Restricţii şi precizări ==
* 3 ≤ N ≤ 100
* 1 ≤ K ≤ 25
* La fiecare joc se câștigă cel puțin o rundă.
* Pentru rezolvarea corectă a primei cerințe se acordă 45 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 45 de puncte. În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.
== Exemplul 1 ==
; joc7.in
1
4 4
16 13 15 9 10 1 5 2 6 14 3 7 11 4 8 12
1 2 3 4 5 6 7 8 12 11 10 9 13 14 15 16
1 5 9 6 2 7 3 8 4 10 11 12 13 14 15 16
1 2 3 4 8 7 6 5 12 11 10 9 16 15 14 13
; joc7.out
2 1
 

== Explicație ==
Ilustrarea rundelor de joc până la momentul identificării unui câștigător este următoarea:

* Runda 1 (începe Teodora): Runda este câștigată de Teodora după 7 marcări. Se completează semidiagonala situată sub diagonala principală.
* Runda 2 (începe Ştefan): Runda este câştigată de Teodora după 14 marcări. Se completează semidiagonala situată sub diagonala secundară.
* Runda 3 (începe Teodora): Runda este câştigată de Ștefan după 8 marcări. Se completează linia a doua.
* Runda 4 (începe Ştefan): Runda nu este câştigată de niciun jucător.
== Exemplul 2 ==
; joc7.in
2
4 4
16 13 15 9 10 1 5 2 6 14 3 7 11 4 8 12
1 2 3 4 5 6 7 8 12 11 10 9 13 14 15 16
1 5 9 6 2 7 3 8 4 10 11 12 13 14 15 16
1 2 3 4 8 7 6 5 12 11 10 9 16 15 14 13
; joc7.out
14
 

== Explicație ==
Doar 3 dintre cele 4 runde jucate au fost câştigate. Până în momentul câştigării în prima rundă s-au făcut 7 marcări, în a doua 14, iar în a treia 8. Deci numărul maxim de marcări făcute până la câştigarea unei runde este 14.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def check_winner(board, N):
# Verificăm liniile și coloanele
for i in range(N):
if all(board[i][j] == board[i][0] and board[i][0] != '.' for j in range(N)):
return True
if all(board[j][i] == board[0][i] and board[0][i] != '.' for j in range(N)):
return True

# Verificăm diagonala principală
if all(board[i][i] == board[0][0] and board[0][0] != '.' for i in range(N)):
return True

# Verificăm diagonala secundară
if all(board[i][N-1-i] == board[0][N-1] and board[0][N-1] != '.' for i in range(N)):
return True

return False

def max_marks_per_round(rounds):
max_marks = 0
for round in rounds:
max_marks = max(max_marks, len(round))
return max_marks

def main():
C = int(input().strip())
N, K = map(int, input().strip().split())
rounds = [input().strip().split() for _ in range(K)]

if C == 1:
# Numărăm câte runde a câștigat fiecare copil
teodora_wins = 0
stefan_wins = 0
for round in rounds:
board = [['.' for _ in range(N)] for _ in range(N)]
for i, mark in enumerate(round):
row = (int(mark) - 1) // N
col = (int(mark) - 1) % N
if i % 2 == 0:
board[row][col] = 'X'
else:
board[row][col] = 'O'
if check_winner(board, N):
if len(round) % 2 == 1:
teodora_wins += 1
else:
stefan_wins += 1

print(teodora_wins, stefan_wins)
elif C == 2:
# Determinăm cel mai mare număr de marcați efectuate până la câștigarea unei runde
max_marks = max_marks_per_round(rounds)
print(max_marks)

if __name__ == "__main__":
main()

</syntaxhighlight>

3187 - RATC2

2024-06-03T15:14:25Z

AjM: /* Exemplul 2 */

== Cerinţa ==
Se dau două numere n p și o listă de n elemente cu urcările în autobuz a mai multor persoane a căror structura este prenume nume bilet_platit, fiecare intrare fiind plasată pe câte o linie. Câmpurile prenume și nume sunt șiruri de caractere, iar bilet_platit este un număr care poate fi 0 sau 1; 0 dacă persoana respectivă nu a plătit biletul sau 1 dacă a plătit biletul. Pentru fiecare bilet neplătit se va contoriza o penalizare persoanei.

Se cere :

a) Prenumele, numele și numărul de penalizări al persoanei care are număr maxim de penalizări. Dacă există mai multe persoane cu număr maxim de penalizări se cere afișarea persoanei care apare prima în ordine alfabetică.
b) Ordonarea listei de persoane descrescător după numărul de penalizări, la număr de penalizări egale, crescător după prenume, la prenume identice, crescător după nume.
== Date de intrare ==
Fișierul de intrare ratc2.in conține pe prima linie numerele n p, iar pe următoarele n linii datele despre fiecare urcare în autobuz separate prin spații.
== Date de ieșire ==
Dacă p = 1 se va rezolva cerința a). În acest caz, fișierul ratc2.out va conține pe prima linie datele cu semnificația din enunț separate printr-un spațiu.
Dacă p = 2 se va rezolva cerința b). În acest caz, fișierul ratc2.out va conține pe câte o linie datele cu semnificația din enunț separate printr-un spațiu.
== Restricţii şi precizări ==
1 ≤ n ≤ 100
șirurile de caractere vor avea maxim 50 de caractere
Atenție, persoanele care urcă în autobuz se pot repeta!
== Exemplul 1 ==
; ratc2.in
5 1
Jotaro Kujo 1
Dio Brando 0
Joseph Joestar 1
Dio Brando 1
Andreescu Ionel 0
; ratc2.out
Andreescu Ionel 1
 

== Explicație ==
Dio Brando și Andreescu Ionel au același număr de penalizări dar Andreescu Ionel e primul în ordine alfabetică.
== Exemplul 2 ==
; ratc2.in
5 2
Jotaro Kujo 1
Dio Brando 0
Joseph Joestar 1
Dio Brando 1
Andreescu Ionel 0
; ratc2.out
Andreescu Ionel 1
Dio Brando 1
Joseph Joestar 0
Jotaro Kujo 0
 
== Explicație ==
Listă a fost ordonată dupa criteriile precizate la cerința b).
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(filename):
with open(filename, 'r') as file:
n, p = map(int, file.readline().split())
data = [tuple(file.readline().split()) for _ in range(n)]
return p, data

def calculate_penalties(data):
penalties = {}
for entry in data:
name = entry[0] + " " + entry[1]
if entry[2] == '0':
penalties[name] = penalties.get(name, 0) + 1
return penalties

def find_max_penalties(penalties):
max_penalties = max(penalties.values())
max_penalty_names = [name for name, penalty in penalties.items() if penalty == max_penalties]
max_penalty_names.sort()
return max_penalty_names[0], max_penalties

def sort_people(data):
return sorted(data, key=lambda x: (-penalties.get(x[0] + " " + x[1], 0), x[0], x[1]))

def write_output(filename, result):
with open(filename, 'w') as file:
for line in result:
file.write(" ".join(line) + "\n")

def main():
p, data = read_input('ratc2.in')
penalties = calculate_penalties(data)

if p == 1:
max_name, max_penalty = find_max_penalties(penalties)
write_output('ratc2.out', [(max_name, str(max_penalty))])
elif p == 2:
sorted_data = sort_people(data)
write_output('ratc2.out', sorted_data)

if __name__ == "__main__":
main()

</syntaxhighlight>

3187 - RATC2

2024-06-03T15:14:02Z

AjM: /* Exemplul 2 */

3187 - RATC2

2024-06-03T15:13:23Z

AjM: Pagină nouă: == Cerinţa == Se dau două numere n p și o listă de n elemente cu urcările în autobuz a mai multor persoane a căror structura este prenume nume bilet_platit, fiecare intrare fiind plasată pe câte o linie. Câmpurile prenume și nume sunt șiruri de caractere, iar bilet_platit este un număr care poate fi 0 sau 1; 0 dacă persoana respectivă nu a plătit biletul sau 1 dacă a plătit biletul. Pentru fiecare bilet neplătit se va contoriza o penalizare persoanei. Se c...

== Cerinţa ==
Se dau două numere n p și o listă de n elemente cu urcările în autobuz a mai multor persoane a căror structura este prenume nume bilet_platit, fiecare intrare fiind plasată pe câte o linie. Câmpurile prenume și nume sunt șiruri de caractere, iar bilet_platit este un număr care poate fi 0 sau 1; 0 dacă persoana respectivă nu a plătit biletul sau 1 dacă a plătit biletul. Pentru fiecare bilet neplătit se va contoriza o penalizare persoanei.

Se cere :

a) Prenumele, numele și numărul de penalizări al persoanei care are număr maxim de penalizări. Dacă există mai multe persoane cu număr maxim de penalizări se cere afișarea persoanei care apare prima în ordine alfabetică.
b) Ordonarea listei de persoane descrescător după numărul de penalizări, la număr de penalizări egale, crescător după prenume, la prenume identice, crescător după nume.
== Date de intrare ==
Fișierul de intrare ratc2.in conține pe prima linie numerele n p, iar pe următoarele n linii datele despre fiecare urcare în autobuz separate prin spații.
== Date de ieșire ==
Dacă p = 1 se va rezolva cerința a). În acest caz, fișierul ratc2.out va conține pe prima linie datele cu semnificația din enunț separate printr-un spațiu.
Dacă p = 2 se va rezolva cerința b). În acest caz, fișierul ratc2.out va conține pe câte o linie datele cu semnificația din enunț separate printr-un spațiu.
== Restricţii şi precizări ==
1 ≤ n ≤ 100
șirurile de caractere vor avea maxim 50 de caractere
Atenție, persoanele care urcă în autobuz se pot repeta!
== Exemplul 1 ==
; ratc2.in
5 1
Jotaro Kujo 1
Dio Brando 0
Joseph Joestar 1
Dio Brando 1
Andreescu Ionel 0
; ratc2.out
Andreescu Ionel 1
 

== Explicație ==
Dio Brando și Andreescu Ionel au același număr de penalizări dar Andreescu Ionel e primul în ordine alfabetică.
== Exemplul 2 ==
; ratc2.in
5 2
Jotaro Kujo 1
Dio Brando 0
Joseph Joestar 1
Dio Brando 1
Andreescu Ionel 0
; ratc2.out
Andreescu Ionel 1
Dio Brando 1
Joseph Joestar 0
Jotaro Kujo 0
 

== Explicație ==
Listă a fost ordonată dupa criteriile precizate la cerința b).
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(filename):
with open(filename, 'r') as file:
n, p = map(int, file.readline().split())
data = [tuple(file.readline().split()) for _ in range(n)]
return p, data

def calculate_penalties(data):
penalties = {}
for entry in data:
name = entry[0] + " " + entry[1]
if entry[2] == '0':
penalties[name] = penalties.get(name, 0) + 1
return penalties

def find_max_penalties(penalties):
max_penalties = max(penalties.values())
max_penalty_names = [name for name, penalty in penalties.items() if penalty == max_penalties]
max_penalty_names.sort()
return max_penalty_names[0], max_penalties

def sort_people(data):
return sorted(data, key=lambda x: (-penalties.get(x[0] + " " + x[1], 0), x[0], x[1]))

def write_output(filename, result):
with open(filename, 'w') as file:
for line in result:
file.write(" ".join(line) + "\n")

def main():
p, data = read_input('ratc2.in')
penalties = calculate_penalties(data)

if p == 1:
max_name, max_penalty = find_max_penalties(penalties)
write_output('ratc2.out', [(max_name, str(max_penalty))])
elif p == 2:
sorted_data = sort_people(data)
write_output('ratc2.out', sorted_data)

if __name__ == "__main__":
main()

</syntaxhighlight>

3111 - Hotar

2024-06-03T15:03:33Z

AjM: /* Exemplu */

== Cerinţa ==
Proprietatea trebuie împărțită fraților în mod egal. Zona are forma unui poligon convex cu vârfurile numerotate începând cu 1. Hotarul trebuie să fie un segment care are unul dintre capete în vârful 1 al poligonului. Trebuie să determinați celălalt capăt al segmentului care stabilește hotarul, așa încât ariile celor două suprafețe formate să fie egale. Punctul determinat trebuie să se afle pe poligon.
== Date de intrare ==
Fișierul de intrare hotar.in conține pe prima linie numărul de vârfuri ale poligonului, notat cu n. Pe fiecare dintre următoarele n linii se află coordonatele vârfurilor, date în ordine trigonometrică (invers acelor de ceasornic), mai întâi ordonata, apoi abscisa, separate printr-un spațiu.
== Date de ieșire ==
Fișierul de ieșire hotar.out mai întâi abscisa, apoi ordonata pentru punctul calculat. Aceste două valori se scriu trunchiate la primele trei zecimale și se separă printr-un spațiu.
== Restricţii şi precizări ==
3 ≤ n ≤ 15
Coordonatele vârfurilor sunt numere întregi cuprinse între -50 și 50
Pentru 30% din punctaj, punctul de afișat este unul dintre vârfurile poligonului;
Pentru 60% din punctaj, punctul de afișat are coordonatele numere întregi;
Nu există trei puncte coliniare pe conturul poligonului dat;
Valorile de la ieșire se scriu cu exact trei zecimale, de exemplu, dacă ar trebui afișat 3 4.231867, se va scrie în fișier 3.000 4.231
== Exemplu ==
; hotar.in
3
0 0
1 0
0 1
; hotar.out
0.500 0.500
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(filename):
with open(filename, 'r') as file:
n = int(file.readline().strip())
vertices = [tuple(map(float, file.readline().split())) for _ in range(n)]
return n, vertices

def calculate_area(vertices):
area = 0
n = len(vertices)
for i in range(n):
x1, y1 = vertices[i]
x2, y2 = vertices[(i + 1) % n]
area += x1 * y2 - x2 * y1
return abs(area) / 2

def find_equal_areas(n, vertices):
total_area = calculate_area(vertices)
for i in range(n):
x1, y1 = vertices[i]
x2, y2 = vertices[(i + 1) % n]
x3, y3 = vertices[(i + 2) % n]
area1 = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2
area2 = total_area - area1
if abs(area1 - area2) < 1e-6: # Verificăm egalitatea ariilor cu o toleranță mică
return (x2 + x3) / 2, (y2 + y3) / 2 # Returnăm coordonatele celui de-al doilea vârf
return None

def write_output(filename, result):
with open(filename, 'w') as file:
file.write("{:.3f} {:.3f}\n".format(*result))

def main():
n, vertices = read_input('hotar.in')
result = find_equal_areas(n, vertices)
write_output('hotar.out', result)

if __name__ == "__main__":
main()

</syntaxhighlight>