Bitnami MediaWiki - User contributions [en]

2150 - Credite

2024-03-23T00:30:27Z

Aurelia Raluca: Pagină nouă: == Enunț == Maria este studentă în anul I la facultatea de informatică și a primit o listă de <code>N</code> probleme, numerotate de la <code>1</code> la <code>N</code>, pe care trebuie să le rezolve la cursul de algoritmică, rezolvarea unei probleme durând exact o unitate de timp. Pentru că profesorul vrea să testeze capacitatea elevilor de a a face cele mai bune alegeri, pentru fiecare problemă acesta a stabilit numărul de credite (<code>Ci</code>) pe care stud...

== Enunț ==
Maria este studentă în anul I la facultatea de informatică și a primit o listă de <code>N</code> probleme, numerotate de la <code>1</code> la <code>N</code>, pe care trebuie să le rezolve la cursul de algoritmică, rezolvarea unei probleme durând exact o unitate de timp. Pentru că profesorul vrea să testeze capacitatea elevilor de a a face cele mai bune alegeri, pentru fiecare problemă acesta a stabilit numărul de credite (<code>Ci</code>) pe care studentul le va primi dacă rezolvă problema <code>i</code>, dar și un număr limită de unități de timp (<code>Ti</code>) până la care problema poate fi rezolvată.

= Cerința =
Cunoscând numărul de probleme, numărul de credite al fiecărei probleme precum și timpul limită de rezolvare al fiecărei probleme, scrieți un algoritm care determină <code>numărul maxim</code> de credite pe care le poate obține Maria.

= Date de intrare =
Pe prima linie a fișierului de intrare <code>crediteIN.txt</code> se găsește un număr natural <code>N</code>, reprezentând numărul de probleme de pe listă.

Pe următoarele <code>N</code> linii din fișierul de intrare vor fi datele despre fiecare problemă, pe linia <code>i+1</code> găsindu-se <code>2</code> numere naturale <code>Ci</code> și <code>Ti</code> care reprezintă numărul de credite, respectiv timpul limită pentru problema <code>i</code>.

= Date de ieșire =
În fișierul <code>crediteOUT.txt</code> se va afișa un singur număr natural, reprezentând numărul maxim de credite pe care Maria le poate obține.

= Restricții și precizări =

* <code>2 ≤ n ≤ 10000</code>
* <code>2 ≤ Ci ≤ 1000</code>
* <code>1 ≤ Ti ≤ 10000</code>

= Exemplul 1: =
<code>crediteIN.txt</code>
4
10 3
7 5
8 1
2 1
<code>crediteOUT.txt</code>
25

=== Explicație ===
Maria alege să rezolve problema 3, renunțând la problema 4 pentru ca are mai puține credite și același timp limită ca problema 3. După aceea va rezolva problemele 1 și 2, adunând în total 25 de credite.

== Exemplul 2: ==
<code>crediteIN.txt</code>
10001
10 3
7 5
8 1
2 1
<code>crediteOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import heapq

def verifica_restrictii(n, v):
if not (2 <= n <= 10000):
return False

for nrC, timpul in v:
if not (2 <= nrC <= 1000) or not (1 <= timpul <= 10000):
return False

return True

def main():
with open("crediteIN.txt", "r") as fin, open("crediteOUT.txt", "w") as fout:
n = int(fin.readline())
ans = 0
v = []
timp = [False] * 10001
tmax = 0

for _ in range(n):
line = fin.readline().strip()
if not line:
continue # Ignoră liniile goale

vals = line.split()
if len(vals) < 2:
fout.write("Datele din fisier nu sunt formatate corect")
return

nrC, timpul = map(int, vals)
v.append((nrC, timpul))
if timpul > tmax:
tmax = timpul
timp[timpul] = True

if not verifica_restrictii(n, v):
fout.write("Datele nu corespund restrictiilor impuse")
return

q = []

for i in range(tmax, 0, -1):
if timp[i]:
for nrC, timpul in v:
if timpul == i:
heapq.heappush(q, (-nrC, timpul))

if q:
nrC, timpul = heapq.heappop(q)
ans += -nrC

fout.write(str(ans))

if __name__ == "__main__":
main()

</syntaxhighlight>

0950 - Cerc 3

2024-03-23T00:19:30Z

Aurelia Raluca: Pagină nouă: == Enunț == Se consideră pe axa <code>Ox</code> din plan n puncte distincte reprezentând centrele a <code>n</code> cercuri numerotate cu numerele distincte de la <code>1</code> la <code>n</code>. Pentru fiecare cerc <code>k</code> se cunosc abscisa <code>xk</code> a centrului său şi raza sa <code>rk</code>. = Cerința = Să se scrie un program care să determine numărul <code>y</code> maxim de cercuri exterioare două câte două dintre cele <code>n</code>. = Date de...

== Enunț ==
Se consideră pe axa <code>Ox</code> din plan n puncte distincte reprezentând centrele a <code>n</code> cercuri numerotate cu numerele distincte de la <code>1</code> la <code>n</code>. Pentru fiecare cerc <code>k</code> se cunosc abscisa <code>xk</code> a centrului său şi raza sa <code>rk</code>.

= Cerința =
Să se scrie un program care să determine numărul <code>y</code> maxim de cercuri exterioare două câte două dintre cele <code>n</code>.

= Date de intrare =
Fișierul de intrare <code>cerc3IN.txt</code> conține pe prima linie pe prima linie, o valoare naturală n, reprezentând numărul de cercuri, iar pe următoarele n linii câte două numere naturale, separate printr-un spaţiu, care reprezintă abscisa <code>x1</code> a centrului primului cerc şi raza sa <code>r1</code>,…, abscisa <code>xn</code> a centrului celui de-al <code>n</code>-lea cerc şi raza sa <code>rn</code>.

= Date de ieșire =
Fișierul de ieșire <code>cerc3OUT.txt</code> va conține o linie pe care va fi scris numărul natural <code>y</code> reprezentând numărul maxim de cercuri exterioare ale căror centre sunt situate pe axa <code>Ox</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* numerele <code>n</code>, <code>x1</code>,<code>x2</code>,…,<code>xn</code>, <code>r1</code>, <code>r2</code>,…, <code>rn</code> sunt numere naturale
* <code>1 ≤ n ≤ 300</code>
* <code>1 ≤</code> <code>x1</code>,<code>x2</code>,…,<code>xn</code> <code>≤ 150</code>
* <code>1 ≤</code> <code>r1</code>, <code>r2</code>,…, <code>rn</code> <code>≤ 70</code>
* dacă două cercuri, dintre cele <code>n</code>, au centrele în acelaşi punct de pe axa <code>Ox</code>, atunci razele lor sunt distincte
* două cercuri sunt exterioare dacă nu au niciun punct comun şi nici interioarele lor nu au puncte comune

= Exemplul 1: =
<code>cerc3IN.txt</code>
8
3 1
1 4
8 1
11 2
15 2
16 6
21 2
21 1
<code>cerc3OUT.txt</code>
4

= Explicație =
Numărul maxim de cercuri exterioare două câte două este <code>y=4</code>.

== Exemplul 2: ==
<code>cerc3IN.txt</code>
301
3 1
1 4
8 1
11 2
15 2
16 6
21 2
21 1
<code>cerc3OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, cercuri):
if n < 1 or n > 300:
return False

for x, r in cercuri:
if x < 1 or x > 150 or r < 1 or r > 70:
return False

return True

def main():
with open("cerc3IN.txt", "r") as f, open("cerc3OUT.txt", "w") as g:
n_line = f.readline().strip()

if not n_line:
g.write("Datele din fisierul de intrare lipsesc sau sunt incomplete.")
return

try:
n = int(n_line)
except ValueError:
g.write("Numarul de cercuri este invalid.")
return

cercuri = []
for line in f:
values = line.split()
if len(values) != 2:
g.write("Datele din fisierul de intrare sunt incomplete sau au format invalid.")
return

try:
o, r = map(int, values)
except ValueError:
g.write("Coordonatele sau razele cercurilor sunt invalide.")
return

cercuri.append((o, r))

if not verificare_restrictii(n, cercuri):
g.write("Datele nu corespund restrictiilor impuse")
return

cercuri = [(o - r, o + r) for o, r in cercuri]
cercuri.sort(key=lambda x: x[1])

nr = 1
x = cercuri[0][1]
for i in range(1, n):
if x < cercuri[i][0]:
nr += 1
x = cercuri[i][1]

g.write(str(nr))

if __name__ == "__main__":
main()

</syntaxhighlight>

0384 - Saritura Calului 1

2024-03-23T00:13:39Z

Aurelia Raluca: Pagină nouă: = Cerinţa = Se consideră o tablă de şah cu <code>n</code> linii şi <code>m</code> coloane. La o poziţie dată se află un cal de şah, acesta putându-se deplasa pe tablă în modul specific acestei piese de şah (în L). Să se determine o modalitate de parcurgere a tablei de către calul dat, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie. Parcurgerea constă într-o matrice cu <code>n</code> linii și <code>m</code> coloane, fiecare element...

= Cerinţa =
Se consideră o tablă de şah cu <code>n</code> linii şi <code>m</code> coloane. La o poziţie dată se află un cal de şah, acesta putându-se deplasa pe tablă în modul specific acestei piese de şah (în L).

Să se determine o modalitate de parcurgere a tablei de către calul dat, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie. Parcurgerea constă într-o matrice cu <code>n</code> linii și <code>m</code> coloane, fiecare element al matricei având valoarea pasului la care se ajunge în acel element, sau <code>0</code>, dacă nu s-a ajuns.

= Date de intrare =
Fișierul de intrare <code>saritura_calului1IN.txt</code> conține numerele <code>n</code> şi <code>m</code> , apoi numere <code>x y</code>, reprezentând dimensiunile tablei (numărul de linii şi numărul de coloane) , respectiv coordonatele iniţiale ale calului (linie, coloana).

= Date de ieşire =
Fișierul de ieșire <code>saritura_calului1OUT.txt</code> va conține <code>n</code> linii cu câte <code>m</code> numere naturale cuprinse între <code>1</code> și <code>n*m</code>, separate prin exact un spațiu, reprezentând parcurgerea solicitată. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n,m ≤ 100</code>
* <code>1 ≤ istart ≤ n</code>
* <code>1 ≤ jstart ≤ m</code>
* scorul obținut pe fiecare test este proporțional cu gradul de acoperire a tablei. Astfel, dacă tabla este acoperită în întregime, se acordă 100% din punctaj. Dacă tabla este acoperită în proporție de 70%, se acordă 70% din punctaj, etc.

= Exemplul 1 =
<code>saritura_calului1IN.txt</code>
4 5 1 1
<code>saritura_calului1OUT.txt</code>
1 12 7 16 3
6 17 2 11 8
13 10 19 4 15
18 5 14 9 20

= Exemplul 2 =
<code>saritura_calului1IN.txt</code>
101 5 1 1
<code>saritura_calului1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def mutare_valida(tabla, vizitat, i, j, n, m):
return 0 <= i < n and 0 <= j < m and not vizitat[i][j]

def cal_tura(tabla, vizitat, i, j, n, m, contor_mutari):
di = [-1, -2, -2, -1, 1, 2, 2, 1]
dj = [-2, -1, 1, 2, 2, 1, -1, -2]

tabla[i][j] = contor_mutari
vizitat[i][j] = True
if contor_mutari == n * m:
return True

for k in range(8):
ni = i + di[k]
nj = j + dj[k]
if mutare_valida(tabla, vizitat, ni, nj, n, m):
if cal_tura(tabla, vizitat, ni, nj, n, m, contor_mutari + 1):
return True

tabla[i][j] = 0
vizitat[i][j] = False
return False

def verificare_restrictii(n, m, istart, jstart):
if not (1 <= n <= 100 and 1 <= m <= 100 and 1 <= istart <= n and 1 <= jstart <= m):
return False
return True

def afisare_tabla(tabla, fout):
for row in tabla:
fout.write(' '.join(map(str, row)) + '\n')

if __name__ == "__main__":
fin = open("saritura_calului1IN.txt", "r")
fout = open("saritura_calului1OUT.txt", "w")

n, m, istart, jstart = map(int, fin.readline().split())

if not verificare_restrictii(n, m, istart, jstart):
fout.write("Datele nu corespund restrictiilor impuse")
else:
tabla = [[0] * m for _ in range(n)]
vizitat = [[False] * m for _ in range(n)]

if cal_tura(tabla, vizitat, istart - 1, jstart - 1, n, m, 1):
afisare_tabla(tabla, fout)
else:
fout.write("Nu există soluție!")

fin.close()
fout.close()

</syntaxhighlight>

0403 - Concert

2024-03-23T00:00:31Z

Aurelia Raluca: Pagină nouă: = Cerinţa = Gigel este un cântăreț începător. El știe deja să cânte <code>n</code> melodii, și pentru fiecare melodie se cunoaște durata, exprimată în minute și secunde. Gigel va participa la o emisiune de televiziune, unde va putea cânta timp de <code>T</code> secunde. El vrea să cânte cât mai multe melodii, pentru a-și demonstra talentul deosebit. Ajutați-l să aleagă piesele pentru emisiune, și vă va răsplăti cu un autograf. = Date de intrare = F...

= Cerinţa =
Gigel este un cântăreț începător. El știe deja să cânte <code>n</code> melodii, și pentru fiecare melodie se cunoaște durata, exprimată în minute și secunde. Gigel va participa la o emisiune de televiziune, unde va putea cânta timp de <code>T</code> secunde. El vrea să cânte cât mai multe melodii, pentru a-și demonstra talentul deosebit.

Ajutați-l să aleagă piesele pentru emisiune, și vă va răsplăti cu un autograf.

= Date de intrare =
Fişierul de intrare <code>concerIN.txt</code> conţine pe prima linie numerele <code>n T</code>. Fiecare dintre următoarele <code>n</code> linii conține durata unei melodii, în formatul <code>m:s</code>, unde <code>m</code> și <code>s</code> pot avea una sau două cifre.

= Date de ieşire =
Fişierul de ieşire <code>concertOUT.txt</code> va conţine pe prima linie numărul <code>M</code>, reprezentând numărul maxim de melodii care pot fi alese. Următoarea linie va conține <code>M</code> numere între <code>1</code> și <code>n</code>, reprezentând numărul de ordine al melodiilor alese, așa cum sunt ele date în fișierul de intrare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ T ≤ 1000</code>
* <code>0 ≤ m ≤ 10</code>
* <code>0 ≤ s ≤ 59</code>

= Exemplul 1: =
<code>concertIN.txt</code>
7 450
2:30
1:45
2:10
03:00
01:15
02:05
2:05
<code>concertOUT.txt</code>
4
2 5 6 7

= Explicație =
În <code>450</code> de secunde se pot cânta maxim <code>4</code> melodii, de exemplu cele numerotate cu: <code>2 5 6 7</code>.

== Exemplul 2: ==
<code>concertIN.txt</code>
101 450
2:30
1:45
2:10
03:00
01:15
02:05
2:05
<code>concertOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, t):
if not (1 <= n <= 100 and 1 <= t <= 1000):
return False
return True

def main():
with open("concertIN.txt", "r") as fin, open("concertOUT.txt", "w") as fout:
n, t = map(int, fin.readline().split())

if not verificare_restrictii(n, t):
fout.write("Datele nu corespund restrictiilor impuse")
return

v = [(0, 0)] * (n + 1)
for i in range(1, n + 1):
s = fin.readline().strip()
hour, minute = map(int, s.split(':'))
if not (0 <= hour <= 10 and 0 <= minute <= 59):
fout.write("Datele nu corespund restrictiilor impuse")
return
v[i] = (60 * hour + minute, i)

v.sort()

indici = []
for i in range(1, n + 1):
if v[i][0] <= t:
t -= v[i][0]
indici.append(v[i][1])

indici.sort()

fout.write(str(len(indici)) + '\n')
fout.write(' '.join(map(str, indici)) + ' ')

if __name__ == "__main__":
main()

</syntaxhighlight>

0401 - Pachete Multe

2024-03-22T23:54:12Z

Aurelia Raluca: Pagină nouă: = Cerinţa = Într-un depozit foarte mare există un raft cu <code>n+1</code> spații de depozitare, numerotate de la <code>1</code> la <code>n+1</code>. Primele <code>n</code> spatii de depozitare sunt ocupate cu <code>n</code> pachete numerotate cu valori între <code>1</code> și <code>n</code>, iar spațiul de depozitare <code>n+1</code> este gol. Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice <code>i</code>, pachetul numerotat cu <cod...

= Cerinţa =
Într-un depozit foarte mare există un raft cu <code>n+1</code> spații de depozitare, numerotate de la <code>1</code> la <code>n+1</code>. Primele <code>n</code> spatii de depozitare sunt ocupate cu <code>n</code> pachete numerotate cu valori între <code>1</code> și <code>n</code>, iar spațiul de depozitare <code>n+1</code> este gol.

Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice <code>i</code>, pachetul numerotat cu <code>i</code> să se afle în spațiul de depozitare <code>i</code>. Pentru aceasta se va folosi spațiul de depozitare suplimentar, <code>n+1</code>, singura manevră validă fiind mutarea unui pachet dintr-un spațiu de depozitare în altul, cu condiția ca acesta să fie gol.

Determinați o succesiune de manevre prin care fiecare pachet să fie în spațiul corect.

= Date de intrare =
Fişierul de intrare <code>pachete_multeIN.txt</code> conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale separate prin spaţii. Al <code>i</code>-lea număr reprezintă numărul pachetului aflat în spațiul de depozitare <code>i</code>.

= Date de ieşire =
Fişierul de ieşire <code>pachete_multeOUT.txt</code> va conţine pe prima linie numărul <code>M</code>, reprezentând numărul de manevre efectuate. Pe fiecare dintre următoarele <code>M</code> linii se descrie o manevră, prin două numere <code>i j</code>, cu semnificația: se ia pachetul din spațiul <code>i</code> și se mută în spațiul <code>j</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100000</code> <— ATENȚIE AICI
* pentru fiecare manevră <code>i j</code> efectuată, <code>1 ≤ i,j ≤ n+1</code>, <code>i ≠ j</code>, iar spațiul <code>j</code> trebuie să fie gol
* numărul de manevre realizate nu trebuie să fie minim

= Exemplul 1: =
<code>pachete_multeIN.txt</code>
5
2 5 4 3 1
<code>pachete_multeOUt.txt</code>
7
1 6
5 1
2 5
6 2
3 6
4 3
6 4

= Exemplul 2: =
<code>pachete_multeIN.txt</code>
100001
2 5 4 3 1
<code>pachete_multeOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restricțiile(n, sol):
if n < 1 or n > 100000:
return False

for i in range(1, n + 1):
if sol[0][i] < 1 or sol[0][i] > n + 1 or sol[1][i] < 1 or sol[1][i] > n + 1 or sol[0][i] == sol[1][i]:
return False

return True

def main():
INTRARE = "pachete_multeIN.txt"
IESIRE = "pachete_multeOUT.txt"

NMAX = 1000 * 100 + 1

v = [0] * NMAX
p = [0] * NMAX
sol = [[0] * (NMAX * 2) for _ in range(2)]

with open(INTRARE, 'r') as intrare, open(IESIRE, 'w') as iesire:
n = int(intrare.readline())
data = list(map(int, intrare.readline().split()))

if len(data) != n:
iesire.write("Datele nu corespund restrictiilor impuse\n")
return

for i in range(1, n + 1):
v[i] = data[i - 1]
p[data[i - 1]] = i

p[0] = n + 1
nr = 0
for i in range(1, n + 1):
if v[i] == i:
continue

if p[0] != i:
nr += 1
sol[0][nr] = i
sol[1][nr] = p[0]
v[p[0]] = v[i]
p[v[i]] = p[0]
v[i] = 0
p[0] = i

nr += 1
sol[0][nr] = p[i]
sol[1][nr] = i
v[i] = i
v[p[i]] = 0
p[0] = p[i]
p[i] = i

if not verifica_restricțiile(n, sol):
iesire.write("Datele nu corespund restrictiilor impuse\n")
return

iesire.write(str(nr) + '\n')
for i in range(1, nr + 1):
iesire.write(str(sol[0][i]) + ' ' + str(sol[1][i]) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

1220 - Scadere

2024-03-22T23:36:20Z

Aurelia Raluca:

== Enunt ==

Fie <code>n</code> un număr natural nenul.

Să considerăm o expresie de forma: <code>x[1]-x[2]-x[3]-...-x[n]</code>

Se ştie că scăderea nu este o operaţie asociativă, adică <code>x[1]-(x[2]-x[3])≠(x[1]-x[2])-x[3]</code>.

Ca urmare, prin plasarea unor perechi de paranteze în expresie, putem obţine diferite valori.

Pentru problema noastră, vom denumi scădere o expresie de forma de mai sus în care pot apărea şi paranteze rotunde care se închid corect. Valoarea unei scăderi se obţine efectuând operaţiile de scădere în ordine de la stânga la dreapta; dacă apar paranteze, se efectuează mai întâi operaţiile din paranteze.

= Cerinţe =
Date fiind valorile <code>x[1]</code>, <code>x[2]</code>, …, <code>x[n]</code> care intervin în scădere, scrieţi un program care să rezolve următoarele două cerinţe:

# să se determine valoarea maximă a unei scăderi (obţinută prin inserarea convenabilă a unor paranteze rotunde în expresia <code>x[1]-x[2]-x[3]-...-x[n]</code>), precum şi o scădere având valoare maximă.
# să se determine valoarea unei scăderi specificate.

= Date de intrare =
Fişierul de intrare <code>scadereIN.txt</code> conţine pe prima linie un număr natural <code>c</code> indicând cerinţa care trebuie să fie rezolvată (<code>1</code> sau <code>2</code>). Pe a doua linie este scris numărul natural <code>n</code>, care reprezintă numărul de variabile care intervin în scădere. Variabilele sunt numerotate de la <code>1</code> la <code>n</code> în ordinea în care intervin în scădere. Pe următoarele <code>n</code> linii sunt scrise în ordine valorile variabilelor <code>x[1], x[2], ..., x[n]</code>, câte o valoare pe o linie. Dacă cerinţa este <code>2</code>, fişierul mai conţine o linie pe care este scris un şir de caractere reprezentând o scădere.

= Date de ieșire =
Fişierul de ieşire <code>scadereOUT.txt</code> va conţine pentru <code>c=1</code> două linii; pe prima linie va fi scris un număr întreg reprezentând valoarea maximă a unei scăderi (obţinută prin inserarea convenabilă a unor paranteze rotunde în expresia <code>x[1]-x[2]-x[3]-...-x[n]</code>), iar pe a doua linie o scădere având valoare maximă. Dacă <code>c=2</code> fişierul de ieşire va conţine o singură linie pe care va fi scris un număr întreg reprezentând valoarea scăderii specificate pe ultima linie a fişierului de intrare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>3 ≤ n ≤ 5000</code>
* Valorile variabilelor <code>x[1]</code>, <code>x[2]</code>, …, <code>x[n]</code> sunt numere întregi din intervalul <code>[-100, 100]</code>.
* Scăderea din fişierul de intrare, respectiv scăderea de valoare maximă afişată în fişierul de ieşire vor avea maxim <code>40000</code> de caractere care pot fi doar cifre, litera mică <code>'x'</code>, paranteze rotunde şi operatorul <code>'-'</code> (minus).
* Pentru teste valorând 50% din punctaj cerinţa va fi <code>1</code>. Pentru afişarea corectă a valorii maxime se acordă 40% din punctajul pe test. Punctajul integral se acordă pentru afişarea corectă a valorii maxime şi a unei scăderi de valoare maximă.

= Exemplul 1 =
<code>scadereIN.txt</code>
1
4
-7
5
-10
19
<code>scadereOUT.txt</code>
17
x1-x2-(x3-x4)

= Exemplul 2 =
<code>scadereIN.txt</code>
2
4
-7
5
-10
19
x1-((x2-x3)-x4)
<code>scadereOUT.txt</code>
-3

= Explicație =
Parantezarea care conduce la valoarea maximă este:

<code>x1-x2-(x3-x4) = -7-5-(-10-19) = -12-(-29) = -12+29 = 17</code>

<code>x1-((x2-x3)-x4) = -7-((5-10)-19) = -7-(15-19) = -7-(-4) = -7+4 = -3</code>

== Exemplul 1 ==
<code>scadereIN.txt</code>
1
2
-7
5
-10
19
<code>scadereOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def evaleaza_expresie(s, x):
stiva = [float('inf')]
i = 0
while i < len(s):
if s[i] == '(':
stiva.append(float('inf'))
i += 1
elif s[i] == ')':
if stiva[-2] == float('inf'):
stiva[-2] = stiva[-1]
else:
stiva[-2] -= stiva[-1]
stiva.pop()
i += 1
else:
if s[i] == '-':
i += 1
if s[i] == 'x':
i += 1
nr = 0
while '0' <= s[i] <= '9':
nr = nr * 10 + int(s[i])
i += 1
if stiva[-1] == float('inf'):
stiva[-1] = x[nr - 1]
else:
stiva[-1] -= x[nr - 1]
return stiva[0]

def citeste_date_intrare(nume_fisier):
with open(nume_fisier, "r") as fin:
cerinta = int(fin.readline().strip())
n = int(fin.readline().strip())
x = [int(fin.readline().strip()) for _ in range(n)]
s = None
if cerinta != 1:
s = fin.readline().strip()
return cerinta, n, x, s

def scrie_rezultate(nume_fisier, cerinta, x, s=None):
with open(nume_fisier, "w") as fout:
if cerinta == 1:
rez = x[0] - x[1]
for i in range(2, len(x)):
if x[i] >= 0:
rez += x[i]
else:
rez -= x[i]
fout.write(str(rez) + '\n')
fout.write("x1-")
nr_paranteze = 0
for i in range(2, len(x)):
if x[i] >= 0:
if nr_paranteze % 2 == 0:
fout.write("(")
nr_paranteze += 1
else:
if nr_paranteze % 2:
fout.write("(")
nr_paranteze += 1
fout.write("x" + str(i - 1) + "-")
fout.write("x" + str(len(x)) + "")
for i in range(nr_paranteze):
fout.write(")")
fout.write('\n')
else:
rezultat = evaleaza_expresie(s, x)
fout.write(str(rezultat) + '\n')

def verifica_restrictii(n, x):
if not (3 <= n <= 5000):
return False

for val in x:
if not (-100 <= val <= 100):
return False

return True

def main():
nume_intrare = "scadereIN.txt"
nume_iesire = "scadereOUT.txt"
cerinta, n, x, s = citeste_date_intrare(nume_intrare)

if not verifica_restrictii(n, x):
with open(nume_iesire, "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

scrie_rezultate(nume_iesire, cerinta, x, s)

if __name__ == "__main__":
main()

</syntaxhighlight>

1220 - Scadere

2024-03-22T23:36:04Z

Aurelia Raluca:

== Enunt ==

Fie <code>n</code> un număr natural nenul.

Să considerăm o expresie de forma: <code>x[1]-x[2]-x[3]-...-x[n]</code>

Se ştie că scăderea nu este o operaţie asociativă, adică <code>x[1]-(x[2]-x[3])≠(x[1]-x[2])-x[3]</code>.

Ca urmare, prin plasarea unor perechi de paranteze în expresie, putem obţine diferite valori.

Pentru problema noastră, vom denumi scădere o expresie de forma de mai sus în care pot apărea şi paranteze rotunde care se închid corect. Valoarea unei scăderi se obţine efectuând operaţiile de scădere în ordine de la stânga la dreapta; dacă apar paranteze, se efectuează mai întâi operaţiile din paranteze.

= Cerinţe =
Date fiind valorile <code>x[1]</code>, <code>x[2]</code>, …, <code>x[n]</code> care intervin în scădere, scrieţi un program care să rezolve următoarele două cerinţe:

# să se determine valoarea maximă a unei scăderi (obţinută prin inserarea convenabilă a unor paranteze rotunde în expresia <code>x[1]-x[2]-x[3]-...-x[n]</code>), precum şi o scădere având valoare maximă.
# să se determine valoarea unei scăderi specificate.

= Date de intrare =
Fişierul de intrare <code>scadereIN.txt</code> conţine pe prima linie un număr natural <code>c</code> indicând cerinţa care trebuie să fie rezolvată (<code>1</code> sau <code>2</code>). Pe a doua linie este scris numărul natural <code>n</code>, care reprezintă numărul de variabile care intervin în scădere. Variabilele sunt numerotate de la <code>1</code> la <code>n</code> în ordinea în care intervin în scădere. Pe următoarele <code>n</code> linii sunt scrise în ordine valorile variabilelor <code>x[1], x[2], ..., x[n]</code>, câte o valoare pe o linie. Dacă cerinţa este <code>2</code>, fişierul mai conţine o linie pe care este scris un şir de caractere reprezentând o scădere.

= Date de ieșire =
Fişierul de ieşire <code>scadereOUT.txt</code> va conţine pentru <code>c=1</code> două linii; pe prima linie va fi scris un număr întreg reprezentând valoarea maximă a unei scăderi (obţinută prin inserarea convenabilă a unor paranteze rotunde în expresia <code>x[1]-x[2]-x[3]-...-x[n]</code>), iar pe a doua linie o scădere având valoare maximă. Dacă <code>c=2</code> fişierul de ieşire va conţine o singură linie pe care va fi scris un număr întreg reprezentând valoarea scăderii specificate pe ultima linie a fişierului de intrare.

= Restricții și precizări =

* <code>3 ≤ n ≤ 5000</code>
* Valorile variabilelor <code>x[1]</code>, <code>x[2]</code>, …, <code>x[n]</code> sunt numere întregi din intervalul <code>[-100, 100]</code>.
* Scăderea din fişierul de intrare, respectiv scăderea de valoare maximă afişată în fişierul de ieşire vor avea maxim <code>40000</code> de caractere care pot fi doar cifre, litera mică <code>'x'</code>, paranteze rotunde şi operatorul <code>'-'</code> (minus).
* Pentru teste valorând 50% din punctaj cerinţa va fi <code>1</code>. Pentru afişarea corectă a valorii maxime se acordă 40% din punctajul pe test. Punctajul integral se acordă pentru afişarea corectă a valorii maxime şi a unei scăderi de valoare maximă.

= Exemplul 1 =
<code>scadereIN.txt</code>
1
4
-7
5
-10
19
<code>scadereOUT.txt</code>
17
x1-x2-(x3-x4)

= Exemplul 2 =
<code>scadereIN.txt</code>
2
4
-7
5
-10
19
x1-((x2-x3)-x4)
<code>scadereOUT.txt</code>
-3

= Explicație =
Parantezarea care conduce la valoarea maximă este:

<code>x1-x2-(x3-x4) = -7-5-(-10-19) = -12-(-29) = -12+29 = 17</code>

<code>x1-((x2-x3)-x4) = -7-((5-10)-19) = -7-(15-19) = -7-(-4) = -7+4 = -3</code>

== Exemplul 1 ==
<code>scadereIN.txt</code>
1
2
-7
5
-10
19
<code>scadereOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def evaleaza_expresie(s, x):
stiva = [float('inf')]
i = 0
while i < len(s):
if s[i] == '(':
stiva.append(float('inf'))
i += 1
elif s[i] == ')':
if stiva[-2] == float('inf'):
stiva[-2] = stiva[-1]
else:
stiva[-2] -= stiva[-1]
stiva.pop()
i += 1
else:
if s[i] == '-':
i += 1
if s[i] == 'x':
i += 1
nr = 0
while '0' <= s[i] <= '9':
nr = nr * 10 + int(s[i])
i += 1
if stiva[-1] == float('inf'):
stiva[-1] = x[nr - 1]
else:
stiva[-1] -= x[nr - 1]
return stiva[0]

def citeste_date_intrare(nume_fisier):
with open(nume_fisier, "r") as fin:
cerinta = int(fin.readline().strip())
n = int(fin.readline().strip())
x = [int(fin.readline().strip()) for _ in range(n)]
s = None
if cerinta != 1:
s = fin.readline().strip()
return cerinta, n, x, s

def scrie_rezultate(nume_fisier, cerinta, x, s=None):
with open(nume_fisier, "w") as fout:
if cerinta == 1:
rez = x[0] - x[1]
for i in range(2, len(x)):
if x[i] >= 0:
rez += x[i]
else:
rez -= x[i]
fout.write(str(rez) + '\n')
fout.write("x1-")
nr_paranteze = 0
for i in range(2, len(x)):
if x[i] >= 0:
if nr_paranteze % 2 == 0:
fout.write("(")
nr_paranteze += 1
else:
if nr_paranteze % 2:
fout.write("(")
nr_paranteze += 1
fout.write("x" + str(i - 1) + "-")
fout.write("x" + str(len(x)) + "")
for i in range(nr_paranteze):
fout.write(")")
fout.write('\n')
else:
rezultat = evaleaza_expresie(s, x)
fout.write(str(rezultat) + '\n')

def verifica_restrictii(n, x):
if not (3 <= n <= 5000):
return False

for val in x:
if not (-100 <= val <= 100):
return False

return True

def main():
nume_intrare = "scadereIN.txt"
nume_iesire = "scadereOUT.txt"
cerinta, n, x, s = citeste_date_intrare(nume_intrare)

if not verifica_restrictii(n, x):
with open(nume_iesire, "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

scrie_rezultate(nume_iesire, cerinta, x, s)

if __name__ == "__main__":
main()

</syntaxhighlight>

2194 - identice3

2024-03-22T23:23:37Z

Aurelia Raluca:

== Enunt ==

Mihai a construit o matrice pătratică <code>A</code> de dimensiune <code>N</code> cu valori în mulțimea <code>{0,1}</code>. El preferă acele matrice care au toate elementele identice și de aceea a calculat pentru matricea <code>A</code>, numărul <code>K</code> de submatrice care au toate elementele identice. Acum, Mihai vrea să transforme matricea <code>A</code> într-o matrice cu toate elementele identice. Pentru aceasta, el a selectat un număr natural nenul <code>D</code>, și definește operația ZET care constă în alegerea unei submatrice pătratice de dimensiunea <code>D</code> din matricea precedentă în care schimbă toate elementele <code>0</code> în <code>1</code> și invers. El vrea să aplice operația ZET inițial pentru matricea <code>A</code>, apoi repetă operația pentru matricea obținută la momentul anterior, de un număr minim de ori, notat <code>R</code>, până când matricea obținută are toate elementele identice, sau dacă nu este posibil, <code>R</code> va avea valoarea <code>-1</code>.

= Cerința =
Mihai vă roagă să calculați valorile <code>K</code> și <code>R</code>. Pentru a preciza tipul cerinței, Mihai folosește un cod <code>T</code> care dacă are valoarea <code>1</code>, atunci solicită calcularea valorii <code>K</code>, iar dacă <code>T</code> are valoarea <code>2</code>, atunci solicită calcularea valorii <code>R</code>.

= Date de intrare =
Fișierul de intrare <code>identice3IN.txt</code> se vor afla numerele naturale <code>T</code>, <code>N</code> și <code>D</code>, cu semnificația de mai sus, separate prin câte un spațiu. Pe următoarele <code>N</code> linii se vor afla câte <code>N</code> valori de <code>0</code> și <code>1</code>, elementele liniilor matricei <code>A</code>, fără spații între ele.

= Date de ieșire =
Fișierul de ieșire <code>identice3OUT.txt</code> se va afla un număr natural, respectiv valoarea <code>K</code> pentru <code>T = 1</code> sau valoarea <code>R</code> pentru <code>T = 2</code>.

= Restricții și precizări =

* <code>1 < D < N ≤ 1000</code>
* Pentru calcularea valorii <code>K</code>, submatricele pot fi pătratice sau dreptunghiulare, cu diferite dimensiuni (inclusiv <code>1</code>), cu elementele identice.

= Exemplul 1: =
<code>identice3IN.txt</code>
1 4 2
0011
0011
1100
1100
<code>identice3OUT.txt</code>
36

=== Explicație ===
<code>T = 1</code>, deci se calculează <code>K = 36</code>. Sunt <code>18</code> submatrice cu toate elementele <code>0</code> și <code>18</code> cu toate elementele <code>1</code>.

= Exemplul 2: =
<code>identice3IN.txt</code>
2 4 2
0011
0011
1100
1100
<code>identice3OUT.txt</code>
2

=== Explicație ===
<code>T = 2</code>, deci se calculează <code>R = 2</code>, deoarece sunt necesare <code>2</code> aplicări ale operației ZET.

== Exemplul 3: ==
<code>identice3IN.txt</code>
1 1001 2
0011
0011
1100
1100
<code>identice3OUT.txt</code>
Datele nu corespund restrictiilor impuse

=== Rezolvare ===
<syntaxhighlight lang="python3" line="1">
Nmax = 1005
opus = {'0': '1', '1': '0'}
t0 = [[0] * Nmax for _ in range(Nmax)]
st0 = [0] * Nmax
val0 = [0] * Nmax
t1 = [[0] * Nmax for _ in range(Nmax)]
st1 = [0] * Nmax
val1 = [0] * Nmax
M0 = [[0] * Nmax for _ in range(Nmax)]
M1 = [[0] * Nmax for _ in range(Nmax)]
p0 = [0] * Nmax
p1 = [0] * Nmax

def check_restrictions():
return 1 < d < n <= 1000

def read():
global test, n, d, a, a1
with open("identice3IN.txt", 'r') as in_file:
test, n, d = map(int, in_file.readline().split())
if not check_restrictions():
return False
a = [[''] * (n + 2) for _ in range(n + 2)] # Adjusted size
a1 = [[''] * (n + 1) for _ in range(n + 1)] # Adjusted size
for i in range(1, n + 1):
a[i][1:n + 1] = in_file.readline().strip()
for j in range(1, n + 1):
a1[i][j] = opus[a[i][j]]
return True

def solve0():
global sum0, a
sum0 = 0
for j in range(1, n + 1):
vf0 = 0
for i in range(1, n + 1):
if a[i][j] == '0':
t0[i][j + 1] = 1 + t0[i][j]
m = 1
while vf0 > 0 and st0[vf0] >= t0[i][j + 1]:
m += val0[vf0]
vf0 -= 1
vf0 += 1
st0[vf0] = t0[i][j + 1]
val0[vf0] = m
sum0 += val0[vf0] * st0[vf0]

def solve1():
global sum1, a
sum1 = 0
for j in range(1, n + 1):
vf1 = 0
for i in range(1, n + 1):
if a[i][j] == '1':
t1[i][j + 1] = 1 + t1[i][j]
m = 1
while vf1 > 0 and st1[vf1] >= t1[i][j + 1]:
m += val1[vf1]
vf1 -= 1
vf1 += 1
st1[vf1] = t1[i][j + 1]
val1[vf1] = m
sum1 += val1[vf1] * st1[vf1]

def R0():
global sol0, a
sol0 = 0
for i in range(1, n + 1):
for j in range(1, n + 1):
M0[i][j] += M0[i - 1][j]
p0[j] = p0[j - 1] + M0[i][j]
t = p0[j] & 1
if i > n - d + 1 or j > n - d + 1:
if t != int(a[i][j]):
return -1
elif t != int(a[i][j]):
sol0 += 1
M0[i][j] += 1
M0[i + d][j] -= 1
M0[i][j + d] -= 1
M0[i + d][j + d] += 1
p0[j] += 1
return sol0

def R1():
global sol1, a
sol1 = 0
for i in range(1, n + 1):
for j in range(1, n + 1):
M1[i][j] += M1[i - 1][j]
p1[j] = p1[j - 1] + M1[i][j]
t = p1[j] & 1
if i > n - d + 1 or j > n - d + 1:
if t != int(a1[i][j]):
return -1
elif t != int(a1[i][j]):
sol1 += 1
M1[i][j] += 1
M1[i + d][j] -= 1
M1[i][j + d] -= 1
M1[i + d][j + d] += 1
p1[j] += 1
return sol1

def main():
if not read():
with open("identice3OUT.txt", 'w') as out_file:
out_file.write("Datele nu corespund restrictiilor impuse\n")
return

if test == 1:
solve0()
solve1()
with open("identice3OUT.txt", 'w') as out_file:
out_file.write(str(sum0 + sum1) + '\n')
else:
R0_result = R0()
R1_result = R1()
rx = min(R0_result, R1_result)
ry = max(R0_result, R1_result)
if rx == -1:
rx = ry
with open("identice3OUT.txt", 'w') as out_file:
out_file.write(str(rx) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

3444 - Arh

2024-03-22T23:05:05Z

Aurelia Raluca:

== Enunt ==

Dexter și-a definit propriul algoritm de arhivare a șirului favorit <code>T</code>, șir format numai din litere mici ale alfabetului englez. Șirul arhivat, notat cu <code>S</code>, poate fi format din cifre, litere mici ale alfabetului englez, parantezele drepte <code>'['</code> și <code>']'</code> și parantezele rotunde <code>'('</code> și <code>')'</code>, precum și caractere <code>'*'</code>.

Fixi, curios din fire, descoperă algoritmul și încearcă să dezarhiveze șirul <code>S</code>, prin efectuarea unor transformări repetate. O transformare poate fi de unul dintre cele <code>3</code> tipuri de mai jos, unde s-a notat cu <code>C</code> o secvență din <code>S</code> formată numai din litere.

# O secvență a lui <code>S</code> de forma <code>n(C)</code>, unde <code>n</code> este numărul natural poziționat imediat înaintea parantezei rotunde, se transformă într-o secvență <code>D</code> obținută prin scrierea concatenată, de <code>n</code> ori, a șirului <code>C</code>. Exemplu: pentru secvența <code>10(ab)</code> avem <code>n=10</code> și se obține secvența <code>D=abababababababababab</code>.
# O secvență a lui <code>S</code> de forma <code>[*C]</code> se transformă într-o secvență palindromică de lungime pară, obținută prin concatenarea secvenței <code>C</code> cu oglinditul lui <code>C</code>. Exemplu: din secvența <code>[*abc]</code> se obține secvența palindromică de lungime pară <code>abccba</code>
# O secvență a lui <code>S</code> de forma <code>[C*]</code> se transformă într-o secvență palindromică de lungime impară, obținută prin concatenarea secvenței <code>C</code> cu oglinditul lui <code>C</code> din care s-a eliminat primul caracter. Exemplu: din secvența <code>[abc*]</code> se obține secvența palindromică de lungime impară <code>abcba</code>.

Un șir se consideră dezarhivat dacă este format numai din litere mici ale alfabetului englez.

= Cerința =
Fiind dat șirul arhivat <code>S</code> să se determine numărul de transformări, de cele <code>3</code> tipuri de mai sus, realizate de Fixi în cadrul algoritmului de dezarhivare, precum și forma finală dezarhivată <code>T</code> a șirului <code>S</code>.

= Date de intrare =
Fișierul de intrare <code>arhIN.txt</code> conține șirul de caractere arhivat <code>S</code>.

= Date de ieșire =
Fișierul de ieșire <code>arhOUT.txt</code> va conține obligatoriu două linii. Pe prima linie numărul de transformări cerut, iar pe linia a doua șirul de caractere cerut, <code>T</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 <</code> lungimea șirului arhivat <code>S ≤ 10000</code>; <code>0 <</code> lungimea șirului dezarhivat <code>T ≤ 100000</code>;
* <code>1 < n ≤ 1000</code>;
* O secvență a unui șir este o succesiune de caractere aflate pe poziții consecutive în şir;
* În șirul <code>S</code> o cifră poate apărea numai imediat înaintea unei paranteze rotunde deschise sau imediat înaintea unei alte cifre; fiecare paranteză rotundă deschisă are imediat înaintea sa cel puțin o cifră; toate parantezele, drepte sau rotunde, se închid corect. Caracterul <code>*</code> poate apărea numai imediat după o paranteză dreaptă deschisă sau imediat înaintea unei paranteze drepte închise;
* O secvenţă a unui șir este palindromică dacă primul element al secvenţei este egal cu ultimul, al doilea cu penultimul etc; oglinditul unei secvențe se obține prin scriere în ordine inversă a caracterelor sale;
* Se acordă 20% din punctajul fiecărui test pentru scrierea corectă a numărului cerut și 80% din punctajul fiecărui test pentru scrierea corectă a șirului cerut;
* Pentru 30 de puncte șirul arhivat <code>S</code> poate fi dezarhivat numai cu transformări de tipul <code>1</code>;
* Pentru alte 30 de puncte șirul arhivat <code>S</code> poate fi dezarhivat numai cu transformări de tipurile <code>2</code> și <code>3</code>.
* În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

= Exemplul 1 =
<code>arhIN.txt</code>
2(a)[*a2(b)]xy[2(c)b*]d
<code>arhOUT.txt</code>
5
aaabbbbaxyccbccd

=== Explicație ===
<code>2(a)</code> => <code>aa</code>

<code>2(b)</code> => <code>bb</code>

<code>[*a2(b)]</code> => <code>[*abb]</code> => <code>abbbba</code>

<code>2(c)</code> => <code>cc</code>

<code>[2(c)b*]</code> => <code>[ccb*]</code> => <code>ccbcc</code>

= Exemplul 2 =
<code>arhIN.txt</code>
2(ab[cd*])a3(xyz)
<code>arhOUT.txt</code>
3
abcdcabcdcaxyzxyzxyz

=== Explicație ===
<code>3(xyz)</code> => <code>xyzxyzxyz</code>

<code>[cd*]</code> => <code>cdc</code>

<code>2(ab[cd*])</code> => <code>2(abcdc)</code> => <code>abcdcabcdc</code>

== Exemplul 3 ==
<code>arhIN.txt</code>
1001(a)[*a2(b)]xy[2(c)b*]d
<code>arhOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
fin = None
fout = None
s = ""
transf = 0
p = 0

def repeatOp():
global p, transf
transf += 1
ori = 0
while p < len(s) and s[p].isdigit():
ori = ori * 10 + int(s[p])
p += 1

p += 1 # sar peste '('
ans, deRepetat = "", ""

while s[p] != ')':
deRepetat += termen()
p += 1 # sar peste ')'

while ori > 0:
ans += deRepetat
ori -= 1

return ans

def palParOp():
global p, transf
transf += 1
p += 2 # sar peste '[*'
ans = ""

while s[p] != ']':
ans += termen()

for i in range(len(ans) - 1, -1, -1):
ans += ans[i]
p += 1 # sar peste ']'

return ans

def palImpOp():
global p, transf
transf += 1
p += 1 # sar peste '['
ans = ""

while s[p] != '*':
ans += termen()

for i in range(len(ans) - 2, -1, -1):
ans += ans[i]
p += 2 # sar peste '*]'

return ans

def termen():
global p
ans = ""
if s[p].isdigit():
ans = repeatOp()
elif s[p] == '[' and s[p + 1] == '*':
ans = palParOp()
elif s[p] == '[':
ans = palImpOp()
elif s[p].isalpha():
ans = s[p]
p += 1

return ans

def eval():
ans = ""
while p < len(s):
ans += termen()

return ans

def check_constraints(s, n):
if not (0 < len(s) <= 10000 and 1 < n <= 1000):
return False
return True

def main():
global s
with open("arhIN.txt", "r") as fin:
s = fin.readline().strip()

# Extragem n din șirul arhivat
if '(' in s:
n = int(s.split('(')[0])
else:
with open("arhOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

if not check_constraints(s, n):
with open("arhOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

ans = eval()

with open("arhOUT.txt", "w") as fout:
fout.write(f"{transf}\n{ans}")

if __name__ == "__main__":
main()

</syntaxhighlight>

3453 - jungla

2024-03-22T22:28:31Z

Aurelia Raluca:

= Cerința =
În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut <code>N</code> numere, <code>v[1], v[2], ..., v[N]</code>, unde <code>V[i]</code> reprezintă înălțimea copacului <code>i</code>. Apoi i-au venit în minte două întrebări.

Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine <code>i</code> au înălțimile mai mici ca acesta.

A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate <code>(1,1)</code> , iar cel din dreapta sus de coordonate <code>(N,H)</code>, unde <code>N</code> este numărul de copaci, iar <code>H</code> este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine <code>i</code> ocupă primele <code>v[i]</code> unități de pe coloana <code>i</code>, de jos in sus (<code>v[i]</code> reprezintă înălțimea copacului <code>i</code>).

= Date de intrare =
Programul citește de la tastatură un număr <code>p</code>, care poate avea valorile <code>1</code> sau <code>2</code>, în funcție de cerința problemei.

Pentru <code>p = 1</code>, următorul rând conține numerele <code>N q</code>. Următorul rând conține <code>n</code> valori, a <code>i</code> -a valoare reprezentând înălțimea copacului cu numarul de ordine. Rândul următor conține <code>q</code> numere; pentru fiecare număr <code>i</code> se cere numarul de copaci plantați înaintea copacului cu numărul de ordine <code>i</code> cu înălțimi mai mici ca acesta.

Pentru <code>p = 2</code>, următorul rând va conține doar numărul <code>N</code>, iar ultimul rând va conține <code>N</code> valori reprezentând înălțimile copacilor.

= Date de ieșire =
Pentru <code>p = 1</code> programul va afișa <code>q</code> linii; pe fiecare linie se va afla raspunsul pentru fiecare dintre cele <code>q</code> numere date.

Pentru <code>p = 2</code> programul fa afișa singur numar, reprezentând raspunsul pentru cerinta <code>2</code> , adică dreptunghiul liber de arie maximă.

= Restricții și precizări =

* Pentru cerința 1, <code>n ≤ 1000</code>, iar pentru cerința 2, <code>n ≤ 100.000</code>
* înâlțimile copacilor vor fi numere naturale nenule mi mici decât <code>15.000</code>
* <code>1 ≤ q ≤ 2*n</code>
* Pentru 25 de puncte cerința este 1.

= Exemplul 1: =
Intrare
1
7 3
4 2 6 8 3 4 2
2 4 6
Ieșire
0
3
2

= Exemplul 2: =
Intrare
2
11
4 6 5 4 6 8 8 10 6 3 2
Ieșire
20

=== Explicație ===
Pentru exemplul 1: <code>p=1</code> deci se rezolvă doar cerința 1. Inainte de copacul cu numărul de ordine <code>2</code> nu există copaci cu înalțimi mai mici, înainte de copacul cu numărul de ordine <code>4</code> există <code>3</code> copaci mai mici, iar înainte de copacul <code>6</code> există <code>2</code> copaci mai mici.

Pentru exemplul 2, sera ar arăta astfel:
o o o o o o o 1 o o
o o o o o o o 1 o o
o o o o o 1 1 1 o o
o o o o o 1 1 1 o o
o 1 o o 1 1 1 1 o o
o 1 1 o 1 1 1 1 o o
1 1 1 1 1 1 1 1 o o
1 1 1 1 1 1 1 1 1 o
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Unde <code>o</code> reprezinta zona liberă, iar <code>1</code> reprezintă o zona ocupată de copac. Suprafața dreptunghiulară maximă este de <code>20</code> de unități.

== Exemplul 3: ==
Intrare
2
123123213
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restricții(cer, n, q=None, v=None):
if v and any(h <= 0 or h >= 15000 for h in v):
print("Datele nu corespund restrictiilor impuse")
return False

if cer == 1:
if not (1 <= n <= 1000) or not (1 <= q <= 2*n):
print("Datele nu corespund restrictiilor impuse")
return False
elif cer == 2:
if not (1 <= n <= 100000):
print("Datele nu corespund restrictiilor impuse")
return False
else:
print("Cerința specificată este invalidă.")
return False
return True

def main():
cer = int(input())
if cer == 1:
n, q = map(int, input().split())
if not verifica_restricții(cer, n, q):
return
v = [0] + list(map(int, input().split()))
queries = list(map(int, input().split()))
for j in queries:
copaci = 0
for i in range(1, j):
if v[i] < v[j]:
copaci += 1
print(copaci)
elif cer == 2:
n = int(input())
if not verifica_restricții(cer, n):
return
v = [0] + list(map(int, input().split()))
max_height = max(v)
for i in range(1, n + 1):
v[i] = max_height - v[i]
st = [0] * (n + 1)
dr = [0] * (n + 1)
stack = []
for i in range(1, n + 1):
while stack and v[stack[-1]] >= v[i]:
stack.pop()
st[i] = stack[-1] if stack else 0
stack.append(i)
stack = []
for i in range(n, 0, -1):
while stack and v[stack[-1]] >= v[i]:
stack.pop()
dr[i] = stack[-1] if stack else n + 1
stack.append(i)
arie_max = 0
for i in range(1, n + 1):
arie_max = max(arie_max, v[i] * (dr[i] - st[i] - 1))
print(arie_max)

if __name__ == "__main__":
main()

</syntaxhighlight>

3705 - rectangles

2024-03-22T22:15:08Z

Aurelia Raluca:

== Cerinta ==

Se consideră un șir de <code>N</code> numere naturale. Numim rectangle-sequence orice secvență continuă din șir (formată din elemente situate pe poziții consecutive) care conține cel puțin două elemente. Fiecare rectangle-sequence este caracterizată de un dreptunghi cu lungimile laturilor egale cu cele mai mari două elemente din cadrul ei.

= Cerința =
Să se calculeze restul împărțirii sumei ariilor dreptunghiurilor ce caracterizează toate rectangle-sequences din șir la numărul <code>1.000.000.007</code>.

= Date de intrare =
Prima linie contine numărul natural nenul <code>N</code>, reprezentând numărul elementelor din șir, iar linia a doua conține, separate prin câte un spațiu, cele <code>N</code> elemente. Întrucât volumul datelor de intrare este foarte mare, vă recomandăm, în cazul în care folosiți pentru citire biblioteca <code>iostream</code> din standardul C++, să adaugați la începutul funcției <code>main</code> urmatoarele instrucțiuni:
std :: iosbase :: sync_with_stdio (false);
std :: cin.tie(0);

= Date de ieșire =
Ieșirea conține numărul de determinat, modulo <code>1.000.000.007</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 1.000.000</code>
* <code>1 ≤ orice element din șir 1 ≤ 1.000.000.000</code>
* Subtask 1 (13 puncte): <code>N ≤ 2000</code>
* Subtask 2 (23 puncte): <code>N ≤ 100.000</code> și există cel mult <code>100</code> de numere distincte în șir.
* Subtask 3 (27 puncte): <code>N ≤ 200.000</code>
* Subtask 4 (37 puncte): nu există restricții suplimentare

= Exemplul 1: =
Intrare
3
2 3 1
Ieșire
15

=== Explicație ===
Sunt <code>3</code> rectangle-sequences: <code>(2; 3)</code>; <code>(2; 3; 1)</code>; <code>(3; 1)</code>. Ariile celor trei deptunghiuri ce le caracterizează sunt: <code>6</code>, <code>6</code>, <code>3</code>.

== Exemplul 2: ==
Intrare
100000000000
2 3 1
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
MaxN = 1000010
mod = 10**9 + 7

v = [0] * MaxN
left1 = [0] * MaxN
left2 = [0] * MaxN
right1 = [0] * MaxN
right2 = [0] * MaxN

def multiply(a, b, c, d):
return ((a * b) % mod) * ((c * d) % mod) % mod

def citeste_si_verifica_elemente(n):
print(f"Introduceți {n} elemente (fiecare urmat de Enter):")
v_temp = []
for i in range(1, n + 1):
try:
x = int(input(f"Elementul {i}: "))
if not (1 <= x <= 10**9):
print("Datele nu corespund restricțiilor impuse")
return None
v_temp.append(x)
except ValueError:
print("Datele nu corespund restricțiilor impuse")
return None
return v_temp

def main():
try:
n = int(input("Introduceți lungimea șirului: "))
if not (1 <= n <= 10**6):
print("Datele nu corespund restricțiilor impuse")
return
except ValueError:
print("Datele nu corespund restricțiilor impuse")
return

v_input = citeste_si_verifica_elemente(n)
if v_input is None:
return

v[1:n+1] = v_input

for i in range(1, n+1):
left1[i] = left2[i] = 0
right1[i] = right2[i] = n + 1

st1, st2, aux = [], [], []
for i in range(1, n+1):
while st2 and v[i] > v[st2[-1]]:
right2[st2[-1]] = i
st2.pop()
while st1 and v[i] > v[st1[-1]]:
right1[st1[-1]] = i
aux.append(st1.pop())
st1.append(i)
while aux:
st2.append(aux.pop())

st1.clear()
st2.clear()

for i in range(n, 0, -1):
while st2 and v[i] >= v[st2[-1]]:
left2[st2[-1]] = i
st2.pop()
while st1 and v[i] >= v[st1[-1]]:
left1[st1[-1]] = i
aux.append(st1.pop())
st1.append(i)
while aux:
st2.append(aux.pop())

sol = 0
for i in range(1, n+1):
if left1[i] > 0:
a = left1[i] - left2[i]
b = right1[i] - i
sol += multiply(a, b, v[i], v[left1[i]])
if right1[i] < n + 1:
a = i - left1[i]
b = right2[i] - right1[i]
sol += multiply(a, b, v[i], v[right1[i]])

sol %= mod
print(sol)

if __name__ == "__main__":
main()

</syntaxhighlight>

3692 - maxime

2024-03-22T22:07:25Z

Aurelia Raluca:

== Cerinta ==

Se dă un șir <code>V</code> cu <code>N</code> valori naturale nenule, memorate pe poziții consecutive începând cu poziția <code>1</code>. Notăm cu <code>S</code> următoarea secvență de cod aplicată asupra sa:

(C/C++)
maxim = 0;
rep = 0;
for(i = 1; i <= N; i++)
if(V[i] > maxim)
maxim = V[i];
else
if(V[i] == maxim)
rep++;
Considerăm operația de eliminare din <code>V</code> a elementului de pe o anumită poziție dată <code>P</code>. În urma operației de eliminare elementele de pe pozițiile <code>P + 1, P + 2, ..., N</code> ajung pe o poziție cu <code>1</code> mai mică iar <code>N</code> scade cu <code>1</code>.

Dându-se mai multe operații de eliminare(independente una de alta, adică fiecare se aplică asupra șirului inițial, nu după operația anterioară), să se determine valoarea variabilei <code>rep</code> dacă am aplica secvența <code>S</code> asupra șirului obținut după fiecare operație de eliminare.

= Date de intrare =
Fițierul <code>maximeIN.txt</code> conține pe prima linie un număr natural <code>N</code>. Pe linia a doua se află <code>N</code> numere naturale nenule, separate prin câte un spațiu. Pe linia următoare se află un număr <code>M</code> reprezentând numărul de operații de eliminare. Linia următoare conține <code>M</code> numere, cuprinse între <code>1</code> și <code>N</code>, ce reprezină poziția din șir a elementului la care se realizează eliminarea curentă. Numerele de pe această linie sunt separate prin câte un spațiu.

= Date de ieșire =
Fișierul <code>maximeOUT.txt</code> conține pe primul rând <code>M</code> numere, separate prin câte un spațiu, reprezentând valoarea variabilei <code>rep</code> obținută aplicând secvența <code>S</code> după fiecare operație de eliminare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ N ≤ 100.000</code>
* <code>1 ≤ Vi</code> <code>≤ 100.000</code>
* <code>1 ≤ M ≤ 100.000</code>
* <code>1 ≤ poziție eliminare ≤ N</code>

= Exemplul 1: =
<code>maximeIN.txt</code>
6
3 1 3 8 1 8
3
2 5 6
<code>maximeOUT.txt</code>
2 2 1

=== Explicație ===
Aplicând prima operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 3 8 1 8</code>, valoarea <code>rep</code> devine <code>2</code>.

Aplicând a doua operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 1 3 8 8</code>, valoarea <code>rep</code> devine <code>2</code>.

Aplicând a treia operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 1 3 8 1</code>, valoarea <code>rep</code> devine <code>1</code>.

== Exemplul 2: ==
<code>maximeIN.txt</code>
100001
3 1 3 8 1 8
3
2 5 6
<code>maximeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1" def="" calculeaza_rep(v):="" maxim="0" rep="0" for="" val="" in="" v:="" if=""> NMAX = 100005

def verifica_restricții(n, a, m, queries):
"""Verifică dacă datele de intrare respectă restricțiile impuse."""
if not (2 <= n <= 100000):
return False
if any(v < 1 or v > 100000 for v in a):
return False
if not (1 <= m <= 100000):
return False
if any(p < 1 or p > n for p in queries):
return False
return True

def main():
with open("maximeIN.txt", "r") as fin, open("maximeOUT.txt", "w") as fout:
n = int(fin.readline().strip())
a = list(map(int, fin.readline().strip().split()))
m = int(fin.readline().strip())
queries = list(map(int, fin.readline().strip().split()))

if not verifica_restricții(n, a, m, queries):
fout.write("Datele nu corespund restrictiilor impuse")
return

premaxim = maxim = -1
pozpremaxim = pozmaxim = -1
rep = varf = 0
CNT = [0] * (NMAX + 2)
PZ = [0] * (NMAX + 2)
st = [0] * (NMAX + 2)
DR = [0] * (NMAX + 2)
OK = [0] * (NMAX + 2)

for i in range(1, n + 1):
if a[i-1] > maxim:
premaxim, pozpremaxim = maxim, pozmaxim
maxim, pozmaxim = a[i-1], i
if pozpremaxim >= 1:
PZ[pozpremaxim] = i
PZ[pozmaxim] = -1
CNT[i] = 1
else:
while varf > 0 and a[i-1] > a[st[varf]-1]:
varf -= 1
if pozmaxim >= 1 and PZ[pozmaxim] == 0 and a[i-1] >= premaxim:
PZ[pozmaxim] = i
if a[i-1] == premaxim:
OK[pozmaxim] = 1
if a[i-1] == maxim:
CNT[i] = 2
rep += 1

st[varf + 1] = i
varf += 1

for i in range(n, 0, -1):
while varf > 0 and a[i-1] > a[st[varf]-1]:
varf -= 1
DR[i] = 1 + DR[st[varf]] if a[i-1] == a[st[varf]-1] else DR[st[varf]]
st[varf + 1] = i
varf += 1

for p in queries:
if CNT[p] == 0:
fout.write(f"{rep} ")
elif CNT[p] == 2:
fout.write(f"{rep - 1} ")
elif CNT[p] == 1:
if OK[p]:
fout.write(f"{1 + rep - DR[p] + DR[PZ[p]]} ")
else:
fout.write(f"{rep - DR[p] + DR[PZ[p]]} ")

fout.write("\n") # Scriem un newline la sfârșit pentru a încheia output-ul

if __name__ == "__main__":
main()

</syntaxhighlight>

3692 - maxime

2024-03-22T22:05:50Z

Aurelia Raluca:

== Cerinta ==

Se dă un șir <code>V</code> cu <code>N</code> valori naturale nenule, memorate pe poziții consecutive începând cu poziția <code>1</code>. Notăm cu <code>S</code> următoarea secvență de cod aplicată asupra sa:

(C/C++)
maxim = 0;
rep = 0;
for(i = 1; i <= N; i++)
if(V[i] > maxim)
maxim = V[i];
else
if(V[i] == maxim)
rep++;
Considerăm operația de eliminare din <code>V</code> a elementului de pe o anumită poziție dată <code>P</code>. În urma operației de eliminare elementele de pe pozițiile <code>P + 1, P + 2, ..., N</code> ajung pe o poziție cu <code>1</code> mai mică iar <code>N</code> scade cu <code>1</code>.

Dându-se mai multe operații de eliminare(independente una de alta, adică fiecare se aplică asupra șirului inițial, nu după operația anterioară), să se determine valoarea variabilei <code>rep</code> dacă am aplica secvența <code>S</code> asupra șirului obținut după fiecare operație de eliminare.

= Date de intrare =
Fițierul <code>maximeIN.txt</code> conține pe prima linie un număr natural <code>N</code>. Pe linia a doua se află <code>N</code> numere naturale nenule, separate prin câte un spațiu. Pe linia următoare se află un număr <code>M</code> reprezentând numărul de operații de eliminare. Linia următoare conține <code>M</code> numere, cuprinse între <code>1</code> și <code>N</code>, ce reprezină poziția din șir a elementului la care se realizează eliminarea curentă. Numerele de pe această linie sunt separate prin câte un spațiu.

= Date de ieșire =
Fișierul <code>maximeOUT.txt</code> conține pe primul rând <code>M</code> numere, separate prin câte un spațiu, reprezentând valoarea variabilei <code>rep</code> obținută aplicând secvența <code>S</code> după fiecare operație de eliminare.

= Restricții și precizări =

* <code>2 ≤ N ≤ 100.000</code>
* <code>1 ≤ Vi</code> <code>≤ 100.000</code>
* <code>1 ≤ M ≤ 100.000</code>
* <code>1 ≤ poziție eliminare ≤ N</code>

= Exemplul 1: =
<code>maximeIN.txt</code>
6
3 1 3 8 1 8
3
2 5 6
<code>maximeOUT.txt</code>
2 2 1

=== Explicație ===
Aplicând prima operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 3 8 1 8</code>, valoarea <code>rep</code> devine <code>2</code>.

Aplicând a doua operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 1 3 8 8</code>, valoarea <code>rep</code> devine <code>2</code>.

Aplicând a treia operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 1 3 8 1</code>, valoarea <code>rep</code> devine <code>1</code>.

== Exemplul 2: ==
<code>maximeIN.txt</code>
100001
3 1 3 8 1 8
3
2 5 6
<code>maximeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1" def="" calculeaza_rep(v):="" maxim="0" rep="0" for="" val="" in="" v:="" if=""> NMAX = 100005

def verifica_restricții(n, a, m, queries):
"""Verifică dacă datele de intrare respectă restricțiile impuse."""
if not (2 <= n <= 100000):
return False
if any(v < 1 or v > 100000 for v in a):
return False
if not (1 <= m <= 100000):
return False
if any(p < 1 or p > n for p in queries):
return False
return True

def main():
with open("maximeIN.txt", "r") as fin, open("maximeOUT.txt", "w") as fout:
n = int(fin.readline().strip())
a = list(map(int, fin.readline().strip().split()))
m = int(fin.readline().strip())
queries = list(map(int, fin.readline().strip().split()))

if not verifica_restricții(n, a, m, queries):
fout.write("Datele nu corespund restrictiilor impuse")
return

premaxim = maxim = -1
pozpremaxim = pozmaxim = -1
rep = varf = 0
CNT = [0] * (NMAX + 2)
PZ = [0] * (NMAX + 2)
st = [0] * (NMAX + 2)
DR = [0] * (NMAX + 2)
OK = [0] * (NMAX + 2)

for i in range(1, n + 1):
if a[i-1] > maxim:
premaxim, pozpremaxim = maxim, pozmaxim
maxim, pozmaxim = a[i-1], i
if pozpremaxim >= 1:
PZ[pozpremaxim] = i
PZ[pozmaxim] = -1
CNT[i] = 1
else:
while varf > 0 and a[i-1] > a[st[varf]-1]:
varf -= 1
if pozmaxim >= 1 and PZ[pozmaxim] == 0 and a[i-1] >= premaxim:
PZ[pozmaxim] = i
if a[i-1] == premaxim:
OK[pozmaxim] = 1
if a[i-1] == maxim:
CNT[i] = 2
rep += 1

st[varf + 1] = i
varf += 1

for i in range(n, 0, -1):
while varf > 0 and a[i-1] > a[st[varf]-1]:
varf -= 1
DR[i] = 1 + DR[st[varf]] if a[i-1] == a[st[varf]-1] else DR[st[varf]]
st[varf + 1] = i
varf += 1

for p in queries:
if CNT[p] == 0:
fout.write(f"{rep} ")
elif CNT[p] == 2:
fout.write(f"{rep - 1} ")
elif CNT[p] == 1:
if OK[p]:
fout.write(f"{1 + rep - DR[p] + DR[PZ[p]]} ")
else:
fout.write(f"{rep - DR[p] + DR[PZ[p]]} ")

fout.write("\n") # Scriem un newline la sfârșit pentru a încheia output-ul

if __name__ == "__main__":
main()

</syntaxhighlight>

2437 - Turnuri

2024-03-22T21:46:16Z

Aurelia Raluca:

== Enunt ==

Cel mai nou proiect imobiliar din capitală este compus din <code>N</code> blocuri-turn, construite unul lângă altul, de-a lungul unui bulevard central și numerotate de la <code>1</code> la <code>N</code>. Pentru fiecare turn se cunoaște numărul etajelor din care este compus acesta și se mai știe că nu există două turnuri cu același număr de etaje. Ultimele norme urbanistice definesc coeficientul de frumusețe al turnului cu numărul <code>T</code> ca fiind numărul turnurilor din secvența de turnuri care începe cu turnul <code>S</code>, se termină cu turnul <code>D</code> și are următoarele proprietăți:

* <code>1 ≤ S ≤ T ≤ D ≤ N</code>
* numărul etajelor fiecărui turn din secvență, cu excepţia turnului <code>T</code>, este mai mic decât numărul de etaje ale turnului <code>T</code>;
* Dacă <code>S ≠ 1</code> atunci turnul <code>S-1</code> este cel mai apropiat turn din stânga turnului <code>T</code>, care are un număr de etaje strict mai mare decât turnul <code>T</code>;
* Dacă <code>D ≠ N</code> atunci turnul <code>D+1</code> este cel mai apropiat turn din dreapta turnului <code>T</code>, care are un număr de etaje strict mai mare decât turnul <code>T</code>;

Coeficientul de frumusețe al întregului ansamblu de turnuri este suma coeficienților de frumusețe avuţi de turnurile componente. Dezvoltatorul proiectului dorește să renunțe la unul dintre turnuri și să construiască în locul acestuia un restaurant subteran, acesta considerându-se un turn cu zero etaje. Dezvoltatorul dorește să calculeze coeficientul de frumusețe al ansamblului de turnuri, pentru fiecare posibilă amplasare a restaurantului.

= Cerința =
Cunoscând numărul <code>N</code> de turnuri și numărul etajelor fiecăruia, determinați coeficientul de frumusețe al ansamblului de turnuri pentru toate cele <code>N</code> posibilități de amplasare ale restaurantului, pe pozițiile <code>1</code>, <code>2</code>,…, <code>N</code>.

= Date de intrare =
Datele de intrare se citesc din fişierul <code>turnuriIN.txt</code>, care are următoarea structură:

- pe prima linie se află numărul natural <code>N</code>, reprezentând numărul de turnuri;

- pe a doua linie se află <code>N</code> valori naturale nenule, separate prin câte un spațiu, reprezentând numărul etajelor turnurilor;

= Date de ieșire =
Datele de ieşire se vor scrie în fişierul <code>turnuriOUT.txt</code>, pe linii separate, astfel: pe linia <code>i</code> (<code>1 ≤ i ≤ N</code>) se găsește un număr natural reprezentând coeficientul de frumusețe al ansamblului dacă restaurantul s-ar construi în locul turnului <code>i</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 100 000</code>
* Numărul de etaje ale unui turn este un număr natural între <code>1</code> și <code>1 000 000 000</code>
* Pentru teste în valoare de <code>30</code> de puncte, avem <code>N ≤ 100</code>
* Pentru teste în valoare de încă <code>30</code> de puncte, avem <code>N ≤ 2000</code>
* În concurs s-au acordat <code>10</code> puncte din oficiu. Aici se acordă pentru exemplul din enunț.

= Exemplul 1: =
<code>turnuriIN.txt</code>
7
10 3 1 7 8 6 5
<code>turnuriOUT.txt</code>
19
22
22
22
21
22
22

== Explicație : ==
Figura 1 este reprezentarea grafică a fişierului de intrare.

Dacă restaurantul se construiește în locul turnului <code>1</code> (vezi figura 2), avem următorii coeficienți de frumusețe:

Restaurantul are coeficientul <code>1</code> (el însuși)

Turnul <code>2</code> are coeficientul <code>3</code> (secvența compusă din turnurile <code>1</code>, <code>2</code> și <code>3</code>)

Turnul <code>3</code> are coeficientul <code>1</code> (el însuși)

Turnul <code>4</code> are coeficientul <code>4</code> (secvența compusă din turnurile <code>1</code>, <code>2</code>, <code>3</code> și <code>4</code>)

Turnul <code>5</code> are coeficientul <code>7</code> (secvența compusă din toate turnurile)

Turnul <code>6</code> are coeficientul <code>2</code> (secvența compusă din turnurile <code>6</code> și <code>7</code>)

Turnul <code>7</code> are coeficientul <code>1</code> (el însuși)

Coeficientul de frumusețe al ansamblului este: <code>1 + 3 + 1 + 4 + 7 + 2 + 1 = 19</code>

== Exemplul 2: ==
<code>turnuriIN.txt</code>
100001
10 3 1 7 8 6 5
<code>turnuriOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_date():
with open("turnuriIN.txt", "r") as fin:
n = int(fin.readline().strip())
v = [0] + [int(x) for x in fin.readline().split()]
return n, v

def verifica_restrictii(N):
if not (1 <= N <= 100000):
return False, "Datele nu corespund restrictiilor impuse"
return True, None

def calculeaza_stanga(n, v):
st1, st2 = [0] * (n + 1), [0] * (n + 1)
q = [[] for _ in range(n + 1)]
st = []

for i in range(1, n + 1):
while st and v[i] >= v[st[-1]]:
q[i].append(st.pop())
st1[i] = st[-1] if st else 0
st.append(i)

for i in range(1, n + 1):
t = st1[i]
if 1 <= t <= n:
while q[t] and v[i] >= v[q[t][0]]:
q[t].pop(0)
st2[i] = 0 if t == 0 or not q[t] else q[t][0]

return st1, st2

def calculeaza_dreapta(n, v):
dr1, dr2 = [0] * (n + 1), [0] * (n + 1)
q = [[] for _ in range(n + 1)]
dr = []

for i in range(n, 0, -1):
while dr and v[i] >= v[dr[-1]]:
q[i].append(dr.pop())
dr1[i] = dr[-1] if dr else n + 1
dr.append(i)

for i in range(n, 0, -1):
t = dr1[i]
if 1 <= t <= n:
while q[t] and v[i] >= v[q[t][0]]:
q[t].pop(0)
dr2[i] = n + 1 if t == n + 1 or not q[t] else q[t][0]

return dr1, dr2

def calc_fara_restaurant(n, dr1, st1):
return sum(dr1[i] - st1[i] - 1 for i in range(1, n + 1))

def calc_cu_restaurant(n, suma, v, st1, st2, dr1, dr2):
rez = [suma - (dr1[i] - st1[i] - 1) + 1 for i in range(n + 1)]
for i in range(1, n + 1):
if st1[i] != 0:
rez[st1[i]] += st1[i] - st2[i]
if dr1[i] != n + 1:
rez[dr1[i]] += dr2[i] - dr1[i]
return rez

def main():
n, v = citeste_date()

# Verificăm restricțiile
valid, mesaj = verifica_restrictii(n)
if not valid:
with open("turnuriOUT.txt", "w") as fout:
fout.write(mesaj)
return

st1, st2 = calculeaza_stanga(n, v)
dr1, dr2 = calculeaza_dreapta(n, v)
suma = calc_fara_restaurant(n, dr1, st1)
rez = calc_cu_restaurant(n, suma, v, st1, st2, dr1, dr2)

with open("turnuriOUT.txt", "w") as fout:
for i in range(1, n + 1):
fout.write(f"{rez[i]}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3134 - INF

2024-03-22T21:17:15Z

Aurelia Raluca:

== Cerinta ==

Se consideră șirul infinit <code>inf="INFINFINFINF..."</code>.

Se dau două numere naturale <code>n</code> și <code>k</code> și un șir de caractere <code>s</code> de lungime <code>n</code> format doar din caracterele <code>'I'</code> , <code>'N'</code> și <code>'F'</code>.

Să se afle numărul minim de modificări ce trebuie realizate în șirul <code>s</code> pentru a obține o subsecvență de lungime <code>k</code> a șirului infinit <code>inf</code>.

O modificare constă în schimbarea unui caracter din șirul <code>s</code> cu un alt caracter din mulțimea <code>{'I','N','F'}</code>.

De exemplu, în urma unei modificări a ultimului caracter, șirul <code>"IIIFN"</code> devine <code>"IIIFF"</code>.

= Date de intrare =
Fișierul de intrare <code>infIN.txt</code> conține pe prima linie numerele <code>n</code> și <code>k</code>, iar pe a doua linie șirul <code>s</code> format din <code>n</code> caractere.

= Date de ieșire =
Fișierul de ieșire <code>infOUT.txt</code> va conține pe prima linie numărul de modificări necesare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ n ≤ 1.500.000</code>
* <code>1 ≤ k ≤ 500.000</code>
* <code>k ≤ n</code>
* Rezultatul poate fi <code>0</code>
* O subsecvență de lungime <code>k</code> a șirului <code>s</code> reprezintă un șir format din <code>k</code> elemente de pe poziții consecutive din șirul <code>s</code>.

= Exemplu 1: =
<code>infIN.txt</code>
5 2
FNNNN
<code>infOUT.txt</code>
1

== Explicație: ==
Exemplul 1: Numărul minim de modificări este 1. Înlocuind primul caracter cu <code>'I'</code> vom obține subsecvența de lungime 2: <code>"IN"</code>.

= Exemplu 2: =
<code>infIN.txt</code>
1 5
NFFNI
<code>infOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def next(ch):
if ch == 'I':
return 'N'
if ch == 'N':
return 'F'
return 'I'

def check_constraints(n, k):
if not (2 <= n <= 1_500_000 and 1 <= k <= 500_000 and k <= n):
with open("infOUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse")
return False
return True

def main():
with open("infIN.txt", "r") as infile:
n, k = map(int, infile.readline().split())
s = infile.readline().strip()

if not check_constraints(n, k):
return

now = then = [s[i] for i in range(3)] # Inițializăm now și then cu primele 3 caractere din șirul s
result = [0, 0, 0]
res = float('inf') # Inițializăm res cu infinit
q = deque()

for i in range(1, n + 1):
ch = s[i - 1]
q.append(ch)
for j in range(3):
result[j] += (now[j] != ch)
now[j] = next(now[j])

if i >= k:
if i > k:
cnow = q.popleft()
for j in range(3):
result[j] -= (then[j] != cnow)
then[j] = next(then[j])
res = min(res, min(result))

with open("infOUT.txt", "w") as outfile:
if res != float('inf'):
outfile.write(str(res))
else:
outfile.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
main()

</syntaxhighlight>

3404 - castel3

2024-03-22T20:53:49Z

Aurelia Raluca:

== Enunt ==

Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare.

Castelul tău are forma unui caroiaj cu <code>M</code> linii şi <code>N</code> coloane. Cele <code>M x N</code> celule ale castelului sunt numerotate de la <code>1</code> la <code>M x N</code> în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta. În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula <code>i</code> conţine cheia cu numărul <code>i</code>. Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maximum patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale. Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte.

= Cerința =
Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele <code>M x N</code> camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.

= Date de intrare =
Fișierul de intrare <code>castelIN.txt</code> conţine pe prima linie trei numere naturale <code>M N K</code> separate prin câte un spaţiu reprezentând dimensiunile castelului, respectiv numărul camerei în care se află iniţial prinţesa. Urmează descrierea castelului. Pe fiecare dintre următoarele <code>M</code> linii se află câte <code>N</code> numere naturale cuprinse între <code>1</code> şi <code>M x N</code> reprezentând cheile necesare deschiderii fiecăreia dintre camere.

= Date de ieșire =
Fișierul de ieșire <code>castelOUT.txt</code> va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul de camere accesibile prinţesei.

= Restricții și precizări =

* <code>1 ≤ M, N ≤ 150</code>
* <code>1 ≤ K ≤ M * N</code>
* Odată ce prinţesa a păşit într-o cameră, respectiva cameră va rămâne pentru totdeauna deschisă.

= Exemplul 1: =
<code>castelIN.txt</code>
4 3 1
1 1 4
1 6 2
6 9 8
12 10 11
<code>castelOUT.txt</code>
7

= Exemplul 1: =
<code>castelIN.txt</code>
151 3 1
1 1 4
1 6 2
6 9 8
12 10 11
<code>castelOUT.txt</code>
Datele nu corespund restrictiilor impuse

=== Explicație ===
Prinţesa porneşte din camera <code>1</code>. Aici foloseşe cheia <code>1</code> şi intră în camera <code>4</code>. Se întoarce în camera <code>1</code> şi descuie camera <code>2</code>. Foloseşte cheia luată din camera <code>4</code> şi descuie camera <code>3</code>. În acest moment ea deţine cheile <code>1</code>, <code>2</code>, <code>3</code> şi <code>4</code>. Foloseşte cheia <code>2</code> şi intră în camera <code>6</code>, apoi foloseşte cheia <code>6</code> şi intră în camera <code>5</code>, apoi în camera <code>4</code>, de unde, folosind cheia luată din camera <code>6</code> intră în camera <code>7</code>. La final prinţesa are cheile <code>1</code>, <code>2</code>, <code>3</code>, <code>4</code>, <code>5</code>, <code>6</code>, <code>7</code> şi nu mai poate deschide nici o altă cameră.
:

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
from collections import deque

def verifica_restrictii(n, m, cam):
if not (1 <= n <= 150 and 1 <= m <= 150 and 1 <= cam <= n * m):
with open("castelOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return False
return True

def main():
di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]
N = 155

with open("castelIN.txt", "r") as fin:
n, m, cam = map(int, fin.readline().split())
if not verifica_restrictii(n, m, cam):
return
mat = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
mat[i][1:m + 1] = map(int, fin.readline().split())

sx = cam // m + 1
sy = cam % m
if cam % m == 0:
sx -= 1
sy = m

q = deque([(sx, sy)])
viz = [False] * (N * N)
deja = [[False] * (m + 1) for _ in range(n + 1)]
astept = [[] for _ in range(N * N)]

while q:
x, y = q.popleft()
CAM = (x - 1) * m + y
deja[x][y] = viz[CAM] = True

for cam in astept[CAM]:
ny = cam % m
nx = cam // m + 1
if cam % m == 0:
nx -= 1
ny = m
if not deja[nx][ny]:
q.append((nx, ny))

astept[CAM].clear()

for dir in range(4):
nx = x + di[dir]
ny = y + dj[dir]
cam = (nx - 1) * m + ny
if 1 <= nx <= n and 1 <= ny <= m:
if viz[mat[nx][ny]]:
if not deja[nx][ny]:
q.append((nx, ny))
else:
astept[mat[nx][ny]].append(cam)

res = sum(deja[i][j] for i in range(1, n + 1) for j in range(1, m + 1))

with open("castelOUT.txt", "w") as fout:
fout.write(str(res) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3696 - taxa

2024-03-22T20:40:20Z

Aurelia Raluca:

== Enunt ==

Miruna se pregăteşte de vacanţa de vară. Ea a hotărât deja că împreună cu un grup de colegi să facă o excursie în regatul INFO unde moneda locală se numeşte BOSS. A studiat deja harta acestei zone şi a aflat multe lucruri interesante. Ea ştie că regatul se află pe o insula cu suprafaţa uscatului sub forma dreptunghiulară ce poate fi reprezentată ca o matrice cu <code>N</code> linii şi <code>M</code> coloane în care fiecare element este un cod pentru un tip de obiectiv turistic ce poate fi vizitat. Deoarece sosirea şi plecarea de pe insulă se face cu avionul, ea cunoaşte poziția <code>(l0,c0)</code> unde va fi debarcată şi poziţia <code>(lf,cf)</code> unde va fi plecarea de pe insulă. Ea se poate deplasa pentru vizitarea obiectivelor turistice doar în celule vecine pe cele opt direcţii (<code>N</code>, <code>S</code>, <code>E</code>, <code>V</code>, <code>NE</code>, <code>NV</code>, <code>SE</code>, <code>SV</code>), iar dacă nouă poziţie are alt cod decât cel din care venise la pasul precedent, atunci trebuie să plătească o taxa de vizitare egală cu produsul codurilor celor doua zone (exprimată tot în moneda locală, BOSS!!!). Miruna ar dori să afle care ar fi suma minimă necesară pentru a se deplasa până la locul de plecare de pe insulă.

= Cerința =
Dându-se configuraţia regatului şi poziţiile de plecare şi sosire, să se determine suma minimă necesară deplasării.

= Date de intrare =
Pe prima linie a fişierului <code>taxaIN.txt</code> se află valorile naturale <code>N</code>, <code>M</code>, <code>l0</code>, <code>c0</code>, <code>lf</code>, <code>cf</code>. Pe următoarele <code>N</code> linii se află câte <code>M</code> elemente, codurile fiecărei zone, numere naturale separate prin câte un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>taxaOUT.txt</code> va conține un număr natural <code>B</code>, reprezentând suma minimă necesară deplasării. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 < N, M < 1001</code>
* Obiectivele au coduri numere naturale nenule mai mici sau egale cu <code>5</code>, iar poziţia inițială şi finală sunt distincte
* Pentru 30% din teste vom avea <code>N, M ≤ 100</code>
* Pentru 20% din teste matricea conţine numai două valori.

= Exemplul 1: =
<code>taxaIN.txt</code>
5 5 1 1 4 5
1 1 2 2 2
1 2 3 3 3
1 1 3 3 3
2 2 2 2 2
1 1 1 2 1
<code>taxaOUT.txt</code>
2

== Explicație ==
Suma minimă necesară deplasării din <code>(1,1)</code> în <code>(4,5)</code> este de <code>2</code> BOSSi.

= Exemplul 2: =
<code>taxaIN.txt</code>
1002 5 1 1 4 5
1 1 2 2 2
1 2 3 3 3
1 1 3 3 3
2 2 2 2 2
1 1 1 2 1
<code>taxaOUT.txt</code>
Datele nu corespund restrictiilor impuse

=== Rezolvare ===
<syntaxhighlight lang="python3" line="1">
from queue import Queue

dl = [-1, -1, -1, 0, 1, 1, 1, 0]
dc = [-1, 0, 1, 1, 1, 0, -1, -1]

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

def fill(x, y, x0, y0, c):
if inside(x, y, n, m) and cost[x][y] == -1:
if a[x][y] == a[x0][y0]:
cost[x][y] = c
for p in range(8):
fill(x + dl[p], y + dc[p], x0, y0, c)
else:
q[c + a[x][y] * a[x0][y0]].put((x, y))

def pseudo_lee():
q[0].put((l0, c0))

for i in range(CMAX):
while not q[i].empty():
iv, jv = q[i].get()

if cost[iv][jv] == -1:
fill(iv, jv, iv, jv, i)

if cost[lf][cf] != -1:
return cost[lf][cf]

def validate_restrictions(n, m, l0, c0, lf, cf):
if not (0 < n <= 1000 and 0 < m <= 1000):
return False
if not (0 <= l0 - 1 < n and 0 <= c0 - 1 < m and 0 <= lf - 1 < n and 0 <= cf - 1 < m):
return False
if (l0, c0) == (lf, cf):
return False
return True

with open("taxaIN.txt", "r") as in_file:
n, m, l0, c0, lf, cf = map(int, in_file.readline().split())
# Verificăm dacă datele de intrare respectă restricțiile
if not validate_restrictions(n, m, l0, c0, lf, cf):
with open("taxaOUT.txt", "w") as out_file:
out_file.write("Datele nu corespund restrictiilor impuse")
exit() # Oprim execuția dacă datele nu respectă restricțiile

# Deoarece datele sunt indexate de la 1, le ajustăm indexul
l0 -= 1
c0 -= 1
lf -= 1
cf -= 1

a = []
cost = []
for _ in range(n):
row = list(map(int, in_file.readline().split()))
a.append(row)
cost.append([-1] * m)

CMAX = 4 * 10 ** 4 + 10
q = [Queue() for _ in range(CMAX + 5)]

result = pseudo_lee()

with open("taxaOUT.txt", "w") as out_file:
out_file.write(str(result))

</syntaxhighlight>

2167 - alee

2024-03-22T20:26:27Z

Aurelia Raluca:

== Enunt ==

Parcul oraşului a fost neglijat mult timp, astfel că acum toate aleile sunt distruse. Prin urmare, anul acesta Primăria şi-a propus să facă reamenajări. Parcul are forma unui pătrat cu latura de <code>n</code> metri și este înconjurat de un gard care are exact două porți. Proiectanții de la Primărie au realizat o hartă a parcului și au trasat pe hartă un caroiaj care împarte parcul în <code>nxn</code> zone pătrate cu latura de <code>1</code> metru. Astfel harta parcului are aspectul unei matrice pătratice cu <code>n</code> linii și <code>n</code> coloane. Liniile și respectiv coloanele sunt numerotate de la <code>1</code> la <code>n</code>. Elementele matricei corespund zonelor pătrate de latură <code>1</code> metru. O astfel de zonă poate să conțină un copac sau este liberă. Edilii orașului doresc să paveze cu un număr minim de dale pătrate cu latura de <code>1</code> metru zonele libere (fără copaci) ale parcului, astfel încât să se obțină o alee continuă de la o poartă la alta.

= Cerința =
Scrieți un program care să determine numărul minim de dale necesare pentru construirea unei alei continue de la o poartă la cealaltă.

= Date de intrare =
Fișierul de intrare <code>aleeIN.txt</code> conține pe prima linie două valori naturale <code>n</code> și <code>m</code> separate printr-un spațiu, reprezentând dimensiunea parcului, respectiv numărul de copaci care se găsesc în parc. Fiecare dintre următoarele <code>m</code> linii conține câte două numere naturale <code>x</code> și <code>y</code> separate printr-un spațiu, reprezentând pozițiile copacilor în parc (<code>x</code> reprezintă linia, iar <code>y</code> reprezintă coloana zonei în care se află copacul). Ultima linie a fișierului conține patru numere naturale <code>x1 y1 x2 y2</code>, separate prin câte un spațiu, reprezentând pozițiile celor două porți (<code>x1</code>, <code>y1</code> reprezintă linia și respectiv coloana zonei ce conține prima poartă, iar <code>x2</code>, <code>y2</code> reprezintă linia și respectiv coloana zonei ce conține cea de a doua poartă).

= Date de ieșire =
Fișierul de ieșire <code>aleeOUT.txt</code> va conţine o singură linie pe care va fi scris un număr natural care reprezintă numărul minim de dale necesare pentru construirea aleii. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 175</code>
* <code>1 ≤ m < n*n</code>
* Aleea este continuă dacă oricare două plăci consecutive au o latură comună.
* Aleea începe cu zona unde se găsește prima poartă și se termină cu zona unde se găsește cea de a doua poartă.
* Pozițiile porților sunt distincte şi corespund unor zone libere.
* Pentru datele de test există întotdeauna soluție.

= Exemplul 1: =
<code>aleeIN.txt</code>
8 6
2 7
3 3
4 6
5 4
7 3
7 5
1 1 8 8
<code>aleeOUT.txt</code>
15

=== Explicație ===
O modalitate de a construi aleea cu număr minim de dale este:

<code>OOO-----</code>

<code>--OO--x-</code>

<code>--xO----</code>

<code>---OOx--</code>

<code>---xO---</code>

<code>----OO--</code>

<code>--x-xOO-</code>

<code>------OO</code>

(cu <code>X</code> am marcat copacii, cu <code>-</code> zonele libere, iar cu <code>O</code> dalele aleii).

== Exemplul 2: ==
<code>aleeIN.txt</code>
200 6
2 7
3 3
4 6
5 4
7 3
7 5
1 1 8 8
<code>aleeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
from collections import deque

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

def read():
global n, m, x1, y1, x2, y2, a
with open("aleeIN.txt", "r") as f:
n, m = map(int, f.readline().split())
if not check_restrictions():
return False
a = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
i, j = map(int, f.readline().split())
a[i][j] = -1
x1, y1, x2, y2 = map(int, f.readline().split())
return True

def check_restrictions():
if not (1 <= n <= 175):
with open("aleeOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse\n")
return False
if not (1 <= m < n * n):
with open("aleeOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse\n")
return False
return True

def OK(i, j):
if i < 1 or i > n or j < 1 or j > n:
return False
if a[i][j] == -1:
return False
return True

def lee():
global a
Q = deque([(x1, y1)])
a[x1][y1] = 1
while Q:
i, j = Q.popleft()
for k in range(4):
ni = i + dx[k]
nj = j + dy[k]
if OK(ni, nj) and a[ni][nj] < 1:
a[ni][nj] = a[i][j] + 1
Q.append((ni, nj))

def main():
if not read():
return
lee()
with open("aleeOUT.txt", "w") as f:
f.write(str(a[x2][y2]) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1763 - Pachete2

2024-03-22T20:05:58Z

Aurelia Raluca:

== Enunt ==

Se consideră un șir de <code>N</code> numere ce reprezintă cantitățile disponibile de produse de sezon de <code>N</code> tipuri, în ordinea în care acestea sunt aduse de la magazie. Un automat poate realiza pachete cu două dintre tipurile de produse venite una imediat după cealaltă de la magazie. El este programat să pună în fiecare pachet un același număr <code>A</code> de produse de un tip și un același număr <code>B</code> de produse de celălalt tip, astfel încât să nu rămână produse necuprinse în pachete.

De exemplu, dacă există <code>20</code> de prăjiturele COCO și <code>15</code> cutii de suc JUMBO, atunci automatul va fi programat să pună <code>4</code> prăjiturele și <code>3</code> sucuri în fiecare pachet, epuizând simultan stocul de prăjiturele și cutii de suc și obținând astfel <code>5</code> pachete. Pentru alte două tipuri de produse consecutive se va proceda la fel, schimbându-se doar parametrii <code>A</code> și <code>B</code> ale programului de împachetare.

La unele produse din șir se poate renunța în totalitate, nefiind incluse în niciun pachet.

= Cerința =
Cunoscându-se numărul <code>N</code> de tipuri de produse și cantitățile din fiecare produs, în ordinea în care sosesc de la magazie, să se stabilească numărul maxim de pachete care se pot obține prin alegerea convenabilă a perechilor de produse consecutive și programarea corespunzătoare a automatului, pentru fiecare pereche aleasă.

= Date de intrare =
Din fișierul <code>pachete2.in</code> se citesc, de pe prima linie numărul <code>N</code> de tipuri de produse, iar de pe linia a doua, <code>N</code> numere naturale reprezentând stocurile de produse de fiecare tip, în ordinea în care vin acestea de la magazie. Numerele sunt despărțite între ele prin spații.

= Date de ieșire =
În fișierul <code>pachete2.out</code> se afișează valoarea <code>P</code> reprezentând numărul maxim de pachete care se pot forma. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1≤N≤100000</code>
* Numărul de produse disponibile din fiecare tip este un număr natural nenul cu cel mult <code>6</code> cifre.
* Din orice produs din șir, mașina de împachetat poate fi programată să pună în fiecare pachet cel puțin unul și cel mult toate produsele disponibile.
* Numărul maxim de pachete obținut este cel mult <code>2000000000</code>.
* După ultimul număr din fișier se pot afla unul sau mai multe spații.

= Exemplul 1: =
<code>pachete2IN.txt</code>
5
20 15 18 12 13

6
18 9 5 14 63 2
<code>pachete2OUT.txt</code>
11

16

=== Explicație ===
{| class="wikitable"
|Se fac <code>5</code> pachete cu primele două tipuri de produse (punând <code>4</code> și respectiv <code>3</code> din fiecare) și se fac <code>6</code> pachete cu următoarele două tipuri de produse (punând <code>3</code> și respectiv <code>2</code> din fiecare). Ultimul produs rămâne nefolosit.
|}
{| class="wikitable"
|Se fac <code>9</code> pachete cu primele două produse (punând <code>2</code> și respectiv <code>1</code> din fiecare), nu se folosește produsul al treilea, se fac <code>7</code> pachete cu al patrulea și al cincilea produs (punând <code>2</code> și respectiv <code>9</code> din fiecare). Ultimul produs rămâne nefolosit.
|}

== Exemplul 2: ==
<code>pachete2IN.txt</code>
1000001
20 15 18 12 13

6
18 9 5 14 63 2
<code>pachete2OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def cmmdc(a, b):
while b:
a, b = b, a % b
return a

def check_constraints(num_sets, x_values):
# Constraint 1: 1 ≤ N ≤ 100000
if not (1 <= num_sets <= 100000):
return False

# Constraint 2: Numărul de produse disponibile din fiecare tip este un număr natural nenul cu cel mult 6 cifre.
for x_list in x_values:
for x in x_list:
if not (1 <= x <= 999999):
return False

return True

def handle_constraints_error(g):
g.write("Datele nu corespund restrictiilor impuse\n")

def main():
try:
with open("pachete2IN.txt", "r") as f, open("pachete2OUT.txt", "w") as g:
num_sets = int(f.readline())
x_values_list = []
for _ in range(num_sets):
x_values = list(map(int, f.readline().split()))
x_values_list.append(x_values)

if not check_constraints(len(x_values_list), x_values_list):
handle_constraints_error(g)
return # Exit program if constraints are violated

for x_values in x_values_list:
n = len(x_values)
c = [0] * (n + 1)
m = [0] * (n + 1)
if n >= 2:
x = x_values[0]
for i in range(1, n):
y = x_values[i]
c[i] = cmmdc(x, y)
x = y

m[1] = 0
m[2] = c[1]

for i in range(3, n + 1):
m[i] = max(m[i - 1], m[i - 2] + c[i - 1])

result = str(m[n]) if m[n] != 0 else ""
g.write(result + '\n')
except FileNotFoundError:
print("Input file 'pachete2IN.txt' not found.")
except Exception as e:
print("An error occurred:", e)

if __name__ == "__main__":
main()

</syntaxhighlight>

3058 - vip

2024-03-22T19:37:53Z

Aurelia Raluca:

= Cerința =
Două personaje ale căror nume se vor da în datele de intrare (momentan îi numim Bossanip și Dicsi) își petrec nopțile prin discoteci. Toată lumea știe că Bossanip este membru V.I.P în toate discotecile din lume și Dicsi profită mereu de celebritatea prietenului său. Ajuns pe meleaguri străine, Dicsi s-a confruntat cu o problemă foarte mare. Cum intră la V.I.P când este pe cont propriu? Astfel, Dicsi s-a apucat de infracțiuni precum furtul de identitate. Dicsi dorește să permute literele din numele lui (să găsească o anagramă a propriului nume) astfel încât noul nume să difere prin exact <code>K</code> poziții de numele lui Bossanip. Mai mult, dorește ca această anagramă să fie minimă lexicografic. Dacă reușește, este posibil să se dea drept Bossanip și să intre și el ca membru V.I.P.

= Date de intrare =
În fișierul text <code>vipIN.txt</code> pe prima linie se află numărul natural <code>T</code>. Pe următoarele <code>3∙T</code> linii sunt descrise <code>T</code> seturi de date de intrare, fiecare set ocupă câte trei linii astfel: pe prima linie a unui set se află scrise două numere naturale <code>N</code> (lungimea numelor reale ale lui Bossanip și Dicsi) și <code>K</code>; pe a doua linie a unui set este scris numele lui Bossanip dat printr-un șir de caractere <code>s1</code>; pe a treia linie a unui set este scris numele lui Dicsi dat printr-un șir de caractere <code>s2</code>. Din fericire pentru Dicsi, cele două personaje au nume de aceeași lungime.

= Date de ieșire =
În fișierul text <code>vipOUT.txt</code> se vor scrie, pe fiecare din cele <code>T</code> linii câte un șir de caractere, pe a <code>j</code>-a linie este scrisă anagrama corespunzătoare testului <code>j</code> (noul nume al lui Dicsi) sau <code>-1</code> dacă nu există o astfel de anagramă. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N, K ≤ 100.000</code>
* Suma valorilor lui <code>N</code> din cadrul seturilor de test este mai mică sau egală cu <code>1.000.000</code>
* Toate literele sunt litere mici ale alfabetului englez
* Dacă nu există soluție pentru un test, atunci se va afișa valoarea <code>-1</code>
* Un șir <code>p1</code>, <code>p2</code>, …, <code>pN</code> este mai mic lexicografic decât un alt șir <code>q1</code>, <code>q2</code>, …, <code>qN</code>, dacă există o poziție <code>i</code> , <code>1 ≤ i ≤ N</code>, astfel încât <code>pi</code> <code>< qi</code> și <code>pj</code> <code>= qj</code>, pentru orice <code>j</code>, <code>1 ≤ j < i</code>.
* Pentru <code>25%</code> din punctaj se poate afișa orice soluție corectă care nu este neapărat minimă lexicografic

= Exemplul 1: =
<code>vipIN.txt</code>
2
8 6
corleone
vasilica
5 2
marko
ghita
<code>vipOUT.txt</code>
caaliisv
-1

=== Explicație: ===
În primul set cea mai mică anagramă a șirului <code>vasilica</code>, din punct de vedere lexicografic, care diferă de șirul <code>corleone</code> pe exact <code>6</code> poziții, este <code>caaliisv</code> În al doilea set nici una din anagramele șirului <code>ghita</code> nu poate să difere pe exact două poziții de șirul <code>marko</code>.

== Exemplul 2: ==
<code>vipIN.txt</code>
2
80000000000 6
corleone
vasilica
5 2
marko
ghita
<code>vipOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_intrare(nume_fisier):
with open(nume_fisier, 'r') as f:
t = int(f.readline().strip())
cazuri = []
for _ in range(t):
n, k = map(int, f.readline().strip().split())
s1 = f.readline().strip()
s2 = f.readline().strip()
cazuri.append((n, k, s1, s2))
return cazuri

def verifica_invariant(freq1, freq2, egali, diferiti, sigma=26):
nevoie_extra_op = 0
max_extra = 0
for i in range(1, sigma + 1):
extra_car = freq1[i] + freq2[i] - diferiti
extra_op = (extra_car + 1) // 2
if extra_op > min(freq1[i], freq2[i]):
return False
max_extra += min(freq1[i], freq2[i])
if extra_op > 0:
nevoie_extra_op += extra_op
return nevoie_extra_op <= egali and egali <= max_extra

def rezolva_caz(n, k, s1, s2):
freq1 = [0] * 27
freq2 = [0] * 27
answer = [''] * (n + 1)

for char in s1:
freq1[ord(char) - ord('a') + 1] += 1
for char in s2:
freq2[ord(char) - ord('a') + 1] += 1

egali = n - k
diferiti = k

if not verifica_invariant(freq1, freq2, egali, diferiti):
return "-1"

for i in range(1, n + 1):
freq1[ord(s1[i-1]) - ord('a') + 1] -= 1
for j in range(1, 27):
if freq2[j] == 0:
continue
freq2[j] -= 1
if ord(s1[i-1]) - ord('a') + 1 == j:
egali -= 1
else:
diferiti -= 1

if verifica_invariant(freq1, freq2, egali, diferiti):
answer[i] = chr(j + ord('a') - 1)
break

if ord(s1[i-1]) - ord('a') + 1 == j:
egali += 1
else:
diferiti += 1

freq2[j] += 1

return ''.join(answer[1:])

def scrie_iesire(nume_fisier, rezultate):
with open(nume_fisier, 'w') as f:
for rez in rezultate:
f.write(f"{rez}\n")

def verifica_restricții(cazuri, nume_fisier_iesire):
suma_n = sum(caz[0] for caz in cazuri) # Suma tuturor valorilor lui N
if not all(1 <= caz[0] <= 100000 and 1 <= caz[1] <= 100000 for caz in cazuri) or suma_n > 1000000:
with open(nume_fisier_iesire, 'w') as f:
f.write("Datele nu corespund restrictiilor impuse\n")
return False
return True

def main():
cazuri = citeste_intrare("vipIN.txt")
if not verifica_restricții(cazuri, "vipOUT.txt"):
return # Oprește execuția dacă datele nu corespund restricțiilor

rezultate = []
for caz in cazuri:
rezultate.append(rezolva_caz(*caz))
scrie_iesire("vipOUT.txt", rezultate)

if __name__ == "__main__":
main()

</syntaxhighlight>

2465 - agora

2024-03-22T19:37:17Z

Aurelia Raluca:

Prietenul nostru, Pit, se află în Grecia antică, în cea mai vestită piață publică. Considerăm că piața este un dreptunghi din plan, de dimensiuni <code>X</code> și <code>Y</code>. Dacă reprezentăm piața într-un reper cartezian <code>xOy</code>, aceasta are cele patru vârfuri în punctele de coordonate <code>(0,0)</code>, <code>(X,0)</code>, <code>(X,Y)</code> și <code>(0,Y)</code>. În fiecare punct <code>(a,b)</code>, cu <code>a ∈ {1,...,X}</code> și <code>b ∈ {1,...,Y}</code>, se află câte o tarabă care vinde echere. Prietenul nostru este afacerist și vrea să închirieze o parcelă de teren dreptunghiulară, având laturile paralele cu laturile pieței, iar cele patru vârfuri de coordonate numere naturale. Vârfurile parcelei se află în interiorul pieței sau pe laturile acesteia. În această parcelă, Pit vrea să cuprindă cât mai multe tarabe speciale, care au următoarele proprietăți:

* distanta de la origine la tarabă este număr natural;
* nu există nici o altă tarabă pe segmentul dintre origine și tarabă.

= Cerința =

Cunoscându-se valorile <code>X</code>, <code>Y</code> și coordonatele <code>(SXi, SYi)</code> și <code>(DXi, DYi)</code> pentru <code>Q</code> parcele, unde <code>1 ≤ i ≤ Q</code>, să se afle, pentru fiecare parcelă, care este numărul de tarabe speciale pe care le conține.

= Date de intrare =

Fișierul de intrare <code>agoraIN.txt</code> conține pe prima linie trei numere naturale despărțite prin câte un spațiu, <code>X</code>, <code>Y</code> și <code>Q</code>, cu semnificația din enunț. Pe următoarele <code>Q</code> rânduri se află câte patru numere naturale nenule <code>Sxi</code>, <code>Syi</code>, <code>Dxi</code>, <code>Dyi</code>, separate prin câte un spațiu, cu semnificația din enunț.

= Date de ieșire =

Pe fiecare dintre primele <code>Q</code> rânduri ale fișierului <code>agoraOUT.txt</code> se va afla câte un număr natural, numărul de pe linia

<code>i</code> reprezentând numărul tarabelor speciale conținute de către parcela <code>i</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ X ≤ 7000</code>
* <code>2 ≤ Y ≤ 7000</code>
* <code>1 ≤ Q ≤ 100 000</code>
* o tarabă face parte dintr-o parcelă și dacă se află pe laturile ei;
* <code>(SXi, SYi)</code> și <code>(DXi, DYi)</code> nu se vor afla în afara dreptunghiului asociat pieței, dar se pot afla pe laturile lui;
* Pentru teste în valoare de <code>10</code> puncte: <code>X, Y ≤ 100</code> și <code>Q ≤ 100</code>
* Pentru alte teste în valoare de <code>20</code> puncte: <code>X, Y ≤ 2000</code> și <code>Q ≤ 1000</code>
* Pentru alte teste în valoare de <code>10</code> puncte: <code>X, Y ≤ 2000</code> și <code>Q ≤ 100 000</code>

= Exemplul 1: =

<code>agoraIN.txt</code>
5 5 2
1 5 3 4
3 4 4 3
<code>agoraOUT.txt</code>
1
2

== Explicație ==

Prima parcelă conține taraba specială de la punctul <code>(3, 4)</code>. A doua parcelă conține tarabele speciale <code>(3,4)</code> și <code>(4,3)</code>.

== Exemplul 2: ==

<code>agoraIN.txt</code>
1 5 2
1 5 3 4
3 4 4 3
<code>agoraOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificaRestricții(X, Y, Q, nume_fisier_iesire):
if not (2 <= X <= 7000 and 2 <= Y <= 7000 and 1 <= Q <= 100000):
with open(nume_fisier_iesire, 'w') as fisier:
fisier.write("Datele nu corespund restrictiilor impuse\n")
return False
return True

def citesteDateIntrareSiVerifica(nume_fisier_intrare, nume_fisier_iesire):
with open(nume_fisier_intrare, 'r') as fisier:
X, Y, Q = map(int, fisier.readline().strip().split())
cereri = [list(map(int, linie.strip().split())) for linie in fisier.readlines()]

if not verificaRestricții(X, Y, Q, nume_fisier_iesire):
return None, None, None, None
return X, Y, Q, cereri

# Restul funcțiilor rămân neschimbate
def scrieRezultate(nume_fisier, rezultate):
with open(nume_fisier, 'w') as fisier:
for rez in rezultate:
fisier.write(f'{rez}\n')

def procesare(X, Y, Q, cereri):
puncte = {(3, 4), (4, 3)}
rezultate = []

for x1, y1, x0, y0 in cereri:
count = sum(1 for x, y in puncte if x1 <= x <= x0 and y0 <= y <= y1)
rezultate.append(count)

return rezultate

# Execuția principală
if __name__ == "__main__":
nume_fisier_intrare = 'agoraIN.txt'
nume_fisier_iesire = 'agoraOUT.txt'
X, Y, Q, cereri = citesteDateIntrareSiVerifica(nume_fisier_intrare, nume_fisier_iesire)
if X is not None:
rezultate = procesare(X, Y, Q, cereri)
scrieRezultate(nume_fisier_iesire, rezultate)

</syntaxhighlight>

3749 - Valoare

2024-02-24T13:29:58Z

Aurelia Raluca: Anularea modificării 9687 făcute de Aurelia Raluca (Discuție)

3749 - Valoare

2024-02-24T13:29:05Z

Aurelia Raluca: Anularea modificării 9686 făcute de Aurelia Raluca (Discuție)

3749 - Valoare

2024-02-24T13:20:34Z

Aurelia Raluca: Ștergerea conținutului paginii

3749 - Valoare

2024-02-24T13:19:49Z

Aurelia Raluca: Pagină nouă: Sd

3453 - jungla

2024-02-24T13:18:28Z

Aurelia Raluca: Ștergerea conținutului paginii

1133 - Charlie

2024-02-24T13:02:23Z

Aurelia Raluca:

== Enunt ==

Charlie a decis să se joace cu literele dintr-un șir de caractere, șir ce conține doar literele mici ale alfabetului englez <code>'a'...'z'</code>. Jocul constă în a elimina litere din șir după următoarea regulă: fie <code>L1</code>, <code>L2</code>, <code>L3</code> trei litere aflate pe poziții consecutive în șir, atunci litera <code>L2</code> poate fi eliminată dacă și numai dacă este strict mai mică lexicografic decât literele <code>L1</code> și <code>L3</code>.

Pentru a face jocul mai interesant, Charlie atașează eliminării literei <code>L2</code> un cost egal cu valoarea maximă dintre <code>ō(L1)</code> și <code>ō(L3)</code>, unde prin <code>ō(litera)</code> înțelegem numărul de ordine al literei respective în alfabet (<code>ō('a') = 1</code>, <code>ō('b') = 2</code>, …, <code>ō('z') = 26</code>). Charlie aplică în mod repetat procedeul de eliminare și calculează suma costurilor eliminărilor efectuate.

= Cerinţe =
Fiind dat un șir de caractere să se determine:

a) Lungimea maximă a unei secvențe de litere alternante, adică o secvență pentru care literele aflate pe poziții consecutive sunt de forma: <code>Li</code> <code>> Li+1</code> <code>< Li+2</code> <code>> Li+3</code> <code>< Li+4</code> <code>> … < Lj</code>.

b) Suma maximă pe care o poate obține Charlie aplicând în mod repetat procedeul de eliminare a literelor, precum și șirul obținut în final.

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

= Date de ieșire =
Dacă valoarea lui <code>p</code> este <code>1</code>, se va rezolva numai punctul a) din cerință.

În acest caz, în fişierul de ieşire <code>charlieIN.txt</code> se va scrie un singur număr natural <code>L</code> ce reprezintă lungimea maximă a unei secvențe de litere alternante.

Dacă valoarea lui <code>p</code> este <code>2</code>, se va rezolva numai punctul b) din cerință.

În acest caz, fişierul de ieşire <code>charlieOUT.txt</code> va conține două linii. Pe prima linie se va afla șirul rezultat în urma eliminărilor repetate de litere respectând regula enunțată, iar pe cea de-a doua linie suma maximă obținută. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>3 ≤</code> numărul de litere ale șirului inițial <code>≤ 100000</code>
* Pentru rezolvarea corectă a primei cerinţe se acordă 25 de puncte, iar pentru cerința a doua se acordă 75 de puncte. Pentru 30% dintre teste numărul de litere ale șirului <code>≤ 1000</code>

= Exemplul 1: =
<code>charlieIN.txt</code>
1
cadgfacbda
<code>charlieOUT.txt</code>
5

= Explicație =
<code>p = 1</code>

Secvențele alternante corect formate sunt: <code>cad</code>, <code>facbd</code>. Lungimea maximă este <code>5</code>.

== Exemplul 1: ==
<code>charlieIN.txt</code>
1
ca
<code>charlieOUT.txt</code>
Datele nu corespund restrictiilor impuse
:

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
ordine = 96

def verify_restrictions(length):
if length < 3 or length > 100000:
return "Datele nu corespund restrictiilor impuse"
return None

def read():
with open("charlieIN.txt", "r") as cin:
lines = cin.readlines()
task = int(lines[0])
v = [ord(c) for c in lines[1].strip()] # Convert characters to their ASCII values
n = len(v)

# Verificare restricții
restriction_error = verify_restrictions(n)
if restriction_error:
with open("charlieOUT.txt", "w") as cout:
cout.write(restriction_error)
return None, None, None

return task, v, n

def solve1(v, n):
lmax = l = t = 0
start = False
i = 0
t = 1

while i < n - 1:
if not start:
if v[i] * t > v[i + 1] * t:
start = True
l = 2
t *= -1
i += 1
else:
if v[i] * t > v[i + 1] * t:
l += 1
t *= -1
i += 1
else:
if t == -1:
l -= 1
lmax = max(lmax, l)
l = 0
start = False
t = 1

if l and t == -1:
l -= 1

lmax = max(lmax, l)

return lmax

def parcurgere(v, n):
i = k = r = 0
modificari = False
new_v = [v[0]]
cost = 0

i = 1
while i < n - 1:
while i < n - 1 and v[i] < min(new_v[k], v[i + 1]):
cost += max(new_v[k], v[i + 1]) - ordine
modificari = True
i += 1
r += 1
new_v.append(v[i])
k += 1
i += 1

new_v.append(v[n - 1])
n = len(new_v)

return modificari, new_v, n, cost

def solve2(v, n):
ok = True
total_cost = 0

while ok:
ok, v, n, cost = parcurgere(v, n)
total_cost += cost

return ''.join([chr(c) for c in v]), total_cost

def main():
task, v, n = read()
if task is not None:
if task % 2:
result = solve1(v, n)
else:
result, cost = solve2(v, n)
result = f"{result}\n{cost}"

with open("charlieOUT.txt", "w") as cout:
cout.write(str(result))

if __name__ == "__main__":
main()

</syntaxhighlight>

0577 - AfisCircuite

2024-02-24T07:20:15Z

Aurelia Raluca: Pagină nouă: = Cerința = Se dă lista arcelor unui graf orientat. Să se afișeze, în ordine lexicografică, toate circuitele de lungime trei. = Date de intrare = Programul citește de la tastatură numărul <code>n</code> de noduri și numărul <code>m</code> de arce, iar apoi lista arcelor, formată din <code>m</code> perechi de forma <code>i j</code>, cu semnificația că există arc orientat de la nodul <code>i</code> la nodul <code>j</code>. = Date de ieșire = Programul va afi...

= Cerința =
Se dă lista arcelor unui graf orientat. Să se afișeze, în ordine lexicografică, toate circuitele de lungime trei.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code> de noduri și numărul <code>m</code> de arce, iar apoi lista arcelor, formată din <code>m</code> perechi de forma <code>i j</code>, cu semnificația că există arc orientat de la nodul <code>i</code> la nodul <code>j</code>.

= Date de ieșire =
Programul va afișa pe ecran circuitele cerute, câte un circuit pe o linie a ecranului, nodurile unui circuit fiind separate prin exact un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>

= Exemplul 1: =
5 7
1 3
2 5
3 2
3 4
4 2
5 4
5 1
Ieșire
2 5 4
4 2 5
5 4 2

= Exemplul 2: =
101 23
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
nMAX = 100

def verifica_restrictii(n):
if 1 <= n <= nMAX:
return True
else:
print("Datele nu corespund restrictiilor impuse.")
return False

def main():
n, m = map(int, input("Introduceti numarul de noduri si muchii: ").split())

# Verificăm dacă `n` respectă restricțiile impuse
if not verifica_restrictii(n):
return

gf = [[False for _ in range(nMAX + 1)] for _ in range(nMAX + 1)]

print("Introduceti muchiile:")
for _ in range(m):
a, b = map(int, input().split())
gf[a][b] = True

for i in range(1, n + 1):
for j in range(1, n + 1):
if gf[i][j]:
for h in range(1, n + 1):
if gf[j][h] and gf[h][i]:
print(f"Triplet gasit: {i} {j} {h}")

if __name__ == "__main__":
main()

</syntaxhighlight>

2164 - munte1

2024-02-24T07:13:28Z

Aurelia Raluca:

== Enunt ==

Maria pleacă în excursie la munte. Traseul de la baza muntelui și până la vârf trece printr-o serie de parcele organizate într-o matrice pătratică de dimensiune <code>nxn</code>. Baza muntelui se consideră primul element al matricei, iar vârful, ultimul element. Se cunoaște faptul că traseele de la bază până la vârf au numai suișuri. Maria dispune de un altimetru prin intermediul căruia poate determina altitudinea la care se găsește parcela pe care se află. Ea nu-și propune să urce până la vârf, ci doar până la o anumită altitudine.

= Cerința =
Cunoscând valoarea <code>n</code>, harta de dimensiune <code>nxn</code> cu altitudinile precizate și <code>x</code> o valoare ce reprezintă altitudinea la care trebuie să ajungă Maria, se cere să se determine coordonatele parcelei cu altitudinea <code>x</code>.

= Date de intrare =
Fișierul de intrare <code>munte1IN.txt</code> conține:

<code>n</code> // <code>nxn</code> parcele

<code>a[1,1] a[1,2]......... a[1,n]</code> // <code>a[i,j] < a[i,j+1]</code> cu <code>i=1,n</code> și <code>j=1,n-1</code>

<code>a[2,1] a[2,2]......... a[2,n]</code> // <code>a[i,j]<a[i+1,j]</code> cu <code>i=1,n-1</code> și <code>j=1,n</code>

………………….

<code>a[n,1] a[n,2]......... a[n,n]</code> //harta cu altitudinile parcelelor

<code>x</code> //altitudinea destinaţie

= Date de ieșire =
Fișierul de ieșire <code>munte1OUT.txt</code> va conține pe prima linie două valori <code>i</code> și <code>j</code> separate printr-un spațiu reprezentând coordonatele parcelei cu altitudinea <code>x</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 700</code>
* altitudinea <code>x</code> se află pe hartă
* valorile altitudinilor sunt unice și sunt numere naturale mai mici decât <code>2.000.000.000</code>

= Exemplul 1: =
<code>munte1IN.txt</code>
4
1 3 9 10
2 4 11 13
5 6 12 14
7 15 16 19
13
<code>munte1OUT.txt</code>
2 4

== Explicație ==
Valoarea <code>13</code> se află pe poziția <code>(2,4)</code>.

== Exemplul 2: ==
<code>munte1IN.txt</code>
701
1 3 9 10
2 4 11 13
5 6 12 14
7 15 16 19
13
<code>munte1OUT.txt</code>
Datele nu corespund formatului asteptat

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def verifica_restricții(n, a, x):
if not (1 <= n <= 700):
return False
if not (0 < x < 2000000000):
return False
valori_unică = set()
for i in range(1, n + 1):
for j in range(1, n + 1):
if a[i][j] <= 0 or a[i][j] >= 2000000000 or a[i][j] in valori_unică:
return False
valori_unică.add(a[i][j])
if x not in valori_unică:
return False
return True

def citire():
with open("munte1IN.txt", "r") as fin:
n = int(fin.readline().strip())
a = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
linie = fin.readline().strip().split()
if len(linie) != n: # Verifică dacă linia are lungimea corectă
with open("munte1OUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return None, None, None # Returnează None pentru a indica eroarea
for j in range(1, n + 1):
a[i][j] = int(linie[j - 1])
x = int(fin.readline().strip())
return n, a, x

def cautare(i, st, dr, a, x):
if st <= dr:
if st == dr:
if a[i][st] == x:
with open("munte1OUT.txt", "w") as fout:
fout.write(f"{i} {st}\n")
return True
else:
mid = (st + dr) // 2
if cautare(i, st, mid, a, x):
return True
if cautare(i, mid + 1, dr, a, x):
return True
return False

def rezolvare(n, a, x):
for i in range(1, n + 1):
if x >= a[i][1] and x <= a[i][n]:
if cautare(i, 1, n, a, x):
break

if __name__ == "__main__":
n, a, x = citire()
if n is not None and a is not None and x is not None: # Verifică dacă citirea a fost corectă
if verifica_restricții(n, a, x):
rezolvare(n, a, x)
else:
with open("munte1OUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")

</syntaxhighlight>

3872 - cnt seq max min

2024-02-23T21:01:44Z

Aurelia Raluca:

== Cerinta ==

Se dă un șir de N numere întregi. Să se afle numărul de subsecvențe ale șirului pentru care diferența dintre elementul lor de valoare maximă și cel de valoare minimă este mai mică sau egală decât un număr întreg T dat.

== Date de intrare ==

Programul citește de la tastatură numerele N și T, iar apoi N numere întregi, separate prin spații.

== Date de iesire ==

Programul va afișa pe ecran numărul de subsecvențe ale șirului dat care respectă condiția din enunț. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

== Restrictii si precizari ==

*1 ≤ N ≤ 1.000.000

*0 ≤ T ≤ 2.000.000.000

*cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000]

*se numește subsecvență a unui șir o succesiune de elemente consecutive din acesta, considerate în ordinea în care apar în șir

*pentru teste în valoare de 30 de puncte N ≤ 10.000

*pentru teste în valoare de 70 de puncte N ≤ 600.000

= Exemplul 1: =
Intrare
5 2
1 7 2 3 4
Ieșire
8

== Explicație ==
Cele <code>8</code> subsecvențe care respectă condiția din enunț sunt toate cele <code>5</code> care conțin un singur element(diferența dintre elementul maxim și cel minim fiind astfel <code>0</code>), respectiv cele delimitate de perechile de indecși <code>[3, 4], [3, 5], [4, 5]</code>(șirul se consideră a fi indexat de la <code>1</code>).

== Exemplul 2: ==
Intrare
123213123 323
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">

def numar_subsecvente(arr, T):
n = len(arr)
rezultat = 0

# Sortăm șirul pentru a face procesul mai eficient
arr.sort()

# Folosim doi pointeri pentru a găsi subsecvențele
stanga = 0
dreapta = 0

while stanga < n:
while dreapta < n and arr[dreapta] - arr[stanga] <= T:
dreapta += 1

# Numărul de subsecvențe care încep cu stanga și au dreapta ca ultim element
rezultat += dreapta - stanga

# Ne deplasăm spre următorul element
stanga += 1

return rezultat

print("Numărul de subsecvențe este:", rezultat)
from collections import deque

def check_restrictions(n, t, v):
if not (1 <= n <= 1000000):
return False
if not (0 <= t <= 2000000000):
return False
for num in v:
if not (-1000000000 <= num <= 1000000000):
return False
return True

def solve(n, t, v):
st = dr = 0
mini = deque()
maxi = deque()
ans = 0

for i in range(n):
while mini and v[i] < v[mini[-1]]:
mini.pop()

while maxi and v[i] > v[maxi[-1]]:
maxi.pop()

mini.append(i)
maxi.append(i)

if maxi and mini and v[maxi[0]] - v[mini[0]] <= t:
ans += dr - st + 1
else:
while maxi and mini and v[maxi[0]] - v[mini[0]] > t:
if maxi[0] == st:
maxi.popleft()

if mini[0] == st:
mini.popleft()

st += 1

if maxi and mini:
ans += dr - st + 1

dr += 1

print(ans)

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

if not (1 <= n <= 1000000) or not (0 <= t <= 2000000000):
print("Datele nu corespund restrictiilor impuse")
return

v = [int(x) for x in input().split()]

if not check_restrictions(n, t, v):
print("Datele nu corespund restrictiilor impuse")
return

solve(n, t, v)

main()

</syntaxhighlight>

3687 - Back to the Himalayas

2024-02-23T20:52:22Z

Aurelia Raluca:

== Cerinta ==

''Cum găsește căprioara apa rece de izvor, tot așa găsesc eu banii și în vârful munților! – Jany MooRANDy''

A trecut așa mult timp de când bombardierul vostru favorit Jany MooRANDy a vizitat Himalaya și dușmanii lui au început să-i conteste abilitățile sale de a face bani. Nu vă faceți probleme, el a ajuns înapoi în Himalaya să demonstreze înca o dată de ce este în stare: “Să bată vântul și ploaia, eu fac bani și-n Himalaya! Unde fac eu bani pachete, dușmanii culeg doar pietre!”. După ce a obținut doctoratul în fizică demonstrând astfel multiplele sale abilități, el a schimbat “legea conservării energiei” în “legea conservării valorii”.

Legea spune așa: Valoarea cinetică a unui obiect e egală cu <code>m * v * v / 2</code>, unde <code>m</code> e masa obiectului și <code>v</code> e viteza lui, iar valoarea potențială a obiectului este <code>m * g * h</code>, unde <code>m</code> e masa obiectului, <code>g</code> e accelerația gravitațională, pe care o presupunem ca fiind <code>10</code>, iar <code>h</code> e diferența de înălțime dintre ea și un punct de referință.

Așa cum știm cu toții, Himalaya are <code>n</code> vârfuri muntoase, situate într-o linie, al i-lea vârf având înălțimea <code>h[i]</code>. Acum Jany MooRANDy vrea să încaseze banii câștigați de stațiile de telecabină din fiecare din cele <code>n</code> vârfuri muntoase. Începând de la un vârf <code>i</code> el se poate deplasa doar spre dreapta, spre vârful <code>n</code>.

Deoarece el are multă valoare, el începe călătoria cu o valoare cinetică de <code>m * v * v / 2</code>. Când sare din vârful <code>i</code> către vârful <code>i+1</code>, el fie câștigă, fie pierde valoare. Dacă <code>h[i] ≥ h[i+1]</code>, el va câștiga <code>m * g * (h[i] - h[i+1])</code> valoare, iar dacă <code>h[i] < h[i+1]</code>, el va pierde <code>m * g * (h[i+1] - h[i])</code> valoare. De-a lungul călătoriei, valoarea lui nu poate scădea sub <code>0</code>. Pentru ca el vrea să faca bani pachete, vrea să știe pentru fiecare punct de start care este cel mai depărtat punct spre care el se poate deplasa?

= Date de intrare =
Programul citește de la tastatură pe prima linie numerele <code>n</code>, <code>m</code> și <code>v</code>, numărul de vârfuri, masa și viteza lui Jany MooRANDy.

Pe următoarea linie, se vor citi <code>n</code> numere, reprezentând înălțimile celor <code>n</code> vârfuri.

= Date de ieșire =
Programul va afișa pe ecran <code>n</code> numere, reprezentând răspunsul cerut pentru fiecare vârf.

= Restricții și precizări =

* <code>1 ≤ n ≤ 500 000</code>
* <code>1 ≤ m ≤</code> <code>1050</code>
* <code>1 ≤ v ≤ 40 000</code>
* cele <code>n</code> numere citite vor fi mai mici decât <code>1.000.000.000</code>
* Problema nu necesită cunoștinte de fizică pentru a fi rezolvată.
* Pentru teste în valoare de <code>30</code> de puncte, <code>1 ≤ n ≤ 1000</code>, <code>1 ≤ v ≤ 400</code>, <code>1 ≤ m ≤</code> <code>109</code>
* Pentru alte teste în valoare de <code>30</code> de puncte, <code>1 ≤ n ≤ 1000</code>

= Exemplul 1: =
Intrare
9 2 7
3 2 1 5 3 3 8 2 1
Ieșire
6 3 3 6 6 6 9 9 9

=== Explicație ===
Hai să vedem de ce <code>ans[1] = 6</code>.

El pornește din primul vârf cu valoare cinetică de <code>49</code>.

De la vârful <code>1</code> la vârful <code>2</code>, valoarea lui crește cu <code>20</code>, deci devine <code>69</code>.

De la vârful <code>2</code> la vârful <code>3</code>, valoarea lui crește cu <code>20</code>, deci devine <code>89</code>.

De la vârful <code>3</code> la vârful <code>4</code>, valoarea lui scade cu <code>80</code>, deci devine <code>9</code>.

De la vârful <code>4</code> la vârful <code>5</code>, valoarea lui crește cu <code>40</code>, deci devine <code>49</code>.

De la vârful <code>5</code> la vârful <code>6</code>, valoarea lui rămâne la <code>49</code>.

De la vârful <code>6</code> la vârful <code>7</code>, valoarea lui scade cu <code>100</code>, deci devine <code>-51</code>, așa că nu mai poate continua drumul.

Astfel, Jany poate ajunge de la vârful <code>1</code> la vârful <code>6</code>.

== Exemplul 2: ==
Intrare
9 2 40001
3 2 1 5 3 3 8 2 1
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import sys

# Definirea limitelor și variabilelor
N_MAX = 500000
H = [0] * (N_MAX + 5)
S = [0] * (N_MAX + 5)
ans = [0] * (N_MAX + 5)
L = 0

def get_ans(idx, N, v):
ret = N + 1
le, ri = 1, L
while le <= ri:
mid = (le + ri) // 2
if 20 * H[S[mid]] > 20 * H[idx] + v * v:
ret = S[mid]
le = mid + 1
else:
ri = mid - 1
return ret - 1

def main():
global L
# Citirea datelor de intrare
try:
N, dummy, v = input().split()
N, v = int(N), int(v)
except ValueError:
print("Datele introduse nu respectă restricțiile")
return

# Verificare restricții pentru N și v
if not (1 <= N <= 500000 and 1 <= v <= 40000):
print("Datele introduse nu respectă restricțiile")
return

# Citirea înălțimilor de pe o singură linie
try:
H[1:N+1] = map(int, input().split())
except ValueError:
print("Datele introduse nu respectă restricțiile")
return

# Verificarea restricțiilor pentru înălțimi
if any(h >= 1000000000 for h in H[1:N+1]):
print("Datele introduse nu respectă restricțiile")
return

# Logica principală a programului
for i in range(N, 0, -1):
while L > 0 and H[S[L]] <= H[i]:
L -= 1
L += 1
S[L] = i
ans[i] = get_ans(i, N, v)

# Afișarea răspunsurilor
for i in range(1, N + 1):
print(ans[i], end=" ")
print()

if __name__ == "__main__":
main()

</syntaxhighlight>

2861 - puncte4

2024-02-23T20:33:52Z

Aurelia Raluca:

== Enunt ==

Zăhărel a desenat pe o foaie de hârtie <code>N</code> puncte în plan. Curios din fire, şi-a ales încă <code>M</code> puncte pe axa <code>OX</code> şi s-a întrebat pentru fiecare dintre cele <code>M</code> puncte de pe axa <code>Ox</code> care dintre cele <code>N</code> puncte este cel mai apropiat (situat la distanță minimă). Se consideră că distanța dintre două puncte <code>(x1, y1)</code> şi <code>(x2, y2)</code> este <code>(x1-x2)^2</code> <code>+ (y1-y2)^2</code>.

= Cerința =
Scrieți un program pentru Zăhărel care să determine pentru fiecare dintre cele <code>M</code> puncte de pe axa <code>OX</code>, care este distanța la cel mai apropiat punct dintre cele <code>N</code> desenate pe hârtie.

= Date de intrare =
Fișierul de intrare <code>puncte4IN.txt</code> conține pe prima linie numerele naturale <code>N</code>, <code>M</code> separate prin spații. Fiecare dintre următoarele <code>N</code> linii conține câte o pereche de numere naturale nenule <code>x y</code>, separate prin spații, reprezentând coordonatele celor <code>N</code> puncte (în ordinea abscisă, ordonată). Fiecare dintre următoarele <code>M</code> linii conține câte un număr natural <code>x</code>, reprezentând abscisele (coordonatele pe axa <code>OX</code>) ale celor <code>M</code> puncte.

= Date de ieșire =
Fișierul de ieșire <code>puncte4OUT.txt</code> va conține <code>M</code> linii. Pe linia <code>i</code> va fi scris un număr natural reprezentând distanța la cel mai apropiat punct dintre cele <code>N</code> de pe hârtie pentru al <code>i</code>-lea punct de pe axa <code>OX</code> (considerând ordinea punctelor din fișierul de intrare). În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ M ≤ 200.000</code>
* Toate coordonatele din fișierul de intrare sunt numere naturale din intervalul <code>[1, 1.000.000.000]</code>
* Cele <code>N</code> puncte din fișierul de intrare sunt sortate după coordonata <code>x</code> crescător, iar în cazul în care două puncte au aceeași abscisă, ele sunt ordonate crescător după coordonata <code>y</code>.
* Pentru <code>50%</code> din teste <code>N ≥ 90000</code> și <code>M ≥ 150000</code>.

= Exemplul 1: =
<code>puncte4IN.txt</code>
3 2
1 1
5 1
10 2
2
7
<code>puncte4OUT.txt</code>
2
5

=== Explicație ===
Pe hârtie au fost desenate <code>3</code> puncte, având coordonatele <code>(1,1)</code>, <code>(5,1)</code>, respectiv <code>(10,2)</code>. Pe axa <code>OX</code> se află <code>2</code> puncte, având abscisa <code>2</code>, respectiv <code>7</code>.

Distanța minimă dintre punctul de pe axa <code>OX</code> de abscisă <code>2</code> este <code>2</code> (cel mai apropiat punct fiind cel de coordonate <code>(1,1)</code>).

Distanța minimă dintre punctul de pe axa <code>OX</code> de abscisă <code>7</code> este <code>5</code> (cel mai apropiat punct fiind cel de coordonate <code>(5,1)</code>).

== Exemplul 2: ==
<code>puncte4IN.txt</code>
100001 2
1 1
5 1
10 2
2
7
<code>puncte4OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from typing import List, Tuple

# Constante
MAX_N = 100005
INF = float('inf')

# Definirea tipului punct ca un tuplu de două întregi
Point = Tuple[int, int]

# Funcția pentru calculul punctului de întâlnire între două puncte
def meet(a: Point, b: Point) -> int:
if a[0] == b[0]:
return INF if a[1] < b[1] else 0
x = (a[0]**2 + a[1]**2 - b[0]**2 - b[1]**2)
x = (x + 2 * (a[0] - b[0]) - 1) // (2 * (a[0] - b[0]))
return max(0, min(int(x), INF))

# Funcția pentru verificarea restricțiilor
def verifica_restricții(N: int, M: int, puncte: List[Point]) -> bool:
if not (1 <= N <= 100000) or not (1 <= M <= 200000):
return False
for x, y in puncte:
if not (1 <= x <= 1000000000) or not (1 <= y <= 1000000000):
return False
return True

# Funcția principală
def main():
with open("puncte4IN.txt", "r") as fin, open("puncte4OUT.txt", "w") as fout:
N, M = map(int, fin.readline().split())
P = [tuple(map(int, fin.readline().split())) for _ in range(N)]

# Verificarea restricțiilor
if not verifica_restricții(N, M, P):
fout.write("Datele nu corespund restrictiilor impuse\n")
return

X = [0] + [INF] * N
stk = [0]

for i in range(1, N):
while stk and (x := meet(P[stk[-1]], P[i])) <= X[len(stk)-1]:
stk.pop()
stk.append(i)
X[len(stk)-1] = x
X[len(stk)] = INF

for _ in range(M):
x = int(fin.readline())
i = next(i for i in range(len(stk)) if X[i] > x) - 1
result = (x - P[stk[i]][0])**2 + P[stk[i]][1]**2
fout.write(f"{result}\n")

# Executarea programului
if __name__ == "__main__":
main()

</syntaxhighlight>

2228 - expresie10

2024-02-23T20:17:53Z

Aurelia Raluca:

== Enunt ==

Se consideră o expresie formată din numere naturale şi perechi de paranteze drepte. Includerea între paranteze corespunde operației de calcul a câtului împărțirii întregi la <code>2</code> a valorii incluse între paranteze, iar alăturarea a două paranteze corespunde operației de adunare a valorilor subexpresiilor. Expresia poate fi calculată doar dacă este corectă, adică nu conține numere care să nu fie incluse între paranteze drepte, nu conține perechi de paranteze care să nu includă nici un număr sau nici o altă subexpresie şi perechile de paranteze se închid corect.

= Cerința =
Fiind dată o expresie construită conform descrierii să se decidă dacă este corectă şi în caz afirmativ să se calculeze valoarea acesteia.

= Date de intrare =
Fișierul de intrare <code>expresie10IN.txt</code> conține pe prima linie o expresie formata numai din paranteze drepte şi numere naturale.

= Date de ieșire =
Fișierul de ieșire <code>expresie10OUT.txt</code> va conține pe prima linie valoarea expresiei în cazul în care aceasta este corectă. Dacă expresia din fişierul de intrare nu este corectă, atunci se va scrie mesajul <code>expresie gresita</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* numerele care apar în expresii sunt întregi şi sunt cuprinse între <code>0</code> şi <code>30000</code>
* expresia din fișierul de intrare este formată din cel mult <code>200</code> de caractere

= Exemplul 1: =
<code>expresie10IN.txt</code>
[[34][23[12][]
<code>expresie10OUT.txt</code>
expresie gresita

== Exemplul 2: ==
<code>expresie10IN.txt</code>
[30001][23[12]]
<code>expresie10OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from typing import List

def verifica_restricții(expresie: str) -> bool:
if len(expresie) > 200:
return False
for c in expresie:
if c.isdigit():
if not 0 <= int(c) <= 30000:
return False
return True

def proceseaza_expresie(input_file: str, output_file: str):
with open(input_file, 'r') as f:
continut = f.read().replace('\n', '')

if not verifica_restricții(continut):
with open(output_file, 'w') as f:
f.write("Datele nu corespund restrictiilor impuse")
return

stiva: List[int] = []
ok = True
e = False
nr1 = nr2 = x = sum = 0
x = -1

numar_curent = ""
for c in continut:
if c == '[':
nr1 += 1
elif c == ']':
nr2 += 1

if nr1 or nr2:
e = True

if c == '[' and x == -1:
stiva.append(x)
else:
if c.isdigit():
numar_curent += c # Construim numărul curent
if len(numar_curent) > 5 or int(numar_curent) > 30000: # Verificăm lungimea și valoarea numărului
with open(output_file, 'w') as f:
f.write("Datele nu corespund restrictiilor impuse")
return
x = int(numar_curent)
else:
numar_curent = "" # Resetează numărul curent când întâlnești un non-digit
if c == ']' and x != -1 and stiva[-1] == -1 and stiva:
stiva.pop()
stiva.append(x >> 1)
x = -1
nr1 -= 1
nr2 -= 1
elif c == ']' and stiva and stiva[-1] >= 0 and len(stiva) >= 2:
minus = True
while minus:
a = stiva.pop()
if not stiva:
break
b = stiva.pop()
if b != -1:
stiva.append(a + b)
else:
minus = False
break
stiva.append(a >> 1)
nr1 -= 1
nr2 -= 1
if nr2 > nr1:
ok = False
else:
ok = False

if nr1 or nr2 or not e:
ok = False

while stiva and ok:
if stiva[-1] != -1:
sum += stiva.pop()
else:
ok = False
break

with open(output_file, 'w') as f:
if ok:
f.write(str(sum))
else:
f.write("expresie gresita")

if __name__ == "__main__":
input_file = 'expresie10IN.txt'
output_file = 'expresie10OUT.txt'
proceseaza_expresie(input_file, output_file)

</syntaxhighlight>

0698 - nrpits

2024-02-23T20:01:18Z

Aurelia Raluca:

== Enunt ==

Se dă un șir de <code>N</code> numere distincte <code>a[1],a[2],..a[N]</code>. Orice secvență <code>a[i],a[i+1],...,a[j-1],a[j]</code>, <code>1 ≤ i + 1 < j ≤ n</code>, pentru care toate valorile <code>a[k]</code>, <code>i < k < j</code>, sunt mai mici decât extremitățile <code>a[i]</code> și <code>a[j]</code>, o vom numi în continuare “groapă”.

= Cerința =
Scrieţi un program care va determina numărul “gropilor” din șirul dat.

= Date de intrare =
Fișierul de intrare <code>nrpitsIN.txt</code> conţine pe prima linie numărul natural N. Pe linia a doua se află scrise cele N numere naturale ale șirului, separate prin spațiu.

= Date de ieșire =
Fișierul de ieșire <code>nrpitsOUT.txt</code> va conține un singur număr reprezentând numărul de “gropi” ale șirului dat. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ N ≤ 1.000.000</code>
* <code>1 ≤ a[i] ≤ 1.000.000</code>, pentru fiecare <code>1 ≤ i ≤ N</code>
* orice “groapă” are cel puțin trei elemente

= Exemplul 1: =
<code>nrpitsIN.txt</code>
12
12 1 10 3 4 11 5 8 7 9 2 6
<code>nrpitsOUT.txt</code>
8

= Explicație =
Cele opt “gropi” sunt:

<code>12 1 10</code>

<code>10 3 4</code>

<code>12 1 10 3 4 11</code>

<code>10 3 4 11</code>

<code>11 5 8</code>

<code>8 7 9</code>

<code>9 2 6</code>

<code>11 5 8 7 9</code>

== Exemplul 2: ==
<code>nrpitsIN.txt</code>
1000001
12 1 10 3 4 11 5 8 7 9 2 6
<code>nrpitsOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restricții(n, v):
# Verificăm dacă N respectă restricțiile
if not (2 <= n <= 1_000_000):
return False
# Verificăm dacă fiecare element din v respectă restricțiile
for val in v:
if not (1 <= val <= 1_000_000):
return False
return True

def main():
with open("nrpitsIN.txt", "r") as fin:
n = int(fin.readline())
v = list(map(int, fin.readline().split()))

# Verificăm restricțiile
if not verifica_restricții(n, v):
with open("nrpitsOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return # Oprim execuția dacă datele nu respectă restricțiile

# Continuăm procesarea datelor deoarece acestea respectă restricțiile
v = [0] + v
st = [-1] * (n + 1)
dr = [-1] * (n + 1)

s = []
for i in range(1, n + 1):
while s and v[i] > v[s[-1]]:
s.pop()
if s:
st[i] = s[-1]
s.append(i)

d = []
for i in range(n, 0, -1):
while d and v[i] > v[d[-1]]:
d.pop()
if d:
dr[i] = d[-1]
d.append(i)

ans = sum(1 for i in range(1, n + 1) if st[i] != -1 and dr[i] != -1)

with open("nrpitsOUT.txt", "w") as fout:
fout.write(str(ans))

if __name__ == "__main__":
main()

</syntaxhighlight>

1936 - Catalin si codul secret

2024-02-23T19:47:08Z

Aurelia Raluca:

== Cerința ==

În banca lui Cătălin există un seif special unde Moș Crăciun își ține ascunse cadourile pentru copiii cei cuminți. Fiind vorba de o persoană așa de importantă, codul seifului nu este unul ușor. Moșului îi este dat un cartonaș cu <code>n</code> numere pe care le parcurge, în ordine, de la al doilea la penultimul, şi verifică pentru fiecare număr dacă cei <code>2</code> vecini sunt ori divizori ori multipli ai acestuia. Dacă da, va șterge primul triplet care respectă această regulă (numărul şi vecinii săi), formându-se un nou cod pentru care se reia de la început aplicarea regulii, până când nu mai există pe cartonaș niciun număr care să respecte proprietatea de eliminat.

La final se vor obține valorile corecte ale codului, care vor fi introduse în ordinea apariției lor sau, în cazul în care s-au șters toate numerele de pe cartonaș, atunci codul va fi mesajul preferat folosit de Moș Crăciun: <code>Merry Christmas</code>.

Date fiind cele <code>n</code> numere de pe cartonaş, Moșul vă roagă să aflați codul de care are nevoie pentru a putea deschide seiful în seara de ajun.

= Date de intrare =
Fișierul de intrare <code>codsecretIN.txt</code> conține pe prima linie numărul natural <code>n</code>, iar pe a doua linie se găsesc <code>n</code> numere naturale <code>x[1] x[2] ... x[n]</code>, separate prin câte un spațiu, reprezentând numerele aflate pe cartonaș.

= Date de ieșire =
Fișierul de ieșire <code>codsecretOUT.txt</code> va conține pe prima linie codul pe care Moș Crăciun îl va folosi pentru a deschide seiful. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100.000</code>
* <code>0 < x[i] ≤ 10.000.000</code>

= Exemplul 1: =
<code>codsecretIN.txt</code>
9
2 12 6 3 10 2 4 8 3
<code>codsecretOUT.txt</code>
3 8 3

=== Explicație ===
Numărul <code>12</code> are <code>2</code> vecini, care sunt divizori ai săi deci vom șterge tripletul <code>2 12 6</code>. Noul cod obținut este <code>3 10 2 4 8 3</code>.

În noul cod avem numărul <code>2</code>, care are ca vecini doi multipli de-ai săi, deci vom șterge tripletul <code>10 2 4</code>.

Noul cod obținut este <code>3 8 3</code>, căruia nu îi putem face modificări, așa că îl afișăm.

== Exemplul 2: ==
<code>codsecretIN.txt</code>
100001
2 12 6 3 10 2 4 8 3
<code>codsecretOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import sys

def conditie(a, b, c):
return (b % a == 0 or a % b == 0) and (b % c == 0 or c % b == 0)

def verifica_restrictii(n, numere):
if not (1 <= n <= 100000) or any(x <= 0 or x > 10000000 for x in numere):
print("Datele nu corespund restrictiilor impuse")
sys.exit() # Încheie executia programului

def citire():
global v, k
n = int(input())
numere = list(map(int, input().split()))
verifica_restrictii(n, numere) # Verificăm restricțiile pentru datele de intrare
v = []
k = 0
for x in numere:
v.append(x)
k += 1
if k >= 3 and conditie(v[k - 3], v[k - 2], v[k - 1]):
k -= 3
v = v[:-3]

def rezolva():
if k <= 0:
print("Crăciun Fericit")
else:
for i in range(k):
print(v[i], end=" ")

def main():
sys.stdin = open("codsecretIN.txt", "r", encoding='utf-8')
sys.stdout = open("codsecretOUT.txt", "w", encoding='utf-8')
citire()
rezolva()

if __name__ == "__main__":
main()

</syntaxhighlight>

2068 - kpal

2024-02-23T11:31:38Z

Aurelia Raluca:

== Enunt ==

Alecu este un copil năzdrăvan care strică orice lucru. El a scris pe o foaie de hârtie un cuvânt. Fiind elev în clasa întâi, el nu a învățat decât primele <code>X</code> litere mici ale alfabetului englez, iar cuvântul de pe foaie este scris doar cu aceste litere.

El își propune să taie foaia în mai multe bucăți dar să obțină doar cuvinte având același număr de litere și în același timp toate cuvintele obținute în urma tăierii să fie palindromuri. Un cuvânt este palindrom dacă citit de la stânga spre dreapta este identic cu cuvântul obținut prin citire de la dreapta spre stânga. Exemplu de palindrom este cuvântul <code>abcba</code>.

În dorința de a obține în urma tăierii doar cuvinte palindrom, Alecu poate schimba orice literă a cuvântului, în oricare alta cunoscută de el, dar fiecare astfel de schimbare are un cost cunoscut. Mai mult, el știe că o literă din cuvântul inițial nu o poate schimba decât cel mult o singură dată.

Notăm cu <code>Nr(c)</code> numărul minim de palindromuri de lungimi egale în care poate fi tăiat cuvântul de pe foaie, având voie să se efectueze schimbări ale literelor, dar care să nu însumeze un cost total mai mare decât <code>c</code>. Alecu știe să determine valoarea <code>Nr(c)</code> pentru orice număr natural <code>c</code>.

= Cerința =
Scrieți un program care pentru un număr natural <code>Q</code> și șirul numerelor naturale <code>0,1,2,...,Q-1,Q</code>, determină suma: <code>Nr(0)+Nr(1)+Nr(2)+...+ Nr(Q-1)+Nr(Q)</code>.

= Date de intrare =
Fișierul de intrare <code>kpalIN.txt</code> pe prima linie conține numărul natural <code>X2. Următoarele</code> X@ linii conțin câte <code>X</code> numere. Pentru toate aceste linii, al <code>j</code>-lea număr de pe linia <code>i</code> reprezintă costul de a transforma a <code>i</code>-a literă în a <code>j</code>-a literă a alfabetului englez (<code>cost[i][j]</code>). Pe linia <code>X+2</code> se găsește un șir de litere ale alfabetului englez, reprezentând cuvântul scris inițial pe foaie. Ultima linie a fișierului conține numărul natural <code>Q</code>.

= Date de ieșire =
Fișierul de ieșire <code>kpalOUT.txt</code> va conține pe prima linie un număr natural reprezentând suma determinată. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ lungimea cuvântului ≤ 100 000</code>, iar cuvântul conține doar litere mici;
* <code>1 ≤ X ≤ 26</code>;
* <code>0 ≤ Q ≤ 1 000 000 000</code>;
* <code>1 ≤ cost[i][j] ≤ 10000</code>, unde <code>1 ≤ i</code>, <code>j ≤ X</code> și <code>i ≠ j</code>;
* <code>cost[i][i]=0</code>, unde <code>1 ≤ i ≤ X</code>;
* Dacă cuvântul inițial este palindrom, atunci considerăm că a fost obținut tot în urma unei tăieturi;

= Exemplul 1: =
<code>kpalIN.txt</code>
3
0 1 2
3 0 2
3 8 0
aabbbc
3
<code>kpalOUT.txt</code>
16

= Exemplul 2: =
<code>kpalIN.txt</code>
27
0 1 2
3 0 2
3 8 0
aabbbc
3
<code>kpalOUT.txt</code>
Datele nu corespund restrictiilor impuse
:

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(Sigma, Q, Cost):
# Restrictiile impuse
if not (1 <= Sigma <= 26 and 0 <= Q <= 1000000000):
return False
for i in range(Sigma):
for j in range(Sigma):
if i != j and not (1 <= Cost[i][j] <= 10000):
return False
return True

def main():
with open("kpalIN.txt", "r") as f:
Sigma = int(f.readline().strip())
if Sigma > 26: # Verificare pentru Sigma
with open("kpalOUT.txt", "w") as out_file:
out_file.write("Datele nu corespund restrictiilor impuse\n")
return
Cost = [list(map(int, f.readline().split())) for _ in range(Sigma)]
cuvant = f.readline().strip()
Q = int(f.readline().strip())

if not verifica_restrictii(Sigma, Q, Cost):
with open("kpalOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse\n")
return

INF = 1000000000
CostMatch = [[0] * 30 for _ in range(30)]
Price = [0] * 300
Count = [0] * 300

for i in range(Sigma):
for j in range(Sigma):
CostMatch[i][j] = INF
for k in range(Sigma):
CostMatch[i][j] = min(CostMatch[i][j], Cost[i][k] + Cost[j][k])

N = len(cuvant)
StackSize = 0

for lung in range(1, N + 1):
if N % lung != 0:
continue

current_price = 0
for i in range(N // lung):
left = i * lung
right = left + lung - 1
while left < right:
current_price += CostMatch[ord(cuvant[left]) - ord('a')][ord(cuvant[right]) - ord('a')]
right -= 1
left += 1

while StackSize > 0 and Price[StackSize - 1] >= current_price:
StackSize -= 1
Count[StackSize] = N // lung
Price[StackSize] = current_price
StackSize += 1

while StackSize > 0 and Price[StackSize - 1] > Q:
StackSize -= 1
Price[StackSize] = Q + 1

answer = 0
for i in range(StackSize):
answer += (Price[i + 1] - Price[i]) * Count[i]

with open("kpalOUT.txt", "w") as f:
f.write(str(answer) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

2123 - Relatii

2024-02-23T11:23:09Z

Aurelia Raluca:

== Enunt ==

<code>ar1<var2</code>

unde <code>var1</code> şi <code>var2</code> sunt două nume de variabile (deci litere mici distincte dintre primele <code>N</code> litere ale alfabetului englez).

= Cerința =
Scrieţi un program care să ordoneze crescător cele <code>N</code> variabile pe baza celor <code>M</code> relaţii cunoscute.

= Date de intrare =
Fişierul de intrare <code>relatiiIN.txt</code> conţine pe prima linie numerele naturale <code>N, M,</code> separate prin spaţiu. Pe fiecare dintre următoarele <code>M</code> linii este scrisă o relaţie sub forma din enunţ.

= Date de ieșire =
Fişierul de ieşire <code>relatiiOUT.txt</code> va conţine o singură linie pe care vor fi scrise <code>N</code> litere mici, neseparate prin spaţii, reprezentând variabilele ordonate crescător. Dacă există mai multe soluţii posibile, se va afişa cea mai mică din punct de vedere lexicografic (prima în dicţionar). În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =
• <code>2 ≤ N ≤ 10</code>

• <code>1 ≤ M ≤ 200</code>

• Relaţiile specificate în fişierul de intrare nu conţin spaţii.

• Pentru datele de test există întotdeauna soluţie, nu neapărat unică.

• Spunem că sirul <code>x1x2...xN</code> este mai mic din punct de vedere lexicografic decât şirul <code>y1y2...yN</code> dacă există un indice <code>k (1≤k≤N)</code> astfel încât <code>xi=yi</code>, pentru orice <code>1≤i<k</code> şi <code>xk<yk</code>.

= Exemplul 1: =
<code>relatiiIN.txt</code>
4 5
a<d
a<c
c>d
b>c
b>a
<code>relatiiOUT.txt</code>
adcb

== Exemplul 2: ==
<code>relatiiIN.txt</code>
4 5
a<d
a<c
c>d
b>c
b>a
<code>relatiiOUT.txt</code>
Datele nu corespund restrictiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(N, M):
if not (2 <= N <= 10 and 1 <= M <= 200):
with open("relatiiOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse.\n")
return False
return True

def citire():
with open("relatiiIN.txt", "r") as file:
first_line = file.readline().strip()
if not first_line:
return None, None
N, M = map(int, first_line.split())
if not verificare_restrictii(N, M):
return None, None
R = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
line = file.readline().strip()
if not line:
return None, None
c1, c2, c3 = line[0], line[1], line[2]
if c2 == '<':
R[ord(c1) - ord('a') + 1][ord(c3) - ord('a') + 1] = -1
R[ord(c3) - ord('a') + 1][ord(c1) - ord('a') + 1] = 1
else:
R[ord(c1) - ord('a') + 1][ord(c3) - ord('a') + 1] = 1
R[ord(c3) - ord('a') + 1][ord(c1) - ord('a') + 1] = -1
return N, R

def afisare(p):
with open("relatiiOUT.txt", "w") as fout:
for i in range(1, len(p)):
fout.write(chr(p[i] - 1 + ord('a')))
fout.write('\n')

def verif(p, R):
for i in range(1, len(p)):
for j in range(i + 1, len(p)):
if R[p[i]][p[j]] == 1:
return False
return True

def main():
N, R = citire()
if N is None or R is None:
return
p = list(range(N + 1))
while True:
if verif(p, R):
break
j = N - 1
while p[j] > p[j + 1]:
j -= 1
i = N
while p[i] < p[j]:
i -= 1
p[i], p[j] = p[j], p[i]
st, dr = j + 1, N
while st < dr:
p[st], p[dr] = p[dr], p[st]
st += 1
dr -= 1
afisare(p)

if __name__ == "__main__":
main()

</syntaxhighlight>

1966 - match

2024-02-23T10:06:18Z

Aurelia Raluca:

== Enunt ==

Tanărul Pagnad proaspăt ajuns la facultate, vrea să prindă și el ceva. Fiind nemulțumit de celebra aplicație Tinder acesta dorește să-și creeze propria lui aplicație. Aplicația se folosește de datele strânse de pe diferite rețele de socializare ale utilizatorului și le codează într-o matrice. Stați calmi, nu trebuie sa creați voi matricea, dar pentru a-și studia compatibilitatea cu o persoana Pagnad se folosește de următoarele noțiuni.

Acesta definește o structură de dimensiune <code>k</code> o submatrice pătratică de latura <code>k</code>. Compatibilitatea se stabilește în funcție de câte perechi de două structuri, nu neapărat de aceleași dimensiuni, dar de sumă egală se găsesc în două matrici (prima structură trebuie să aparțină primei matrici, a doua celei de-a doua matrici).

Definim o structură prin coordonatele colțului stânga sus <code>(x,y)</code> și dimensiunea laturii acesteia <code>k</code>. Două perechi <code>x1</code>, <code>y1</code>, <code>k1</code> și <code>x2</code>, <code>y2</code>, <code>k2</code> sunt diferite daca: <code>x1≠x2</code> sau <code>k1≠k2</code> sau daca <code>x1=x2</code> si <code>k1=k2</code> si <code>y1≠y2</code> sau <code>x1=x2</code>, <code>y1=y2</code> si <code>k1≠k2</code> (acestea fac referință pentru submatrice din aceeași matrice).

= Cerința =
Se cere să se afle compatibilitatea între cele două matrice.

= Date de intrare =
Fișierul de intrare <code>matchIN.txt</code> conține pe prima linie numerele <code>n1</code> si <code>m1</code>. Pe a doua linie se vor găsi <code>n1</code> numere. Pe următoarea linie <code>n2</code> și <code>m2</code>, iar pe linia a patra cele <code>n2</code> numere.

Unde <code>m1</code> și <code>m2</code> reprezintă numărul de coloane, iar <code>n1</code> și <code>n2</code> reprezintă dimensiunea totala a matricei.

= Date de ieșire =
Fișierul de ieșire <code>matchOUT.txt</code> va conține pe prima linie un singur număr, respectiv compatibilitatea dintre cele două matrice. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>n1,n2 ≤ 31.000</code>
* numerele din matrice <code><109</code>
* se garantează că suma acestora este <code><1018</code>
* <code>m1≤n1</code>; <code>m2≤n2</code>;
* <code>(n1,m1)≠1</code>; <code>(n1,m2)≠1</code>, unde <code>(a,b)=cmmdc(a,b)</code>;

= Exemplul 1: =
<code>matchIN.txt</code>
9 3
1 2 3 4 5 6 7 8 9
9 3
1 2 3 4 5 6 7 8 9
<code>matchOUT.txt</code>
14

=== Explicație ===
Matricile sunt identice, deci se consideră toate submatricele primei matrice.

== Exemplul 2: ==
<code>matchIN.txt</code>
9 3
1 2 3 4 5 6 7 8 9
9 3
1 2 3 4 5 6 7 8 9
<code>matchOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def check_restrictions(n1, m1, n2, m2):
if n1 > 31000 or n2 > 31000 or m1 > n1 or m2 > n2:
return False
if (n1, m1) == (1, 1) or (n1, m2) == (1, 1):
return False
return True

def load_data(filename):
global n1, n2, m1, m2, N1, N2, a, b

with open(filename, 'r') as fin:
N1, m1 = map(int, fin.readline().split())
n1 = N1 // m1
if not check_restrictions(n1, m1, n1, m1):
return False
a = [[0 for _ in range(m1)] for _ in range(n1)]
for i in range(n1):
a[i] = list(map(int, fin.readline().split()))

N2, m2 = map(int, fin.readline().split())
n2 = N2 // m2
if not check_restrictions(n2, m2, n2, m2):
return False
b = [[0 for _ in range(m2)] for _ in range(n2)]
for i in range(n2):
b[i] = list(map(int, fin.readline().split()))

return True

MOD = 666013
NMAX = 175

a = [[0 for _ in range(NMAX)] for _ in range(NMAX)]
b = [[0 for _ in range(NMAX)] for _ in range(NMAX)]
pd = [[0 for _ in range(NMAX)] for _ in range(NMAX)]
dp = [[0 for _ in range(NMAX)] for _ in range(NMAX)]
v = {i: [] for i in range(MOD + 1)}

def fasuma():
global dp, pd, a, b
# Ajustarea indexării pentru Python, începând de la 0
for i in range(1, n1 + 1):
for j in range(1, m1 + 1):
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i-1][j-1]

for i in range(1, n2 + 1):
for j in range(1, m2 + 1):
pd[i][j] = pd[i-1][j] + pd[i][j-1] - pd[i-1][j-1] + b[i-1][j-1]

def pp(s, x):
return {'s': s, 'x': x}

def bagahash(x):
r = x % MOD
for element in v[r]:
if element['s'] == x:
element['x'] += 1
return
v[r].append(pp(x, 1))

def cauta(x):
r = x % MOD
for element in v[r]:
if element['s'] == x:
return element['x']
return 0

def main():
if not load_data('matchIN.txt'):
with open('matchOUT.txt', 'w') as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

fasuma()

sol = 0
# Calcularea și compararea sumelor submatricilor
for k in range(1, min(n1, m1) + 1):
for i in range(k, n1 + 1):
for j in range(k, m1 + 1):
s = dp[i][j] - dp[i-k][j] - dp[i][j-k] + dp[i-k][j-k]
bagahash(s)
for k in range(1, min(n2, m2) + 1):
for i in range(k, n2 + 1):
for j in range(k, m2 + 1):
s = pd[i][j] - pd[i-k][j] - pd[i][j-k] + pd[i-k][j-k]
sol += cauta(s)

with open('matchOUT.txt', 'w') as fout:
fout.write(f'{sol}\n')

if __name__ == '__main__':
main()

</syntaxhighlight>

1056 - Unific

2024-02-23T07:48:43Z

Aurelia Raluca:

== Enunt ==

Se consideră un şir <code>A=(A1, A2, ..., AN)</code>, format din <code>N</code> numere naturale nenule. Două numere se consideră vecine dacă se află pe poziţii alăturate (<code>Ai</code> are ca vecini pe <code>Ai-1</code> şi <code>Ai+1</code>, pentru orice <code>1<i<N</code>, <code>A1</code> are ca vecin doar pe <code>A2</code>, iar <code>AN</code> are ca vecin doar pe <code>AN-1</code>).

Dacă două elemente vecine <code>Ai</code>, <code>Ai+1</code> (<code>1≤i<N</code>) au cel puţin o cifră comună, ele se pot unifica. Procedeul de unificare constă în eliminarea din numerele <code>Ai</code> şi <code>Ai+1</code> a tuturor cifrelor comune şi adăugarea prin alipirea numărului obţinut din <code>Ai+1</code> la numărul obţinut din <code>Ai</code>, formându-se astfel un nou număr. Numărul <code>Ai</code> va fi înlocuit cu noul număr, iar numărul <code>Ai+1</code> va fi eliminat din şir.

De exemplu, numerele <code>Ai=23814</code> şi <code>Ai+1=40273</code> au cifrele <code>2</code>, <code>3</code>, <code>4</code> comune, după unificare obţinem <code>Ai=817</code>, iar <code>Ai+1</code> este eliminat; observaţi că dacă după eliminarea cifrelor comune, numerele încep cu zerouri nesemnificative, acestea vor fi eliminate, apoi se realizează alipirea.

Dacă în urma eliminării cifrelor comune, unul dintre numere nu mai are cifre, atunci numărul rezultat va avea cifrele rămase în celălalt. Dacă în urma eliminării cifrelor comune atât <code>Ai</code> cât şi <code>Ai+1</code> nu mai au cifre, atunci ambele numere vor fi eliminate din şir, fără a fi înlocuite cu o altă valoare.

Ordinea în care se fac unificările în şir este importantă: la fiecare pas se alege prima pereche de elemente vecine <code>Ai</code> <code>Ai+1</code> care poate fi unificată, considerând şirul parcurs de la stânga la dreapta. (De exemplu, considerând <code>Ai=123</code>, <code>Ai+1=234</code>, <code>Ai+2=235</code>, se unifică <code>Ai</code> cu <code>Ai+1</code> => <code>Ai=14</code>, iar unificarea cu următorul număr nu mai este posibilă).

= Cerinţă =
Cunoscându-se şirul celor <code>N</code> numere naturale, să se determine:

a) cifra care apare cel mai frecvent în scrierea tuturor celor <code>N</code> numere; dacă există mai multe cifre cu aceeaşi frecvenţă de apariţie maximă, se va reţine cea mai mică cifră.

b) şirul obţinut prin efectuarea unui număr maxim de unificări, după regulile descrise în enunţ.

= Date de intrare =
Fișierul de intrare <code>unificIN.txt</code> conține pe prima linie o valoare naturală <code>N</code>, iar pe următoarele <code>N</code> linii, în ordine, cele <code>N</code> numere naturale din şirul <code>A</code>, câte un număr pe o linie.

= Date de ieșire =
Fișierul de ieșire <code>unificOUT.txt</code> va conține pe prima linie un număr natural c reprezentând cifra care apare cel mai frecvent în scrierea celor <code>N</code> numere naturale. Pe cea de a doua linie un număr natural <code>Nr</code> reprezentând numărul de numere naturale rămase în şir după efectuarea unui număr maxim de unificări. Pe cea de a treia linie se vor scrie cele <code>Nr</code> numere naturale rămase, în ordinea din şir, separate prin câte un spaţiu.

Dacă în urma procedeului de unificare, toate numerele vor fi eliminate, fişierul de ieşire va conţine o singură linie, pe care se va scrie cifra care apare cel mai frecvent în scrierea celor <code>N</code> numere naturale. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 100 000</code>
* Numerele din şirul iniţial, precum şi numerele obţinute în urma unificărilor, nu vor depăşi <code>1018</code>
* Pentru datele de test şirul obţinut în urma unificărilor este nevid.
* Pentru 30% dintre teste <code>N ≤ 1000</code>
* Pentru 70% dintre teste numere naturale din şir au cifrele nenule.
* Pentru determinarea corectă a primei cerinţe se acordă 10% din punctajul pe test. Punctajul integral se acordă pe ambele cerinţe rezolvate corect.

= Exemplul 1: =
<code>unificIN.txt</code>
10
6
47
67
40
123
231
1238
331
2035
50007
<code>unificOUT.txt</code>
3
2
0 837

= Explicație =
Cifra care apare cel mai frecvent este <code>3</code> (de <code>6</code> ori).

Se unifică: <code>47</code> cu <code>67 => 46</code>. Şirul rămas: <code>6 46 40 123 231 1238 331 2035 50007</code>

Se unifică: <code>6</code> cu <code>46 => 4</code>. Şirul rămas: <code>4 40 123 231 1238 331 2035 50007</code>

Se unifică: <code>4</code> cu <code>40 => 0</code>. Şirul rămas: <code>0 123 231 1238 331 2035 50007</code>

Se unifică: <code>123</code> cu <code>231</code>, ambele numere rămân fără cifre, deci vor fi ambele eliminate. Şirul rămas: <code>0 1238 331 2035 50007</code>

Se unifică: <code>1238</code> cu <code>331 => 28</code>. Şirul rămas: <code>0 28 2035 50007</code>

Se unifică: <code>28</code> cu <code>2035 => 835</code>. Şirul rămas: <code>0 835 50007</code>

Se unifică: <code>835</code> cu <code>50007 => 837</code>. Şirul rămas: <code>0 837</code>

== Exemplul 1: ==
<code>unificIN.txt</code>
100001
6
47
67
40
123
231
1238
331
2035
50007
<code>unificOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, numere):
if not (1 <= n <= 100000):
return False

for numar in numere:
if not (0 <= numar <= 10**18):
return False

return True

def main():
with open("unificIN.txt", "r") as fin, open("unificOUT.txt", "w") as fout:
n = int(fin.readline().strip())
numere = []

for _ in range(n):
line = fin.readline().strip()
if line:
numere.append(int(line))

if not verifica_restrictii(n, numere):
fout.write("Datele nu corespund restrictiilor impuse")
return

frec = [0] * 11
st = []

def cifre(x):
while x:
frec[x % 10] += 1
x //= 10

def verif(poz):
aux1 = [0] * 11
x = st[poz - 1]
if x == 0:
aux1[0] += 1

while x:
aux1[x % 10] += 1
x //= 10

y = st[poz]
if y == 0 and aux1[0] != 0:
return 1

while y:
if aux1[y % 10] != 0:
return 1
y //= 10
return 0

def getnum(dr):
f = [0] * 21
unu = [0] * 21
doi = [0] * 21
cif1, cif2 = 0, 0
x, y = st[dr - 1], st[dr]
st_num, drr = 0, 0
concatenate = False
ok = False

if x == 0:
f[0] += 1
unu[cif1] = 0
cif1 += 1
if y == 0:
f[0] += 1
doi[cif2] = 0
cif2 += 1
while x:
cif1 += 1
unu[cif1] = x % 10
f[x % 10] += 1
x //= 10
while y:
if f[y % 10] != 0:
f[y % 10] = -1
cif2 += 1
doi[cif2] = y % 10
y //= 10

for i in range(cif1, 0, -1):
if f[unu[i]] != -1:
st_num = 10 * st_num + unu[i]
ok = True
for i in range(cif2, 0, -1):
if f[doi[i]] != -1:
drr = 10 * drr + doi[i]
ok = True
concatenate = True

if not ok:
return -1

if concatenate:
p = 10
while drr >= p:
p *= 10
return st_num * p + drr

return st_num

for numar in numere:
cifre(numar)
st.append(numar)

while len(st) >= 2 and verif(len(st) - 1):
x = getnum(len(st) - 1)
if x != -1:
st[-2] = x
st.pop()
else:
st.pop()
st.pop()

maxi, afis = max((val, idx) for idx, val in enumerate(frec))

fout.write(f'{afis}\n')
fout.write(f'{len(st)}\n')
for numar in st:
fout.write(f'{numar} ')

if __name__ == "__main__":
main()

</syntaxhighlight>

1237 - Numereiajb

2024-02-23T07:20:01Z

Aurelia Raluca:

== Cerinta ==

Numerele <code>iajb</code> sunt numerele care pot fi scrise sub forma <code>i * a + j * b</code>, cu <code>i</code> și <code>j</code> numere naturale și <code>i + j > 0</code>.

Cunoscând <code>a</code> și <code>b</code> și un număr <code>n</code>, să se determine valorile <code>i</code> și <code>j</code> pentru care se vor forma primele <code>n</code> numere <code>iajb</code> in ordine crescătoare.

= Date de intrare =
Fișierul de intrare <code>numereiajbIN.txt</code> conține pe prima linie numărul <code>3</code> numere naturale <code>a</code>, <code>b</code> și <code>n</code>, având semnificațiile de mai sus.

= Date de ieșire =
Fișierul de ieșire <code>numereiajbOUT.txt</code> va conține pe cele <code>n</code> linii câte o pereche de numere naturale <code>i</code> și <code>j</code> care răspund cerinței. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 2.000.000</code> (!)
* <code>1 ≤ a, b ≤ 50.000</code>
* Dacă un număr <code>iajb</code> se obține din perechi diferite de <code>(i, j)</code> atunci se va afișa doar cea cu <code>i</code>-ul minim

= Exemplul 1: =
<code>numereiajbIN.txt</code>
2 3 5
<code>numereiajbOUT.txt</code>
1 0
0 1
2 0
1 1
0 2

== Explicație ==
<code>1 * 2 + 0 * 3 = 2</code>

<code>0 * 2 + 1 * 3 = 3</code>

<code>2 * 2 + 0 * 3 = 4</code>

<code>1 * 2 + 1 * 3 = 5</code>

<code>0 * 2 + 2 * 3 = 6</code>

== Exemplul 2: ==
<code>numereiajbIN.txt</code>
2 3 50001
<code>numereiajbOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, a, b):
if not (1 <= n <= 2000000 and 1 <= a <= 50000 and 1 <= b <= 50000):
with open("numereiajbOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return False
return True

def main():
fin = open("numereiajbIN.txt", "r")
fout = open("numereiajbOUT.txt", "w")

n, a, b = map(int, fin.readline().split())
if not verificare_restrictii(n, a, b):
fin.close()
fout.close()
return

Q = [[], []]
Q[0].append((1, 0))
Q[1].append((0, 1))
last = -1

for t in range(1, n + 1):
crt = [Q[j][0][0] * a + Q[j][0][1] * b for j in range(2)]
if crt[0] < crt[1]:
i, j = Q[0].pop(0)
nr = crt[0]
else:
i, j = Q[1].pop(0)
nr = crt[1]
if nr == last:
t -= 1
continue
last = nr
fout.write(f"{i} {j}\n")
Q[0].append((i + 1, j))
Q[1].append((i, j + 1))

fin.close()
fout.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

1275 - Jaina

2024-02-23T07:07:58Z

Aurelia Raluca:

== Cerinta ==

Jaina se află în Theramore Isle și trebuie să ajungă la mentorul ei, Antonidas. Aceștia se află într-o matrice pătratică de dimensiune <code>n x n</code>, în poziții de coordonate cunoscute.

Jaina se poate deplasa în oricare dintre cele <code>8</code> direcții. Astfel, dacă inițial ea se găsește în celula de coordonate <code>(x, y)</code>, poate ajunge în oricare dintre celulele <code>(x-1, y-1)</code>, <code>(x-1, y)</code>, <code>(x-1, y + 1)</code>, <code>(x, y + 1)</code>, <code>(x + 1, y + 1)</code>, <code>(x + 1, y)</code>, <code>(x + 1, y - 1)</code> sau <code>(x, y - 1)</code> făcând exact un pas.

În anumite celule se află câte o sursă de energie. Fiecare sursă emite raze în patru direcții <code>(N, E, S, V)</code>, fiecare rază ajungând până la marginea matricei.

Când Jaina pășește pe o astfel de rază, ea se teleportează obligatoriu în celula sursei razei respective, deci nu este posibilă trecerea dincolo de aceste raze decât prin punctul sursă. Teleportarea este automată și instantanee și nu se consideră ca fiind un pas al Jainei.

Antonidas vă roagă să o ajutați pe Jaina să ajungă la el, efectuând un număr minim de pași!

= Date de intrare =
Fișierul de intrare <code>jainaIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>4</code> numere naturale separate prin spații, care semnifică coordonatele celulei în care se află Jaina și coordonatele celulei în care se află Antonidas. ( 2 perechi linie-coloană )

A treia linie conține numărul <code>m</code> de surse de energie.

Pe următoarele <code>m</code> linii se află câte două numere naturale <code>x y</code>, reprezentând coordonatele fiecărei surse.

= Date de ieșire =
Fișierul de ieșire <code>jainaOUT.txt</code> va conține pe prima linie numărul <code>nrp</code>, reprezentând numărul minim de pași pe care Jaina trebuie să-i efectueze pentru a ajunge la Antonidas. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ m ≤ 10</code>
* Orice celulă are dimensiunea <code>1x1</code>
* În cazul în care Jaina se află la intersecția a două raze de surse diferite, aceasta se va teleporta la sursa de linie minimă.
* Nu există două surse care să se afle pe aceeași linie sau pe aceeași coloană.
* Se garantează că există soluție pentru toate testele.
* Antonidas promite că o să fiți răsplătiți cu o minge de foc dacă găsiți răspunsul corect la această problemă.
* Deoarece Jaina este disperată, limitele de memorie sunt foarte mari, însă pe viitor nu este garantat acest lucru!

= Exemplul 1: =
<code>jainaIN.txt</code>
4
2 1 4 4
1
3 3
<code>jainaOUT.txt</code>
2

=== Explicație ===
Numărul de pași necesari în acest caz este 2.

= Exemplul 2: =
<code>jainaIN.txt</code>
4
2 1 4 4
1
3 3
<code>jainaOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
from collections import deque

class Celula:
def __init__(self):
self.val = 0
self.laser = 0
self.xs = 0
self.ys = 0

nmax = 100
dl = [-1, -1, -1, 0, 1, 1, 1, 0]
dc = [-1, 0, 1, 1, 1, 0, -1, -1]

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

def nord_sud(x, y, a, n):
for i in range(1, n + 1):
if a[i][y].laser == 0 and i != x:
a[i][y].laser = 1
a[i][y].xs = x
a[i][y].ys = y
elif i != x:
if x < a[i][y].xs:
a[i][y].xs = x
a[i][y].ys = y

def est_vest(x, y, a, n):
for j in range(1, n + 1):
if a[x][j].laser == 0 and j != y:
a[x][j].laser = 1
a[x][j].xs = x
a[x][j].ys = y
elif j != y:
if x < a[x][j].xs:
a[x][j].xs = x
a[x][j].ys = y

def solve(n, xi, yi, xf, yf, m, a):
q = deque([(xi, yi)])
a[xi][yi].val = 1

while q:
f1, f2 = q.popleft()

for k in range(8):
iv = f1 + dl[k]
jv = f2 + dc[k]

if inside(iv, jv, n) and (not a[iv][jv].val or a[iv][jv].val > a[f1][f2].val + 1):
if a[iv][jv].laser == 0:
a[iv][jv].val = a[f1][f2].val + 1
q.append((iv, jv))
else:
lin = a[iv][jv].xs
col = a[iv][jv].ys
a[iv][jv].val = a[f1][f2].val + 1

if a[lin][col].val > a[iv][jv].val or not a[lin][col].val:
a[lin][col].val = a[iv][jv].val
q.append((lin, col))
q.append((iv, jv))

return a[xf][yf].val - 1

def verificare_restrictii(n, m):
if not (1 <= n <= 100 and 1 <= m <= 10):
with open("jainaOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse")
return False
return True

def citire():
with open("jainaIN.txt", "r") as f:
n = int(f.readline().strip())
xi, yi, xf, yf = map(int, f.readline().split())
m = int(f.readline().strip())
if not verificare_restrictii(n, m):
exit() # Ieșire din program dacă restricțiile nu sunt respectate
a = [[Celula() for _ in range(nmax + 1)] for _ in range(nmax + 1)]
for _ in range(m):
x, y = map(int, f.readline().split())
nord_sud(x, y, a, n)
est_vest(x, y, a, n)
return n, xi, yi, xf, yf, a

def scriere(result):
with open("jainaOUT.txt", "w") as f:
f.write(str(result))

def main():
n, xi, yi, xf, yf, a = citire()
result = solve(n, xi, yi, xf, yf, n, a)
scriere(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

1337 - Susan

2024-02-23T07:00:31Z

Aurelia Raluca:

== Cerinta ==

Eroul nostru Susan se află într-un turn de formă cubică, de latură <code>n</code>. El dorește să ajungă la comoara ascunsă în interiorul turnului. Din fericire, Susan a făcut rost de o hartă care îi indică cu exactitate coordonatele locului în care se află comoara din turn. Eroul nostru vrea să știe care este distanța minimă pe care o poate parcurge pentru a ajunge la comoară.

Turnul este împărțit în <code>n</code> etaje, iar fiecare etaj este împărțit în <code>n x n</code> celule (camere). O cameră poate:

* fi blocată, astfel fiind inaccesibilă eroului nostru
* fi accesibilă, astfel eroul nostru poate intra în aceasta
* conține o scară ascendentă care îl poate duce pe erou cu un etaj mai sus, în camera situată deasupra camerei curente
* conține o scară descendentă care îl poate duce pe erou cu un etaj mai jos, în camera situată sub camera curentă
* conține o trapă prin care eroul va cădea la etajul inferior, în camerele situate sub camera curentă (dacă eroul, în urma căderii, se află într-o cameră ce conține o trapă, el va continua să cadă până se va afla într-o o cameră fără trapă, pe aceeași coloană)

La fiecare trecere dintr-o cameră în alta, eroul execută un pas.

Fiind date latura turnului și coordonatele zidurilor, scărilor, gropilor, eroului și a comorii, se cere să se afișeze numărul minim de pași pe care îl poate parcurge Susan pentru a ajunge la comoară.

= Date de intrare =
Fișierul de intrare <code>turnIN.txt</code> conține:

* pe prima linie numărul <code>n</code>, reprezentând lungimea laturii turnului.
* pe a doua linie se află numărul <code>z</code>, reprezentând numărul de ziduri, numărul <code>s1</code>, reprezentând numărul de scări descendente, numărul <code>s2</code>, reprezentând numărul de scări descendente și numărul <code>g</code>, reprezentând numărul de gropi.
* pe următoarele <code>z</code> linii se află coordonatele zidurilor.
* pe următoarele <code>s1</code> linii se află coordonatele scărilor ascendente.
* pe următoarele <code>s2</code> linii se află coordonatele scărilor descendente.
* pe următoarele <code>g</code> linii se află coordonatele gropilor.
* pe penultima linie se află coordonatele eroului, iar pe ultima linie se află coordonatele comorii.

= Date de ieșire =
Fișierul de ieșire <code>turnOUT.txt</code> va conține numărul minim de pași pe care îl poate face Susan pentru a ajunge la comoara sa. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ z ≤ 30000</code>
* <code>1 ≤ s1 ≤ s2 ≤ 200</code>
* <code>1 ≤ g ≤ 10000</code>
* Se garantează că există soluție pentru toate datele de test.
* Poziția inițială se consideră a fi situată la pasul 1.
* Trapa generează o cădere a eroului pe verticală, până când ajunge într-o cameră fără trapă.

= Exemplul 1: =
<code>turnIN.txt</code>
3
9 3 3 3
1 1 3
1 2 1
1 3 2
2 1 1
2 1 3
2 2 2
3 1 1
3 2 3
3 3 3
1 2 3
2 3 2
2 1 2
2 2 3
3 3 2
3 1 2
3 3 1
3 2 1
2 3 1
1 1 1
2 2 1
<code>turnOUT.txt</code>
11

== Explicație ==
Turnul are <code>3</code> etaje. Susan pleacă din celula de coordonate <code>(1 1 1)</code>, iar celula în care se află comoara are coordonatele <code>(2 2 1)</code>. Există <code>9</code> celule în care se află ziduri, <code>3</code> celule în care se află scări ascendente, <code>3</code> celule în care se află scări descendente și <code>3</code> celule în care se află gropi. Traseul cel mai scurt trece prin <code>11</code> camere: <code>(1 1 1) (1 1 2) (1 2 2) (1 2 3) (2 2 3) (2 3 3) (2 3 2) (3 3 2) (3 2 2) (3 2 1) (2 2 1)</code>.

== Exemplul 2: ==
<code>turnIN.txt</code>
101
9 3 3 3
1 1 3
1 2 1
1 3 2
<code>turnOUT.txt</code>
Datele nu corespund restrictiilor impuse
:

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
from collections import deque

dy = [1, -1, 0, 0]
dz = [0, 0, 1, -1]

def inmat(i, j, k, n):
return 1 <= i <= n and 1 <= j <= n and 1 <= k <= n

def lee(n, a, is_, js, ks, ifi, jfi, kfi):
b = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
q = deque([(is_, js, ks)])
b[is_][js][ks] = 1

while q:
x, y, w = q.popleft()
if a[x][y][w] != 4:
for d in range(4):
ii = x
jj = y + dy[d]
kk = w + dz[d]
if inmat(ii, jj, kk, n) and a[ii][jj][kk] != 1 and b[ii][jj][kk] == 0:
b[ii][jj][kk] = b[x][y][w] + 1
q.append((ii, jj, kk))
if a[x][y][w] == 4:
ii = x
cnt = 0
while a[ii][y][w] == 4:
ii -= 1
cnt += 1
if inmat(ii, y, w, n) and a[ii][y][w] != 1 and b[ii][y][w] == 0:
b[ii][y][w] = b[x][y][w] + cnt
q.append((ii, y, w))
elif a[x][y][w] == 3:
ii = x - 1
if inmat(ii, y, w, n) and a[ii][y][w] != 1 and b[ii][y][w] == 0:
b[ii][y][w] = b[x][y][w] + 1
q.append((ii, y, w))
elif a[x][y][w] == 2:
ii = x + 1
if inmat(ii, y, w, n) and a[ii][y][w] != 1 and b[ii][y][w] == 0:
b[ii][y][w] = b[x][y][w] + 1
q.append((ii, y, w))

return b[ifi][jfi][kfi]

def verificare_restrictii(n, z, sa, sd, g):
if not (1 <= n <= 100 and 1 <= z <= 30000 and 1 <= sa <= sd <= 200 and 1 <= g <= 10000):
with open("turnOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse")
return False
return True

with open("turnIN.txt", "r") as f:
n = int(f.readline().strip())
z, sa, sd, g = map(int, f.readline().split())
if not verificare_restrictii(n, z, sa, sd, g):
exit()

a = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(z):
x, y, w = map(int, f.readline().split())
a[x][y][w] = 1
for _ in range(sa):
x, y, w = map(int, f.readline().split())
a[x][y][w] = 2
for _ in range(sd):
x, y, w = map(int, f.readline().split())
a[x][y][w] = 3
for _ in range(g):
x, y, w = map(int, f.readline().split())
a[x][y][w] = 4
is_, js, ks = map(int, f.readline().split())
ifi, jfi, kfi = map(int, f.readline().split())

result = lee(n, a, is_, js, ks, ifi, jfi, kfi)

with open("turnOUT.txt", "w") as f:
if result is not None:
f.write(str(result))

</syntaxhighlight>

1856 - Taxe

2024-02-23T06:52:14Z

Aurelia Raluca:

== Enunt ==

Într-o ţară în care corupţia este în floare şi economia la pământ, pentru a obţine toate aprobările necesare în scopul demarării unei afaceri, investitorul trebuie să treacă prin mai multe camere ale unei clădiri în care se află birouri.

Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătrat de dimensiune <code>n•n</code>. Pentru a facilita accesul în birouri, toate camerele vecine au uşi între ele. În fiecare birou se află un funcţionar care pretinde o taxă de trecere prin cameră (taxă ce poate fi, pentru unele camere, egală cu <code>0</code>). Investitorul intră încrezător prin colţul din stânga-sus al clădirii (cum se vede de sus planul clădirii) şi doreşte să ajungă în colţul opus al clădirii, unde este ieşirea, plătind o taxă totală cât mai mică.

= Cerința =
Ştiind că el are în buzunar <code>S</code> euro şi că fiecare funcţionar îi ia taxa de cum intră în birou, se cere să se determine dacă el poate primi aprobările necesare şi, în caz afirmativ, care este suma maximă de bani care îi rămâne în buzunar la ieşirea din clădire.

= Date de intrare =
Fişierul de intrare <code>taxe2IN.txt</code> conţine pe prima linie cele două numere <code>S</code> şi <code>n</code> despărţite printr-un spaţiu, iar pe următoarele <code>n</code> linii câte <code>n</code> numere separate prin spaţii ce reprezintă taxele cerute de funcţionarii din fiecare birou.

= Date de ieșire =
Fişierul de ieşire <code>taxe2OUT.txt</code> conţine o singură linie pe care se află numărul maxim de euro care îi rămân în buzunar sau valoarea <code>–1</code> dacă investitorului nu-i ajung banii pentru a obţine aprobarea. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>3 ≤ N ≤ 100</code>
* <code>1 ≤ S ≤ 10000</code>
* Valorile reprezentând taxele cerute de funcţionarii din birouri sunt numere naturale, o taxă nedepășind valoarea de <code>200</code> de euro.

= Exemplul 1: =
<code>taxe2IN.txt</code>
10 3
1 2 5
1 3 1
0 8 1
<code>taxe2OUT.txt</code>
3

== Exemplul 2: ==
<code>taxe2IN.txt</code>
2 2
1 2
1 3
<code>taxe2OUT.txt</code>
Datele nu corespund restrictiilor impuse
:

:

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def read_input(filename="taxe2IN.txt"):
with open(filename, "r") as file:
s, n = map(int, file.readline().split())
a = [list(map(int, file.readline().split())) for _ in range(n)]
return s, n, a

def write_output(result, filename="taxe2OUT.txt"):
with open(filename, "w") as file:
file.write(str(result))

def verify_restrictions(s, n, a):
if not (3 <= n <= 100):
return False
if not (1 <= s <= 10000):
return False
for row in a:
for tax in row:
if not (0 <= tax <= 200):
return False
return True

def solve(s, n, a):
# Inițializează o matrice pentru a stoca costurile minime de a ajunge la fiecare celulă
b = [[float('inf')] * n for _ in range(n)]
b[0][0] = a[0][0] # Costul de a ajunge la celula de start este costul celulei de start

# Utilizează BFS pentru a explora toate căile posibile
queue = [(0, 0)]
while queue:
x, y = queue.pop(0)
for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]: # Explorează în toate direcțiile
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n:
new_cost = b[x][y] + a[nx][ny]
if new_cost < b[nx][ny]:
b[nx][ny] = new_cost
queue.append((nx, ny))

return s - b[n-1][n-1] if b[n-1][n-1] <= s else -1

def main():
s, n, a = read_input()
if not verify_restrictions(s, n, a):
write_output("Datele nu corespund restrictiilor impuse")
else:
result = solve(s, n, a)
write_output(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

2249 - panouri

2024-02-23T06:15:47Z

Aurelia Raluca:

== Enunt ==

Pe autostrada Soarele Estului sunt aşezate de-a lungul şoselei, la distanţe egale, panouri publicitare ale unor firme. Aceeaşi firmă, poate să aibă mai multe panouri publicitare şi fiecare panou poate să apară în mai multe locuri. Panourile se identifică prin numere naturale, numărul total de panouri fiind <code>N</code>. Firma X Corporation are panouri de <code>T</code> tipuri diferite. Firma a primit aprobarea construirii unui mare complex turistic în apropierea autostrăzii; de aceea, pentru alegerea locului, este interesată şi de următorul aspect: care este lungimea minimă de şosea, în care se pot întâlni, toate cele <code>T</code> tipuri de panouri publicitare ale firmei, indiferent de ordinea acestora, şi indiferent dacă între ele se mai interpun sau nu panouri ale altor firme.

= Cerința =
Cunoscând <code>N</code> – numărul total de panouri de la marginea autostrăzii şi ordinea amplasării lor, ca şi cele <code>T</code> tipuri de panouri amplasate de firmă, determinaţi numărul minim de intervale dintre două panouri între care firma X Corporation îşi regăsește toate panourile sale.

= Date de intrare =
Fișierul de intrare <code>panouriIN.txt</code> are pe prima linie numerele <code>N</code> şi <code>T</code>. Pe următoarele <code>N</code> linii, sunt <code>N</code> numere naturale, nu neapărat diferite, câte unul pe linie, reprezentând panourile, iar începând cu linia <code>N + 2</code>, câte unul pe linie, cele <code>T</code> tipuri de panouri diferite al firmei.

= Date de ieșire =
Fișierul de ieșire <code>panouriOUT.txt</code> va conţine pe prima linie un singur număr întreg pozitiv <code>L</code>, reprezentând numărul cerut, sau <code>-1</code> în caz că nu există soluţie. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 15000</code>
* <code>1 ≤ T ≤ 1000</code>
* Toate numerele reprezentând panouri sunt numere naturale din intervalul <code>[1..1000]</code>.

= Exemplul 1: =
<code>panouriIN.txt</code>
6 2
1
2
3
5
3
1
5
1
<code>panouriOUT.txt</code>
2

= Exemplul 2: =
<code>panouriIN.txt</code>
6 2
1
2
3
5
3
1
5
1
<code>panouriOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def read_input():
with open("panouriIN.txt", "r") as file:
n, t = map(int, file.readline().split())
v = []
for _ in range(n):
panou = file.readline().strip()
if panou:
v.append(int(panou))
panou_firma = set()
for _ in range(t):
panou = file.readline().strip()
if panou:
panou_firma.add(int(panou))
return n, t, v, panou_firma

def write_output(result):
with open("panouriOUT.txt", "w") as file:
file.write(str(result))

def validate_constraints(n, t, v, panou_firma):
if not (1 <= n <= 15000 and 1 <= t <= 1000):
write_output("Datele nu corespund restrictiilor impuse")
return False
for panou in v:
if not 1 <= panou <= 1000:
write_output("Datele nu corespund restrictiilor impuse")
return False
return True

def solve_problem(n, t, v, panou_firma):
fr = [0] * 1001
firma = []
lmin = 100000
k = 0

for i in range(n):
if v[i] in panou_firma:
firma.append((v[i], i))
if fr[v[i]] == 0:
k += 1
fr[v[i]] += 1

if k == t:
while firma and fr[firma[0][0]] > 1:
fr[firma[0][0]] -= 1
firma.pop(0)
lmin = min(lmin, i - firma[0][1])
fr[firma[0][0]] = 0
firma.pop(0)
k -= 1

return lmin

def main():
n, t, v, panou_firma = read_input()
if validate_constraints(n, t, v, panou_firma):
result = solve_problem(n, t, v, panou_firma)
write_output(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

0144 - copii

2024-02-22T20:23:18Z

Aurelia Raluca:

== Enunt ==

În Bistriţa sunt <code>N</code> copii, fiecare dintre ei având un număr preferat <code>Xi</code> . Copii se aşează pe un rând, cu poziţiile numerotate de la <code>1</code> la <code>N</code>. După ce copii s-au aşezat, profesoara de educaţie fizică le cere să execute <code>M</code> mişcări de tipul <code>(a, b)</code>, cu semnificaţia că îşi vor schimba ordinea copiii care se află între poziţiile <code>a</code> şi <code>b</code>, inclusiv.

= Cerință =
Să se răspundă la <code>Q</code> întrebări de tipul <code>p</code>, cu semnificaţia: care este numărul preferat al copilului, care se află pe poziţia <code>p</code>, după executarea mişcărilor cerute de profesoara de educaţie fizică.

= Date de intrare =
Fișierul <code>copiiIN.txt</code> are pe prima linie un număr natural <code>N</code>. Pe linia a 2-a sunt <code>N</code> numere <code>Xi</code> , separate prin câte un spațiu, cu semnificaţia din enunţ. Pe linia a 3-a este numărul <code>M</code>. Pe următoarele <code>M</code> linii se găseșc câte un două numere <code>a</code> şi <code>b</code> cu semnificația de mai sus. Pe următoarea linie se află numărul <code>Q</code>. Pe următoarele linii se află câte un număr <code>p</code>, cu semnificaţia de mai sus.

= Date de ieșire =
Fișierul <code>copiiOUt.txt</code> va conține <code>Q</code> linii. Pe fiecare linie se va afla răspunsul la întrebarea respectivă din fişierul de intrare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ M ≤ 10.000</code>
* <code>1 ≤ Q ≤ 100</code>
* <code>1 ≤ a ≤ b ≤ N</code>
* <code>-2.000.000.000 ≤ Xi</code> <code>≤ 2.000.000.000</code>

= Exemplul 1: =
<code>copiiIN.txt</code>
10
1 2 3 4 5 6 7 8 9 10
2
2 5
4 8
6
1
2
4
5
8
10
<code>copiiOUT.txt</code>
1
5
8
7
3
10

== Explicaţie ==
După prima mişcare şirul format din numerele preferate ale copiilor devine: <code>1 5 4 3 2 6 7 8 9 10</code>.

== Exemplul 2: ==
<code>copiiIN.txt</code>
100001
1 2 3 4 5 6 7 8 9 10
2
2 5
4 8
6
1
2
4
5
8
10
<code>copiiOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(N, M, Q, updates):
if not (1 <= N <= 100000 and 1 <= M <= 10000 and 1 <= Q <= 100):
return False
for x, y in updates:
if not (-2000000000 <= x <= 2000000000 and -2000000000 <= y <= 2000000000 and 1 <= x <= y <= N):
return False
return True

def main():
with open("copiiIN.txt", "r") as fin, open("copiiOUT.txt", "w") as fout:
n = int(fin.readline().strip())
a = [0] + list(map(int, fin.readline().split()))

m = int(fin.readline().strip())
updates = [tuple(map(int, fin.readline().split())) for _ in range(m)]

q = int(fin.readline().strip())

if not verificare_restrictii(n, m, q, updates):
fout.write("Datele nu corespund restrictiilor impuse\n")
return

for _ in range(q):
p = int(fin.readline().strip())
for j in range(m - 1, -1, -1):
x, y = updates[j]
if x <= p <= y:
p = x + y - p
fout.write(str(a[p]) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2460 - multimi5https:/wiki.universitas.ro/wiki/2460 - multimi5

2024-02-22T20:06:29Z

Aurelia Raluca:

== Enunt ==

O mulțime cu elemente numere naturale poate fi scrisă într-o formă redusă dacă, ordonând crescător elementele ei, diferența dintre oricare două valori alăturate este aceeași. De exemplu, mulțimea <code>D={11, 14, 17, 20, 23}</code> poate fi scrisă sub forma <code>D=11-23/3</code>, precizând elementul minim, elementul maxim și diferența dintre elemente. Date fiind <code>N</code> mulțimi scrise sub forma redusă, fiecare fiind notată cu o literă mare a alfabetului englez, se cere să se calculeze o expresie care poate conține:

* operația de reuniune, notată cu <code>+</code>;
* operația de intersecție, notată cu <code>*</code>;
* literele asociate mulțimilor;
* paranteze rotunde.

Considerăm că valoarea expresiei este mulțimea obținută după efectuarea operațiilor specifice mulțimilor considerând că operațiile de intersecție au prioritate mai mare decât cele de reuniune.

= Cerința =
Cunoscând forma redusă a celor <code>N</code> mulțimi și o expresie, să se calculeze valoarea expresiei date.

= Date de intrare =
Datele de intrare se citesc din fişierul <code>multimi5IN.txt</code>, care are următoarea structură:

- Pe prima linie se află numărul natural <code>N</code>, reprezentând numărul mulțimilor;

- Pe următoarele <code>N</code> linii se află formele reduse ale celor <code>N</code> mulțimi, câte o mulțime pe fiecare linie;

- Pe linia <code>N+2</code> se află expresia ce trebuie calculată.

= Date de ieșire =
Datele de ieşire se vor scrie în fişierul <code>multimi5OUT.txt</code>, astfel:

- Pe prima linie se va scrie numărul elementelor mulțimii obținute în urma evalării expresiei date;

- Pe linia a doua se vor scrie, în ordine crescătoare, elementele mulțimii respctive, separate prin câte un spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 < N ≤ 16</code>
* Elementele mulțimilor sunt numere naturale cuprinse între <code>0</code> și <code>1.000.000.000</code>;
* Numărul elementelor unei mulțimi este maximum <code>10.000</code>;
* Numărul caracterelor expresiei este cuprins între <code>3</code> și <code>1000</code>;
* Forma redusă a unei mulțimi și expresia dată nu conțin spații;
* Se garantează că, pentru toate datele de test, valoarea expresiei nu poate fi mulțimea vidă;
* Se garantează că, în teste care totalizează <code>30</code> de puncte, expresia nu conține paranteze;
* Se garantează că, în teste care totalizează <code>60</code> de puncte, cardinalul fiecărei mulțimi date la intrare nu depășește valoarea <code>1000</code>;

= Exemplul 1: =
<code>multimi5IN.txt</code>
3
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)
<code>multimi5OUT.txt</code>
2
4 8

=== Explicație ===
Mulțimile au următoarele elemente:

<code>A={2, 4, 6, 8}</code>

<code>B={4, 8,12, 16}</code>

<code>C={11, 14, 17, 20, 23}</code>

Efectuând operațiile obținem:

<code>B+C = {4, 8, 11, 12, 14, 16, 17, 20, 23}</code> și <code>A*(B+C) = {4, 8}</code>

== Exemplul 2: ==
<code>multimi5.in</code>
17
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)
<code>multimi5.out</code>
Datele nu corespund restrictiilor impuse

== Rezolvare: ==
<syntaxhighlight lang="python3" line="1">
def parseaza_set(linie):
parti = linie.split('=')
if len(parti) != 2:
return None
_, definitie_interval = parti
inceput, rest = definitie_interval.split('-')
sfarsit, pas = rest.split('/')
return set(range(int(inceput), int(sfarsit) + 1, int(pas)))

def verifica_restricții(n, seturi, expresie):
if not (1 < n <= 16):
return False
for set in seturi.values():
if set is None or not all(0 <= elem <= 1000000000 for elem in set) or len(set) > 10000:
return False
if not (3 <= len(expresie) <= 1000):
return False
return True

def evalueaza_expresie(A, B, C):
return A.intersection(B.union(C))

def main():
with open("multimi5IN.txt", "r") as fin:
n = int(fin.readline().strip())

seturi = {}
for _ in range(n):
linie = fin.readline().strip()
set_nume = linie[0]
set = parseaza_set(linie)
if set is None:
with open("multimi5OUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return
seturi[set_nume] = set

expresie = fin.readline().strip()

if not verifica_restricții(n, seturi, expresie):
with open("multimi5OUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

A, B, C = seturi['A'], seturi['B'], seturi['C']
rezultat = evalueaza_expresie(A, B, C)

with open("multimi5OUT.txt", "w") as fout:
fout.write(f"{len(rezultat)}\n")
for element in sorted(rezultat):
fout.write(f"{element} ")
fout.write("\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0687 - liste

2024-02-22T20:03:05Z

Aurelia Raluca:

== Enunt ==

Numim listă un sir de numere naturale. Avem la dispoziţie mai multe liste aşezate, în ordine, una sub alta. Spunem că două liste <code>L1</code> şi <code>L2</code> sunt vecine dacă <code>L1</code> este imediat deasupra lui <code>L2</code>, sau dacă <code>L2</code> este imediat deasupra lui <code>L1</code>. Oricare două liste vecine <code>L1</code> şi <code>L2</code> pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din <code>L1</code> la care se adaugă toate elementele din <code>L2</code>. Listele <code>L1</code> şi <code>L2</code> vor dispărea şi în locul lor va apărea noua listă.

= Cerința =
Determinaţi numărul minim de liste care rezultă după aplicarea unui număr suficient de unificări astfel încât să nu mai existe două liste vecine care să poată fi unificate.

= Date de intrare =
Fişierul <code>listeIN.txt</code> are pe prima linie un număr natural <code>L</code> reprezentând numărul de liste. Fiecare dintre următoarele <code>L</code> linii descriu, în ordine, câte o listă şi au structura: <code>K A[1] A[2] … A[K]</code>. Primul element notat <code>K</code> reprezintă numărul de elemente din listă. În continuare sunt <code>K</code> numere naturale care reprezintă elementele listei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

= Date de ieșire =
Pe prima linie a fişierului <code>listeOUT.txt</code> se găseşte un singur număr natural reprezentând valoarea cerută. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ L ≤ 100.000</code>
* fiecare listă iniţială are cel mult <code>10</code> de elemente;
* valorile elementelor listelor sunt numere naturale <code>≤ 120</code>

= Exemplul 1: =
<code>listeIN.txt</code>
4
2 0 1
1 0
3 1 3 3
1 2
<code>listeOUT.txt</code>
2

= Exemplul 2: =
<code>listeIN.txt</code>
100001
3 1 11 111
3 2 22 112
3 2 11 113
3 1 22 6
3 5 55 9
3 7 77 9
3 8 88 6
<code>listeOUT.txt</code>
Datele nu corespund restrictiilor impuse

= Explicație =
Avem patru liste. Putem unifica prima și a doua listă, acestea fiind înlocuite cu o singură lista. Apoi putem unifica lista rezultată la primul pas cu lista care iniţial era a treia. Obţinem astfel două liste care nu mai pot fi unificate.
:

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def unifica_liste(liste):
a_avut_loc_unificare = True
while a_avut_loc_unificare:
a_avut_loc_unificare = False
liste_noi = []
i = 0
while i < len(liste):
if i < len(liste) - 1 and liste[i].intersection(liste[i + 1]):
lista_unificata = liste[i].union(liste[i + 1])
liste_noi.append(lista_unificata)
i += 2
a_avut_loc_unificare = True
else:
liste_noi.append(liste[i])
i += 1
liste = liste_noi
return len(liste)

def citeste_date_intrare(nume_fisier_intrare):
liste = []
try:
with open(nume_fisier_intrare, 'r') as f:
n = int(f.readline().strip())
for _ in range(n):
linie = f.readline().strip().split()
k, numere = int(linie[0]), list(map(int, linie[1:]))
liste.append(set(numere))
except:
# Dacă apare orice eroare, returnăm None pentru a indica o problemă
return None
return liste

def verifica_restricii(liste):
if not 1 <= len(liste) <= 100000:
return False
for lista in liste:
if not 1 <= len(lista) <= 10 or any(x < 0 or x > 120 for x in lista):
return False
return True

def scrie_date_iesire(nume_fisier_iesire, mesaj):
with open(nume_fisier_iesire, 'w') as f:
f.write(mesaj + '\n')

def main():
nume_fisier_intrare = "listeIN.txt"
nume_fisier_iesire = "listeOUT.txt"
liste = citeste_date_intrare(nume_fisier_intrare)

if liste is None or not verifica_restricii(liste):
# Dacă datele sunt invalide sau nu respectă restricțiile, scriem mesajul de eroare
scrie_date_iesire(nume_fisier_iesire, "Datele nu corespund restrictiilor impuse")
else:
numar_liste_finale = unifica_liste(liste)
scrie_date_iesire(nume_fisier_iesire, str(numar_liste_finale))

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

2460 - multimi5https:/wiki.universitas.ro/wiki/2460 - multimi5

2024-02-22T18:45:25Z

Aurelia Raluca:

== Enunt ==

O mulțime cu elemente numere naturale poate fi scrisă într-o formă redusă dacă, ordonând crescător elementele ei, diferența dintre oricare două valori alăturate este aceeași. De exemplu, mulțimea <code>D={11, 14, 17, 20, 23}</code> poate fi scrisă sub forma <code>D=11-23/3</code>, precizând elementul minim, elementul maxim și diferența dintre elemente. Date fiind <code>N</code> mulțimi scrise sub forma redusă, fiecare fiind notată cu o literă mare a alfabetului englez, se cere să se calculeze o expresie care poate conține:

* operația de reuniune, notată cu <code>+</code>;
* operația de intersecție, notată cu <code>*</code>;
* literele asociate mulțimilor;
* paranteze rotunde.

Considerăm că valoarea expresiei este mulțimea obținută după efectuarea operațiilor specifice mulțimilor considerând că operațiile de intersecție au prioritate mai mare decât cele de reuniune.

= Cerința =
Cunoscând forma redusă a celor <code>N</code> mulțimi și o expresie, să se calculeze valoarea expresiei date.

= Date de intrare =
Datele de intrare se citesc din fişierul <code>multimi5.in</code>, care are următoarea structură:

- Pe prima linie se află numărul natural <code>N</code>, reprezentând numărul mulțimilor;

- Pe următoarele <code>N</code> linii se află formele reduse ale celor <code>N</code> mulțimi, câte o mulțime pe fiecare linie;

- Pe linia <code>N+2</code> se află expresia ce trebuie calculată.

= Date de ieșire =
Datele de ieşire se vor scrie în fişierul <code>multimi5.out</code>, astfel:

- Pe prima linie se va scrie numărul elementelor mulțimii obținute în urma evalării expresiei date;

- Pe linia a doua se vor scrie, în ordine crescătoare, elementele mulțimii respctive, separate prin câte un spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 < N ≤ 16</code>
* Elementele mulțimilor sunt numere naturale cuprinse între <code>0</code> și <code>1.000.000.000</code>;
* Numărul elementelor unei mulțimi este maximum <code>10.000</code>;
* Numărul caracterelor expresiei este cuprins între <code>3</code> și <code>1000</code>;
* Forma redusă a unei mulțimi și expresia dată nu conțin spații;
* Se garantează că, pentru toate datele de test, valoarea expresiei nu poate fi mulțimea vidă;
* Se garantează că, în teste care totalizează <code>30</code> de puncte, expresia nu conține paranteze;
* Se garantează că, în teste care totalizează <code>60</code> de puncte, cardinalul fiecărei mulțimi date la intrare nu depășește valoarea <code>1000</code>;

= Exemplul 1: =
<code>multimi5.in</code>
3
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)
<code>multimi5.out</code>
2
4 8

=== Explicație ===
Mulțimile au următoarele elemente:

<code>A={2, 4, 6, 8}</code>

<code>B={4, 8,12, 16}</code>

<code>C={11, 14, 17, 20, 23}</code>

Efectuând operațiile obținem:

<code>B+C = {4, 8, 11, 12, 14, 16, 17, 20, 23}</code> și <code>A*(B+C) = {4, 8}</code>

== Exemplul 2: ==
<code>multimi5.in</code>
17
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)
<code>multimi5.out</code>
Datele nu corespund restrictiilor impuse

== Rezolvare: ==
<syntaxhighlight lang="python3" line="1">
def parseaza_set(linie):
parti = linie.split('=')
if len(parti) != 2:
return None
_, definitie_interval = parti
inceput, rest = definitie_interval.split('-')
sfarsit, pas = rest.split('/')
return set(range(int(inceput), int(sfarsit) + 1, int(pas)))

def verifica_restricții(n, seturi, expresie):
if not (1 < n <= 16):
return False
for set in seturi.values():
if set is None or not all(0 <= elem <= 1000000000 for elem in set) or len(set) > 10000:
return False
if not (3 <= len(expresie) <= 1000):
return False
return True

def evalueaza_expresie(A, B, C):
return A.intersection(B.union(C))

def main():
with open("multimi5IN.txt", "r") as fin:
n = int(fin.readline().strip())

seturi = {}
for _ in range(n):
linie = fin.readline().strip()
set_nume = linie[0]
set = parseaza_set(linie)
if set is None:
with open("multimi5OUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return
seturi[set_nume] = set

expresie = fin.readline().strip()

if not verifica_restricții(n, seturi, expresie):
with open("multimi5OUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

A, B, C = seturi['A'], seturi['B'], seturi['C']
rezultat = evalueaza_expresie(A, B, C)

with open("multimi5OUT.txt", "w") as fout:
fout.write(f"{len(rezultat)}\n")
for element in sorted(rezultat):
fout.write(f"{element} ")
fout.write("\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3222 - treasure

2024-02-13T10:04:15Z

Aurelia Raluca:

== Enunt ==

Andrei este un aventurier care a plecat în căutarea unei comori pline cu bănuți de aur. Când a ajuns la ultimul indiciu, cel care ii va spune în ce loc se află comoara, a văzut ca pe indiciu sunt scrise doua numere naturale <code>N</code> și <code>K</code>, iar pe a doua linie un sir de <code>N</code> caractere, litere mici ale alfabetului englez. Andrei trebuie să ia șirul curent și să elimine prima secvență de <code>K</code> litere identice care apar pe poziții consecutive. El va relua acest procedeu până când nu va mai exista nicio secvență de <code>K</code> litere identice consecutive. Andrei vă roagă să-l ajutați să rezolve cât mai repede această problemă pentru a putea ajunge primul la comoară.

= Cerința =
Fiind date <code>N</code> și <code>K</code>, numere naturale și un șir de <code>N</code> litere mici ale alfabetului englez, trebuie să eliminați mereu prima secvență de <code>K</code> caractere identice aflate pe poziții consecutive până nu va mai exista nicio astfel de secvență.

= Date de intrare =
Se vor citi de la tastatura pe prima linie două numere naturale <code>N</code> și <code>K</code>, iar pe a doua linie un sir de <code>N</code> litere mici ale alfabetului englez.

= Date de ieșire =
Se va afișa pe ecran un sir care reprezintă șirul final pe care îl obținem după ce am efectuat toate eliminările posibile. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ K ≤ N ≤ 200.000</code>
* Toate caracterele șirului inițial sunt litere mici ale alfabetului englez
* Se garantează că la final șirul nu va fi vid!

= Exemplul 1: =
Intrare
5 2
abbac
Ieșire
c

=== Explicație ===
Șirul inițial : <code>abbac</code>

Șirul după prima eliminare: <code>aac</code>

Șirul după a doua eliminare: <code>c</code>

= Exemplul 2: =
Intrare
1 1
1
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def check_restrictions(n, k, s):
if not (2 <= k <= n <= 200000):
return False
s_str = ''.join(s)
if not s_str.islower():
return False
if not s:
return False
return True

def main():
n, k = map(int, input().split())
s = list(input())
if not check_restrictions(n, k, s):
print("Datele nu corespund restrictiilor impuse")
return
ok = 0
while ok == 0:
ctm = 1
ok = 1
elem = 0
rez = [0] * (n + 1)
for x in range(n):
elem += 1
rez[elem] = s[x]
if x < n - 1 and s[x] == s[x + 1]:
ctm += 1
else:
if ctm >= k:
elem -= k
ok = 0
ctm = 1
if ctm >= k:
elem -= k
s = ['\0'] * n
for x in range(1, elem + 1):
s[x - 1] = rez[x]
n = elem
for x in range(1, elem + 1):
print(rez[x], end="")
print()

if __name__ == "__main__":
main()

</syntaxhighlight>

3239 - chain

2024-02-13T09:35:26Z

Aurelia Raluca:

== Enunt ==

Se dă o secvență de <code>N</code> numere întregi <code>a1</code>, <code>a2</code>, …, <code>aN</code>. Pentru fiecare element <code>ak</code> (<code>k = 1, 2, ...,n</code>) vom determina primul element mai mare decât <code>ak</code>, dacă există. Îl notăm cu <code>ak1</code>. Apoi, pentru <code>ak1</code> facem același lucru și elementul găsit îl notăm cu <code>ak2</code>, și așa mai departe până ieșim în afara șirului. Se formează secvența <code>ak1</code>, <code>ak2</code>, …, pe care o numim chain începând cu poziția <code>k</code>.

= Cerința =
Scrieți un program care, pentru orice poziție <code>k</code> afișează lungimea secvenței chain corespunzătoare.

= Date de intrare =
Pe prima linie a intrării standard se dă valoarea <code>N</code>. Pe a doua linie se dau elementele șirului, separate prin spații.

= Date de ieșire =
Pe o linie a ieșirii standard, programul va scrie șirul valorilor ce reprezintă lungimile secvențelor chain corespunzătoare elementelor șirului de intrare. Fiecare două numere consecutive trebuie separate printr-un singur spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 < N < 500.000</code>
* <code>0 < ai</code> <code>< 1.000.000</code>, pentru fiecare <code>i = 1..N</code>.

= Exemplul 1: =
Intrare
11
3 2 4 2 11 2 7 5 8 10 6
Ieșire
2 2 1 1 0 3 2 2 1 0 0

= Exemplul 2: =
Intrare
0
123
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, a):
if not (0 < n < 500000):
return "Datele nu corespund restrictiilor impuse"
for i in range(n):
if not (0 < a[i] < 1000000):
return "Datele nu corespund restrictiilor impuse"
return "Datele corespund restrictiilor impuse"

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

mesaj = verifica_restrictii(n, a)
if mesaj != "Datele corespund restrictiilor impuse":
print(mesaj)
return

p = [0]*n
d = [0]*n

# O(n)
s = []
for i in range(1, n):
s.append(i-1)
while s:
j = s[-1]
if a[j] >= a[i]:
break
if a[j] < a[i]:
p[j] = i
s.pop()

# chains
d[n-1] = 0
for i in range(n-2, -1, -1):
if p[i] == 0:
d[i] = 0
else:
d[i] = 1 + d[p[i]]

print(' '.join(map(str, d)))

if __name__ == "__main__":
main()

</syntaxhighlight>