Bitnami MediaWiki - User contributions [en]

1103 - Harta

2024-03-26T16:45:08Z

Raul: Pagină nouă: Pe baza unei imagini preluate din satelit, se realizează harta unei mici localități. Localitatea ocupă o suprafață dreptunghiulară, cu laturile orientate pe direcțiile Nord-Sud, respectiv Est-Vest. Studiind imaginea obținută de la satelit, cartografii au constatat că toate cele <code>k</code> clădiri au forma unor dreptunghiuri distincte. Imaginea poate fi reprezentată sub forma unui tablou cu <code>n•m</code> celule așezate pe <code>n</code> linii numerotate...

Pe baza unei imagini preluate din satelit, se realizează harta unei mici localități. Localitatea ocupă o suprafață dreptunghiulară, cu laturile orientate pe direcțiile Nord-Sud, respectiv Est-Vest. Studiind imaginea obținută de la satelit, cartografii au constatat că toate cele <code>k</code> clădiri au forma unor dreptunghiuri distincte. Imaginea poate fi reprezentată sub forma unui tablou cu <code>n•m</code> celule așezate pe <code>n</code> linii numerotate de la <code>1</code> la <code>n</code> și <code>m</code> coloane numerotate de la <code>1</code> la <code>m</code>.

Numim drum, un dreptunghi al tabloului care străbate întreaga localitate pe direcția Est-Vest și are un număr maxim de linii sau un dreptunghi care străbate întreaga localitate pe direcția Nord-Sud și are un număr maxim de coloane. Drumurile, evident, nu trebuie să treacă prin clădiri.

Cartografii sunt interesați ca pe această hartă să fie reprezentate la scară doar clădirile, nu și drumurile. De aceea, pentru realizarea hărții, lățimile drumurilor au fost reduse la o singură celulă

Tabloul care reprezintă imaginea localității se codifică astfel: <code>1</code> pentru o celulă ocupată de o clădire și <code>0</code> pentru o celulă neocupată.

= Cerinţe =
Cunoscând <code>n</code>, <code>m</code> și <code>k</code>, precum și tabloul care codifică imaginea, se cere să se determine:

'''1.''' Numărul <code>S</code> de celule ocupate de către clădirea pătratică cu latura maximă și numărul de clădiri <code>C</code> alese dintre celelalte <code>k – 1</code> clădiri, cu proprietatea că fiecare dintre ele “încape” în interiorul clădirii pătratice cu latură maximă, fără să se suprapună peste celulele marginale ale acesteia.

'''2.''' Tabloul care reprezintă harta, în urma prelucrării imaginii inițiale.

= Date de intrare =
Fişierul de intrare <code>harta.in</code> conţine pe prima linie un număr natural <code>p</code>. Pentru toate testele de intrare, numărul <code>p</code> poate avea doar valoarea <code>1</code> sau valoarea <code>2</code>.

Pe linia a doua se găsesc numerele naturale <code>n</code>, <code>m</code> și <code>k</code> separate prin câte un spațiu.

Pe fiecare dintre următoarele <code>k</code> linii, se găsesc câte patru numere naturale <code>i1 j1 i2 j2</code>

separate prin câte un spațiu, primele două numere reprezentând coordonatele celulei din extremitatea Nord-Vest, iar ultimele două, coordonatele celulei din extremitatea Sud-Est pentru fiecare dintre cele <code>k</code> clădiri.

= Date de ieșire =

* Dacă valoarea lui <code>p</code> este <code>1</code>, atunci se va rezolva numai cerința <code>1</code>. În acest caz, în fişierul de ieşire <code>harta.out</code> se vor scrie cele două numere <code>S</code> și <code>C</code> având semnificația descrisă la cerința <code>1</code>, separate printr-un singur spațiu.
* Dacă valoarea lui <code>p</code> este <code>2</code>, atunci se va rezolva numai cerința <code>2</code>. În acest caz, fişierul de ieşire <code>harta.out</code> va conține tabloul care reprezintă harta obținută pe baza imaginii din satelit. Fișierul va avea <code>n1</code> linii. Pe fiecare linie se vor găsi câte <code>m1</code> valori <code>0</code> sau <code>1</code> separate prin câte un singur spațiu. Celulele situate pe marginile clădirilor vor avea valoarea <code>1</code>. Celulele din interiorul clădirilor, ca și cele din exterior, vor avea valoarea <code>0</code>.

= Restricții și precizări =

* <code>3 ≤ n, m ≤ 1500</code>
* <code>1 ≤ i1 ≤ i2 ≤ n</code>
* <code>1 ≤ j1 ≤ j2 ≤ m</code>
* <code>1 ≤ k ≤ 1000</code>
* <code>1 ≤ Lmax ≤ 50</code> (<code>Lmax</code> – latura maximă a unui dreptunghi)
* Se garantează că există soluție pentru ambele cerințe, pentru toate datele de test.
* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.

= Exemplul 1 =
<code>harta.in</code>
1
7 7 4
1 1 4 4
6 2 6 4
3 6 3 6
6 6 7 7
<code>harta.out</code>
16 2

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import numpy as np

#define pb push_back
#define DIM 1501
typedef vector<int> VI;

d = []
xa = []
ya = []
x = [0]
y = [0]
s1 = [True]
s2 = [True]
c1 = []
c2 = []
b1 = []
b2 = []
k = 0
N = 0
M = 0
n = 0
m = 0
Lmax = 0
L = 0
H = 0
T = 0
nr_dr = 0
A = np.zeros((1501, 1501), dtype=bool)

def GetPos(v, val):
n = len(v)
lo = 0
hi = n
while lo <= hi:
mid = lo + (hi - lo) // 2
if v[mid] == val:
return mid
if val < v[mid]:
hi = mid - 1
else:
lo = mid + 1
return 0

def WriteMatr(a, N, M):
for i in range(1, N+1):
for j in range(1, M+1):
fout.write(str(int(a[i][j])) + ' ')
fout.write('\n')

with open("harta.in", "r") as fin:
lines = fin.readlines()
T, N, M, k = map(int, lines[0].split())
imax = 0
jmax = 0
for i in range(k):
i1, j1, i2, j2 = map(int, lines[i+1].split())
d.append((i1, j1, i2, j2))
L = i2 - i1 + 1
H = j2 - j1 + 1
if L == H and L > Lmax:
Lmax = L
for i in range(i1, i2+1):
xa.extend([i, i])
ya.extend([j1, j2])
if not s1[i]:
x.append(i)
s1[i] = True
for j in range(j1, j2+1):
xa.extend([i1, i2])
ya.extend([j, j])
if not s2[j]:
y.append(j)
s2[j] = True
if not s1[i1 - 1]:
x.append(i1 - 1)
s1[i1 - 1] = True
if not s2[j1 - 1]:
y.append(j1 - 1)
s2[j1 - 1] = True
imax = max(imax, i2)
jmax = max(jmax, j2)
if T == 1:
for i in range(k):
L = d[i][2] - d[i][0] + 1
H = d[i][3] - d[i][1] + 1
if L < Lmax - 1 and H < Lmax - 1:
nr_dr += 1
fout.write(str(Lmax * Lmax) + ' ' + str(nr_dr) + '\n')
else:
c1 = [0] * (imax + 1)
c2 = [0] * (jmax + 1)
for i in range(len(x)):
c1[x[i]] += 1
for i in range(len(y)):
c2[y[i]] += 1
for i in range(1, imax+1):
c1[i] += c1[i - 1]
for i in range(1, jmax+1):
c2[i] += c2[i - 1]
b1 = [0] * len(x)
b2 = [0] * len(y)
for i in range(len(x)):
b1[c1[x[i]] - 1] = x[i]
c1[x[i]] -= 1
for i in range(len(y)):
b2[c2[y[i]] - 1] = y[i]
c2[y[i]] -= 1
n = 0
m = 0
for k in range(len(xa)):
i = GetPos(b1, xa[k])
j = GetPos(b2, ya[k])
n = max(n, i)
m = max(m, j)
A[i][j] = True
if n < M:
n += 1
if m < M:
m += 1
WriteMatr(A, n, m)
</syntaxhighlight>

1674 - Livada1

2024-03-26T16:24:31Z

Raul: Pagină nouă: Fermierul Quinto are o livadă plină cu pomi fructiferi. Livada are <code>N</code> rânduri, numerotate de la <code>1</code> la <code>N</code>, pe fiecare rând aflându-se câte <code>M</code> pomi fructiferi, numerotaţi de la <code>1</code> la <code>M</code>. Livada lui Quinto este una specială, aşa că pentru unii pomi se cunoaşte cantitatea de fructe (exprimată în kg) care poate fi culeasă, iar pentru alţii aceasta poate fi determinată pe baza unei formule. Qui...

Fermierul Quinto are o livadă plină cu pomi fructiferi. Livada are <code>N</code> rânduri, numerotate de la <code>1</code> la <code>N</code>, pe fiecare rând aflându-se câte <code>M</code> pomi fructiferi, numerotaţi de la <code>1</code> la <code>M</code>. Livada lui Quinto este una specială, aşa că pentru unii pomi se cunoaşte cantitatea de fructe (exprimată în kg) care poate fi culeasă, iar pentru alţii aceasta poate fi determinată pe baza unei formule. Quinto şi-a propus să recolteze <code>C</code> kg de fructe din pomii aflaţi în livada lui. Acesta foloseşte un utilaj modern pentru culesul fructelor. Utilajul poate fi folosit pe oricare din rândurile livezii, dar poate aduna doar fructele dintr-un şir consecutiv de pomi, începând cu primul pom de pe rândul respectiv, neavând posibilitatea de a culege parţial fructele dintr-un pom. Preocupat de frumuseţea livezii sale, Quinto s-a gândit la restricţii suplimentare pentru recoltarea cantităţii <code>C</code> de fructe. Astfel, el doreşte să adune fructele din pomi de pe maximum <code>R</code> rânduri diferite, pentru ca <code>N-R</code> rânduri să rămână complete. De asemenea, el doreşte să culeagă cu prioritate pomii care au o cantitate cât mai mică de fructe, pentru ca în livadă să rămână cei mai roditori pomi. Quinto şi-a dat seama că este dificil să culeagă fix <code>C</code> kg de fructe, prin urmare este mulţumit şi cu o cantitate mai mare, care respectă celelalte condiţii impuse de el.

= Cerința =
Determinaţi cea mai mică valoare <code>X</code> posibilă astfel încât să se poată culege, în condițiile de mai sus, o cantitate de cel puțin <code>C</code> kg de fructe și orice pom din care se culeg fructe să conțină cel mult <code>X</code> kg de fructe.

= Date de intrare =

* Pe prima linie a fişierului <code>livada1.in</code> se află <code>4</code> numere naturale <code>N M C R</code> cu semnificaţia din enunţ.
* Pe a doua linie din fişierul de intrare se află <code>5</code> numere naturale <code>x y z w u</code>, separate printr-un spaţiu.
* Dacă notăm cu <code>A[i][j]</code> cantitatea de fructe (exprimată în kg) din cel de-al <code>j</code>-lea pom de pe linia <code>i</code>, atunci:
** Linia a treia din fişierul de intrare conţine <code>M</code> valori <code>A[1][i]</code>, <code>1≤i≤M</code>, separate printr-un spaţiu
** Linia a patra din fişierul de intrare conţine <code>N-1</code> valori <code>A[i][1]</code>, <code>2≤i≤N</code>, separate printr-un spaţiu
** Celelalte valori <code>A[i][j]</code>, <code>2≤i≤N</code>, <code>2≤j≤M</code>, se calculează conform formulei: <code>A[i][j] = (x*A[i-1][j] + y*A[i][j-1] + z*A[i-1][j-1] + w) % u</code>.

= Date de ieșire =
Fișierul de ieșire <code>livada1.out</code> va conține o singură valoare scrisă pe prima linie, care reprezintă cea mai mică valoare a cantităţii de fructe (exprimată în kg) dintr-un pom cules, astfel încât să fie respectate toate restricţiile problemei.

= Restricții și precizări =

* <code>1 ≤ R ≤ N ≤ 100</code>
* <code>1 ≤ M ≤ 25000</code>
* <code>0 ≤ x,y,z,w,u ≤ 10^9</code>
* <code>0 ≤ A[i][j] ≤ 10^9</code>
* Atenție la determinarea fiecărei valori <code>A[i][j]</code> pentru că în formulă sunt produse care pot să furnizeze valori mai mari decât <code>2^32-1</code>.
* <code>1 ≤ C ≤ 10^18</code>
* Se garantează că pentru toate testele problema are soluție
* Pentru 30% din teste se garantează faptul că <code>1 ≤ M ≤ 100</code> şi <code>1 ≤ A[i][j] ≤ 100</code>
* Pentru 70% din teste se garantează faptul că <code>1 ≤ M ≤ 4000</code>

= Exemplu: =
<code>livada1.in</code>
5 6 18 4
3 6 5 2 7
4 1 3 5 1 2
5 2 6 3
<code>livada1.out</code>
4

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import numpy as np

NMax = 100
MMax = 25000
A = np.zeros((NMax+5, MMax+5), dtype=int)
Max = np.zeros((NMax+5, MMax+5), dtype=int)
Sum = np.zeros((NMax+5, MMax+5), dtype=int)
N = 0
M = 0
R = 0
Sol = 0
C = 0

def Read():
global N, M, C, R
global A
x = 0
y = 0
z = 0
w = 0
u = 0
with open("livada1.in", "r") as fin:
lines = fin.readlines()
N, M, C, R = map(int, lines[0].split())
x, y, z, w, u = map(int, lines[1].split())
A[1, :] = list(map(int, lines[2].split()))
for i in range(2, N+1):
A[i, 1] = int(lines[i+1])
for j in range(2, M+1):
A[i, j] = (x * A[i - 1, j] + y * A[i, j - 1] + z * A[i - 1, j - 1] + w) % u

def Precalculate():
global N, M
global A, Max, Sum
for i in range(1, N+1):
for j in range(1, M+1):
Sum[i, j] = A[i, j] + Sum[i, j-1]
Max[i, j] = max(Max[i, j-1], A[i, j])

def Find(i, Value):
global M
global A, Sum, Max
Crop = 0
Left = 1
Right = M
while Left <= Right:
Mid = (Left+Right) // 2
if Max[i, Mid] <= Value:
Crop = Sum[i, Mid]
Left = Mid + 1
else:
Right = Mid - 1
return Crop

def Check(Value):
global N, R, C
V = np.zeros(NMax, dtype=int)
k = 0
for i in range(1, N+1):
V[k] = Find(i, Value)
k += 1
V = np.sort(V[:k])[::-1]
Total = 0
for i in range(1, R+1):
if i <= k:
Total += V[i-1]
return Total >= C

def Solve():
global Sol
Left = 1
Right = 1000000000
while Left <= Right:
Mid = (Left + Right) // 2
if Check(Mid):
Sol = Mid
Right = Mid - 1
else:
Left = Mid + 1

def Print():
global Sol
with open("livada1.out", "w") as fout:
fout.write(str(Sol) + "\n")

if __name__ == '__main__":
Read()
Precalculate()
Solve()
Print()
</syntaxhighlight>

2977 - Poarta 1

2024-03-26T16:19:34Z

Raul: Pagină nouă: Sindbad a descoperit un recipient care conține o poțiune magică și o inscripție care descrie cum se poate deschide poarta unui templu. Urmând instrucțiunile din inscripție, Sindbad a ajuns la un tunel acoperit cu dale pătrate, aliniate astfel încât formează linii și coloane. Tunelul are mai multe linii, iar pe fiecare linie sunt câte <code>N</code> dale. Dalele din tunel sunt numerotate începând cu <code>1</code>, astfel încât, parcurgându-le linie cu lini...

Sindbad a descoperit un recipient care conține o poțiune magică și o inscripție care descrie cum se poate deschide poarta unui templu. Urmând instrucțiunile din inscripție, Sindbad a ajuns la un tunel acoperit cu dale pătrate, aliniate astfel încât formează linii și coloane. Tunelul are mai multe linii, iar pe fiecare linie sunt câte <code>N</code> dale. Dalele din tunel sunt numerotate începând cu <code>1</code>, astfel încât, parcurgându-le linie cu linie și fiecare linie de la stânga la dreapta, se obține un șir strict crescător de numere naturale consecutive. Sindbad se află la intrare, înaintea primei linii. Pentru a deschide poarta templului, el trebuie să ajungă pe dala numerotată cu <code>P</code>, călcând pe un număr minim de dale. Dacă există mai multe astfel de soluții, o va alege pe cea pentru care consumul total de picături de poțiune magică este minim. Pe parcursul deplasării el trebuie să respecte următoarele reguli:

* de la intrare, poate sări pe orice dală aflată pe prima line, fără a consuma poțiune magică;
* de pe o dală numerotată cu <code>X</code>, Sindbad poate sări fie pe dala numerotată cu <code>X + 1</code>, consumând o picătură de poțiune magică, fie pe dala numerotată cu <code>2 * X</code>, consumând două picături de poțiune magică.

= Cerința =
Scrieți un program care citește valorile <code>N</code> și <code>P</code> cu semnificația din enunț și rezolvă următoarele cerințe:

1. afișează numărul minim de dale pe care trebuie să calce pentru a deschide poarta;

2. afișează numărul natural <code>T</code>, reprezentând numărul minim de picături de poțiune magică necesare pentru deschiderea porții.

= Date de intrare =
Fișierul de intrare <code>poarta.in</code> conține pe prima linie un număr natural <code>C</code> reprezentând cerința din problemă care trebuie rezolvată (<code>1</code> sau <code>2</code>). Pe a doua linie se află numărul natural <code>N</code>, iar pe a treia linie se află numărul natural <code>P</code> cu semnificația din enunț.

= Date de ieșire =
Fișierul de ieșire <code>poarta.out</code> va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerința <code>C</code>.

= Restricții și precizări =

* <code>2 ≤ N < 10.000</code>
* <code>P</code> este număr natural nenul cu cel mult <code>1000</code> de cifre; pentru o parte dintre teste, valorând în total 60 de puncte, <code>P</code> are cel mult <code>18</code> cifre.
* Recipientul conține o cantitate suficientă de poțiune magică.
* Pentru rezolvarea '''cerinței 1''' se acordă maximum <code>60</code> de puncte, iar pentru rezolvarea '''cerinței 2''' se acordă maximum <code>30</code> de puncte.
* În concurs s-au acordat <code>10</code> puncte din oficiu. Aici se acordă pentru exemplele din enunț.

=== Explicație ===
Tunelul are <code>5</code> dale pe fiecare linie. Sindbad trebuie să ajungă pe dala numerotată cu <code>9</code>. Numărul minim de dale pe care trebuie să calce pentru a ajunge pe dala <code>9</code> pentru a deschide poarta este <code>3</code>. De pe margine poate sări:

– pe dala numerotată cu <code>4</code> (consumă <code>0</code> picături de poțiune magică);

– de pe dala numerotată cu <code>4</code> pe cea numerotată cu <code>8</code> (consumă <code>2</code> picături de poțiune magică);

– de pe dala numerotată cu <code>8</code> pe cea numerotată cu <code>9</code> (consumă <code>1</code> picătură de poțiune magică).

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
def main():
i = 0
k = 1
ck = 0
nv = 0
j = 0
v = [0] * 1001
nk = 0
gata = False
cer = 0
pas = 0
n = 0
ok = 0
T = 0
c = ''
f = open("poarta.in", "r")
g = open("poarta.out", "w")
cer, n = map(int, f.readline().split())
nv = 0
ok = 0
while True:
c = f.read(1)
if not c:
break
if c >= '0' and c <= '9':
nv += 1
v[nv] = int(c)
f.close()
ck = n
while ck:
nk += 1
ck = ck // 10
while not gata:
j = 0
k += 1
if v[nv] % 2 == 0:
T += 2
pas = 2
for i in range(1, nv + 1):
j = j * 10 + v[i]
v[i] = j // 2
j = j % 2
else:
T += 1
pas = 1
v[nv] -= 1
if v[1] == 0:
i = 1
j = 1
while v[i] == 0:
i += 1
nv = nv - i + 1
while j <= nv:
v[j] = v[i]
j += 1
i += 1
if nv <= nk:
ck = 0
for i in range(1, nv + 1):
ck = ck * 10 + v[i]
if ck <= n:
gata = True
if pas == 2 and ck * 2 == n + 1:
ck = n
T = T - 1
if cer == 1:
g.write(str(k) + "\n")
else:
g.write(str(T) + "\n")
g.close()
return 0

if __name__ == "__main__":
main()

</syntaxhighlight>

2383 - Plaja1

2024-02-18T17:17:31Z

Raul: Pagină nouă: Primăria orașului Constanța reamenajează plaja din stațiunea Mamaia. Aceasta este reprezentată ca o zonă dreptunghiulară cu lățimea de <code>a</code> unități și lungimea de <code>b</code> unități. Pe plajă sunt trasate linii paralele cu laturile dreptunghiului astfel încât să formeze pătrate cu latura de o unitate, numite zone. Pe plajă se vor pune obiecte: umbrele și prosoape. Se consideră că dacă un obiect intră în interiorul unei zone, o ocupă...

Primăria orașului Constanța reamenajează plaja din stațiunea Mamaia. Aceasta este reprezentată ca o zonă dreptunghiulară cu lățimea de <code>a</code> unități și lungimea de <code>b</code> unități. Pe plajă sunt trasate linii paralele cu laturile dreptunghiului astfel încât să formeze pătrate cu latura de o unitate, numite zone. Pe plajă se vor pune obiecte: umbrele și prosoape. Se consideră că dacă un obiect intră în interiorul unei zone, o ocupă în întregime. Se poziționează <code>u</code> umbrele de soare. Într-o zonă se poate așeza cel mult o umbrelă.

<code>N</code> turişti vin şi îşi aşează prosoapele pe plajă. Un prosop are formă dreptunghiulară şi va fi aşezat paralel cu laturile dreptunghiului. Turiştii îşi pot aşeza prosoapele pe zone libere sau peste prosoape deja aşezate. Un turist nu îşi poate aşeza însă prosopul pe plajă dacă suprafaţa acoperită de acesta include cel puţin o zonă în care se află o umbrelă.

<code>M</code> localnici au suprafeţe favorite pentru aşezarea prosoapelor. O suprafaţă favorită are forma unui dreptunghi cu laturile paralele cu laturile dreptunghiului care marchează plaja. După ce turiştii termină aşezarea prosoapelor, localnicii verifică dacă zonele din suprafaţa favorită sunt libere (neacoperite de prosoape aşezate de turişti sau de umbrele).

= Cerința =
Scrieţi un program care să determine numărul de turişti care au reuşit să îşi aşeze prosoapele pe plajă, precum și numărul de localnici ale căror zone favorite sunt libere.

= Date de intrare =
Fișierul de intrare <code>plaja1.in</code> conține pe prima linie trei numere naturale, separate prin câte un spațiu, <code>a</code>, <code>b</code> şi <code>u</code>, având semnificația din enunț. Fiecare din următoarele <code>u</code> linii conține o pereche de numere naturale <code>x y</code>, reprezentând o zonă în care se găsește o umbrelă. Următoarea linie din fișier conține un număr natural <code>N</code>, reprezentând numărul de turiști. Următoarele <code>N</code> linii descriu prosoapele turiștilor. Fiecare linie conține patru numere naturale <code>x1 y1 x2 y2</code>, ce reprezintă colțurile unui prosop. Linia următoare conține o singură valoare, <code>M</code>, reprezentând numărul de localnici. Pe următoarele <code>M</code> linii se află câte patru numere, separate prin câte un spațiu, <code>x1’ y1’ x2’ y2’</code>, ce reprezintă colțurile unei suprafețe favorite.

= Date de ieșire =
Fișierul de ieșire <code>plaja1.out</code> conţine pe prima linie două numere naturale separate printr-un spaţiu. Primul număr reprezintă numărul de turişti care şi-au aşezat prosoapele pe plajă, iar cel de-al doilea număr reprezintă numărul de localnici ale căror zone favorite sunt libere.

= Restricții și precizări =

* Colţul din stânga sus al zonei dreptunghiulare are coordonatele <code>(1,1)</code>
* <code>3 ≤ a, b ≤ 2.000</code>
* <code>0 ≤ u ≤ 100</code>
* <code>3 ≤ m, n ≤ 100.000</code>
* Un prosop descris de <code>(x1, y1, x2, y2)</code> va avea <code>1 ≤ x1 ≤ x2 ≤ a</code> şi <code>1 ≤ y1 ≤ y2 ≤ b</code>
* O suprafaţă favorită descrisă de <code>(x1’, y1’, x2’, y2’)</code> va avea <code>1 ≤ x1’ ≤ x2’ ≤ a</code> şi <code>1 ≤ y1’ ≤ y2’ ≤ b</code>

= Exemplu: =
<code>plaja1.in</code>
12 13 1
6 11
4
3 4 7 7
5 6 8 8
9 2 10 3
5 10 8 12
3
1 8 3 13
10 3 12 4
2 10 5 12
<code>plaja1.out</code>
3 2

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

NMax = 2004

M, N, A, B, U = 0, 0, 0, 0, 0
X = [0] * 128
Y = [0] * 128
S = [[0 for _ in range(NMax)] for _ in range(NMax)]
Res = 0

def main():
global M, N, A, B, U, X, Y, S, Res

i, j, x1, y1, x2, y2 = 0, 0, 0, 0, 0, 0
ok = False

sys.stdin = open('plaja1.intxt', 'r')
sys.stdout = open('plaja1.outtxt', 'w')

A, B, U = map(int, input().split())
for i in range(1, U + 1):
X[i], Y[i] = map(int, input().split())
N = int(input())
for i in range(1, N + 1):
x1, y1, x2, y2 = map(int, input().split())

for j in range(1, U + 1):
if x1 <= X[j] <= x2 and y1 <= Y[j] <= y2:
ok = False
break
ok = True

if not ok:
continue

Res += 1
S[x1][y1] += 1
S[x2 + 1][y2 + 1] += 1
S[x1][y2 + 1] -= 1
S[x2 + 1][y1] -= 1

print(Res)

for i in range(1, A + 1):
for j in range(1, B + 1):
S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]

for i in range(1, U + 1):
S[X[i]][Y[i]] = 1

for i in range(1, A + 1):
for j in range(1, B + 1):
S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (S[i][j] != 0)

Res = 0
M = int(input())
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
if S[x2][y2] - S[x2][y1 - 1] - S[x1 - 1][y2] + S[x1 - 1][y1 - 1] == 0:
Res += 1

print(Res)

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

1584 - Spirala2

2024-02-18T17:12:55Z

Raul: Pagină nouă: = Cerința = Se consideră un tablou bidimensional format din <code>n</code> linii și <code>n</code> coloane, completat cu elemente de la <code>1</code> la <code>n2</code>. Completarea acestuia se face pornind din colțul din stânga sus la cel din dreapta sus, de la cel din dreapta sus la cel din dreapta jos ș.a. (exemplu mai jos). Scrieți un program care citește un număr natural <code>n</code> și determină: # Suma resturilor împărțirii la <code>10000...

= Cerința =
Se consideră un tablou bidimensional format din <code>n</code> linii și <code>n</code> coloane, completat cu elemente de la <code>1</code> la <code>n2</code>. Completarea acestuia se face pornind din colțul din stânga sus la cel din dreapta sus, de la cel din dreapta sus la cel din dreapta jos ș.a. (exemplu mai jos).

Scrieți un program care citește un număr natural <code>n</code> și determină:

# Suma resturilor împărțirii la <code>100003</code> a elementelor de pe linia <code>k</code> și de pe coloana <code>k</code>; elementul care se află la intersecția acestora nu se va adăuga în sumă.
# Matricea formată prin inversarea coloanei <code>k</code> cu linia <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>spirala2.in</code> conține pe prima linie un număr natural <code>p</code>. Pentru toate testele de intrare, numărul <code>p</code> poate avea doar valoarea <code>1</code> sau <code>2</code>. A doua linie a fișierul conține două numere naturale <code>n</code> și <code>k</code> cu semnificațiile din enunț.

= Date de ieșire =

* Dacă valoarea lui <code>p</code> este <code>1</code>, se va rezolva numai punctul <code>1</code> din cerință. În acest caz, în fişierul de ieşire <code>spirala2.out</code> se va scrie un singur număr natural, reprezentând suma elementelor.
* Dacă valoarea lui <code>p</code> este <code>2</code>, se va rezolva numai punctul <code>2</code> din cerință. În acest caz, în fişierul de ieşire <code>spirala2.out</code> se va scrie noua matrice cu proprietatea din cerință.

= Restricții și precizări =

* <code>2 ≤ n ≤ 500</code>
* <code>1 ≤ k ≤ n</code>
* Pentru rezolvarea corectă a primei cerinţe se acordă <code>30</code> de puncte, iar pentru cerința a doua se acordă <code>70</code> de puncte.

= Exemplul 1: =
<code>spirala2.in</code>
1
3 2
<code>spirala2.out</code>
20

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

sys.stdin = open('spirala2.intxt', 'r')
sys.stdout = open('spirala2.outtxt', 'w')

n, k, i, j, p, nr, v = 501, 501, 0, 0, 0, 0, [[0]*501 for _ in range(501)]
s, w, a, b, x, y = 0, [[0]*501 for _ in range(501)], 0, 0, 0, 0

p, n, k = map(int, input().split())

for a in range(1, n+1):
x = a
y = n - a + 1
for i in range(x, y+1):
nr += 1
v[x][i] = nr
for i in range(x+1, y+1):
nr += 1
v[i][y] = nr
for i in range(y-1, x-1, -1):
nr += 1
v[y][i] = nr
for i in range(y-1, x, -1):
nr += 1
v[i][x] = nr

if p == 1:
for i in range(1, n+1):
if i != k:
s += v[i][k] % 100003 + v[k][i] % 100003
print(s)
else:
for i in range(1, n+1):
w[i][k] = v[k][i]
w[k][i] = v[i][k]
for i in range(1, n+1):
for j in range(1, n+1):
if not w[i][j]:
print(v[i][j], end=' ')
else:
print(w[i][j], end=' ')
print()
</syntaxhighlight>

2564 - Macara

2024-02-18T17:10:19Z

Raul: Pagină nouă: O macara industrială automatizată execută operații de mutare a unor containere aflate într-un depozit de materiale. Acest depozit poate fi reprezentat ca o matrice dreptunghiulară cu <code>m</code> linii şi <code>n</code> coloane, fiecare element al matricei reprezentând un container. Mai exact, elementul situat pe linia <code>i(1 ≤ i ≤ m)</code> şi coloana <code>j (1 ≤ j ≤ n)</code> din matrice reprezintă numărul de dale de granit aflate în containerul si...

O macara industrială automatizată execută operații de mutare a unor containere aflate într-un depozit de materiale. Acest depozit poate fi reprezentat ca o matrice dreptunghiulară cu <code>m</code> linii şi <code>n</code> coloane, fiecare element al matricei reprezentând un container. Mai exact, elementul situat pe linia <code>i(1 ≤ i ≤ m)</code> şi coloana <code>j (1 ≤ j ≤ n)</code> din matrice reprezintă numărul de dale de granit aflate în containerul situat în depozit pe poziția corespunzătoare. Toate dalele aflate în acelaşi container au aceeaşi culoare. În containerele cu dale negre, numărul de dale conținute este prim, în timp ce în containerele cu dale albe, numărul de dale conținute nu este prim. Primul container cu dale negre situat pe fiecare linie a matricei (dacă un astfel de container există) are un senzor special. Dalele din containere trebuie să fie transportate de către macara spre un terminal. Macaraua poate executa cel mult <code>K</code> comenzi. La o comandă, macaraua va colecta toate dalele aflate în containerele situate într-o zonă dreptunghiulară din depozit. Mai exact, o comandă are forma <code>i1 j1 i2 j2</code>, unde <code>(i1, j1)</code> reprezintă coordonatele containerului aflat în colțul din stânga-sus (linia, respectiv coloana), iar <code>(i2, j2)</code> coordonatele containerului aflat în colțul din dreapta-jos ale zonei dreptunghiulare. Macaraua ar trebui să care la un terminal toate dalele conținute în containere situate în pozițiile <code>(i, j)</code> pentru care <code>i1 ≤ i ≤ i2</code> şi <code>j1 ≤ j ≤ j2</code>. Însă, macaraua are un defect de funcționare. Pentru fiecare comandă, atunci când ajunge la un container cu dale negre, dacă acest container nu are senzor special nu va transporta la terminal dalele conținute de acesta. După executarea unei comenzi, un robot va umple din nou containerele golite cu acelaşi număr de dale pe care le avea inițial, aceste dale având exact aceeaşi culoare cu cea inițială.

= Cerința =
Calculați și afișați:

a) <code>S</code> – Suma dalelor negre din containerele cu senzor special de pe fiecare linie.

b) <code>M</code> – numărul maxim de dale pe care le poate transporta macaraua la terminal din cele <code>k</code> comenzi diferite.

c) Comanda optimă de forma: <code>i1 j1 i2 j2</code> din cele <code>k</code>, pentru care macaraua transportă un număr maxim de dale <code>M</code> aduse la terminal. Dacă sunt mai multe comenzi optime afișați-le pe fiecare în ordinea apariției lor, urmate de numărul de ordine al comenzii din cele <code>k</code> comenzi date.

= Date de intrare =
Din fișierul de intrare <code>macara.in</code> se citesc pe prima linie <code>m</code> și <code>n</code> reprezentând dimensiunile matricei. Se citesc apoi elementele matricei ce reprezintă numărul de dale din fiecare container. Citim apoi pe o linie separată numărul <code>k</code> iar pe următoarele <code>k</code> linii câte o comandă cu cele patru poziții : <code>i1 j1 i2 j2</code>

= Date de ieșire =
a) Pe prima linie a fișierului <code>macara.out</code> se afișează numărul <code>S</code> conform cerinței a).

b) Pe a doua linie numărul <code>M</code> conform cerinței b).

c) Pe următoarea linie/linii, comanda/comenzile optime de forma: <code>i1 j1 i2 j2</code> urmate de numărul de ordine conform cerinței c).

= Restricții și precizări =

* <code>1 ≤ i1 ≤ i2 ≤ m, 1 ≤ j1 ≤ j2 ≤ n, 1 ≤ m ≤ 1000, 1 ≤ n ≤ 1000, 1 ≤ k ≤ 1000</code>
* numărul de dale aflate într-un container <code>≤ 5000</code>
* comenzile nu sunt unice, orice comandă se poate repeta
* se asigură <code>20%</code> din punctaj pentru rezolvarea corectă a cerinței a)
* pentru <code>30%</code> din teste <code>1 ≤ n ≤ 250, 1 ≤ m ≤ 250, 1 ≤ k ≤ 250</code>

= Exemplu: =
<code>macara.in</code>
5 6
6 2 5 7 12 13
3 9 15 11 4 3
18 7 9 3 31 9
15 5 5 13 4 6
8 6 11 10 23 7
5
1 2 4 4
2 1 3 5
2 2 4 5
2 1 3 5
1 3 5 5
<code>macara.out</code>
28
65
2 1 3 5 2
2 1 3 5 4
1 3 5 5 5

=== Explicație ===
a) Calculăm de pe fiecare linie suma dalelor din primul container cu dale negre astfel: <code>2+3+7+5+11=28</code>

b) Maximul obținut din suma dalelor care ajung la terminal este <code>65</code>

c) Acest maxim este obținut din trei comenzi : primele două sunt identice pe pozițiile <code>2</code> și <code>4</code>:

<code>2 1 3 5 2</code> și <code>2 1 3 5 4</code> cu suma <code>3 + 9 + 15 + 4 + 18 + 7 + 9 = 65</code>

<code>1 3 5 5 5</code> – cu suma <code>12 + 15 + 4 + 9 + 4 + 11 + 10 = 65</code> și este comanda de pe poziția <code>5</code> din <code>k = 5</code> comenzi inițiale date.

Numerele subliniate reprezintă dale negre care aparțin containerelor care nu pot ajunge la terminal

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import numpy as np

NMax = 5005
Nk = 1001
a = np.zeros((Nk, Nk))
ti1 = np.zeros(Nk)
ti2 = np.zeros(Nk)
tj1 = np.zeros(Nk)
tj2 = np.zeros(Nk)
Poz = np.zeros(Nk)
i1 = 0
i2 = 0
j1 = 0
j2 = 0
n = 0
t = 0
m = 0
k = 0
nr = 0
sp = 0
b = np.zeros((Nk, Nk))
w = np.zeros(NMax)
ok = False

def sieve_of_eratosthenes():
for i in range(2, NMax):
if w[i] == 0:
for j in range(i*i, NMax, i):
w[j] = 1
w[1] = 1

def main():
with open("macara.in", "r") as f, open("macara.out", "w") as g:
m, n = map(int, f.readline().split())
sieve_of_eratosthenes()

for i in range(1, m+1):
s = 0
ok = True
for j in range(1, n+1):
a[i][j] = int(f.readline())
if ok and w[a[i][j]] == 0:
ok = False
sp += a[i][j]
s += a[i][j]
b[i][j] = s
if w[a[i][j]] == 1:
s += a[i][j]
b[i][j] = s
else:
b[i][j] = s

k = int(f.readline())

maxx = 0
for t in range(1, k+1):
i1, j1, i2, j2 = map(int, f.readline().split())
s = 0
for i in range(i1, i2+1):
s += b[i][j2] - b[i][j1-1]
if s > maxx:
maxx = s
nr = 1
ti1[nr] = i1
tj1[nr] = j1
ti2[nr] = i2
tj2[nr] = j2
Poz[nr] = t
elif s == maxx:
nr += 1
ti1[nr] = i1
tj1[nr] = j1
ti2[nr] = i2
tj2[nr] = j2
Poz[nr] = t

g.write(str(sp) + "\n")
g.write(str(maxx) + "\n")
for i in range(1, nr+1):
g.write(f"{ti1[i]} {tj1[i]} {ti2[i]} {tj2[i]} {Poz[i]}\n")

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

3434 - Furnica 1

2024-02-18T17:06:52Z

Raul: Pagină nouă: Cercetătorii au descoperit că activitatea miriapodelor este stimulată de culoarea galben și de aceea o furnică este supusă unui experiment. Pe marginea mesei pe care se realizează experimentul s-au lipit una lângă alta, <code>N</code> foi dreptunghiulare, de culoare galbenă, numerotate în ordine, de la stânga la dreapta, de la <code>1</code> la <code>N</code>. Furnica se află pe masă, în fața primei foi și urmează un traseu deplasându-se doar pe laturile li...

Cercetătorii au descoperit că activitatea miriapodelor este stimulată de culoarea galben și de aceea o furnică este supusă unui experiment. Pe marginea mesei pe care se realizează experimentul s-au lipit una lângă alta, <code>N</code> foi dreptunghiulare, de culoare galbenă, numerotate în ordine, de la stânga la dreapta, de la <code>1</code> la <code>N</code>. Furnica se află pe masă, în fața primei foi și urmează un traseu deplasându-se doar pe laturile libere ale foilor (care nu sunt lipite de alte foi sau de masă), pe verticală sau orizontală, (așa cum indică săgețile din imaginea de mai jos), ajungând din nou pe masă. Știind că în urcare furnica parcurge un centimetru în <code>5</code> secunde, în coborâre parcurge un centimetru în <code>2</code> secunde, iar dacă se deplasează pe orizontală parcurge un centimetru în <code>3</code> secunde, ajutați-i pe cercetători să obțină unele date.

= Cerințe =
Scrieţi un program care să rezolve următoarele cerințe:

# determină timpul (exprimat în secunde) necesar furnicii pentru a parcurge tot traseul menționat;
# determină lungimea maximă (exprimată în centimetri) a unei porțiuni de traseu în care furnica NU coboară deloc;
# determină ce număr de ordine are foaia pe care se află furnica după <code>T</code> secunde.

= Date de intrare =
Fișierul de intrare <code>furnica.in</code> conţine:

* pe prima linie un număr natural <code>C</code> care reprezintă numărul cerinţei şi poate avea valorile <code>1</code>, <code>2</code> sau <code>3</code>.
* pe cea de-a doua linie un număr natural <code>N</code> ce reprezintă numărul foilor galbene dacă cerința este <code>1</code> sau <code>2</code>, respectiv două numere naturale <code>N</code> și <code>T</code>, dacă cerința este <code>3</code>.
* pe următoarele <code>N</code> linii, câte două numere naturale, ce reprezintă laturile foilor (exprimate în centimetri), în ordinea numerotării acestora. Primul număr reprezintă dimensiunea laturii orizontale, iar cel de-al doilea număr reprezintă dimensiunea laturii verticale a foii galbene.
* numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

= Date de ieșire =
Fișierul de ieșire <code>furnica.out</code> va conține o singură linie pe care va fi scris un număr natural ce reprezintă rezultatul determinat pentru cerința <code>C</code>.

= Restricții și precizări =

* <code>1 ≤ N,T ≤ 10 000</code>; laturile foilor sunt numere naturale nenule cu cel mult nouă cifre fiecare;
* dacă furnica ajunge într-un punct aflat la îmbinarea a două foi, se consideră că se află pe foaia din stânga;
* pentru orice <code>T</code> furnica se va afla pe una din foi;
* în concurs, pentru fiecare cerință s-au acordat 30 de puncte. Pe site se acordă 10 puncte pentru exemple.

= Exemplul 1 =
<code>furnica.in</code>
1
5
3 9
5 9
2 6
2 13
1 4
<code>furnica.out</code>
151

= Explicații =
În primul exemplu, cerința este <code>1</code>. Sunt 5 foi galbene iar traseul parcurs de furnică este pe modelul din imaginea de mai sus. Traseul are o lungime de <code>45</code> de centimetri și furnica îl va termina în <code>151</code> de secunde.

În al doilea exemplu cerința este <code>2</code>. Cea mai lungă porțiune de traseu, în care furnica nu coboară are <code>9+3+5=17</code> cm.

În al treilea exemplu cerința este <code>3</code>. După <code>100</code> de secunde furnica se va afla pe foaia <code>4</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

f = open("furnica.intxt", "r")
g = open("furnica.outtxt", "w")
dist_coborare = 0
dist_urcare = 0
dist_oriz = 0
lungime = 0
maxi = 0
TIMP = 0

def main():
global dist_coborare, dist_urcare, dist_oriz, lungime, maxi, TIMP
H = 0
L = 0
H1 = 0
L1 = 0
n = 0
i = 0
cerinta = 0
t_oriz = 3
t_urcare = 5
t_coborare = 2
cladire = 0

cerinta, n = map(int, f.readline().split())
if cerinta == 3:
TIMP = int(f.readline())
L1, H1 = map(int, f.readline().split())
H = H1
dist_urcare = H1
dist_oriz = L1
dist_coborare = 0
lungime = H1 + L1
maxi = lungime
i = 1
TIMP = TIMP - (dist_urcare * t_urcare + dist_oriz * t_oriz)
if TIMP <= 0:
cladire = 1
for i in range(2, n + 1):
L, H = map(int, f.readline().split())
dist_oriz += L
if H >= H1: # URCARE
lungime = lungime + H - H1 + L
dist_urcare = dist_urcare + H - H1
if TIMP > 0:
TIMP = TIMP - (H - H1) * t_urcare
if TIMP <= 0:
cladire = i
else: # COBORARE
dist_coborare = dist_coborare + H1 - H
lungime = L
if TIMP > 0:
TIMP = TIMP - (H1 - H) * t_coborare
if TIMP <= 0:
cladire = i - 1
if TIMP > 0:
TIMP = TIMP - L * t_oriz
if TIMP <= 0:
cladire = i
if lungime > maxi:
maxi = lungime
H1 = H
L1 = L
if TIMP > 0:
if TIMP - H * t_coborare <= 0:
cladire = n
else:
cladire = -1

if cerinta == 1:
g.write(str(dist_oriz * t_oriz + dist_urcare * t_urcare + (dist_coborare + H) * t_coborare) + '\n')
elif cerinta == 2:
g.write(str(maxi) + '\n')
elif cerinta == 3:
g.write(str(cladire) + '\n')

f.close()
g.close()

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

1967 - CMMDC 0

2024-02-17T17:49:05Z

Raul: Pagină nouă: = Cerința = Andreea a primit de ziua ei un joc cu cifre de plastic, din fiecare cifră nenulă având <code>30</code> de exemplare. Cifrele se aflau într-un săculeţ, iar Andreea s-a gândit să scoată la întâmplare un număr oarecare de cifre din săculeţ, să efectueze produsul lor, şi dacă obţinea un număr mai mic decât <code>1.000.000.001</code> pe care nu-l mai obţinu-se până atunci, îl scria pe un cartonaş, punând apoi cifrele înapoi în săculeţ....

= Cerința =
Andreea a primit de ziua ei un joc cu cifre de plastic, din fiecare cifră nenulă având <code>30</code> de exemplare. Cifrele se aflau într-un săculeţ, iar Andreea s-a gândit să scoată la întâmplare un număr oarecare de cifre din săculeţ, să efectueze produsul lor, şi dacă obţinea un număr mai mic decât <code>1.000.000.001</code> pe care nu-l mai obţinu-se până atunci, îl scria pe un cartonaş, punând apoi cifrele înapoi în săculeţ. Astfel, după o muncă asiduă, a scris toate numerele posibile pe cartonaşe. Prietena ei, Ana, făcându-i o vizită, a văzut cartonaşele, a luat la întâmplare unul dintre ele şi a calculat cel mai mare divizor comun al numărului de pe cartonaşul luat cu fiecare număr de pe cartonaşele rămase, scriind pe fiecare dintre cartonaşele rămase rezultatul obţinut. Dacă se cunosc numerele aflate pe <code>N</code> cartonaşe dintre cele scrise de Andreea şi Ana, aflaţi numărul de pe cartonaşul luat de Ana.

= Date de intrare =
Fişierul de intrare <code>cmmdc0.in</code> conţine pe prima linie numărul <code>N</code> de cartonaşe care se dau, iar pe fiecare din următoarele <code>N</code> linii câte o pereche de numere naturale <code>x,d</code> reprezentând numărul scris de Andreea pe cartonaş, respectiv cel mai mare divizor comun calculat de Ana.

= Date de ieșire =
Fişierul de ieşire <code>cmmdc0.out</code> va conţine numărul de pe cartonaşul luat de Ana. Dacă există mai multe numere care verifică datele de intrare, se va afişa cel mai mic dintre ele.

= Restricții și precizări =

* <code>1 ≤ N ≤ 5.000</code>
* <code>1 ≤ d ≤ x ≤ 1.000.000.000</code>
* Valorile lui <code>x</code> de pe cartonaşe sunt distincte
* Pentru orice test există soluţie

= Exemplu: =
<code>cmmdc0.in</code>
3
8 2
45 3
14 2
<code>cmmdc0.out</code>
6

=== Explicație ===
Numărul de pe cartonaşul luat de Ana este <code>6</code>. El verifică relaţiile <code>c.m.m.d.c.(8,6)=2</code> , <code>c.m.m.d.c.(45,6)=3</code> , <code>c.m.m.d.c.(14,6)=2</code>, şi este singurul dintre numerele scrise de Andreea pe cartonaşe care verifică relaţiile cerute.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

n = 0
i = 0
ok = 0
m = 0
i2 = 0
i3 = 0
i5 = 0
i7 = 0
x = 0
y = 0
r = 0
minim = 0
a = [0]*6000
b = [0]*6000
d = [0]*6000

with open("cmmdc0.in", "r") as f:
n = int(f.readline())
for i in range(1, n+1):
line = f.readline().split()
a[i] = int(line[0])
d[i] = int(line[1])

def main():
ok = 1
b[1] = 1
m = 1
i2 = 1
i3 = 1
i5 = 1
i7 = 1

while ok:
ok = 0
for i in range(1, n+1):
x = a[i]
y = b[m]
r = x % y
while r != 0:
x = y
y = r
r = x % y
if y != d[i]:
ok = 1
break

if ok:
minim = b[i2] * 2
if b[i3] * 3 < minim:
minim = b[i3] * 3
if b[i5] * 5 < minim:
minim = b[i5] * 5
if b[i7] * 7 < minim:
minim = b[i7] * 7
m += 1
b[m] = minim
if b[i2] * 2 == minim:
i2 += 1
if b[i3] * 3 == minim:
i3 += 1
if b[i5] * 5 == minim:
i5 += 1
if b[i7] * 7 == minim:
i7 += 1

with open("cmmdc0.out", "w") as g:
g.write(str(b[m]))

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

1823 - P Prim

2024-02-17T17:45:52Z

Raul: Pagină nouă: = Cerința = Un număr natural nenul se numeste <code>“p-prim”</code> dacă el se descompune în <code>p</code> moduri ca produs de doi factori primi între ei. De exemplu, numărul <code>60</code> este <code>4</code>-prim deoarece <code>60</code> se decompune în <code>4</code> moduri ca produs de doi factori primi între ei <code>60=1*60=4*15=5*12=20*3</code>, iar numărul <code>7</code> este <code>1</code>-prim. Pentru un interval închis <code>[a,b]</code> să se det...

= Cerința =
Un număr natural nenul se numeste <code>“p-prim”</code> dacă el se descompune în <code>p</code> moduri ca produs de doi factori primi între ei. De exemplu, numărul <code>60</code> este <code>4</code>-prim deoarece <code>60</code> se decompune în <code>4</code> moduri ca produs de doi factori primi între ei <code>60=1*60=4*15=5*12=20*3</code>, iar numărul <code>7</code> este <code>1</code>-prim. Pentru un interval închis <code>[a,b]</code> să se determine câte numere <code>p</code>-prime aparţin intervalului. De exemplu intervalul <code>[7, 20]</code> conţine numerele <code>2</code>-prime: <code>10,12, 14,18,20</code>.

= Date de intrare =
Din fişierul de intrare <code>pprim.in</code> se citesc de pe prima linie două numere naturale <code>N</code> şi <code>P</code> şi de pe urmatoarele <code>N</code> linii câte două numere ce reprezintă capetele unui interval.

= Date de ieșire =
În fişierul de ieşire <code>pprim.out</code> se va scrie pe prima linie intervalul cu cele mai multe numere <code>p</code>-prime. Extremitatile intervalului se vor afisa in ordine crecatoare. Dacă există mai multe intervale cu același număr se va afișa ultimul interval citit. Dacă <code>NU</code> există niciun interval se va afișa mesajul <code>nu exista</code>.

= Restricții și precizări =

* <code>3 ≤ N ≤ 1000</code>
* <code>1 ≤ P ≤ 1000</code>
* <code>1 ≤ a[i],b[i] ≤ 33000</code>, unde <code>a[i]</code> şi <code>b[i]</code> sunt capetele intervalelor, <code>i=1,2,..N</code>

= Exemplu: =
<code>pprim.in</code>
4 2
20 7
5 10
35 39
3 4
<code>pprim.out</code>
7 20

=== Explicație ===

* Intervalul <code>[7, 20]</code> conţine numerele <code>2</code>-prime: <code>10,12,14,15,18,20</code>;
* intervalul <code>[5, 10]</code> conţine numerele <code>2</code>-prim <code>2</code>, <code>6</code> si <code>10</code>;
* intervalul <code>[35, 39]</code> conţine numere <code>2</code>-prime <code>35, 36, 38, 39</code>;
* intervalul <code>[3, 4]</code> nu conţine niciun număr <code>2</code>-prim.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

a = 0
v = 0
i = 0
n = 0
p = 0
b = 0
a1 = 0
b1 = 0
x = 0
y = 0
nr = 0
j = 0
k = 0
l = 0
r = 0
nr1 = 0
aux = 0

def main():
max_val = 0
with open("pprim.in", "r") as f:
with open("pprim.out", "w") as g:
n, p = map(int, f.readline().split())
max_val = 0
for i in range(1, n+1):
a, b = map(int, f.readline().split())
if a > b:
aux = a
a = b
b = aux
nr1 = 0
for j in range(a, b+1):
nr = 0
for k in range(1, j//2):
if j % k == 0:
x = k
y = j // k
if x < y:
while y:
r = x % y
x = y
y = r
if x == 1:
nr += 1
if nr == p:
nr1 += 1
if nr1 >= max_val:
max_val = nr1
a1 = a
b1 = b
if max_val == 0:
g.write("nu exista")
else:
g.write(str(a1) + " " + str(b1))

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

1483 - Coronite

2024-02-17T17:43:29Z

Raul: Pagină nouă: În vederea premierii la un concurs de informatică <code>N</code> candidați sunt rugați să se așeze pe un cerc. Elevii sunt identificați în ordine prin numerele de la <code>1</code> la <code>N</code>. Comisia pleacă din dreptul primului elev, face <code>x1</code> pași pe cerc și pune coronița elevului respectiv. Mai departe, comisia merge în continuare pe cerc <code>x2</code> pași și pune o a doua coroniță elevului curent. Daca elevul cur...

În vederea premierii la un concurs de informatică <code>N</code> candidați sunt rugați să se așeze pe un cerc. Elevii sunt identificați în ordine prin numerele de la <code>1</code> la <code>N</code>. Comisia pleacă din dreptul primului elev, face <code>x1</code> pași pe cerc și pune coronița elevului respectiv. Mai departe, comisia merge în continuare pe cerc <code>x2</code> pași și pune o a doua coroniță elevului curent. Daca elevul curent are deja o coroniță atunci se numără și acea poziție și trece mai departe. După <code>N</code> astfel de acțiuni premierea se încheie. Premierea se consideră a fi validă dacă toți candidații au primit câte o coroniță.

= Cerința =
Aflați dacă premierea a fost validă și de asemenea, aflați a câta coroniță a fost pusă elevului cu numărul <code>1</code>.

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

* Pe prima linie numărul <code>N</code> de elevi.
* Pe a doua linie, <code>N</code> valori <code>x1</code>, <code>x2</code>, … , <code>xN</code> numere naturale nenule, reprezentând, în ordine, numărul de pași pe cerc pe care îl efectuează comisia pentru premierea următorului elev.

= Date de ieșire =
Fișierul de ieșire <code>coronite.out</code> va conține:

* Pe prima linie se va scrie numărul <code>1</code> dacă premierea a fost validă sau <code>0</code> în caz contrar -Pe a doua linie o valoare <code>NR</code> reprezentând a câta coroniță i-a fost acordată elevului cu numărul de concurs <code>1</code>. Dacă elevul <code>1</code> nu a fost premiat valoarea lui <code>NR</code> va fi <code>0</code>.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100</code>
* <code>1 ≤ xi ≤ 2*N</code>
* Dacă primul copil primește mai multe coronițe, se va afișa numărul de ordine al primei coronițe primite de el.

= Exemplul 1 =
<code>coronite.in</code>
6
3 1 9 4 1 2
<code>coronite.out</code>
1
5

=== Explicație ===
Se pun coronite, in ordine, elevilor: <code>4</code>, <code>5</code>, <code>2</code>, <code>6</code>, <code>1</code>, <code>3</code>. Toți elevii au coronițe. Elevului <code>1</code> i se pune a <code>5</code>-a coroniță.

= Exemplul 2 =
<code>coronite.in</code>
4
1 3 4 1
<code>coronite.out</code>
0
2

=== Explicație ===
Se pun coronițe elevilor: <code>2</code>, <code>1</code>. Elevul <code>1</code> primește a <code>2</code>-a coroniță.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python">
with open("coronite.in", "r") as fin, open("coronite.out", "w") as fout:
x = [0] * 101
sel = [0] * 101
n = 0

def main():
n = int(fin.readline())
for i in range(1, n+1):
x[i] = int(fin.readline())

for i in range(1, n+1):
for j in range(1, x[i]+1):
poz += 1
if poz > n:
poz = 1
if poz == 1 and sel[1] == 0:
nr = i
sel[poz] = 1

ok = 1
for i in range(1, n+1):
if sel[i] == 0:
ok = 0

if ok:
fout.write("1\n")
else:
fout.write("0\n")

fout.write(str(nr) + "\n")

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

1784 - Flori 3

2024-02-17T17:38:26Z

Raul: Pagină nouă: = Cerința = După o amorţeală care durase mai bine de 3 luni, Mama Natură îşi dădu seama că primăvara stătea să vină şi florile cu care trebuia curând să umple câmpiile nu erau încă pregătite. Înainte de începerea iernii, a lucrat să combine nuanţe din care să creeze flori pline de culoare, iar acum are camera plină de discuri de diferite culori, care aşteaptă să fie asamblate în flori viu colorate, fie pe post de mijloc, fie ca şi petale. Pen...

= Cerința =
După o amorţeală care durase mai bine de 3 luni, Mama Natură îşi dădu seama că primăvara stătea să vină şi florile cu care trebuia curând să umple câmpiile nu erau încă pregătite. Înainte de începerea iernii, a lucrat să combine nuanţe din care să creeze flori pline de culoare, iar acum are camera plină de discuri de diferite culori, care aşteaptă să fie asamblate în flori viu colorate, fie pe post de mijloc, fie ca şi petale.

Pentru a forma o floare, Mama Natură alege un mijloc de orice culoare şi cel puţin <code>K</code> petale. Totodată, ea nu îşi doreşte să strice ordinea firească a lucrurilor şi de aceea nu va folosi niciodată două culori diferite de petale pentru aceeaşi floare. Ea admite, în schimb, flori cu petalele și mijlocul de aceeași culoare.

Deoarece timpul e scurt şi Mama Natură are lucruri mai importante de făcut decât să stea să asambleze flori, ea îşi cheamă în ajutor toate prietenele şi doreşte să îi dea fiecăreia ceva de lucru. Pentru aceasta, ea are la dispoziţie un şir <code>D</code> de <code>N</code> numere, unde numărul de pe poziţia <code>i</code> din șir reprezintă câte discuri de culoarea <code>i</code> a pregătit. Apoi, Mama Natură îşi pune <code>M</code> întrebări de forma <code>x y</code>, prin care doreşte să afle care este numărul maxim de flori care se pot forma folosind doar discuri de culori din intervalul <code>[x, y]</code> din şirul <code>D</code>.

= Date de intrare =
Fișierul de intrare <code>flori3.in</code> conține pe prima linie două numere naturale, <code>N</code> şi <code>K</code>, separate prin spaţiu, cu semnificaţia din enunţ. Pe următoarea linie se vor afla <code>N</code> numere naturale (elementele șirului <code>D</code>). Următoarea linie a fişierului va conţine numărul <code>M</code> şi va fi urmată de <code>M</code> linii conţinând perechi de numere întregi <code>x</code> și <code>y</code>, cu semnificaţia din enunţ.

= Date de ieșire =
Fișierul de ieșire <code>flori3.out</code> va conține, pe rânduri separate, <code>M</code> numere naturale, reprezentând răspunsul la fiecare dintre cele <code>M</code> întrebări.

= Restricții și precizări =

* <code>1 ≤ N ≤ 105</code>
* <code>1 ≤ D[i] ≤ 109</code>, <code>Ɐ i = 1,..,N</code>
* <code>1 ≤ M ≤ 105</code>
* <code>1 ≤ K ≤ 1000</code>
* <code>1 ≤ x ≤ y ≤ N</code>

= Exemplu: =
<code>flori3.in</code>
4 4
4 2 1 10
2
1 3
1 4
<code>flori3.out</code>
1
3

=== Explicație ===
Pentru prima întrebare, Mama Natură poate alege o singură floare, cu petale de culoarea <code>1</code> și mijloc de culoarea <code>2</code> sau <code>3</code>.

Pentru a doua întrebare, putem forma 3 flori:

* <code>3 4 4 4 4</code>
* <code>2 4 4 4 4 4 4</code>
* <code>2 1 1 1 1</code>

O alternativă: pentru a doua floare folosim mai puţine petale, rămânând in final două flori nefolosite de culoare <code>4</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import numpy as np

def main():
nmax = 1000006
SP = np.zeros(nmax, dtype=np.int64)
CP = np.zeros(nmax, dtype=np.int64)
sol = 0

with open("flori3.in", "r") as f:
n, k = map(int, f.readline().split())
for i in range(1, n + 1):
x = int(f.readline())
assert 1 <= x <= 1000000000
SP[i] = SP[i - 1] + x // k
CP[i] = CP[i - 1] + x % k
m = int(f.readline())
assert 1 <= n <= 100000
assert 1 <= m <= 100000
assert 1 <= k <= 1000
for _ in range(m):
x, y = map(int, f.readline().split())
S = SP[y]
C = CP[y]
if x - 1 >= 0:
S -= SP[x - 1]
C -= CP[x - 1]
if S <= C:
sol = S
else:
x = (S - C) // (k + 1)
sol = min(S - x, C + k * x)
x += 1
sol = max(sol, min(S - x, C + k * x))

with open("flori3.out", "w") as g:
g.write(f"{sol}\n")

if __name__ == '__main__':
main()

</syntaxhighlight>

1755 - Democratie

2024-02-17T17:34:28Z

Raul: Pagină nouă: Arpsod are în curtea sa <code>N</code> copaci foarte bătrâni, așezați în linie și numerotați de la <code>1</code> la <code>N</code>. Fiecare copac are o înălțime cunoscută, <code>Hi</code>. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni. Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea <code>1, 2, 3, ... ,N</code> iar cel de-al doilea în ordi...

Arpsod are în curtea sa <code>N</code> copaci foarte bătrâni, așezați în linie și numerotați de la <code>1</code> la <code>N</code>. Fiecare copac are o înălțime cunoscută, <code>Hi</code>. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni.

Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea <code>1, 2, 3, ... ,N</code> iar cel de-al doilea în ordinea <code>N, N-1, N-2, ... 1</code>.

Fiind un tărâm democratic, fiecare muncitor dorește să fie plătit pentru fiecare metru pe care îl taie. Muncitorul <code>1</code> are un tarif de <code>T1</code> pe metru iar muncitorul <code>2</code> un tarif de <code>T2</code> pe metru. Dacă un muncitor a început să taie un copac, acesta îl va tăia integral. Din motive de protecție a muncii, muncitorilor nu le este permis să lucreze simultan. De aici apare următoarea pretenție: dacă după tăierea unui copac, muncitorul nu este înlocuit de colegul său, acesta va cere un cost suplimentar <code>C</code> pentru a rămâne să taie în continuare.

De exemplu, dacă avem <code>3</code> copaci: <code>1, 2, 3</code> și muncitorul <code>1</code> taie singur toți copacii, acesta va cere un cost suplimentar de <code>2</code> ori (pentru copacul <code>2</code> și copacul <code>3</code>).

= Cerința =
Arpsod vă cere să determinați costul minim pe care îl poate plăti astfel încât toți cei <code>N</code> copaci să fie tăiați.

= Date de intrare =
Pe prima linie a fișierului <code>democratie.in</code> se va afla numărul natural <code>N</code>, reprezentând numărul de copaci.

Pe cea de-a doua linie vor exista <code>N</code> numere naturale nenule reprezentând înălțimile celor <code>N</code> copaci.

Pe cea de-a treia linie se vor afla două numere naturale <code>T1</code> și <code>T2</code> reprezentând tariful pe metru al muncitorului <code>1</code> respectiv al muncitorului <code>2</code>.

Pe ultima linie se vor afla două numere naturale <code>C1</code> și <code>C2</code> reprezentând costul suplimentar cerut de muncitorul <code>1</code> respectiv muncitorul <code>2</code>.

= Date de ieșire =
În fișierul <code>democratie.out</code> se va scrie, pe prima și singura linie din fișier, costul minim pe care Arpsod trebuie să-l plătească.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ T1, T2 ≤ 100</code>
* <code>1 ≤ C1, C2 ≤ 10.000</code>
* <code>1 ≤ Hi ≤ 100</code>
* Se garantează că pentru <code>20%</code> din teste <code>1 ≤ N ≤ 10</code>
* Costul suplimentar este același indiferent de înălțimea copacului ce va fi tăiat.
* Este posibil ca un muncitor să taie singur toți copacii.
* Un muncitor va tăia complet un copac.
* Cam scumpă democrația asta!

= Exemplu: =
<code>democratie.in</code>
4
1 2 3 4
7 2
3 9
<code>democratie.out</code>
34

=== Explicație ===
Ordinea muncitorilor:

<code>M2 -> M1 -> M2 -> M2</code>

Costul: <code>(2*4) + (7*1) + (2*3) + (2*2 + 9)</code>

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

Nmax = 100002
inf = 2000000000

N, T1, T2, C1, C2 = 0, 0, 0, 0, 0
v = [0] * Nmax
Sol = inf
config = [0] * Nmax

def bkt(poz):
global N, T1, T2, C1, C2, Sol, v, config

if poz > N:
st, dr = 1, N
Total = 0

for i in range(1, N + 1):
if config[i] == 1:
Total += v[st] * T1
st += 1

if config[i - 1] == config[i]:
Total += C1
else:
Total += v[dr] * T2
dr -= 1

if config[i - 1] == config[i]:
Total += C2

Sol = min(Sol, Total)
return

for i in range(1, 3):
config[poz] = i
bkt(poz + 1)

def main():
global N, T1, T2, C1, C2, Sol, v, config

lines = sys.stdin.readlines()
N = int(lines[0])

v = list(map(int, lines[1].split()))

T1, T2, C1, C2 = map(int, lines[2].split())

bkt(1)

print(Sol)

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

1618 - Cifre 12

2024-02-16T17:05:46Z

Raul: Pagină nouă: Un indicator numeric este un dispozitiv de afişaj electronic destinat afişării unei cifre zecimale. Acesta conține <code>7</code> segmente notate cu <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code>, <code>e</code>, <code>f</code>, <code>g</code>, ca în figura de mai jos. Afişarea unei cifre se face prin aprinderea unei combinații de segmente conform tabelului: {| class="wikitable" !Cifră !0 !1 !2 !3 !4 !5 !6 !7 !8 !9 |- |Segmente aprinse |a,b,c,d,e,f...

Un indicator numeric este un dispozitiv de afişaj electronic destinat afişării unei cifre zecimale.

Acesta conține <code>7</code> segmente notate cu <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code>, <code>e</code>, <code>f</code>, <code>g</code>, ca în figura de mai jos.

Afişarea unei cifre se face prin aprinderea unei combinații de segmente conform tabelului:
{| class="wikitable"
!Cifră
!0
!1
!2
!3
!4
!5
!6
!7
!8
!9
|-
|Segmente aprinse
|a,b,c,d,e,f
|b,c
|a,b,d,e,g
|a,b,c,d,g
|b,c,f,g
|a,c,d,f,g
|a,c,d,e,f,g
|a,b,c
|a,b,c,d,e,f,g
|a,b,c,d,f,g
|}

= Cerința =
Cunoscând un număr natural <code>N</code> afișat cu ajutorul mai multor indicatoare numerice, să se scrie un program care determină:

# Numărul de segmente aprinse pentru afișarea numărului <code>N</code>.
# Numărul de numere distincte mai mari decât <code>N</code>,ce se pot forma prin aprinderea a cel puțin unui segment în plus, față de cele utilizate pentru afișarea numărului <code>N</code>, fără a folosi alte indicatoare numerice, și fără a stinge niciun segment dintre cele deja aprinse.

= Date de intrare =
Fișierul de intrare <code>cifre12.in</code> conține pe prima linie numărul natural <code>V</code> a cărui valoare poate fi doar <code>1</code> sau <code>2</code>, iar pe a doua linie numărul natural <code>N</code>.

= Date de ieșire =
Fișierul de ieșire este <code>cifre12.out</code>.

Dacă valoarea lui <code>V</code> este <code>1</code> atunci fişierul de ieşire va conţine pe prima linie un singur număr natural ce reprezintă numărul de segmente aprinse pentru afișarea numărului <code>N</code>.

Dacă valoarea lui <code>V</code> este <code>2</code> atunci fişierul de ieşire va conține pe prima linie un singur număr natural reprezentând numărul de numere distincte mai mari decât <code>N</code>, ce se pot forma prin aprinderea a cel puțin unui segment în plus, față de cele utilizate pentru afișarea numărului <code>N</code>, fără a folosi alte indicatoare numerice.

= Restricții și precizări =

* <code>10 ≤ N ≤ 1019</code>
* 20% din teste vor avea valoarea <code>V = 1</code>, iar 80% din teste vor avea valoarea <code>V = 2</code>.

= Exemplul 1 =
<code>cifre12.in</code>
1
823
<code>cifre12.out</code>
17

=== Explicație ===
<code>V = 1</code>, deci se rezolvă NUMAI prima cerință. <code>N = 823</code>;

Pentru afișarea cifrei <code>8</code> s-au aprins <code>7</code> segmente, pentru cifra <code>2</code> s-au aprins <code>5</code> segmente și pentru cifra <code>3</code> tot <code>5</code> segmente. În total s-au aprins <code>17</code> segmente.

= Exemplul 2 =
<code>cifre12.in</code>
2
823
<code>cifre12.out</code>
5

=== Explicație ===
<code>V = 2</code>, deci se rezolvă NUMAI a doua cerință. <code>N = 823</code>;

Din cifra <code>8</code> nu se mai pot obține alte cifre prin aprinderea de noi segmente.

Din cifra <code>2</code> se poate obține cifra <code>8</code> iar din cifra <code>3</code> se pot obține cifrele <code>8</code> și <code>9</code> prin aprinderea de noi segmente. Așadar, se pot obține <code>5</code> numere mai mari ca <code>823</code>: <code>828</code>, <code>829</code>, <code>883</code>, <code>888</code>, <code>889</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
# Technology stack: C++
import sys

def main():
n = 0
N = 0
S = 0
P = 0

# cate segmente are fiecare cifra
s = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# cate cifre strict mai mari se pot obtine din cifra curenta prin adaugare
a = [1, 5, 1, 2, 2, 3, 1, 2, 0, 0]

# cate cifre se pot obtine din cifra curenta prin adaugare, inclusiv cifra curenta
b = [2, 7, 2, 3, 3, 4, 2, 5, 1, 2]

c = 0
k = 0
i = 0
j = 0
w = [25]
aux = 0
v = 0

f = open("cifre12.in")
g = open("cifre12.out", "w")

v, n = map(int, f.readline().split())

if v == 1:
N = n
S = 0
while N > 0:
c = N % 10
S += s[c]
N //= 10
g.write(str(S) + "\n")

if v == 2:
# duc cifrele intr-un vector
N = n
k = 0
while N > 0:
w[k] = N % 10
k += 1
N //= 10

# reversez vectorul
i = 0
j = k - 1
while i < j:
aux = w[i]
w[i] = w[j]
w[j] = aux
i += 1
j -= 1

S = 0
i = 0
while i < k:
if a[w[i]]:
P = a[w[i]]
j = i + 1
while j < k:
P *= b[w[j]]
j += 1
S += P
i += 1
g.write(str(S) + "\n")

f.close()
g.close()

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

1143 - Dominant

2024-02-16T17:03:25Z

Raul: Pagină nouă: Considerând un șir de valori binare, numim secvență dominantă un set de elemente aflate pe poziții consecutive în șir care are proprietatea că numărul valorilor egale cu <code>1</code> este strict mai mare decât numărul valorilor de <code>0</code>. De exemplu, în șirul <code>1,0,0,0,1,1,0,1,1,1,0,0</code> o secvență dominantă este <code>0,1,1</code> și o alta, de lungime mai mare, este <code>0,1,1,0,1,1,1</code>. Secvența dominantă maximală este secvența...

Considerând un șir de valori binare, numim secvență dominantă un set de elemente aflate pe poziții consecutive în șir care are proprietatea că numărul valorilor egale cu <code>1</code> este strict mai mare decât numărul valorilor de <code>0</code>. De exemplu, în șirul <code>1,0,0,0,1,1,0,1,1,1,0,0</code> o secvență dominantă este <code>0,1,1</code> și o alta, de lungime mai mare, este <code>0,1,1,0,1,1,1</code>. Secvența dominantă maximală este secvența dominantă de lungime maximă. În șirul din exemplu secvența dominantă maximală este <code>1,0,0,0,1,1,0,1,1,1,0</code> (adică întreg șirul, fără ultimul zero).

= Cerinţă =
Dat fiind un șir de valori binare, să se determine lungimea unei secvențe dominante maximale precum și numărul acestor secvențe.

= Date de intrare =
Fișierul de intrare <code>dominant.in</code> conține pe prima linie un număr natural <code>V</code>, iar pe linia a doua șirul de valori binare, fără spații.

= Date de ieșire =
Fișierul de ieșire <code>dominant.out</code> va conține:

* varianta 1: dacă <code>V=1</code>, atunci pe prima linie a fișierului de ieșire va fi un singur număr natural reprezentând lungimea unei secvențe dominante maximale.
* varianta 2: dacă <code>V=2</code>, atunci pe prima linie a fișierului de ieșire va fi un singur număr natural reprezentând numărul secvențelor dominante maximale.

= Restricții și precizări =

* <code>V</code> poate fi <code>1</code> sau <code>2</code>
* Lungimea șirului de valori binare este de cel mult <code>300 000</code>.
* Pentru toate testele șirul binar va conține cel puțin o valoare de <code>1</code>.
* Pentru 60% din punctaj <code>V = 1</code>.

= Exemplul 1 =
<code>dominant.in</code>
1
100011011100
<code>dominant.out</code>
11

= Explicație =
Secvența dominantă maximală este <code>10001101110</code> și are lungimea <code>11</code>.

= Exemplul 2 =
<code>dominant.in</code>
2
100011011100
<code>dominant.out</code>
1

= Explicație =
Secvența dominantă maximală este <code>10001101110</code> și are lungimea <code>11</code>. Este o singură secvență dominantă maximală.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

Nmax = 300005
inFile = "dominant.intxt"
outFile = "dominant.outtxt"

s = [''] * Nmax
x = [0] * (2*Nmax)
y = [0] * (2*Nmax)
st = None
dr = None
optiune = 0

def main():
global s, optiune, st, dr
i = 0
n = 0
suma = 0
vmin = 0
vmax = 0
lgMax = 0

# citire
fin = open(inFile, 'r')
fout = open(outFile, 'w')
optiune = int(fin.readline())
s = '*' + fin.readline().strip()

s[0] = '*'
n = len(s[1:])

suma = 0
for i in range(1, n+1):
if s[i] == '1':
suma += 1
else:
suma -= 1
if suma > 0:
if optiune == 1:
fout.write(str(n) + "\n")
else:
fout.write("1\n")
fout.close()
return 0

st = x[Nmax:]
dr = y[Nmax:]

# initializare st si dr
for i in range(-n, n+1):
st[i] = 10000000
dr[i] = -10000000

# calcul st si dr
# st[i] = cea mai din stanga pozitie unde apare valoarea i
# dr[i] = cea mai din dreapta pozitie unde apare valoarea i
st[0] = dr[0] = 0
suma = 0
vmin = 10000000
vmax = -10000000
for i in range(1, n+1):
if s[i] == '0':
suma -= 1
else:
suma += 1
st[suma] = min(st[suma], i)
dr[suma] = max(dr[suma], i)
vmin = min(vmin, suma)
vmax = max(vmax, suma)

# lungimea maxima a secventei
lgMax = 0
for i in range(vmin, vmax):
lgMax = max(lgMax, dr[i+1] - st[i])

# numarul de aparitii ale secventei maximale
s0 = 0
s1 = 0
suma = 0
for i in range(1, lgMax+1):
if s[i] == '0':
s0 += 1
else:
s1 += 1
if s1 > s0:
suma += 1
for i in range(lgMax+1, n):
if s[i-lgMax] == '0':
s0 -= 1
else:
s1 -= 1
if s[i] == '0':
s0 += 1
else:
s1 += 1
if s1 > s0:
suma += 1

if optiune == 1:
fout.write(str(lgMax) + "\n")
else:
fout.write(str(suma) + "\n")
fout.close()
fin.close()
return 0

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

1057 - Max P

2024-02-16T17:00:42Z

Raul:

Considerăm un şir de numere <code>a1</code>, <code>a2</code>, …, <code>aN</code>. O secvenţă nevidă în acest şir este de forma <code>ai</code>, <code>ai+1</code>, …, <code>aj</code>, unde <code>i ≤ j</code>. De exemplu, pentru <code>N=4</code> şi şirul <code>2 3 4 3</code>, secvenţele nevide sunt: <code>2</code>, <code>2 3</code>, <code>2 3 4</code>, <code>2 3 4 3</code>, <code>3</code>, <code>3 4</code>, <code>3 4 3</code>, <code>4</code>, <code>4 3</code>, <code>3</code>. Definim puterea unui element <code>ai</code> ca fiind numărul de secvenţe care-l conţin pe <code>ai</code> şi în care <code>ai</code> este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul <code>2 3 4 3</code> puterea elementului <code>a1</code> este <code>1</code> (fiind maxim doar în secvenţa formată din el însuşi), a elementului <code>a2</code> este <code>2</code> (<code>a2</code> fiind maxim în secvenţele <code>2 3</code> şi <code>3</code>), a elementului <code>a3</code> este <code>6</code> (fiind maxim în secvenţele <code>2 3 4</code>, <code>2 3 4 3</code>, <code>3 4</code>, <code>3 4 3</code>, <code>4</code> şi <code>4 3</code>), iar a elementului <code>a4</code> este <code>1</code>.

= Cerinţe =
Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul de elemente din şir care au cea mai mare putere.

= Date de intrare =
Fișierul de intrare <code>maxp.in</code> conține pe prima linie numărul natural <code>N</code>, iar pe a doua linie, în ordine, numerele naturale <code>a1</code>, <code>a2</code>, …, <code>aN</code> separate prin câte un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>maxp.out</code> va conține pe prima linie un număr natural ce reprezintă puterea cea mai mare a unui element din şirul dat şi pe a doua linie va conţine un număr natural ce reprezintă numărul de elemente din şir care au cea mai mare putere.

= Restricții și precizări =

* <code>2 <= N <= 200.000</code>
* Elementele şirului sunt numere naturale şi au cel mult <code>6</code> cifre

= Exemplul 1 =
<code>maxp.in</code>
7
9 3 4 5 1 2 2
<code>maxp.out</code>
12
1

= Explicație =
Elementul <code>5</code> de pe poziţia <code>4</code> este maxim în <code>12</code> secvenţe:

<code>3 4 5</code>, <code>3 4 5 1</code>, <code>3 4 5 1 2</code>, <code>3 4 5 1 2 2</code>, <code>4 5</code>,

<code>4 5 1</code>, <code>4 5 1 2</code>, <code>4 5 1 2 2</code>, <code>5</code>, <code>5 1</code>, <code>5 1 2</code>,

<code>5 1 2 2</code>, deci puterea lui este <code>12</code>. Este singurul element care are această putere, celelalte elemente având puteri mai mici.

= Exemplul 2 =
<code>maxp.in</code>
6
1 0 7 7 2 6
<code>maxp.out</code>
3
2

= Explicație =
Elementele din poziţiile <code>3</code> şi <code>4</code> sunt maxime în <code>3</code> secvenţe, deci puterea lor este <code>3</code>. Celelalte elemente au puteri mai mici.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python2">
import sys

inFile = "maxp.intxt"
outFile = "maxp.outtxt"
dim = 200001

a = [0] * dim
st = [0] * dim
dr = [0] * dim
q = [0] * dim
poz = [0] * dim
n = 0

def main():
global n
i, k, x, nrsol, p, pmax = 0, 0, 0, 0, 0, 0

#citire
with open(inFile, 'r') as fin:
n = int(fin.readline())
for i in range(1, n+1):
a[i] = int(fin.readline())

# constructie st
k = 0
q[k] = dim + 2
poz[k] = 0
st[k] = 0
for i in range(1, n+1):
x = a[i]
while q[k] < x:
k -= 1
st[i] = i - poz[k] - 1
k += 1
q[k] = x
poz[k] = i

# constructie dr
k = 0
q[k] = dim + 2
poz[k] = n + 1
dr[k] = 0
for i in range(n, 0, -1):
x = a[i]
while q[k] < x:
k -= 1
dr[i] = poz[k] - i - 1
k += 1
q[k] = x
poz[k] = i

# calcul
nrsol = 1
pmax = (st[1] + 1)
pmax *= (dr[1] + 1)
for i in range(2, n+1):
p = (st[i] + 1)
p = (p * (dr[i] + 1))
if p > pmax:
pmax = p
nrsol = 1
elif p == pmax:
nrsol += 1

with open(outFile, 'w') as fout:
fout.write(str(pmax) + "\n" + str(nrsol) + "\n")

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

1057 - Max P

2024-02-16T16:59:34Z

Raul: Pagină nouă: Considerăm un şir de numere <code>a1</code>, <code>a2</code>, …, <code>aN</code>. O secvenţă nevidă în acest şir este de forma <code>ai</code>, <code>ai+1</code>, …, <code>aj</code>, unde <code>i ≤ j</code>. De exemplu, pentru <code>N=4</code> şi şirul <code>2 3 4 3</code>, secvenţele nevide sunt: <code>2</code>, <code>2 3</code>, <code>2 3 4</code>, <code>2 3 4 3</code>, <code>3</code>, <code>...

Considerăm un şir de numere <code>a1</code>, <code>a2</code>, …, <code>aN</code>. O secvenţă nevidă în acest şir este de forma <code>ai</code>, <code>ai+1</code>, …, <code>aj</code>, unde <code>i ≤ j</code>. De exemplu, pentru <code>N=4</code> şi şirul <code>2 3 4 3</code>, secvenţele nevide sunt: <code>2</code>, <code>2 3</code>, <code>2 3 4</code>, <code>2 3 4 3</code>, <code>3</code>, <code>3 4</code>, <code>3 4 3</code>, <code>4</code>, <code>4 3</code>, <code>3</code>. Definim puterea unui element <code>ai</code> ca fiind numărul de secvenţe care-l conţin pe <code>ai</code> şi în care <code>ai</code> este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul <code>2 3 4 3</code> puterea elementului <code>a1</code> este <code>1</code> (fiind maxim doar în secvenţa formată din el însuşi), a elementului <code>a2</code> este <code>2</code> (<code>a2</code> fiind maxim în secvenţele <code>2 3</code> şi <code>3</code>), a elementului <code>a3</code> este <code>6</code> (fiind maxim în secvenţele <code>2 3 4</code>, <code>2 3 4 3</code>, <code>3 4</code>, <code>3 4 3</code>, <code>4</code> şi <code>4 3</code>), iar a elementului <code>a4</code> este <code>1</code>.

= Cerinţe =
Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul de elemente din şir care au cea mai mare putere.

= Date de intrare =
Fișierul de intrare <code>maxp.in</code> conține pe prima linie numărul natural <code>N</code>, iar pe a doua linie, în ordine, numerele naturale <code>a1</code>, <code>a2</code>, …, <code>aN</code> separate prin câte un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>maxp.out</code> va conține pe prima linie un număr natural ce reprezintă puterea cea mai mare a unui element din şirul dat şi pe a doua linie va conţine un număr natural ce reprezintă numărul de elemente din şir care au cea mai mare putere.

= Restricții și precizări =

* <code>2 <= N <= 200.000</code>
* Elementele şirului sunt numere naturale şi au cel mult <code>6</code> cifre

= Exemplul 1 =
<code>maxp.in</code>
7
9 3 4 5 1 2 2
<code>maxp.out</code>
12
1

= Explicație =
Elementul <code>5</code> de pe poziţia <code>4</code> este maxim în <code>12</code> secvenţe:

<code>3 4 5</code>, <code>3 4 5 1</code>, <code>3 4 5 1 2</code>, <code>3 4 5 1 2 2</code>, <code>4 5</code>,

<code>4 5 1</code>, <code>4 5 1 2</code>, <code>4 5 1 2 2</code>, <code>5</code>, <code>5 1</code>, <code>5 1 2</code>,

<code>5 1 2 2</code>, deci puterea lui este <code>12</code>. Este singurul element care are această putere, celelalte elemente având puteri mai mici.

= Exemplul 2 =
<code>maxp.in</code>
6
1 0 7 7 2 6
<code>maxp.out</code>
3
2

= Explicație =
Elementele din poziţiile <code>3</code> şi <code>4</code> sunt maxime în <code>3</code> secvenţe, deci puterea lor este <code>3</code>. Celelalte elemente au puteri mai mici.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python">
import sys

inFile = "maxp.intxt"
outFile = "maxp.outtxt"
dim = 200001

a = [0] * dim
st = [0] * dim
dr = [0] * dim
q = [0] * dim
poz = [0] * dim
n = 0

def main():
global n
i, k, x, nrsol, p, pmax = 0, 0, 0, 0, 0, 0

#citire
with open(inFile, 'r') as fin:
n = int(fin.readline())
for i in range(1, n+1):
a[i] = int(fin.readline())

# constructie st
k = 0
q[k] = dim + 2
poz[k] = 0
st[k] = 0
for i in range(1, n+1):
x = a[i]
while q[k] < x:
k -= 1
st[i] = i - poz[k] - 1
k += 1
q[k] = x
poz[k] = i

# constructie dr
k = 0
q[k] = dim + 2
poz[k] = n + 1
dr[k] = 0
for i in range(n, 0, -1):
x = a[i]
while q[k] < x:
k -= 1
dr[i] = poz[k] - i - 1
k += 1
q[k] = x
poz[k] = i

# calcul
nrsol = 1
pmax = (st[1] + 1)
pmax *= (dr[1] + 1)
for i in range(2, n+1):
p = (st[i] + 1)
p = (p * (dr[i] + 1))
if p > pmax:
pmax = p
nrsol = 1
elif p == pmax:
nrsol += 1

with open(outFile, 'w') as fout:
fout.write(str(pmax) + "\n" + str(nrsol) + "\n")

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

1055 - Compar

2024-02-16T16:55:27Z

Raul: Pagină nouă: Ana şi Bogdan au inventat jocul ''“Compar”''. Ana scrie pe tablă o secvenţă formată din <code>N</code> numere naturale distincte cuprinse între <code>1</code> şi <code>N</code>, apoi compară fiecare două numere învecinate din secvenţă scriind între ele semnul <code><</code> sau semnul <code>></code>, după caz. De exemplu, dacă secvenţa de pe tablă este <code>6 4 2 1 3 5</code>, după compararea elementelor învecinate şi inserarea semnelor în secvenţ...

Ana şi Bogdan au inventat jocul ''“Compar”''. Ana scrie pe tablă o secvenţă formată din <code>N</code> numere naturale distincte cuprinse între <code>1</code> şi <code>N</code>, apoi compară fiecare două numere învecinate din secvenţă scriind între ele semnul <code><</code> sau semnul <code>></code>, după caz.

De exemplu, dacă secvenţa de pe tablă este <code>6 4 2 1 3 5</code>, după compararea elementelor învecinate şi inserarea semnelor în secvenţă, Ana obţine:

<code>6>4>2>1<3<5</code>

După aceea Ana şterge cele <code>N</code> elemente ale secvenţei şi păstrează numai semnele, astfel:

<code>>>><<</code>

La final, Ana îi arată lui Bogdan şirul semnelor şi îi cere să reconstituie secvenţa de numere naturale scrisă iniţial pe tablă.

= Cerinţă =
Cunoscând şirul semnelor construit de Ana, scrieţi un program care să îl ajute pe Bogdan să reconstituie secvenţa de numere naturale distincte scrisă iniţial pe tablă.

= Date de intrare =
Fișierul de intrare <code>compar.in</code> conține pe prima linie o secvenţă de caractere din mulţimea <code>{'<', '>'}</code>, reprezentând şirul semnelor obţinut de Ana după compararea elementelor vecine din secvenţa iniţială.

= Date de ieșire =
Fișierul de ieșire <code>compar.out</code> va conține pe prima linie numărul natural <code>N</code>, reprezentând lungimea secvenţei iniţiale. Pe a doua linie vor fi scrise <code>N</code> numere naturale distincte cuprinse între <code>1</code> şi <code>N</code>, separate prin câte un spaţiu, reprezentând elementele secvenţei iniţiale, reconstituită pe baza semnelor din fişierul de intrare.

= Restricții și precizări =

* <code>1 < N ≤ 100000</code>
* Dacă există mai multe soluţii, afişaţi oricare dintre acestea.
* Pentru determinarea corectă a lungimii secvenţei se acordă 10% din punctajul pe test.
*

= Exemplu: =
<code>compar.in</code>
>>><<
<code>compar.out</code>
6
6 4 2 1 3

= Explicație =
<code>6>4>2>1<3<5</code>

Există şi alte soluţii posibile, aceasta este doar una dintre ele.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import os

s = ['' for i in range(100000)]

def main():
fin = open("compar.intxt", "r")
fout = open("compar.outtxt", "w")

s = fin.readline().strip()
N = len(s) + 1
fout.write(str(N) + "\n")
maxx = N
minn = 1
for i in range(N):
if s[i] == '<':
fout.write(str(minn) + " ")
minn += 1
else:
fout.write(str(maxx) + " ")
maxx -= 1
fout.close()

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

1048 - Schi

2024-02-15T10:34:59Z

Raul: Pagină nouă: La proba de sărituri cu schiurile din cadrul jocurilor olimpice de iarnă participă <code>N</code> concurenți, numerotați cu numere de la <code>1</code> la <code>N</code>. Regulile de desfășurare a probei sunt următoarele: * concurenții evoluează pe rând, în ordine de la <code>1</code> la <code>N</code>; * fiecare concurent va efectua o singură săritură; * după efectuarea săriturii fiecare concurent primește un anumit punctaj; * pe tot parcursul concursului...

La proba de sărituri cu schiurile din cadrul jocurilor olimpice de iarnă participă <code>N</code> concurenți, numerotați cu numere de la <code>1</code> la <code>N</code>.

Regulile de desfășurare a probei sunt următoarele:

* concurenții evoluează pe rând, în ordine de la <code>1</code> la <code>N</code>;
* fiecare concurent va efectua o singură săritură;
* după efectuarea săriturii fiecare concurent primește un anumit punctaj;
* pe tot parcursul concursului, comisia de arbitri are obligația să alcătuiască o listă cu punctajele obținute de concurenți, în ordinea evoluției lor;
* evoluția unui concurent durează exact un minut;
* nu se face pauză între evoluțiile a doi concurenți care au numere de ordine consecutive;
* afișarea punctajului nu necesită timp suplimentar după efectuarea săriturii;
* proba se încheie la un minut după evoluția ultimului concurent.

Pe tot parcursul concursului se ține în mod neoficial și un clasament parțial, pe baza rezultatelor obținute de concurenții care au evoluat până în acel moment. Asta pentru că șeful comisiei de arbitri are o curiozitate aparte și pune <code>K</code> întrebări sub forma următoare: ''Câte minute s-a ocupat primul loc din clasament cu un punctaj egal cu <code>X</code> puncte?'' Dacă nici un concurent nu s-a clasat pe primul loc cu <code>X</code> puncte atunci primește ca răspuns valoarea <code>0</code>.

= Cerința =
Scrieți un program care determină răspunsul pentru fiecare dintre cele <code>K</code> întrebări puse de șeful comisiei de arbitri.

= Date de intrare =
Fișierul de intrare <code>schi.in</code> conține pe prima linie un număr natural, <code>N</code> reprezentând numărul de concurenți. Pe a doua linie a fișierului sunt scrise cele <code>N</code> numere naturale separate prin câte un spațiu, reprezentând punctajele obținute de fiecare dintre cei <code>N</code> concurenți, în ordinea în care aceștia au evoluat. Pe a treia linie a fișierului este scris numărul natural <code>K</code> ce reprezintă numărul de întrebări puse de șef. Pe a patra linie a fișierului sunt scrise <code>K</code> numere naturale separate prin câte un spațiu, reprezentând valorile <code>X</code> ale punctajelor alese de șeful comisiei de arbitri.

= Date de ieșire =
Fișierul de ieșire <code>schi.out</code> va conține pe prima linie <code>K</code> numere, separate prin câte un spațiu, reprezentând, în ordine, răspunsurile la cele <code>K</code> întrebări.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100 000</code>
* <code>1 ≤ K ≤ 100 000</code>
* <code>0 ≤</code> punctajele obținute de concurenți <code>≤ 1 000 000 000</code>
* <code>0 ≤</code> valorile <code>X</code> alese de șeful arbitrilor <code>≤ 1 000 000 000</code>

= Exemplu: =
<code>schi.in</code>
10
1 6 5 3 6 8 8 6 1 9
6
5 1 6 8 2 9
<code>schi.out</code>
0 1 4 4 0 1

= Explicație =
Cu punctajul <code>5</code> nu s-a ocupat niciodată locul <code>1</code>, cu punctajul <code>1</code> s-a ocupat primul loc un singur minut, cu punctajele <code>6</code> și <code>8</code> s-a ocupat locul <code>1</code> câte <code>4</code> minute. Cu punctajul <code>2</code> nu s-a ocupat locul <code>1</code>. El nici nu a fost obținut de vreun concurent. Cu punctajul <code>9</code> s-a ocupat locul <code>1</code> un minut.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

DIM = 100010
v = [0] * DIM
n = 0
i = 0
T = 0
st = 0
dr = 0
x = 0
q = 0
maxim = 0

def cautMinim(x):
p = 1
u = n
mid = 0
while p <= u:
mid = (p + u) // 2
if x <= v[mid]:
u = mid - 1
else:
p = mid + 1
if v[p] == x:
return p
else:
return -1

def cautMaxim(x):
p = 1
u = n
mid = 0
while p <= u:
mid = (p + u) // 2
if x >= v[mid]:
p = mid + 1
else:
u = mid - 1
if v[u] == x:
return u
else:
return -1

if __name__ == "__main__":
fin = open("schi.intxt", "r")
fout = open("schi.outtxt", "w")
n = int(fin.readline())
maxim = -1
for i in range(1, n+1):
x = int(fin.readline())
if x > maxim:
maxim = x
v[i] = maxim
q = int(fin.readline())
for i in range(1, q+1):
x = int(fin.readline())
st = cautMinim(x)
if st == -1:
fout.write("0 ")
else:
dr = cautMaxim(x)
fout.write(str(dr - st + 1) + " ")

fin.close()
fout.close()
</syntaxhighlight>

1071 - OZN

2024-02-15T10:28:59Z

Raul: Pagină nouă: O invazie de <code>N</code> farfurii zburătoare (denumite uzual OZN) dă bătăi de cap autorităţilor. În fiecare astfel de OZN se află extratereştri care au ca misiune distrugerea planetei noastre. Radarul care a detectat invazia are un ecran similar cu planul <code>XOY</code>. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă. Pentru anihilarea OZN-urilor, autorităţile dispun de <code>K</code> arme laser. Armele sunt poziţionate pe sol (ilustrat...

O invazie de <code>N</code> farfurii zburătoare (denumite uzual OZN) dă bătăi de cap autorităţilor. În fiecare astfel de OZN se află extratereştri care au ca misiune distrugerea planetei noastre. Radarul care a detectat invazia are un ecran similar cu planul <code>XOY</code>. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă.

Pentru anihilarea OZN-urilor, autorităţile dispun de <code>K</code> arme laser. Armele sunt poziţionate pe sol (ilustrat pe ecranul radarului prin axa <code>OX</code>). Fiecare armă emite o rază laser, ilustrată pe ecran printr-o paralelă cu axa <code>OY</code>. Dacă o rază laser intersectează segmentul de pe ecranul radarului corespunzător unui OZN, raza va omorî toţi extratereştrii aflaţi în OZN-ul respectiv.

Din păcate, în preajmă se află doar un militar specializat în arme laser, aşa că autorităţile doresc să ştie exact ce armă trebuie să folosească acesta pentru a distruge cât mai mulţi extratereştri.

= Cerinţă =
Ajutaţi autorităţile să determine numărul de extratereştri care pot fi anihilaţi cu fiecare armă din dotare.

= Date de intrare =
Fișierul de intrare <code>ozn.in</code> conține pe prima linie două numere naturale separate prin spaţiu <code>N K</code> reprezentând numărul de OZN-uri şi respectiv numărul de arme laser. Pe următoarele <code>N</code> linii sunt descrise cele N OZN-uri, câte unul pe linie. Un OZN este descris prin <code>5</code> numere naturale separate prin câte un spaţiu <code>x1 y1 x2 y2 nr</code>, reprezentând în ordine coordonatele capetelor segmentului corespunzător <code>(x1, y1)</code>, <code>(x2, y2)</code>, iar <code>nr</code> – numărul de extratereştri din el. Pe ultima linie se găsesc <code>K</code> numere naturale <code>a1</code> <code>a2</code> <code>a3</code> … <code>aK</code>, separate prin câte un spaţiu, reprezentând coordonatele pe axa <code>OX</code> (abscisele) unde sunt amplasate armele laser.

= Date de ieșire =
Fișierul de ieșire <code>ozn.out</code> va conține <code>K</code> linii. Pe linia <code>i</code> va fi scris numărul total de extratereştri care pot fi distruşi cu arma <code>i</code>, considerând armele numerotate în ordinea în care acestea apar în fişierul de intrare.

= Restricții și precizări =

* <code>1 ≤ N ≤ 20 000</code>
* <code>1 ≤ K ≤ 20 000</code>
* <code>1 ≤</code> orice coordonată din fişierul de intrare <code>≤ 2 000 000</code>
* <code>1 ≤ nr ≤ 100</code>, pentru orice OZN
* <code>x1 < x2</code>, pentru orice OZN
* Pe ecranul radarului segmentele ce descriu navele se pot intersecta.
* Dacă raza laser trece prin unul dintre capetele unui OZN atunci acesta este distrus.
* Pentru 50% dintre testele de intrare <code>1 ≤ N*K ≤ 10 000 000</code>

= Exemplu: =
<code>ozn.in</code>
5 3
1 1 3 2 2
2 3 4 1 3
6 5 8 5 8
5 1 7 1 6
6 2 7 4 1
3 7 5
<code>ozn.out</code>
5
15
6
Explicație

Arma care emite din punctul <code>(3,0)</code> doboară farfuriile reprezentate de segmentele <code>{(1,1)(3,2)}</code> şi <code>{(2,3)(4,1)}</code> distrugând în total <code>5</code> extratereştri.

Arma care emite din punctul <code>(7,0)</code> doboară farfuriile reprezentate de segmentele <code>{(5,1)(7,1)}, {(6,2)(7,4)}</code> şi <code>{(6,5)(8,5)}</code> distrugând în total <code>15</code> extratereştri.

Arma care emite din punctul <code>(5,0)</code> doboară farfuria reprezentată de segmentul <code>{(5,1)(7,1)}</code> şi distruge <code>6</code> extratereştri.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

MAXX = 2000010
MAXN = 100010

f = open("ozn.in", "r")
g = open("ozn.out", "w")

A = [0] * MAXX
N, K = map(int, f.readline().split())
X1, Y1, X2, Y2, nr, i = 0, 0, 0, 0, 0, 0

for i in range(1, N + 1):
X1, Y1, X2, Y2, nr = map(int, f.readline().split())
A[X1] += nr
A[X2 + 1] -= nr

for i in range(1, MAXX):
A[i] += A[i - 1]

for i in range(1, K + 1):
X1 = int(f.readline())
g.write(str(A[X1]) + '\n')

g.close()
f.close()
</syntaxhighlight>

1070 - Deal

2024-02-15T10:26:21Z

Raul: Pagină nouă: Vasilică are la grădiniţă <code>N</code> turnuri cu înălţimile <code>h1</code>, <code>h2</code>, …, <code>hN</code>. Când aşază în linie nişte turnuri, cel puţin două, astfel încât înălţimile lor să fie în ordine crescătoare, Vasilică spune că a construit un ''deal''. Înălţimea dealului este egală cu înălţimea celui mai înalt turn folosit. Iată, de exemplu, că aşezând în ordine turnurile cu înălţimile...

Vasilică are la grădiniţă <code>N</code> turnuri cu înălţimile <code>h1</code>, <code>h2</code>, …, <code>hN</code>. Când aşază în linie nişte turnuri, cel puţin două, astfel încât înălţimile lor să fie în ordine crescătoare, Vasilică spune că a construit un ''deal''. Înălţimea dealului este egală cu înălţimea celui mai înalt turn folosit. Iată, de exemplu, că aşezând în ordine turnurile cu înălţimile <code>2 4 4 7 9</code> a format un deal cu înălţimea <code>9</code>.

Vasilică şi-ar dori să aşeze în linie cele <code>N</code> turnuri, formând o succesiune de dealuri astfel încât suma înălţimilor dealurilor formate să fie maximă.

= Cerinţă =
Scrieţi un program care, cunoscând înălţimile celor <code>N</code> turnuri, va determina suma înălţimilor dealurilor ce se pot forma aşezând în linie cele <code>N</code> turnuri, maximă posibil.

= Date de intrare =
Fișierul de intrare <code>deal.in</code> conține pe prima linie numărul natural <code>N</code>. Pe cea de a doua linie se află <code>N</code> numere naturale separate prin spaţii, reprezentând înălţimile celor <code>N</code> turnuri.

= Date de ieșire =
Fișierul de ieșire <code>deal.out</code> va conține o singură linie pe care va fi scris un număr natural reprezentând cerinţa problemei.

= Restricții și precizări =

* <code>2 ≤ N ≤ 100 000</code>
* <code>1 ≤</code> Înălţimile turnurilor <code>≤ 100 000</code>
* Dacă după aranjarea turnurilor <code>hi ≤ hi+1</code> atunci turnurile <code>i</code> şi <code>i+1</code> fac parte din acelaşi deal.

= Exemplu: =
<code>deal.in</code>
7
10 2 2 2 7 5 2
<code>deal.out</code>
22

= Explicație =
O soluţie posibilă cu suma înălţimilor <code>22</code> ar fi: <code>2 10 2 5 2 2 7</code>

S-au format trei dealuri: <code>2 10</code> (cu înălţimea <code>10</code>) şi <code>2 5</code> (cu înălţimea <code>5</code>) şi <code>2 2 7</code> cu înălțimea <code>7</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import numpy as np

nmax = 100001

def main():
with open("deal.intxt", 'r') as f, open("deal.outtxt", 'w') as g:
n = int(f.readline())
w = np.zeros(nmax)
v = np.zeros(nmax)
i = 1
x = 0
st = 0
dr = 0
pdp = 0
s = 0

for i in range(1, nmax):
w[i] = 0

for i in range(1, n+1):
x = int(f.readline())
w[x] += 1

for i in range(1, n+1):
v[i] = w[i]

st = 1
dr = nmax - 1

while w[st] == 0:
st += 1

while w[dr] == 0:
dr -= 1

while st != dr:
if w[st] == 0:
st += 1
else:
if w[dr] == 0:
dr -= 1
else:
s += dr
w[st] -= 1
w[dr] -= 1

pdp = (n - w[dr]) // 2 + 1 - (v[dr] - w[dr])

if w[dr] // 2 <= pdp:
s += dr * (w[dr] // 2)
else:
s += dr * pdp

g.write(str(s))
</syntaxhighlight>

1034 - Roata

2024-02-15T10:22:38Z

Raul: Pagină nouă: Una dintre atracţiile celebrului parc de distracţii Prater din Viena este Marea Roată Vieneză. Din ea se poate admira priveliştea întregii Viene. Roata are <code>n</code> cabine, numerotate de la <code>1</code> la <code>n</code> în sens orar şi dispuse simetric pe circumferinţa roţii. Îmbarcarea clienţilor se face în cabina în care roata este tangentă cu solul, iar rotirea începe cu cabina <code>1</code> aflată în poziţia de îmbarcare şi se face în sens...

Una dintre atracţiile celebrului parc de distracţii Prater din Viena este Marea Roată Vieneză. Din ea se poate admira priveliştea întregii Viene.

Roata are <code>n</code> cabine, numerotate de la <code>1</code> la <code>n</code> în sens orar şi dispuse simetric pe circumferinţa roţii. Îmbarcarea clienţilor se face în cabina în care roata este tangentă cu solul, iar rotirea începe cu cabina <code>1</code> aflată în poziţia de îmbarcare şi se face în sens antiorar. Un client plăteşte pentru o rotire <code>1 EUR</code> şi poate cumpăra un număr oarecare de rotiri.

Cei <code>p</code> clienţi care doresc utilizarea roţii trebuie să respecte următoarea procedură: clientul cu numărul de ordine <code>i</code> îşi cumpără un bilet pe care sunt înscrise numărul său de ordine şi numărul de rotiri <code>ci</code>, <code>1≤ i ≤ p</code>, apoi se aşează la rând. Când în poziţia de îmbarcare este o cabină liberă sau se eliberează o cabină, roata se opreşte şi urcă următorul clientul. Un client coboară după ce se efectuează numărul de rotiri înscris pe bilet.

= Cerinţa =
Să se scrie un program care, cunoscând numărul <code>n</code> de cabine al roţii, numărul <code>p</code> de clienţi, precum şi numărul de rotiri cumpărate de fiecare client, <code>ci</code>, <code>1≤ i ≤ p</code>, să calculeze:

* suma totală încasată de administratorul roţii de la clienţi;
* ordinea în care coboară clienţii din roată;
* numărul cabinei din care coboară ultimul client.

= Date de intrare =
Fișierul de intrare <code>roata.in</code> conține pe prima linie numărul natural <code>n</code>, pe al doilea rând numărul natural <code>p</code> iar pe al treilea rând numerele naturale <code>ci</code>, <code>1 ≤ i ≤ p</code>, separate printr-un spaţiu, cu semnificaţiile de mai sus.

= Date de ieșire =
Fișierul de ieșire <code>roata.out</code> va conține pe prima linie suma totală încasată, pe a doua linie numerele de ordine ale clienţilor, în ordinea coborârii, separate printr-un spaţiu, iar pe a treia linie numărul cabinei din care va coborî ultimul client.

= Restricții și precizări =

* <code>2 ≤ n ≤ 360</code>
* <code>1 ≤ p ≤ 100 000</code>
* <code>1 ≤ ci ≤ 100 000</code>

= Exemplu: =
<code>roata.in</code>
4
7
6 4 1 5 2 8 3
<code>roata.out</code>
29
3 5 2 4 1 7 6
3

= Explicație =
Roata are <code>n=4</code> cabine şi numărul de clienţi este <code>p=7</code>.

Primul client cumpără <code>6</code> rotiri, al doilea <code>4</code> rotiri, … , iar al şaptelea client cumpără <code>3</code> rotiri. Suma totală încasată este de <code>29 EUR</code>.

După ce primii <code>4</code> clienţi se urcă în roată şi se efectuează o rotire completă, primul care coboară este clientul al <code>3</code>-lea şi imediat se urcă clientul al <code>5</code>-lea. După încă <code>2</code> rotiri, clientul al <code>5</code>-lea coboară şi se urcă clientul al <code>6</code>-lea. După încă o rotire coboară clientul al <code>2</code>-lea şi se urcă al <code>7</code>-lea client. Ultimii <code>4</code> clienţi coboară în ordinea <code>4,1,7,6</code>.

Cabina din care coboară ultimul client este cabina cu numărul <code>3</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

nmax = 361
pmax = 100001

f = open("roata.intxt", "r")
g = open("roata.outtxt", "w")

# n = numarul de cabine, p = numarul de persoane

def main():
# o - ordinea la urcare, c - costul biletului
n, p = map(int, f.readline().split())
o = [0] * nmax
c = [0] * pmax
s = 0

# initializez numerele de ordine ale primilor n clienti
for i in range(1, n+1):
o[i] = i

# citesc numarul de rotiri si calculez suma totala incasata
for i in range(1, p+1):
c[i] = int(f.readline())
s += c[i]

# afisez suma totala incasata
g.write(str(s) + "\n")

if n < p:
for k in range(n+1, p+1):
# determin clientul care urmeaza sa coboare
pozmin = 1
for i in range(2, n+1):
if c[i] < c[pozmin]:
pozmin = i

# afisez ordinea la coborare
g.write(str(o[pozmin]) + " ")

# resetez toate valorile lui c[i] pentru ca sunt prea mari
if c[pozmin] > 10000000:
for i in range(1, n+1):
c[i] -= 10000000

c[pozmin] += c[k] # o mica smecherie - in loc sa scad din toate minimul, am adunat
o[pozmin] = k
else:
n = p

# determin numarul cabinei din care va cobora ultimul client
pozmax = 1
for i in range(2, n+1):
if c[i] >= c[pozmax]:
pozmax = i

for k in range(1, n+1):
# determin clientul care urmeaza sa coboare
pozmin = 1
for i in range(2, n+1):
if c[i] < c[pozmin]:
pozmin = i

# afisez ordinea la coborare
g.write(str(o[pozmin]) + " ")

c[pozmin] += 100001

# afisez numarul cabinei din care va cobora ultimul client
g.write("\n" + str(pozmax) + "\n")

f.close()
g.close()
return 0

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

1065 - Vase 1

2024-02-15T10:18:20Z

Raul: Pagină nouă: Specialiştii chimişti au reuşit crearea în laborator a unei game diversificate de substanţe lichide nemiscibile (care nu se amestecă între ele), de aceeaşi densitate şi de culori diferite. Acest rezultat a fost utilizat de către specialiştii fizicieni pentru studiul principiului vaselor comunicante. Conform acestui principiu „într-un sistem de vase comunicante nivelul lichidului este acelaşi, indiferent de forma vaselor.“ Experimentele fizicienilor se desf...

Specialiştii chimişti au reuşit crearea în laborator a unei game diversificate de substanţe lichide nemiscibile (care nu se amestecă între ele), de aceeaşi densitate şi de culori diferite.

Acest rezultat a fost utilizat de către specialiştii fizicieni pentru studiul principiului vaselor comunicante. Conform acestui principiu „într-un sistem de vase comunicante nivelul lichidului este acelaşi, indiferent de forma vaselor.“

Experimentele fizicienilor se desfăşoară astfel:

Într-un sistem cu '''două''' vase comunicante, gradat identic pe fiecare ramură cu <code>0</code>, <code>1</code>, <code>2</code>, <code>3</code>,…, fizicienii introduc un număr de <code>n</code> lichide, pe ramura din stânga sau pe ramura din dreapta. Volumele introduse din fiecare lichid, notate cu <code>Vi</code> (<code>1≤i≤n</code>), sunt numere naturale nenule pare astfel încât, la echilibru, orice lichid se va aşeza între două gradaţii de aceeaşi parte a unei ramuri sau pe cele două ramuri ale sistemului de vase comunicante. Lichidele sunt identificate prin intermediul culorii acestora, culori numerotate cu <code>1</code>, <code>2</code>, <code>3</code>, … , <code>n</code>. Introducerea lichidelor în sistemul cu două vase comunicante se face în ordinea crescătoare a numerelor culorilor, începând cu lichidul de culoare <code>1</code>.

Scopul experimentului este de a determina gradaţia maximă la care se ridică lichidele în sistemul cu două vase comunicante, precum şi între ce gradaţii se găseşte un lichid de culoare <code>x</code>, dintre cele introduse.

De exemplu, dacă în sistemul cu două vase comunicante se introduc <code>n=3</code> lichide în ordinea: <code>V1=4</code> lichid de culoare <code>1</code> introdus prin ramura din dreapta (operaţie codificată <code>4 D</code>), <code>V2=4</code> lichid de culoare <code>2</code> introdus prin ramura din stânga (operaţie codificată <code>4 S</code>) şi <code>V3=2</code> lichid de culoare <code>3</code> introdus prin ramura din stânga (operaţie codificată <code>2 S</code>) atunci gradaţia maximă la care se ridică nivelul lichidelor în sistemul cu două vase comunicante este <code>5</code>, iar lichidul de culoare <code>x=2</code> se găseşte între gradaţiile: <code>3</code> pe ramura din stânga (<code>3 S</code>) şi <code>1</code> pe ramura din dreapta (<code>1 D</code>), conform figurii alăturate.

= Cerinţă =
Să se scrie un program care cunoscând numărul <code>n</code> de lichide introduse în sistemul cu două vase comunicante, volumul <code>Vi</code> şi ramura prin care se face introducerea lichidului de culoare <code>i</code> (<code>1≤i≤n</code>), precum şi culoarea <code>x</code>, să calculeze gradaţia maximă la care se ridică lichidele în acest sistem la echilibru şi între ce gradaţii se găseşte lichidul de culoare <code>x</code>.

= Date de intrare =
Prima linie a fişierului de intrare <code>vase1.in</code> conţine un singur număr natural nenul <code>n</code>, cu semnificaţia de mai sus. Fiecare linie, din următoarele <code>n</code>, conţine câte două valori separate printr-un spaţiu: un număr natural nenul par şi o literă mare, <code>S</code> sau <code>D</code>, reprezentând volumul introdus din lichidul de culoare <code>i</code>, respectiv ramura (<code>S</code> pentru ramura din stânga şi <code>D</code> pentru ramura din dreapta) prin care se face introducerea acestuia. Linia <code>n+2</code> a fişierului de intrare conţine un singur număr nenul <code>x</code> ce reprezintă culoarea lichidului căutat.

= Date de ieșire =
Fişierul de ieşire <code>vase1.out</code> va conţine pe prima linie un număr natural nenul ce reprezintă gradaţia maximă la care se ridică lichidele în sistemul de vase comunicante la echilibru. Următoarele două linii vor conţine fiecare câte două valori separate printr-un spaţiu: un număr natural şi o literă mare (<code>S</code> sau <code>D</code>), reprezentând gradaţia şi ramura între care se aşează lichidul căutat.

= Restricții și precizări =

* <code>1 ≤ x ≤ n ≤ 100 000</code>
* <code>2 ≤ Vi ≤ 100 000</code> pentru <code>1 ≤ i ≤ n</code>
* sistemul de vase este gradat în aceleaşi unităţi de măsură în care sunt exprimate volumele de lichid;
* dacă lichidul căutat, de culoare <code>x</code>, se aşează pe aceeaşi ramură se va afişa întâi gradaţia superioară şi apoi cea inferioară;
* dacă lichidul căutat, de culoare <code>x</code>, se aşează pe ramuri diferite se va afişa întâi gradaţia de pe ramura din stânga şi apoi cea de pe ramura din dreapta;
* dacă una dintre gradaţiile între care se situează lichidul căutat, de culoare <code>x</code>, este <code>0</code> atunci se consideră că aceasta gradaţie se găseşte pe aceeaşi ramură cu cealaltă gradaţie;
* pentru rezolvarea primei cerinţe se acordă 20% din punctaj, iar pentru a doua cerinţă 80% din punctaj.

= Exemplu: =
<code>vase1.in</code>
3
4 D
4 S
2 S
2
<code>vase1.out</code>
5
3 S
1 D

= Explicație =
Se introduc <code>3</code> lichide în sistemul de două vase comunicante:

* primul cu volumul <code>4</code>, se introduce prin dreapta şi are culoarea <code>1</code>;
* al doilea cu volumul <code>4</code>, se introduce prin stânga şi are culoarea <code>2</code>;
* al treilea cu volumul <code>2</code>, se introduce prin stânga şi are culoarea <code>3</code>;

Se caută gradaţiile ce corespund lichidului de culoare <code>2</code>.

Gradaţia maximă la care ajunge nivelul lichidului este <code>5</code>.

Lichidul de culoare <code>2</code> se aşează între gradaţiile <code>3</code> pe ramura din stânga şi <code>1</code> pe ramura din dreapta.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

nmax = 100001

class Lichid:
def __init__(self, cantitate, ramura, culoare):
self.cant = cantitate
self.ram = ramura
self.cul = culoare

st = [None] * nmax
dr = [None] * nmax
vst = 0
vdr = 0

f = open("vase1.in", "r")
g = open("vase1.out", "w")

def main():
i = 0
n = 0
x = 0
z = 0
mij = 0
l1 = 0
l2 = 0
h1 = 0
h2 = 0
gasit = 0
s = 0
l1r = ' '
l2r = ' '

n = int(f.readline())

for i in range(1, n+1):
line = f.readline().split()
x = int(line[0])
c = line[1]
s += x
if c == 'S':
vst += 1
st[vst] = Lichid(x, c, i)
elif c == 'D':
vdr += 1
dr[vdr] = Lichid(x, c, i)

z = int(f.readline())

mij = s // 2
h1 = mij
gasit = 0

while h1 > -mij and vst > 0 and not gasit:
if st[vst].cul == z:
if h1 < 0:
l1 = -h1
l1r = 'D'
else:
l1 = h1
l1r = 'S'
if h1 - st[vst].cant < 0:
l2 = -(h1 - st[vst].cant)
l2r = 'D'
else:
l2 = h1 - st[vst].cant
l2r = 'S'
gasit = 1
h1 -= st[vst].cant
vst -= 1

h2 = mij

while h2 > -mij and vdr > 0 and not gasit:
if dr[vdr].cul == z:
if h2 < 0:
l1 = -h2
l1r = 'S'
else:
l1 = h2
l1r = 'D'
if h2 - dr[vdr].cant < 0:
l2 = -(h2 - dr[vdr].cant)
l2r = 'S'
else:
l2 = h2 - dr[vdr].cant
l2r = 'D'
gasit = 1
h2 -= dr[vdr].cant
vdr -= 1

if l1 == 0:
l1r = l2r
if l2 == 0:
l2r = l1r

g.write(str(mij) + "\n")

if l1r == 'D' and l2r == 'S':
g.write(str(l2) + " " + l2r + "\n")
g.write(str(l1) + " " + l1r + "\n")
elif l1r == 'S' and l2r == 'D':
g.write(str(l1) + " " + l1r + "\n")
g.write(str(l2) + " " + l2r + "\n")
elif l1 > l2:
g.write(str(l1) + " " + l1r + "\n")
g.write(str(l2) + " " + l2r + "\n")
else:
g.write(str(l2) + " " + l2r + "\n")
g.write(str(l1) + " " + l1r + "\n")

f.close()
g.close()

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

1072 - Magic

2024-02-13T15:00:10Z

Raul: Pagină nouă: Rămaşi singuri în pădure, Hansel şi Grettel, ştiu că singura lor şansă de supravieţuire este să găsească şi să intre în Castelul de Turtă Dulce. Poarta castelului este închisă şi pentru a intra este nevoie de un cuvânt magic şi de un număr fermecat. Zâna cea Bună îi vede pe copii şi pentru că vrea să–i ajute le spune: „Mergeţi tot înainte, iar în drumul vostru o să întâlniţi copaci pe a căror trunchiuri sunt scrise caractere repreze...

Rămaşi singuri în pădure, Hansel şi Grettel, ştiu că singura lor şansă de supravieţuire este să găsească şi să intre în Castelul de Turtă Dulce. Poarta castelului este închisă şi pentru a intra este nevoie de un cuvânt magic şi de un număr fermecat.

Zâna cea Bună îi vede pe copii şi pentru că vrea să–i ajute le spune:

„Mergeţi tot înainte, iar în drumul vostru o să întâlniţi copaci pe a căror trunchiuri sunt scrise caractere reprezentând litere sau cifre. Cuvântul magic este format din toate caracterele literă în ordinea în care apar, dar scrise toate cu majuscule. Numărul fermecat este cel mai mic număr cu cifre distincte care se poate forma din caracterele cifră.”

= Cerinţe: =
Pentru a-i ajuta pe Hansel şi Grettel să intre în Castelul de Turtă Dulce, scrieţi un program care citeşte un număr natural <code>n</code>, apoi <code>n</code> caractere şi determină:

a) cuvântul magic;

b) numărul fermecat;

= Date de intrare =
un număr natural <code>n</code>, reprezentând numărul de caractere scrise pe copaci. Pe cea de a doua linie sunt <code>n</code> caractere separate prin câte un spaţiu, reprezentând caracterele scrise pe copaci.

= Date de ieșire =
Fișierul de ieșire <code>magic.out</code> va conținedouă linii:

a) pe prima linie se va scrie un şir de litere mari, reprezentând cuvântul magic;

b) pe a doua linie se va scrie un număr natural cu cifre distincte, reprezentând numărul fermecat.

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>
* Caracterele sunt doar cifre sau litere mici ale alfabetului englez.
* Printre cele n caractere se află întotdeauna cel puțin o literă şi cel puţin o cifră.
* Pe fiecare copac este scris un singur caracter.
* Numărul magic începe întotdeauna cu o cifră diferită de zero.
* Pentru rezolvarea cerinţei a) se acordă 40% din punctaj, pentru cerinţa b) 60% din punctaj

= Exemplul 1 =
<code>magic.in</code>
6
c 2 5 5 b 2
<code>magic.out</code>
CB
25

== Explicație ==
Cel mai mic număr cu cifre distincte ce se poate obţine este <code>25</code>.

= Exemplul 1 =
<code>magic.in</code>
8
c a 5 0 b 2 5 d
<code>magic.out</code>
CABD
205

== Explicație ==
Cel mai mic număr cu cifre distincte ce se poate obţine este <code>205</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import string

with open('magic.in', 'r') as f:
n = int(f.readline().strip())
s = [''] * (n + 1) # Adjusting index to start from 1
c = [0] * 10
ncifre = 0
for i in range(1, n + 1):
s[i] = f.readline().strip().upper()
if s[i].isdigit():
ncifre += 1
c[int(s[i])] += 1

with open('magic.out', 'w') as g:
for i in range(1, n + 1):
if s[i] in string.ascii_uppercase:
g.write(s[i])
g.write('\n')
i = 1
while c[i] == 0:
i += 1
if c[0]:
g.write(f"{i}0")
else:
g.write(f"{i}")
for j in range(i + 1, 10):
if c[j]:
g.write(f"{j}")

</syntaxhighlight>

1075 - Grad 1

2024-02-13T14:57:34Z

Raul: Pagină nouă: Se consideră un şir <code>x1</code>, <code>x2</code>, …, <code>xn</code> de <code>n</code> numere naturale distincte, două câte două. Pentru o secvenţă de <code>k</code> numere <code>(xp, xp+1, ..., xp+k-1)</code>, care începe cu numărul de pe poziţia <code>p</code> din şirul dat, definim gradul său ca fiind numărul de numere din secvenţă, care rămân pe aceleaşi poziţii după ordonarea cres...

Se consideră un şir <code>x1</code>, <code>x2</code>, …, <code>xn</code> de <code>n</code> numere naturale distincte, două câte două. Pentru o secvenţă de <code>k</code> numere <code>(xp, xp+1, ..., xp+k-1)</code>, care începe cu numărul de pe poziţia <code>p</code> din şirul dat, definim gradul său ca fiind numărul de numere din secvenţă, care rămân pe aceleaşi poziţii după ordonarea crescătoare a secvenţei. De exemplu, pentru <code>n=7</code> şi şirul format din numerele: <code>1, 5, 7, 4, 6, 2, 9</code>, secvenţa formată din numerele <code>7, 4, 6, 2</code> (corespunzătoare lui <code>p=3</code> şi <code>k=4</code>) are gradul egal cu <code>2</code> deoarece, după ordonarea crescătoare a numerelor din secvenţă, aceasta devine <code>2, 4, 6, 7</code>, numerele <code>4</code> şi <code>6</code> rămânând pe aceleaşi poziţii.

= Cerinţă =
Scrieţi un program care citeşte numerele <code>n</code>, <code>k</code>, <code>x1</code>, <code>x2</code>, …, <code>xn</code>, cu semnificaţia din enunţ, şi apoi determină:

a) gradul întregului şir de numere;

b) poziţia primului element din prima secvenţă de lungime <code>k</code> ce are gradul maxim, precum şi gradul acestei secvenţe.

= Date de intrare =
Fișierul de intrare <code>grad1.in</code> conține pe prima linie numerele <code>n</code> şi <code>k</code>, separate printr-un spaţiu, iar pe linia următoare <code>n</code> numere naturale distincte <code>x1</code>, <code>x2</code>, …, <code>xn</code>, corespunzătoare şirului de numere, separate prin câte un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>grad1.out</code> va conține pe prima linie un număr natural reprezentând gradul întregului şir de numere, iar pe următoarea linie două numere naturale, separate printr-un singur spaţiu, primul număr reprezentând poziţia primului element din prima secvenţă de lungime <code>k</code> ce are grad maxim şi cel de-al doilea număr reprezentând gradul acestei secvenţe.

= Restricții și precizări =

* <code>0 < n < 10001</code>
* <code>0 < k < n+1</code>
* Numerele din şir sunt numere naturale strict mai mici decât <code>32000</code>.
* O secvenţă de numere din şir reprezintă o succesiune de numere din acel şir, aflate pe poziţii consecutive.
* Gradul întregului şir de numere este egal cu gradul secvenţei de <code>n</code> numere care începe cu numărul de pe poziţia <code>1</code> şi conţine toate cele <code>n</code> numere din şir.
* Pentru rezolvarea corectă a subpunctului a) se obţine 40% din punctaj.
* Pentru rezolvarea corectă a subpunctului b) se obţine 60% din punctaj.

= Exemplu: =
<code>grad1.in</code>
7 4
1 5 7 4 6 2 9
<code>grad1.out</code>
3
3 2

= Explicație =
După ordonare, şirul <code>1 5 7 4 6 2 9</code> devine <code>1 2 4 5 6 7 9</code>, pe aceleaşi poziţii rămân <code>1</code>, <code>6</code> şi <code>9</code>, deci gradul întregului şir este <code>3</code>.

Avem patru secvenţe cu câte 4 elemente:

* <code>1 5 7 4</code>, care are gradul <code>1</code>
* <code>5 7 4 6</code>, care are gradul <code>0</code>
* <code>7 4 6 2</code>, care are primul număr pe poziţia <code>3</code> și gradul <code>2</code>.
* <code>4 6 2 9</code>, care are gradul <code>1</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
def read_input(filename):
with open(filename, 'r') as fin:
n, k = map(int, fin.readline().split())
x = [0] + [int(num) for num in fin.readline().split()]
return n, k, x

def sort_subarray(y, n):
sorted = False
while not sorted:
sorted = True
for i in range(1, n):
if y[i] > y[i + 1]:
y[i], y[i + 1] = y[i + 1], y[i]
sorted = False

def main():
n, k, x = read_input("grad1.in")
y = x.copy()
sort_subarray(y, n)
g = sum(1 for i in range(1, n + 1) if x[i] == y[i])

with open("grad1.out", 'w') as fout:
fout.write(f"{g}\n")

y = x[1:k+1]
sort_subarray(y, k)
gmax = sum(1 for i in range(1, k + 1) if x[i] == y[i])
pmax = 1

for i in range(2, n - k + 2):
j = 1
while j <= k and y[j] != x[i - 1]:
j += 1
if j <= k:
y[j] = x[i + k - 1]
while j > 1 and y[j - 1] > y[j]:
y[j], y[j - 1] = y[j - 1], y[j]
j -= 1
while j < k and y[j] > y[j + 1]:
y[j], y[j + 1] = y[j + 1], y[j]
j += 1

gr = sum(1 for j in range(1, k + 1) if y[j] == x[i + j - 1])
if gr > gmax:
gmax = gr
pmax = i

fout.write(f"{pmax} {gmax}")

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

1089 - Cladiri 1

2024-02-13T14:55:18Z

Raul: Pagină nouă: Institutul de Fizică a Pământului studiază efectele unui potenţial cutremur folosind simulări computerizate. Harta plană a clădirilor de pe un teritoriu oarecare este reprezentată folosind coordonatele GPS în plan, longitudine şi latitudine, faţă de un reper considerat de coordonate <code>(0,0)</code>, ca în figura de mai jos. Fiecare dintre clădirile aflate pe hartă, au două coordonate GPS, (Longitudine, Latitudine) şi un Grad de rezistenţă la cutremure....

Institutul de Fizică a Pământului studiază efectele unui potenţial cutremur folosind simulări computerizate. Harta plană a clădirilor de pe un teritoriu oarecare este reprezentată folosind coordonatele GPS în plan, longitudine şi latitudine, faţă de un reper considerat de coordonate <code>(0,0)</code>, ca în figura de mai jos.

Fiecare dintre clădirile aflate pe hartă, au două coordonate GPS, (Longitudine, Latitudine) şi un Grad de rezistenţă la cutremure.

Un cutremur se poate produce în orice punct de coordonate de pe hartă, numit centrul seismului şi are o anumită intensitate. Unda de şoc se propagă sub forma unor pătrate concentrice cu centrul seismului, numite nivele (nivelul <code>0</code> reprezintă centrul seismului, nivelul <code>1</code> primul pătrat concentric, nivelul <code>2</code> al doilea pătrat concentric şi aşa mai departe). Intensitatea slăbeşte la fiecare pătrat concentric cu centrul seismului cu câte o unitate. Clădirile sunt afectate de cutremur doar dacă gradul lor de rezistenţă la cutremur este mai mic sau egal cu intensitatea cutremurului în poziţia clădirii.

= Cerința =
Scrieţi un program care să citească coordonatele centrului seismului şi intensitatea sa în acel punct, precum şi coordonatele clădirilor şi gradul lor de rezistenţă la cutremur, şi apoi să determine:

a) numărul <code>N</code> total de clădiri afectate;

b) numărul <code>M</code> maxim de clădiri afectate pe un nivel;

c) numerele nivelelor cu <code>M</code> clădiri afectate, în ordinea crescătoare a numerelor acestor nivele.

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

* pe prima linie, trei numere naturale <code>Long Lat Intensitate</code>, separate prin câte un spaţiu, reprezentând coordonatele centrului seismului şi respectiv intensitatea sa;
* pe fiecare dintre următoarele linii, până la sfârşitul fişierului, câte <code>trei</code> numere naturale <code>Long Lat Grad</code>, separate prin câte un spaţiu, reprezentând coordonatele unei clădiri, respectiv gradul de rezistenţă la cutremur.

= Date de ieșire =
Fișierul de ieșire <code>cladiri1.out</code> va conține trei linii:

* pe prima linie se va scrie numărul natural <code>N</code> reprezentând numărul total de clădiri afectate;
* pe a doua linie se va scrie numărul natural <code>M</code> reprezentând numărul maxim de clădiri afectate pe un nivel;
* pe a treia linie se vor scrie numerele nivelelor cu <code>M</code> clădiri afectate, în ordinea crescătoare a numerelor acestor nivele.

= Restricții și precizări =

* <code>0 ≤ Long, Lat, Grad, Intensitate ≤ 10000</code>
* <code>0 <</code> număr clădiri <code>≤ 100000</code>
* în centrul seismului se pot afla clădiri;
* nu există mai multe clădiri cu aceleaşi coordonate;

= Exemplu =
<code>cladiri1.in</code>
12 7 11
10 9 2
10 7 3
13 5 1
8 11 4
8 7 6
15 4 3
15 9 10
13 10 1
16 8 4
<code>cladiri1.out</code>
8
3
2 4

= Explicație =
Numărul <code>N</code> total al clădirilor afectate este <code>8</code>.

Numărul <code>M</code> maxim de clădiri afectate pe acelaşi nivel este <code>3</code> şi este atins pe nivelele <code>2</code> şi <code>4</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import math

# Initialize the arrays with zeros
a = [0] * 10001
b = [0] * 10001

# Open the input file
with open('cladiri1.in', 'r') as f:
cx, cy, g = map(int, f.readline().split())
nr = 0

# Process each line in the file
for line in f:
x, y, rez = map(int, line.split())
max_dist = max(abs(cx - x), abs(cy - y))
if g - max_dist > 0 and rez - (g - max_dist) <= 0:
nr += 1
a[max_dist] += 1

# Find the maximum value and its indices
max_value = -1
k = 0
for i in range(10001):
if max_value == a[i]:
k += 1
b[k] = i
elif max_value < a[i]:
max_value = a[i]
k = 1
b[k] = i

# Open the output file
with open('cladiri1.outtxt', 'w') as ff:
ff.write(str(nr) + '\n')
ff.write(str(max_value) + '\n')
if nr != 0:
for i in range(1, k + 1):
ff.write(str(b[i]) + ' ')
</syntaxhighlight>

1085 - Loto

2024-02-13T14:52:24Z

Raul:

La Loteria Naţională există <code>N</code> bile inscripţionate cu numere naturale, nenule, distincte de cel mult <code>4</code> cifre. Şeful de la loterie primeşte o cutie în care se află cele <code>6</code> bile extrase la ultima rundă, restul bilelor neextrase fiind puse într-un seif. Deoarece are o fire poznaşă, el scoate din cutie bila pe care este înscris numărul cel mai mic şi o păstrează în buzunarul hainei sale. În locul ei va pune o bilă neextrasă, aflată în seif, având numărul cel mai apropiat de aceasta. Apoi continuă operaţia şi scoate din cutie şi bila pe care este înscris numărul maxim extras iniţial, pe care o va pune în celălalt buzunar al său. De asemenea o va înlocui cu o altă bilă neextrasă iniţial, aflată în seif, având numărul cel mai apropiat de aceasta.

= Cerinţă =
Realizaţi un program care afişează în ordine crescătoare numerele de pe bilele aflate în cutie după modificările făcute de şef.

= Date de intrare =
Fișierul de intrare <code>loto.in</code> conține numărul natural <code>N</code>, pe a doua linie cele <code>N</code> numere naturale scrise pe bile, iar pe a treia linie cele 6 numere naturale scrise pe bilele extrase de angajaţii loteriei. Valorile scrise pe aceeaşi linie sunt separate prin spaţii.

= Date de ieșire =
Fișierul de ieșire <code>loto.out</code> se vor afişa pe prima linie, separate prin câte un spaţiu, cele 6 numere obţinute în cutie după modificările făcute de şef, în ordine crescătoare.

= Restricții și precizări =

* <code>8 < N < 1000</code>
* Dacă o bilă poate fi înlocuită cu două bile la fel de apropiate de ea, atunci aceasta se va înlocui cu bila având numărul mai mare.
* Pentru datele de test, atât bila cu numărul cel mai mic, cât şi bila cu numărul cel mai mare pot fi înlocuite cu alte bile.

= Exemplul 1 =
<code>loto.in</code>
10
231 212 32 123 453 675 1321 54 67 567
212 32 67 567 675 1321
<code>loto.out</code>
54 67 212 453 567 675

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python2" line="1">
n = int(input())
a = [False] * 10001
b = [0] * 6

for _ in range(n):
x = int(input())
a[x] = True

max_value = 0
min_value = 10000
mx = 0
mn = 0

for i in range(6):
b[i] = int(input())
a[b[i]] = False
if b[i] < min_value:
min_value = b[i]
mn = i
if b[i] > max_value:
max_value = b[i]
mx = i

i = min_value
j = min_value
while not (a[i] or a[j]):
if i < 10000:
i += 1
if j > 1:
j -= 1

if a[i]:
b[mn] = i
else:
b[mn] = j
a[b[mn]] = False

i = max_value
j = max_value
while not (a[i] or a[j]):
if i < 10000:
i += 1
if j > 1:
j -= 1

if a[i]:
b[mx] = i
else:
b[mx] = j

# Sorting the array b
b.sort()

for i in range(5):
print(b[i], end=' ')
print(b[5])

</syntaxhighlight>

1085 - Loto

2024-02-13T14:51:03Z

Raul: Pagină nouă: La Loteria Naţională există <code>N</code> bile inscripţionate cu numere naturale, nenule, distincte de cel mult <code>4</code> cifre. Şeful de la loterie primeşte o cutie în care se află cele <code>6</code> bile extrase la ultima rundă, restul bilelor neextrase fiind puse într-un seif. Deoarece are o fire poznaşă, el scoate din cutie bila pe care este înscris numărul cel mai mic şi o păstrează în buzunarul hainei sale. În locul ei va pune o bilă neextras...

La Loteria Naţională există <code>N</code> bile inscripţionate cu numere naturale, nenule, distincte de cel mult <code>4</code> cifre. Şeful de la loterie primeşte o cutie în care se află cele <code>6</code> bile extrase la ultima rundă, restul bilelor neextrase fiind puse într-un seif. Deoarece are o fire poznaşă, el scoate din cutie bila pe care este înscris numărul cel mai mic şi o păstrează în buzunarul hainei sale. În locul ei va pune o bilă neextrasă, aflată în seif, având numărul cel mai apropiat de aceasta. Apoi continuă operaţia şi scoate din cutie şi bila pe care este înscris numărul maxim extras iniţial, pe care o va pune în celălalt buzunar al său. De asemenea o va înlocui cu o altă bilă neextrasă iniţial, aflată în seif, având numărul cel mai apropiat de aceasta.

= Cerinţă =
Realizaţi un program care afişează în ordine crescătoare numerele de pe bilele aflate în cutie după modificările făcute de şef.

= Date de intrare =
Fișierul de intrare <code>loto.in</code> conține numărul natural <code>N</code>, pe a doua linie cele <code>N</code> numere naturale scrise pe bile, iar pe a treia linie cele 6 numere naturale scrise pe bilele extrase de angajaţii loteriei. Valorile scrise pe aceeaşi linie sunt separate prin spaţii.

= Date de ieșire =
Fișierul de ieșire <code>loto.out</code> se vor afişa pe prima linie, separate prin câte un spaţiu, cele 6 numere obţinute în cutie după modificările făcute de şef, în ordine crescătoare.

= Restricții și precizări =

* <code>8 < N < 1000</code>
* Dacă o bilă poate fi înlocuită cu două bile la fel de apropiate de ea, atunci aceasta se va înlocui cu bila având numărul mai mare.
* Pentru datele de test, atât bila cu numărul cel mai mic, cât şi bila cu numărul cel mai mare pot fi înlocuite cu alte bile.

= Exemplul 1 =
<code>loto.in</code>
10
231 212 32 123 453 675 1321 54 67 567
212 32 67 567 675 1321
<code>loto.out</code>
54 67 212 453 567 675

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
n = int(input())
a = [False] * 10001
b = [0] * 6

for _ in range(n):
x = int(input())
a[x] = True

max_value = 0
min_value = 10000
mx = 0
mn = 0

for i in range(6):
b[i] = int(input())
a[b[i]] = False
if b[i] < min_value:
min_value = b[i]
mn = i
if b[i] > max_value:
max_value = b[i]
mx = i

i = min_value
j = min_value
while not (a[i] or a[j]):
if i < 10000:
i += 1
if j > 1:
j -= 1

if a[i]:
b[mn] = i
else:
b[mn] = j
a[b[mn]] = False

i = max_value
j = max_value
while not (a[i] or a[j]):
if i < 10000:
i += 1
if j > 1:
j -= 1

if a[i]:
b[mx] = i
else:
b[mx] = j

# Sorting the array b
b.sort()

for i in range(5):
print(b[i], end=' ')
print(b[5])

</syntaxhighlight>

1080 - Livada

2024-02-13T14:48:17Z

Raul: Pagină nouă: Norocosul Gigel tocmai a primit în dar de la bunicul său, Nelu, o imensă plantaţie de pomi fructiferi. Fost profesor de geometrie, Nelu a plantat în mod riguros pomii fructiferi pe <code>m</code> rânduri paralele, iar pe fiecare rând a plantat exact câte <code>n</code> pomi fructiferi. Însă, din motive mai mult sau mai puţin obiective, domnul Nelu nu a plantat pe fiecare rând toţi pomii de acelaşi soi, ci din mai multe soiuri diferite. Soiurile de pomi plantaţi...

Norocosul Gigel tocmai a primit în dar de la bunicul său, Nelu, o imensă plantaţie de pomi fructiferi. Fost profesor de geometrie, Nelu a plantat în mod riguros pomii fructiferi pe <code>m</code> rânduri paralele, iar pe fiecare rând a plantat exact câte <code>n</code> pomi fructiferi. Însă, din motive mai mult sau mai puţin obiective, domnul Nelu nu a plantat pe fiecare rând toţi pomii de acelaşi soi, ci din mai multe soiuri diferite. Soiurile de pomi plantaţi în livadă sunt codificate cu numere naturale cuprinse între <code>1</code> şi <code>p</code>.

Cuprins de febra rigurozităţii matematice şi de cea a statisticii, Gigel a definit noţiunea de soi majoritar astfel: dacă pe un rând <code>k</code> format din <code>n</code> pomi fructiferi avem cel puţin <code>[n/2]+1</code> pomi de acelaşi soi <code>x</code>, atunci spunem că soiul <code>x</code> este soi majoritar pe rândul <code>k</code> (prin <code>[y]</code> se înţelege partea întreagă a numărului real <code>y</code>).

= Cerinţă =
Cunoscând numerele <code>m</code>, <code>n</code> şi <code>p</code>, precum şi soiul fiecărui pom de pe fiecare rând al plantaţiei, ajutaţi-l pe Gigel să determine:

# pe câte rânduri din livadă există un soi majoritar;
# care este cel mai mare număr de pomi de acelaşi soi plantaţi în poziţii consecutive pe un rând.

= Date de intrare =
Fișierul de intrare <code>livada.in</code> conține pe prima linie trei numere naturale <code>m</code>, <code>n</code> şi <code>p</code> cu semnificaţia din enunţ, iar pe fiecare dintre următoarele <code>m</code> linii se găsesc câte <code>n</code> numere, despărţite prin câte un spaţiu, reprezentând soiurile pomilor de pe rândul respectiv.

= Date de ieșire =
Fișierul de ieșire <code>livada.out</code> va conține două linii:

# pe prima linie se va scrie un număr natural reprezentând numărul de rânduri din livadă pe care există un soi majoritar;
# pe a doua linie se va scrie un număr natural reprezentând cel mai mare număr de pomi de același soi plantaţi în poziţii consecutive pe un rând.

= Restricții și precizări =

* <code>1 ≤ m ≤ 100</code>
* <code>1 ≤ n ≤ 700.000</code>
* <code>1 ≤ m*n ≤ 700.000</code>
* <code>1 ≤ p ≤ 998.560.000</code>
* Pe fiecare rând diferenţa dintre valoarea maximă şi cea minimă este cel mult <code>250.000</code>.
* Dacă doar valoarea de pe prima linie este corectă, se acordă 40% din punctaj. Dacă doar valoarea de pe a doua linie este corectă, se acordă 60% din punctaj. Dacă ambele valori sunt corecte, se acordă 100% din punctajul testului respectiv.

= Exemplu: =
<code>livada.in</code>
4 7 9
2 1 2 3 8 2 2
4 7 2 4 9 7 4
5 5 2 5 5 5 7
2 3 2 3 2 3 1
<code>livada.out</code>
2
3

= Explicație =
Plantaţia este formată din <code>m=4</code> rânduri, iar pe fiecare rând avem câte <code>n=7</code> pomi.

Pentru ca un soi sa fie majoritar pe un rând trebuie ca pe acel rând să existe cel puţin <code>[7/2]+1 = 4</code> pomi din soiul respectiv.

Există soiuri majoritare pe două rânduri: primul şi al treilea.

Pe rândul al treilea exista <code>3</code> poziții consecutive în care se află pomi din același soi (soiul <code>5</code>).

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
def read_ints_from_file(file):
return list(map(int, file.readline().split()))

def main():
with open("livada.in", "r") as fin:
m, n, p = read_ints_from_file(fin)
max_length = 0
rsm = 0
for i in range(m):
v = read_ints_from_file(fin)
rmax = 0
j = 0
while j < n - 1:
k = j + 1
while k < n and v[k] == v[j]:
k += 1
if k - j > rmax:
rmax = k - j
j = k
if rmax > max_length:
max_length = rmax
sm = v[0]
cnt = 1
for j in range(1, n):
if cnt == 0:
sm = v[j]
cnt = 1
elif v[j] == sm:
cnt += 1
else:
cnt -= 1
if cnt == 0:
sm = 0
else:
cnt = sum(1 for x in v if x == sm)
if cnt < n // 2 + 1:
sm = 0
if sm != 0:
rsm += 1
with open("livada.out", "w") as fout:
fout.write(f"{rsm}\n{max_length}")

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

1096 - Expresie 8

2024-02-13T14:42:46Z

Raul: Pagină nouă: Costel are de rezolvat o temă grea la matematică: având la dispoziţie <code>N</code> numere naturale nenule trebuie să aşeze între acestea <code>2</code> operaţii de înmulţire şi <code>N-3</code> operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date. De exemplu, dacă <code>N=5</code> şi numerele sunt <code>4</code>, <code>7</code>, <code>1</code>, <code>5</code>, <code>3</code...

Costel are de rezolvat o temă grea la matematică: având la dispoziţie <code>N</code> numere naturale nenule trebuie să aşeze între acestea <code>2</code> operaţii de înmulţire şi <code>N-3</code> operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date.

De exemplu, dacă <code>N=5</code> şi numerele sunt <code>4</code>, <code>7</code>, <code>1</code>, <code>5</code>, <code>3</code>, operaţiile pot fi aşezate <code>4+7*1+5*3</code>, <code>4*7*1+5+3</code>, e.t.c

= Cerinţă =
Scrieţi un program care să aşeze două operaţii de înmulţire şi <code>N-3</code> operaţii de adunare între cele <code>N</code> valori date astfel încât valoarea expresiei obţinute să fie maximă.

= Date de intrare =
Fișierul de intrare <code>expresie8.in</code> are următoarea structură:

* Pe prima linie se află un număr natural <code>N</code>, reprezentând numărul elementelor date.
* Pe următoarele linii se află cele <code>N</code> numere naturale date, fiecare pe câte o linie.

= Date de ieșire =
Fișierul de ieșire <code>expresie8.out</code> va conține pe prima linie valoarea maximă obţinută prin evaluarea expresiei.

= Restricții și precizări =

* <code>4 <= N <= 1000</code>
* Numerele date sunt numere naturale între <code>1</code> şi <code>10000</code>

= Exemplu: =
<code>expresie8.in</code>
5
4
7
1
5
3
<code>expresie8.out</code>
44

= Explicație =
Valoarea maximă se obţine prin aşezarea operaţiilor sub forma: <code>4 * 7 + 1 + 5*3</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
with open("expresie8.in", "r") as fin, open("expresie8.out", "w") as fout:
n = int(fin.readline())
v = list(map(int, fin.readline().split()))

s = 0
Max = 0
for i in range(1, n+1):
s += v[i]

for i in range(1, n-1):
cc = s - v[i] - v[i+1] - v[i+2] + (v[i] * v[i+1] * v[i+2])
if cc > Max:
Max = cc

for i in range(1, n-2):
for j in range(i+2, n):
cc = s - v[i] - v[i+1] - v[j] - v[j+1] + (v[i] * v[i+1]) + (v[j] * v[j+1])
if cc > Max:
Max = cc

fout.write(str(Max) + "\n")
</syntaxhighlight>

2175 - Factori

2024-02-12T15:30:12Z

Raul: Pagină nouă: Gigel a aflat la matematică definiţia factorialului unui număr natural nenul <code>n</code>. Acesta este produsul tuturor numerelor naturale începând cu <code>1</code> şi terminând cu numărul respectiv şi se notează cu <code>n!</code>. Astfel, factorialul numărului natural <code>6</code> este <code>6!=1*2*3*4*5*6</code> şi este egal cu <code>720</code>. Factorialele numerelor naturale cresc însă extrem de repede. De exemplu, <code>7!=5040</code> în timp ce <cod...

Gigel a aflat la matematică definiţia factorialului unui număr natural nenul <code>n</code>. Acesta este produsul tuturor numerelor naturale începând cu <code>1</code> şi terminând cu numărul respectiv şi se notează cu <code>n!</code>. Astfel, factorialul numărului natural <code>6</code> este <code>6!=1*2*3*4*5*6</code> şi este egal cu <code>720</code>. Factorialele numerelor naturale cresc însă extrem de repede. De exemplu, <code>7!=5040</code> în timp ce <code>10!=3628800</code>.

Fiind un bun matematician, Gigel a imaginat o altă metodă de a indica factorialul unui număr. Astfel, el ştie că un număr natural nenul se poate descompune în factori primi. De exemplu <code>720</code> poate fi scris ca <code>24*32*51</code>. Gigel codifică descompunerea în factori primi astfel: <code>4 2 1</code> însemnând faptul că în descompunerea lui <code>720</code> în factori primi apare factorul <code>2</code> de <code>4</code> ori, factorul <code>3</code> apare de două ori şi factorul <code>5</code> apare o dată. Cu alte cuvinte, Gigel indică pentru fiecare număr prim <code>≤ n</code> puterea la care acesta apare în descompunerea în factori primi a lui <code>n!</code>.

= Cerința =
Scrieţi un program care să citească o secvenţă de numere naturale nenule şi care să afişeze în modul descris în enunţ factorialele numerelor citite.

= Date de intrare =
Fişierul de intrare <code>factori.in</code> conţine mai multe numere naturale nenule, câte un număr pe linie. Ultima linie a fişierului de intrare conţine valoarea <code>0</code> indicând faptul că setul de numere s-a terminat.

= Date de ieșire =
Fişierul de ieşire <code>factori.out</code> va conţine câte o linie pentru fiecare număr nenul din fişierul de intrare. Pe linia <code>i</code> din fişierul de ieşire va fi descrisă descompunerea în factori primi a factorialului numărului de pe linia <code>i</code> din fişierul de intrare, în modul descris în enunţ. Numerele scrise pe aceeaşi linie vor fi separate prin câte un spaţiu.

= Restricții și precizări =
Numerele naturale din fişierul de intrare (exceptând ultimul) sunt din intervalul <code>[2, 60000]</code>.

Fişierul de intrare conţine maxim <code>10</code> numere naturale nenule.

= Exemplu: =
<code>factori.in</code>
2
8
15
10
0
<code>factori.out</code>
1
7 2 1 1
11 6 3 2 1 1
8 4 2 1

=== Explicație ===
<code>2! = 2</code>

<code>8! = 2*2*2*2*2*2*2*3*3*5*7</code>

<code>15! = 2*2*2*2*2*2*2*2*2*2*2*3*3*3*3*3*3*5*5*5*7*7*11*13</code>

<code>10! = 2*2*2*2*2*2*2*2*3*3*3*3*5*5*7</code>

== Încărcare soluție ==

=== Lipește codul aici ===

1575 - Paritate OJI

2024-02-12T15:26:13Z

Raul: Pagină nouă: În vederea asigurării unei transmiteri cât mai exacte a informaţiilor pe reţea, transmiterea se efectuează caracter cu caracter, fiecare caracter fiind dat prin codul său ASCII, adică o grupă de <code>8</code> biţi (octet). Pentru fiecare <code>8</code> biţi transmişi se calculează un bit de paritate care are valoarea <code>0</code> (dacă codul ASCII al caracterului conţine un număr par de cifre binare <code>1</code>) sau <code>1</code> (în caz contrar). Deo...

În vederea asigurării unei transmiteri cât mai exacte a informaţiilor pe reţea, transmiterea se efectuează caracter cu caracter, fiecare caracter fiind dat prin codul său ASCII, adică o grupă de <code>8</code> biţi (octet). Pentru fiecare <code>8</code> biţi transmişi se calculează un bit de paritate care are valoarea <code>0</code> (dacă codul ASCII al caracterului conţine un număr par de cifre binare <code>1</code>) sau <code>1</code> (în caz contrar). Deoarece în problema noastră se transmit numai caractere ASCII standard, cu codul ASCII din intervalul <code>[32,127]</code>, codul lor ASCII are bitul <code>7</code> (primul bit din stânga) egal cu <code>0</code>. Pe această poziţie va fi pus bitul de paritate, economisind astfel câte un bit pentru fiecare caracter transmis.

De exemplu, dacă mesajul care trebuie transmis conţine caracterele <code>Paritate</code>, succesiunea de biţi transmisă va fi:

<code>01010000 11100001 01110010 01101001 01110100 11100001 01110100 01100101</code>

În plus, pe lângă caracterele amintite, în mesaj mai poate să apară un caracterul special, caracter care indică trecerea la începutul unui nou rând. Acest caracter are codul ASCII 10.

= Cerința =
Să se scrie un program care să verifice dacă un text a fost sau nu transmis corect.

= Date de intrare =
Fişierul de intrare paritate.in are pe prima linie o succesiune de caractere <code>0</code> şi <code>1</code> care reprezintă mesajul transmis. Între caractere nu există spaţii. Linia se termină cu caracterul marcaj de sfârşit de linie (newline).

= Date de ieșire =
Fişierul de ieşire paritate.out are pe prima linie mesajul <code>DA</code> dacă textul a fost transmis corect sau <code>NU</code> în caz contrar. În cazul în care mesajul de pe prima linie este <code>DA</code> liniile următoare vor conţine textul transmis în clar. În cazul în care mesajul de pe prima linie este <code>NU</code> linia următoare va conţine numerele de ordine ale caracterelor care nu au fost transmise corect, în ordine strict crescătoare, separate prin câte un spaţiu.

= Restricții și precizări =

* Cei <code>8</code> biţi ai codului ASCII a unui caracter se numerotează de la <code>0</code> la <code>7</code>, de la dreapta la stânga, cel mai din stânga bit fiind bitul <code>7</code> iar cel mai din dreapta bitul <code>0</code>.
* Textul transmis are cel mult <code>60.000</code> caractere.
* Numărul de caractere <code>0</code> şi <code>1</code> din prima linie a fişierului de intrare este multiplu de <code>8</code>.
* Codurile ASCII ale caracterelor din text aparţin mulţimii <code>{10, 32–127}</code>, codul <code>10</code> însemnând trecerea la începutul unui rând nou.
* Nici o linie din fişierul de ieşire nu va avea mai mult de <code>255</code> caractere.

= Exemplu: =
<code>paritate.in</code>
0101000011100001011100100110100101110100111000010111010001100101
<code>paritate.out</code>
DA

=== Explicație ===
Toate codurile sunt corecte.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import math

in_file = open("paritate.intxt", "r")
out_file = open("paritate.outtxt", "w")

raj = [0] * 60001
rong = [0] * 60001

wrong = False
ctr = 0
rong_ctr = 0

while True:
nr1 = 0
t = 0
bin_val = in_file.read(1)
if not bin_val:
break
if bin_val == '1':
nr1 += 1
for i in range(6, -1, -1):
bin_val = in_file.read(1)
if bin_val == '1':
nr1 += 1
t += pow(2, i)
if nr1 % 2:
wrong = True
rong[rong_ctr] = ctr
rong_ctr += 1
if not wrong:
raj[ctr] = t
ctr += 1

if wrong:
out_file.write("NU\n")
for i in range(rong_ctr):
out_file.write(str(rong[i]) + " ")
else:
out_file.write("DA\n")
for i in range(ctr - 1):
if raj[i] == 10:
out_file.write('\n')
else:
out_file.write(str(raj[i]))

intxt_file.close()
outtxt_file.close()
</syntaxhighlight>

1215 - Mesaj

2024-02-12T15:19:16Z

Raul: Pagină nouă: În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii ''Mi'' și ''Gi'' se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul ''Mi'' scrie și trimite un mesaj piticului ''Gi'' respectând următoarele reguli: * un mesaj conține una sau mai multe secvențe; * orice literă care apare în mesaj, de cel pu...

În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii ''Mi'' și ''Gi'' se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul ''Mi'' scrie și trimite un mesaj piticului ''Gi'' respectând următoarele reguli:

* un mesaj conține una sau mai multe secvențe;
* orice literă care apare în mesaj, de cel puțin două ori, pe poziții alăturate, este numită terminator;
* o secvență se încheie când s-a întâlnit o succesiune de litere terminator;
* cuvântul este format din prima majusculă și ultima minusculă din secvență, fără a lua în seamă litera terminator a secvenței;
* o secvență ascunde un cuvânt dacă terminatorul său se repetă de exact două ori și dacă conține cel puțin o literă mare și o literă mică, ignorând terminatorul de secvență;
* costul unui cuvânt este egal cu numărul total de apariții al celor două litere din care este format, în cadrul secvenței în care a fost ascuns, luând în considerare inclusiv literele terminator.

De exemplu secvența <code>s f u E e t R u E E</code> ascunde un cuvânt deoarece conține și majuscule și minuscule, iar litera terminator de secvență, <code>E</code>, se repetă de exact două ori. Secvența ascunde cuvântul <code>Eu</code>, iar costul cuvântului este <code>5</code> (<code>3</code> litere <code>E</code> + <code>2</code> două litere <code>u</code>).

La primirea mesajului, piticul ''Gi'' determină, pentru fiecare majusculă, costul maxim al cuvintelor care încep cu aceasta.

= Cerinţe =
Scrieţi un program care determină:

1) numărul de secvențe trimise care nu ascund cuvinte;

2) cuvintele din mesaj, în ordinea în care au fost trimise de piticul ''Mi'';

3) pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de ''Gi''.

fi afișate în ordine de la <code>A</code> la <code>Z</code>, însă doar cele pentru care au existat în mesaj cuvinte care au început cu ele.

= Date de intrare =
Fișierul de intrare <code>mesaj.in</code> conţine pe prima linie un număr natural <code>P</code>. Pentru toate testele de intrare, numărul <code>P</code> poate avea numai una dintre valorile <code>1</code>, <code>2</code> sau <code>3</code>. Pe a doua linie a fișierului de intrare se găsește numărul natural N reprezentând numărul de litere folosite de ''Mi'' pentru scrierea mesajului. Pe a treia linie se găsesc <code>N</code> litere mari și mici ale alfabetului englez, separate prin câte un spațiu, reprezentând literele mesajului, în ordinea în care au fost trimise.

= Date de ieșire =
Dacă valoarea lui <code>P</code> este <code>1</code>, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire <code>mesaj.out</code> va conține pe prima linie un număr natural reprezentând răspunsul la cerinţa 1).

Dacă valoarea lui <code>P</code> este <code>2</code>, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire <code>mesaj.out</code> va conține cuvintele din mesaj, fiecare cuvânt scris pe câte o linie, în ordinea în care au fost trimise.

Dacă valoarea lui <code>P</code> este <code>3</code>, se va rezolva numai punctul 3) din cerințe. În acest caz, fişierul de ieşire <code>mesaj.out</code> va conține pe fiecare linie câte o majusculă urmată de un număr natural nenul, separate printr-un spațiu. Majusculele vor fi afișate în ordine de la <code>A</code> la <code>Z</code>, însă doar cele pentru care au existat în mesaj cuvinte care au început cu ele.

= Restricții și precizări =

* <code>1 ≤ N ≤ 2000000</code>
* litera terminator a unei secvențe poate fi ori minusculă ori majusculă;
* ultimele litere din fișier sunt literele terminator ale ultimei secvențe din mesajul trimis; se garantează că în șirul de litere din fișierul de intrare se află ascuns cel puțin un cuvânt;
* majusculele alfabetului englez sunt <code>A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z</code>;
* pentru 50% din teste <code>N ≤ 1000000</code>
* Pentru rezolvarea cerinţei 1) se acordă 20 de puncte, pentru rezolvarea cerinţei 2) se acordă 40 de puncte, iar pentru rezolvarea cerinţei 3) se acordă 40 de puncte.

= Exemplul 1 =
<code>mesaj.in</code>
1
34
w w w w e D o r F D o r r t R n e R e y y j j i M

o e i t t t j w w
<code>mesaj.out</code>
4

=== Explicație ===
Textul conține șase secvențe:

# <code>w w w w</code>
# <code>e D o r F D o r r</code>
# <code>t R n e R e y y</code>
# <code>j j</code>
# <code>i M o e i t t t</code>
# <code>j w w</code>

Sunt <code>4</code> secvențe care nu ascund cuvinte:

* prima secvență și a patra deoarece conțin numai terminatorul;
* secvența a cincea nu se decodifică deoarece terminatorul se repetă de mai mult de două ori;
* secvența a șasea nu conține majuscule.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import string

in_file = open("mesaj.in", "r")
out_file = open("mesaj.out", "w")

maj_counts = [0] * 256
min_counts = [0] * 256
max_cost = [0] * 256
max_cost_counts = [0] * 256

P = int(in_file.readline())
N = int(in_file.readline())

num_secvente = 0
num_secvente_cu_cuvinte = 0

ch = '#'
count_ch = 1

maj_ch = '#'
min_ch = '#'

for i in range(N):
peek_ch = in_file.read(1)
if i == N - 1:
peek_ch = '#'

if ch == peek_ch:
count_ch += 1
else:
if count_ch == 1:
if P == 1 or P == 2 or P == 3:
if ch.isupper() and maj_ch == '#':
maj_ch = ch
if ch.islower():
min_ch = ch
if P == 3:
if ch.isupper():
maj_counts[ord(ch)] += 1
if ch.islower():
min_counts[ord(ch)] += 1

elif count_ch == 2:
if P == 1:
num_secvente += 1
if maj_ch != '#' and min_ch != '#':
num_secvente_cu_cuvinte += 1
maj_ch = min_ch = '#'
elif P == 2:
if maj_ch != '#' and min_ch != '#':
out_file.write(maj_ch + min_ch + '\n')
maj_ch = min_ch = '#'
elif P == 3:
if ch.isupper():
maj_counts[ord(ch)] += 2
if ch.islower():
min_counts[ord(ch)] += 2
if maj_ch != '#' and min_ch != '#':
cost = maj_counts[ord(maj_ch)] + min_counts[ord(min_ch)]
if cost > max_cost[ord(maj_ch)]:
max_cost[ord(maj_ch)] = cost
max_cost_counts[ord(maj_ch)] = 1
elif cost == max_cost[ord(maj_ch)]:
max_cost_counts[ord(maj_ch)] += 1
maj_ch = min_ch = '#'
maj_counts = [0] * 256
min_counts = [0] * 256

else:
if P == 1:
num_secvente += 1
maj_ch = min_ch = '#'
elif P == 2:
maj_ch = min_ch = '#'
elif P == 3:
maj_ch = min_ch = '#'
maj_counts = [0] * 256
min_counts = [0] * 256

count_ch = 1
ch = peek_ch

if P == 1:
out_file.write(str(num_secvente - num_secvente_cu_cuvinte) + '\n')
elif P == 3:
for ch in string.ascii_uppercase:
if max_cost[ord(ch)]:
out_file.write(ch + ' ' + str(max_cost_counts[ord(ch)]) + '\n')

in_file.close()
out_file.close()
</syntaxhighlight>

1123 - Iepurasi

2024-02-12T15:13:25Z

Raul: Pagină nouă: Se construieşte un şir de numere naturale care respectă restricţiile: * primul număr din şir este <code>9</code>; * numerele se generează în ordine strict crescătoare; * şirul conţine toate numerele formate doar cu cifrele <code>7</code>, <code>8</code> şi <code>9</code> cu proprietatea că numărul cifrelor <code>9</code> este mai mare sau egal decât numărul cifrelor <code>8</code> şi numărul cifrelor <code>8</code> este mai mare sau egal decât numărul cif...

Se construieşte un şir de numere naturale care respectă restricţiile:

* primul număr din şir este <code>9</code>;
* numerele se generează în ordine strict crescătoare;
* şirul conţine toate numerele formate doar cu cifrele <code>7</code>, <code>8</code> şi <code>9</code> cu proprietatea că numărul cifrelor <code>9</code> este mai mare sau egal decât numărul cifrelor <code>8</code> şi numărul cifrelor <code>8</code> este mai mare sau egal decât numărul cifrelor <code>7</code>. Primii <code>14</code> termeni ai şirului, în ordine, sunt: <code>9</code>, <code>89</code>, <code>98</code>, <code>99</code>, <code>789</code>, <code>798</code>, <code>879</code>, <code>897</code>, <code>899</code>, <code>978</code>, <code>987</code>, <code>989</code>, <code>998</code>, <code>999</code>.

Pornind de la aceste numere, Liv a inventat un joc interactiv: <code>N</code> iepuraşi sunt aşezaţi în şir, fiecare având câte un cartonaş. Fiecare cartonaş are două feţe, o faţă albă pe care este inscripţionat un număr din acest şir şi o faţă gri, pe care este inscripţionată poziţia acelui număr în şir, poziţii numerotate în ordine, începând cu valoarea <code>1</code>.

'''Exemple.''' Cartonaşul care are pe faţa gri inscripţionat numărul <code>1</code> va avea pe faţa albă inscripţionat numărul <code>9</code>, iar cartonaşul care are pe faţa gri inscripţionat numărul <code>5</code> va avea pe faţa albă inscripţionat numărul <code>789</code>.

Iepuraşii sunt aşezaţi într-o ordine oarecare şi ţin cartonaşele astfel încât să se vadă faţa gri. Jocul constă în a rearanja iepuraşii de la stânga la dreapta, descrescător după numerele inscripţionate pe feţele gri, având la dispoziţie doar operaţia <code>TAP</code> pe un iepuraş. Când se aplică operaţia <code>TAP</code> unui iepuraş atunci secvenţa de iepuraşi, începând de la cel pe care s-a făcut <code>TAP</code> şi până la sfârşitul şirului (spre dreapta), este oglindită (ca în imaginea de mai sus). După oglindire, toţi iepuraşii din acea secvenţă ţin cartonaşele astfel încât să se vadă faţa albă. Se doreşte aplicarea unui număr cât mai mic de operaţii TAP pentru rearanjarea iepuraşilor.

= Cerinţe =
Scrieţi un program care să citească numerele naturale <code>N</code> (reprezentând numărul de iepuraşi) şi <code>a1</code>, <code>a2</code>,…, <code>aN</code> (reprezentând, în ordine, numerele inscripţionate pe feţele gri) și care să determine:

'''a)''' Numărul minim de operaţii <code>TAP</code> necesare rearanjării iepuraşilor;

'''b)''' Cel mai mic număr aflat pe o faţă albă care nu se vede, în cazul în care au rămas cartonaşe neîntoarse. Dacă toate cartonaşele au fost întoarse (la toate fiind vizibilă faţa albă) se va afişa cel mai mare număr aflat pe o faţă albă a unui cartonaş.

= Date de intrare =
Fișierul de intrare <code>iepurasi.in</code> conține pe prima linie numărul natural <code>N</code> reprezentând numărul de iepuraşi. A doua linie a fişierului conţine, în ordine, cele <code>N</code> numere: <code>a1</code>, <code>a2</code>a<code>N</code>, separate prin câte un spaţiu, reprezentând în ordine, numerele inscripţionate pe feţele gri ale cartonașelor.

= Date de ieșire =
Fișierul de ieșire <code>iepurasi.out</code> va conține pe prima linie un număr reprezentând numărul minim de operaţii <code>TAP</code> necesare rearanjării iepuraşilor. A doua linie va conține un număr reprezentând cel mai mic număr aflat pe o faţă albă care nu se vede (în cazul în care au rămas cartonaşe neîntoarse), respectiv cel mai mare număr aflat pe o faţă albă a unui cartonaş, în cazul în care toate cartonaşele au fost întoarse (la toate fiind vizibilă faţa albă).

= Restricții și precizări =

* <code>2 ≤ N ≤ 10000</code>;
* <code>1 ≤ ai ≤ 10000</code> (<code>1≤i≤N</code>);
* <code>N, a1</code>, <code>a2</code>, …, <code>aN</code> sunt numere naturale;
* pentru rezolvarea cerinţei a) se acordă 50% din punctaj, iar pentru cerinţa b) se acordă 50% din punctaj.

= Exemplu: =
<code>iepurasi.in</code>
5
14 5 8 9 10
<code>iepurasi.out</code>
1
999

= Explicație =
Se aplică o singură operaţie <code>TAP</code> pe iepuraşul cu numărul de ordine <code>5</code>. Cartonaşul neîntors are numărul de ordine <code>14</code> (<code>999</code>).

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

f = open("iepurasi.txtin", "r")
g = open("iepurasi.txtout", "w")

toate = [0] * 200001
ncurent = 0
N = 0
a = [0] * 10001
dim_sir = 0
TAP = 0
nr1 = 0
nr2 = 0
viz = [False] * 10001
fr7 = [0] * 200001
fr8 = [0] * 200001
fr9 = [0] * 200001

def main():
global N, a, TAP, viz
i = 0
j = 0
k = 0
maxi = 0
imax = 0
aux = 0
c7 = 0
c8 = 0
c9 = 0

#citire
N = int(f.readline())
a = list(map(int, f.readline().split()))

#sortare descrescatoare
for i in range(1, N + 1):
imax = i
maxi = a[i]
for j in range(i + 1, N + 1):
if a[j] > maxi:
maxi = a[j]
imax = j
if imax != i:
if a[N] != maxi:
TAP += 1
#TAP pe iepurasul imax
for j in range(imax, k, -1):
aux = a[j]
a[j] = a[k]
a[k] = aux
viz[j] = True
viz[k] = True
#TAP pe iepurasul i
if a[i] != maxi:
TAP += 1
for j in range(i, k, -1):
aux = a[j]
a[j] = a[k]
a[k] = aux
viz[j] = True
viz[k] = True

#det cartonas minim/maxim
if viz[1]:
k = a[1]
else:
i = 1
while not viz[i] and i <= N:
i += 1
k = a[i - 1]

#constructie sir de numere cu cifrele 7,8,9 pana la numarul de pe pozitia k
fr7[1] = 1
fr8[2] = 1
fr9[3] = 1
toate[1] = 7
toate[2] = 8
toate[3] = 9
dim_sir = 0
nr1 = 1
nr2 = 3
while dim_sir < k:
c7 = fr7[nr1]
c8 = fr8[nr1]
c9 = fr9[nr1]
ncurent = toate[nr1]
nr1 += 1
nr2 -= 1
if c7 <= c8 and c8 <= c9:
dim_sir += 1
fr7[nr1 + nr2] = c7 + 1
fr8[nr1 + nr2] = c8
fr9[nr1 + nr2] = c9
toate[nr1 + nr2] = 10 * ncurent + 7
nr2 += 1
fr7[nr1 + nr2] = c7
fr8[nr1 + nr2] = c8 + 1
fr9[nr1 + nr2] = c9
toate[nr1 + nr2] = 10 * ncurent + 8
nr2 += 1
fr7[nr1 + nr2] = c7
fr8[nr1 + nr2] = c8
fr9[nr1 + nr2] = c9 + 1
toate[nr1 + nr2] = 10 * ncurent + 9
nr2 += 1

#afisare
g.write(str(TAP) + "\n" + str(ncurent) + "\n")
f.close()
g.close()
sys.exit(0)

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

1147 - Oni Gim

2024-02-12T15:09:21Z

Raul: Pagină nouă: La ONIGIM2013 participă <code>N</code> elevi de clasa a V-a având ca id-uri, în ordine, numerele naturale de la <code>1</code> la <code>N</code>. Anul acesta organizatorii au afişat la clasa a V-a toate punctajele distincte obţinute de elevi, în ordine strict crescătoare <code>p1</code>, <code>p2</code>,…, <code>pK</code>, şi un şir de <code>N</code> valori <code>a1</code>, <code>a2</code>,…, <code>aN</...

La ONIGIM2013 participă <code>N</code> elevi de clasa a V-a având ca id-uri, în ordine, numerele naturale de la <code>1</code> la <code>N</code>. Anul acesta organizatorii au afişat la clasa a V-a toate punctajele distincte obţinute de elevi, în ordine strict crescătoare <code>p1</code>, <code>p2</code>,…, <code>pK</code>, şi un şir de <code>N</code> valori <code>a1</code>, <code>a2</code>,…, <code>aN</code>, unde <code>ai</code> reprezintă numărul de elevi care au punctaje strict mai mici decât punctajul elevului având id-ul <code>i</code> (<code>1≤i≤N</code>).

= Cerință =
Cunoscând numărul de elevi (<code>N</code>), numărul de punctaje distincte (<code>K</code>) obţinute de elevii de clasa a V-a, punctajele <code>p1</code>, <code>p2</code>,…, <code>pK</code>, în ordine strict crescătoare, şi valorile <code>a1</code>, <code>a2</code>,…, <code>aN</code> cu semnificaţia din enunţ, să se scrie un program care determină:

'''a)''' Punctajul obţinut de fiecare elev în ordinea crescătoare a id-urilor.

'''b)''' Numărul de distincţii acordate de organizatori. Numărul de distincţii este egal cu numărul de elevi care au obţinut cele mai mari trei punctaje distincte.

'''c)''' Numărul maxim de elevi care au obţinut acelaşi punctaj.

= Date de intrare =
Fișierul de intrare <code>onigim.in</code> conține pe prima linie numerele naturale <code>N</code> şi <code>K</code> reprezentând numărul de elevi, respectiv numărul de punctaje distincte obţinute de elevi. Pe a doua linie sunt <code>K</code> numere naturale în ordine strict crescătoare <code>p1</code>, <code>p2</code>,…, <code>pK</code> reprezentând punctajele distincte obţinute de elevi, şi pe a treia linie sunt <code>N</code> numere naturale <code>a1</code>, <code>a2</code>,…, <code>aN</code>, unde <code>ai</code> reprezintă numărul de elevi care au punctaje strict mai mici decât punctajul elevului cu id-ul <code>i</code>.

= Date de ieșire =
Fișierul de ieșire <code>onigim.out</code> va conține trei linii. Pe prima linie se află <code>N</code> numere naturale <code>v1</code>, <code>v2</code>,…, <code>vN</code> reprezentând punctajele obţinute de cei <code>N</code> concurenţi (<code>vi</code>- punctajul concurentului cu id-ul <code>i</code>), pe a doua linie se află un număr natural <code>D</code> reprezentând numărul de distincţii acordate de organizatori, pe a treia linie se află un număr natural <code>M</code> reprezentând numărul maxim de elevi care au obţinut acelaşi punctaj.

= Restricții și precizări =

* <code>1 ≤ N ≤ 1000</code>;
* <code>1 ≤ pi ≤ 300</code>, (<code>1≤i≤N</code>);
* <code>0 ≤ ai < 1000</code>, (<code>1≤i≤N</code>);
* <code>1 ≤ K ≤ 1000</code>;

= Exemplu: =
<code>onigim.in</code>
6 4
100 150 175 200
4 2 0 0 3 4
<code>onigim.out</code>
200 150 100 100 175 200
4
2

= Explicație =
Sunt <code>4</code> elevi care au punctajul mai mic decât punctajul elevului cu id-ul <code>1</code>, <code>2</code> elevi cu punctajul mai mic decât punctajul elevului cu id-ul <code>2</code>, etc.

Cele mai mari <code>3</code> punctaje sunt obţinute de <code>4</code> elevi. Numărul maxim de elevi care au acelaşi punctaj este <code>2</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

sys.stdin = open("onigim.intxt", "r")
sys.stdout = open("onigim.outtxt", "w")

n, k = map(int, input().split())
p = list(map(int, input().split()))
v = [0] * 1001
a = [0] * 1001
fr = [0] * 1001
nrdistinctii = 0
nr = 0

for i in range(1, k + 1):
p[i] = int(input())

for i in range(1, n + 1):
a[i] = int(input())
fr[a[i]] += 1

i = 1
for j in range(n + 1):
if fr[j] != 0:
v[j] = p[i]
i += 1

for i in range(1, n + 1):
a[i] = v[a[i]]

for i in range(1, n + 1):
print(a[i], end=' ')
print()

i = n
while i >= 0:
if fr[i] != 0 and nr < 3:
nrdistinctii += fr[i]
nr += 1
i -= 1

print(nrdistinctii)

nr = 0
for i in range(n):
if nr < fr[i]:
nr = fr[i]

print(nr)
</syntaxhighlight>

1731 - Numar 5

2024-02-12T15:04:26Z

Raul: Pagină nouă: Pentru un număr dat cu <code>k</code> cifre , se numeşte algoritm de deplasare circulară spre dreapta de la o cifră iniţială , la o cifră finală , deplasarea din cifră în cifră spre dreapta de ori (<code>1≤i,j≤k</code>). Dacă pe parcursul deplasării s-a ajuns la cifra , se continuă deplasarea circulară spre dreapta cu cifra . Un număr cu <code>k</code> cifre se numeşte număr „circular” dacă îndeplineşte următoarele două cerinţe: * toate c...

Pentru un număr dat cu <code>k</code> cifre , se numeşte algoritm de deplasare circulară spre dreapta de la o cifră iniţială , la o cifră finală , deplasarea din cifră în cifră spre dreapta de ori (<code>1≤i,j≤k</code>). Dacă pe parcursul deplasării s-a ajuns la cifra , se continuă deplasarea circulară spre dreapta cu cifra

.

Un număr cu <code>k</code> cifre se numeşte număr „circular” dacă îndeplineşte următoarele două cerinţe:

* toate cifrele sunt nenule;
* pornind de la cifra , aplicând algoritmul de deplasare circulară spre dreapta de exact <code>k</code> ori, se ajunge din nou la , fiecare dintre cifrele numărului fiind exact o singură dată cifră iniţială.

De exemplu, numărul <code>2396</code> este un număr “circular”, pentru că are doar cifre nenule şi algoritmul de deplasare circulară spre dreapta se aplică astfel:

''1.'' Se porneşte de la cifra iniţială <code>2</code> (<code>2 3 9 6</code>) şi se numără două cifre spre dreapta, ajungând la cifra finală <code>9</code>: <code>2 3 9 6</code>.

''2.'' Se porneşte de la cifra iniţială <code>9</code> şi se numără nouă cifre spre dreapta, ajungând la cifra finală <code>6</code>: <code>2 3 9 6</code>.

''3.'' Se porneşte de la cifra iniţială <code>6</code> şi se numără şase cifre spre dreapta, ajungând la cifra finală <code>3</code>: <code>2 3 9 6</code>.

''4.'' Se porneşte de la cifra iniţială <code>3</code> şi se numără trei cifre spre dreapta, ajungând la cifra finală <code>2</code>: <code>2 3 9 6</code>.

Astfel, se ajunge la prima cifră din număr, adică la cifra <code>2</code>, după exact <code>4</code> aplicări ale algoritmului, iar fiecare dintre cifrele numărului este exact o dată cifră iniţială.

= Cerința =
Scrieţi un program care citeşte numărul natural nenul <code>n</code>, apoi numerele naturale
, şi determină:
a) cel mai mare număr din şir în care există cel puţin o cifră care apare de minimum două ori, iar în cazul în care în şir nu există un astfel de număr, se va afişa cel mai mare număr din şir;
b) un şir de <code>n</code> numere naturale pentru care un element (<code>1≤i≤n</code>)se calculează astfel:

= Date de intrare =
Fişierul <code>numar.in</code> conţine pe prima linie numărul <code>n</code>, iar pe următoarele <code>n</code> linii numerele naturale

= Date de ieșire =
Fişierul <code>numar.out</code> va conţine pe prima linie un număr natural determinat conform cerinţei a), iar pe următoarele <code>n</code> linii şirul de numere determinat conform cerinţei de la punctul b), fiecare număr pe câte un rând.

= Restricții și precizări =

* <code>0 < n < 100</code>
* <code>9 <</code> x <code>< 999589</code>, <code>1 ≤ i ≤ n</code>

= Exemplu: =
<code>numar.in</code>
5
15
123
1972
222
515
<code>numar.out</code>
515
15
117
1959
222
522

=== Explicație ===
a) <code>515</code> este cel mai mare număr dintre cele cinci numere citite, număr ce conţine o cifră care apare de minimum două ori.

b) Pentru <code>15</code>: de la cifra iniţială <code>1</code>, se numără o cifră şi se ajunge la cifra finală <code>5</code>, apoi începând de la cifra <code>5</code> ca cifră iniţială, se numără cinci cifre şi se ajunge la cifra finală <code>1</code>. Astfel cifrele <code>1</code>, <code>5</code> sunt o singură dată cifre iniţiale şi după două aplicări ale algoritmului de deplasare se ajunge la prima cifră, deci <code>15</code> este număr circular.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

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

a = [0] * 10000
n = 0

def date():
global n
n = int(input())
for i in range(n):
a[i] = int(input())

def cifre_repetate(x):
digits = [0] * 10
while x:
if digits[x % 10] != 0:
return 1
else:
digits[x % 10] = 1
x = x // 10
return 0

def max():
max1 = 0
max2 = 0
for i in range(n):
if cifre_repetate(a[i]):
if max2 < a[i]:
max2 = a[i]
if max1 < a[i]:
max1 = a[i]
if max2 == 0:
return max1
else:
return max2

def este(x):
i = 1
a = [0] * 100
b = [0] * 100
k = 0
t = 0
z = 0
j = 0
ok = 0

while x != 0:
a[i] = x % 10
if a[i] == 0:
return 0
x //= 10
b[i] = 1
i += 1

i -= 1
for j in range(i // 2):
z = a[j]
a[j] = a[i - j]
a[i - j] = z

z = 0
t = a[1]
k = 1
ok = 1
for j in range(1, i + 1):
if k + t <= i:
k = k + t
else:
k = (t - (i - k + 1)) % i + 1
if b[k] != 0:
z += 1
b[k] = 0
else:
ok = 0
t = a[k]

if ok:
return 1
else:
return 0

def main():
global n
p = -1
z = 0
date()
print(max())
z = 0
for i in range(n):
if este(a[i]):
print(a[i])
else:
p = 0
x = a[i]
while not p:
if este(x):
p = 1
else:
x += 1
p = 0
y = a[i]
while not p:
if este(y):
p = 1
else:
y -= 1
if (x - a[i]) > (a[i] - y):
print(y)
else:
print(x)

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

1727 - Culori 3

2024-02-05T11:22:04Z

Raul: Pagină nouă: Fiecare dintre cei <code>N</code> copii, numerotați de la <code>1</code> la <code>N</code>, primește câte un cartonaș colorat. Doamna dirigintă îi așează în cerc, în ordinea numerotării, în sens orar. Astfel, fiecare copil are doi vecini, așezați în stânga, respectiv în dreapta lui. Andrei, pasionat de informatică, asociază fiecărei culori distincte un cod, reprezentat printr-un număr natural nenul, și inscripționează fiecare cartonaș cu codul cores...

Fiecare dintre cei <code>N</code> copii, numerotați de la <code>1</code> la <code>N</code>, primește câte un cartonaș colorat. Doamna dirigintă îi așează în cerc, în ordinea numerotării, în sens orar. Astfel, fiecare copil are doi vecini, așezați în stânga, respectiv în dreapta lui.

Andrei, pasionat de informatică, asociază fiecărei culori distincte un cod, reprezentat printr-un număr natural nenul, și inscripționează fiecare cartonaș cu codul corespunzător culorii acestuia.

= Cerința =
Scrieţi un program care citeşte două numere naturale <code>N</code> şi <code>K</code> şi determină pentru Andrei:

a) numărul copiilor din cerc care au cartonaşe de aceeaşi culoare cu cartonaşele vecinilor;

b) numărul maxim de cartonaşe de aceeaşi culoare ce sunt deţinute de copiii aşezaţi pe <code>K</code> poziţii consecutive în cercul format.

= Date de intrare =
Fişierul de intrare <code>culori.in</code> conţine pe prima linie numerele naturale <code>N</code> şi <code>K</code>, separate printr-un spaţiu, şi pe fiecare dintre următoarele <code>N</code> linii, câte un număr natural. Cele <code>N</code> numere reprezintă codurile culorilor cartonaşelor, în ordinea numerotării copiilor, începând cu copilul <code>1</code>.

= Date de ieșire =
Fişierul de ieşire <code>culori.out</code> conţine:

pe prima linie, numărul natural determinat la cerinţa a);

pe a doua linie, numărul natural determinat la cerinţa b).

= Restricții și precizări =

* <code>2 < N ≤ 1000</code>
* <code>2 < K ≤ N</code>
* codurile culorilor sunt numere naturale nenule, consecutive, mai mici sau egale cu <code>100</code>
* dacă <code>C</code> este codul maxim asociat unei culori ( <code>1 ≤ C ≤ 100</code> ) atunci există cel puţin <code>C</code> cartonaşe care au codurile distincte: <code>1,2,3,…,C</code>.

= Exemplu: =
<code>culori.in</code>
8 5
3
1
2
1
1
1
3
3
<code>culori.out</code>
2
4

=== Explicație ===
Sunt doi copii care au, fiecare, cartonaşe identice cu cei doi vecini (copilul <code>5</code> şi copilul <code>8</code>).

Numărul maxim de cartonaşe de aceeaşi culoare deţinute de copiii aşezaţi pe <code>K = 5</code> poziţii consecutive în cercul format este <code>4</code> (dintre copiii <code>2,3,4,5,6</code> doar copiii <code>2,4,5</code> şi <code>6</code> au cartonaşe de culoarea <code>1</code>).

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
def read_input(filename):
with open(filename, 'r') as fin:
N, k = map(int, fin.readline().split())
x = [0] * (2 * N + 3)
x[1] = int(fin.readline())
x[N + 1] = x[1]
c = x[1]
x[2] = int(fin.readline())
x[N + 2] = x[2]
if x[2] > c:
c = x[2]
for i in range(3, N + 1):
x[i] = int(fin.readline())
x[N + i] = x[i]
if x[i] > c:
c = x[i]
nrc = sum(1 for i in range(2, N) if x[i - 1] == x[i - 2] == x[i])
if x[1] == x[N] == x[N - 1]:
nrc += 1
if x[1] == x[2] == x[N]:
nrc += 1
return N, k, x, c, nrc

def main():
N, k, x, c, nrc = read_input('culori.in')
maxck = 0
apc1 = [0] * (c + 1)
for i in range(1, k + 1):
apc1[x[i]] += 1
maxck = max(maxck, apc1[x[i]])
for i in range(2, N + 1):
apc1[x[i - 1]] -= 1
apc1[x[i + k - 1]] += 1
for j in range(1, c + 1):
maxck = max(maxck, apc1[j])
with open('culori.out', 'w') as fout:
fout.write(f"{nrc}\n{maxck}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1708 - Cuburi 3

2024-02-05T11:18:36Z

Raul: Pagină nouă: Ionuţ a învăţat la şcoală să lucreze cu numere mari. El are la dispoziţie un şir de <code>N</code> numere naturale nenule. Din fiecare număr el şterge exact trei cifre, fără să schimbe ordinea cifrelor rămase, astfel încât să obţină cel mai mic număr natural nenul posibil. De exemplu, din numărul <code>20731049</code> se obţine numărul <code>20049</code>, iar din numărul <code>13004</code> se obţine numărul <code>10</code>. Înlocuind fiecare număr...

Ionuţ a învăţat la şcoală să lucreze cu numere mari. El are la dispoziţie un şir de <code>N</code> numere naturale nenule. Din fiecare număr el şterge exact trei cifre, fără să schimbe ordinea cifrelor rămase, astfel încât să obţină cel mai mic număr natural nenul posibil. De exemplu, din numărul <code>20731049</code> se obţine numărul <code>20049</code>, iar din numărul <code>13004</code> se obţine numărul <code>10</code>. Înlocuind fiecare număr citit cu numărul obţinut prin operaţia de mai sus, Ionuţ obţine un nou şir şi scrie termenii acestuia pe feţele unor cuburi astfel: primele şase numere din şir le scrie pe primul cub şi îl notează pe acesta cu <code>1</code>, următoarele şase numere din şir le scrie pe un alt cub pe care îl notează cu <code>2</code> ş.a.m.d.

Aceste cuburi au fost distribuite în piramide după modelul din figura. Piramidele au fost numerotate cu numere naturale consecutive. Piramida cu numărul de ordine <code>1</code> este formată numai din cubul cu numărul de ordine <code>1</code> şi are un singur nivel, piramida cu numărul de ordine <code>2</code> are pe primul nivel cuburile <code>2</code>, <code>3</code> şi <code>4</code> iar pe ultimul nivel cubul <code>5</code> ş.a.m.d.

Două niveluri alăturate în cadrul unei piramide diferă prin exact două cuburi. Primul nivel al unei piramide conţine cu două cuburi mai mult decât primul nivel al piramidei precedente. Piramida se consideră completă dacă pe ultimul nivel are un singur cub.

= Cerința =
Scrieţi un program care citeşte numerele naturale nenule <code>N</code> şi <code>K</code>, apoi cele <code>N</code> numere naturale ce fac parte din şirul iniţial, şi determină:

a) Numărul de piramide complete construite de Ionuţ.

b) Numerele scrise pe cuburile din primele <code>K</code> piramide.

= Date de intrare =
Fişierul <code>cuburi.in</code> are două linii: prima linie conţine două numere naturale, <code>N</code> şi <code>K</code>, iar a doua linie conţine <code>N</code> numere naturale. Pe fiecare linie a fişierului numerele sunt separate prin câte un spaţiu.

= Date de ieșire =
Fişierul <code>cuburi.out</code> are două linii: prima linie conţine numărul de piramide complete care au fost construite, iar a doua linie conţine toate numerele scrise pe cuburile ce formează primele <code>K</code> piramide. Numerele sunt scrise separate prin câte un spaţiu, în ordinea apariţiei lor în şirul nou obţinut.

= Restricții și precizări =

* <code>6 ≤ N ≤ 100000</code>
* Se garantează că se pot construi cel puţin <code>K</code> piramide complete.
* Cele <code>N</code> numere naturale de pe a doua linie a fişierului de intrare au minimum <code>4</code> cifre şi maximum <code>9</code> cifre.

= Exemplu: =
<code>cuburi.in</code>
31 2
18250 9280 18250 953805 20800 6040065 24208 4405 8794 1720 98886 96400 45544 8560056 36055 60400 80200 11560 36475 26992 68320 69400 20296 72640 34048 57700 66520 47440 91232 26080 90280
<code>cuburi.out</code>
2
10 2 10 305 20 4005 20 4 4 1 86 40 44 5005 30 40 20 10 34 22 20 40 20 20 30 50 20 40 12 20

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import math

def nrmin(x, nrc):
v = [int(digit) for digit in str(x)]
Min = v[0]
imin = 0
for i in range(4):
if v[i] < Min and v[i] != 0:
Min = v[i]
imin = i
nr = Min
in_index = imin + 1
sf = 4
while sf < nrc:
Min = v[in_index]
imin = in_index
for i in range(in_index, sf + 1):
if v[i] < Min:
Min = v[i]
imin = i
nr = nr * 10 + Min
in_index = imin + 1
sf += 1
return nr

def main():
with open("cuburi.in", "r") as stdin, open("cuburi.out", "w") as stdout:
n, k = map(int, stdin.readline().split())
nr = sum(i * i * 6 for i in range(1, k + 1))
w = []
nrpir = 0
s = 0
for i in range(1, n + 1):
x = int(stdin.readline())
nrc = int(math.log10(x)) + 1
if i % 6 == 0 and math.sqrt(i // 6) == int(math.sqrt(i // 6)):
s += i
if s <= n:
nrpir += 1
if i <= nr:
w.append(nrmin(x, nrc))
stdout.write(f"{nrpir}\n")
for num in w:
stdout.write(f"{num} ")
stdout.write("\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1989 - Teatru

2024-02-05T11:16:16Z

Raul: Pagină nouă: Alina este mare iubitoare de teatru. Directorul teatrului i-a oferit șansa să joace în mai multe spectacole, ca figurant, deocamdată. Costumiera de scenă a decis să-i dea <code>C</code> costume diferite dintre cele care sunt destinate acestei stagiuni. Alina va duce costumele acasă și le va ajusta ca să-i vină bine. Stagiunea durează <code>Z</code> zile consecutive și în fiecare zi se joacă câte o piesă. Aceeași piesă se va juca, desigur în una sau mai mai...

Alina este mare iubitoare de teatru. Directorul teatrului i-a oferit șansa să joace în mai multe spectacole, ca figurant, deocamdată. Costumiera de scenă a decis să-i dea <code>C</code> costume diferite dintre cele care sunt destinate acestei stagiuni. Alina va duce costumele acasă și le va ajusta ca să-i vină bine. Stagiunea durează <code>Z</code> zile consecutive și în fiecare zi se joacă câte o piesă. Aceeași piesă se va juca, desigur în una sau mai mai multe zile ale stagiunii. Fiecărei piese i se asociază un unic costum de figurant, deci pentru fiecare piesă în care joacă, Alina trebuie să îmbrace un singur costum, acela asociat piesei respective. Costumele de figuranți sunt identificate prin literele mari ale alfabetului englez: <code>A</code>, <code>B</code>, <code>C</code>, …, <code>X</code>, <code>Y</code>, <code>Z</code>. Alina are voie să-și aleagă cele <code>C</code> costume diferite.

= Cerința =
Cunoscând costumul asociat fiecărei zile a stagiunii, ajutați-o pe Alina să-și aleagă cele <code>C</code> costume diferite, în așa fel încât să poată juca într-un număr cât mai mare de piese consecutive.

= Date de intrare =
Fișierul de intrare <code>teatru.in</code> conține pe prima linie două numere naturale <code>Z</code> și <code>C</code> despărțite printr-un spațiu. <code>Z</code> este numărul de zile din stagiune iar <code>C</code> este numărul de costume diferite pe care Alina le poate primi. Pe linia a doua, se găsesc <code>Z</code> caractere, litere mari ale alfabetului englez. Caracterul al <code>i</code>-lea identifică costumul de figurant care trebuie îmbrăcat în spectacolul din ziua <code>i</code>.

= Date de ieșire =
Fișierul de ieșire <code>teatru.out</code> va conține pe prima linie un număr natural <code>N</code>, reprezentând numărul maxim de spectacole consecutive în care Alina poate juca. Pe linia a doua se scriu <code>N</code> caractere, fără spații între ele, corespunzătoare costumelor care vor fi îmbrăcate în cele <code>N</code> piese de teatru alese, în ordinea spectacolelor în care va juca. Dacă există mai multe soluții de lungime <code>N</code> atunci se afișează cea căreia îi corespunde o zi de început mai aproape de începutul stagiunii.

= Restricții și precizări =

* <code>1 ≤ Z ≤ 55000</code>
* <code>1 ≤ C ≤ 26</code>
* <code>C ≤ Z</code>
* Pentru 20% dintre teste <code>Z ≤ 350</code>

= Exemplul 1 =
<code>teatru.in</code>
10 3
XKUFKFEGXG
<code>teatru.out</code>
5
KUFKF

= Exemplul 2 =
<code>teatru.in</code>
15 4
IAJRAMRCZJJCDNS
<code>teatru.out</code>
6
AJRAMR

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
def read_input():
global n, k, s
n, k = map(int, input().split())
s = input().strip()

def print_output():
print(Lmax)
print(''.join(s[imax:jmax+1]))

def calculate():
global imax, jmax, Lmax
i = j = nr = 0
f = {chr(c): 0 for c in range(65, 91)}
f[s[0]] += 1
nr += 1
while i < n and j < n:
while nr <= k and j < n:
j += 1
if j >= n:
break
if f[s[j]] == 0:
f[s[j]] += 1
nr += 1
else:
f[s[j]] += 1
if j - i > Lmax:
Lmax = j - i
imax = i
jmax = j - 1
while nr > k:
f[s[i]] -= 1
if f[s[i]] == 0:
nr -= 1
i += 1

with open('teatru.in', 'r') as fin:
n, k = map(int, fin.readline().split())
s = fin.readline().strip()

imax = jmax = Lmax = 0
calculate()

with open('teatru.out', 'w') as fout:
fout.write(f"{Lmax}\n")
fout.write(''.join(s[imax:jmax+1]) + '\n')

if __name__ == '__main__':
calculate()
</syntaxhighlight>

2079 - Auto 1

2024-02-05T11:11:46Z

Raul: Pagină nouă: Se consideră o autostradă dispusă în linie dreaptă având <code>N</code> puncte de acces (intrare şi ieşire). În fiecare punct de acces există containere pentru colectarea deşeurilor, toate containerele au aceeaşi capacitate şi în fiecare punct de acces pot fi mai multe astfel de containere. Firma care asigură curăţenia dispune de un singur mijloc de transport al containerelor. Acest mijloc de transport poate încărca exact un număr <code>K</code> de contain...

Se consideră o autostradă dispusă în linie dreaptă având <code>N</code> puncte de acces (intrare şi ieşire). În fiecare punct de acces există containere pentru colectarea deşeurilor, toate containerele au aceeaşi capacitate şi în fiecare punct de acces pot fi mai multe astfel de containere. Firma care asigură curăţenia dispune de un singur mijloc de transport al containerelor. Acest mijloc de transport poate încărca exact un număr <code>K</code> de containere. Accesul mijlocului de transport pe autostradă se face cu restricţii pentru a nu perturba traficul şi din acest motiv trebuie ca la fiecare acces pe autostradă să fie colectate exact atâtea containere cât este capacitatea maşinii, dar dintr-un punct de colectare trebuie să ia exact un container, deci dacă se intră pe autostradă la punctul de acces <code>P</code>, unde <code>P≤N-K+1</code>, atunci trebuie să ia containere de la punctele de acces numerotate cu <code>P</code>, <code>P+1</code>, <code>P+2</code>,…, <code>P+K-1</code>, în aceste puncte de acces scade cu <code>1</code> numărul containerelor rămase. Firma trebuie să găsească toate valorile posibile pentru <code>K</code> astfel încât să poată colecta toate containerele.

= Cerința =
Se cere să se găsească toate valorile posibile pentru <code>K</code> astfel încât să fie adunate toate containerele.

= Date de intrare =
Fişierul de intrare <code>auto.in</code> va conţine pe prima linie numărul natural <code>T</code>, reprezentând numărul de seturi de date de intrare. În continuare urmează seturile de date de intrare, fiecare pe cate două linii. Pe prima linie a unui set se află numărul <code>N</code>, având semnificația din enunț. Pe următoarea linie se află <code>N</code> numere naturale separate printr-un spațiu, reprezentând numărul de containere din fiecare punct de acces.

= Date de ieșire =
Fișierul de ieșire <code>auto.out</code> va conține <code>T</code> linii, pe linia <code>i</code> aflându-se răspunsul pentru al <code>i</code>-lea set de date de intrare. Valorile posibile pentru <code>K</code> se vor afișa în ordine crescătoare, separate printr-un spațiu.

= Restricții și precizări =

* <code>2 ≤ T ≤ 30</code>
* <code>2 ≤ N ≤ 9000</code>
* <code>1 ≤ K ≤ N</code>
* <code>0 ≤</code> numărul de containere din fiecare punct de acces <code>≤ 1000</code>

= Exemplu: =
<code>auto.in</code>
2
8
1 2 3 4 2 0 0 0
3
1 1 1
<code>auto.out</code>
1 2
1 3

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys
import time

MAXN = 9001
MAXDIV = 770

def check(K, N, A, pos, st):
steps = 0
t = 1
p = 0
val = 0
for i in range(1, N + 1):
steps += 1
while t <= p and pos[t] <= i - K:
val -= st[t]
t += 1
if A[i] < val or (i > N - K + 1 and A[i] != val):
return False, steps
if A[i] > val:
p += 1
pos[p] = i
st[p] = A[i] - val
val = A[i]
return True, steps

def read_and_solve(N, A):
NR = 0
sol = [0] * MAXDIV
d = sum(A[1:N+1])
pos = [0] * MAXN
st = [0] * MAXN
for i in range(1, N + 1):
if d % i == 0:
is_valid, _ = check(i, N, A, pos, st)
if is_valid:
sol[NR] = i
NR += 1
sol = sorted(sol[:NR])
print(' '.join(map(str, sol)))

def main():
# sys.stdin = open("auto.in", "r")
# sys.stdout = open("auto.out", "w")
start = time.time()
teste = int(input())
steps = 0
for _ in range(teste):
N = int(input())
A = [0] + list(map(int, input().split()))
read_and_solve(N, A)
end = time.time()
# sys.stderr.write(f"{steps}\n")
# sys.stderr.write(f"{(end - start)}\n")

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

1443 - Control 2

2024-02-05T11:01:06Z

Raul: /* Lipește codul aici */

Gigel a primit spre păstrare un set de <code>n</code> cutii de greutăţi nu neapărat distincte. El a cântărit cutiile şi pentru fiecare greutate distinctă a notat pe o foaie, în ordine crescătoare a greutăţilor, numărul de cutii cu greutatea respectivă.

Deoarece fratele său mai mic avea prostul obicei să se joace cu numerele scrise de el pe foaie, Gigel s-a gândit să calculeze un „număr de control” după următorul algoritm: începând de la primul număr a grupat numerele de apariţii ale greutăţilor câte trei (dacă îi rămân numere negrupate la sfârşit, le ignoră). Dacă într-un grup sunt numai numere pare sau numai impare notează grupul cu cifra <code>1</code>, altfel îl notează cu cifra <code>0</code>. Din şirul astfel obţinut, se formează un număr care are ca valoare cifra zecilor egală cu numărul de valori <code>1</code> şi cifra unităţilor egală cu numărul de valori <code>0</code>, obţinându-se astfel „numărul de control”.

= Cerința =
Citind greutăţile cutiilor, să se determine „numărul de control” şi să se verifice dacă este număr prim.

= Date de intrare =
Pe prima linie a fişierului de intrare <code>control2.in</code> se găseşte numărul natural <code>n</code>, iar pe următoarele <code>n</code> linii câte un număr natural, reprezentând greutăţile celor <code>n</code> cutii.

= Date de ieșire =
Fişierul <code>control2.out</code> va conţine pe prima linie „numărul de control”, urmat, pe linia a doua, de valoarea <code>0</code> sau <code>1</code>. Pe linia a doua se va afişa <code>1</code> dacă numărul este prim, respectiv <code>0</code> în caz contrar.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* fiecare greutate este un număr natural, mai mic sau egal cu <code>200</code>

= Exemplu: =
<code>control2.in</code>
21
1
3
2
6
2
6
2
8
9
8
8
9
10
8
11
18
11
12
14
15
17
<code>control2.out</code>
31
1

=== Explicație ===
După ordonare se obţine şirul: <code>1 2 2 2 3 6 6 8 8 8 8 9 9 10 11 11 12 14 15 17 18</code>

Se obţine apoi
.
Din valorile <code>1 1 0 1</code> se obţine numărul de control 31, care este număr prim.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

def main():
sys.stdin = open('control2.txtin', 'r')
sys.stdout = open('control2.txtout', 'w')

numarGreutati = int(input())
greutati = list(map(int, input().split()))
greutati.sort()

aparitii = []
numarApariti = 0
numarControl = 0
elementeSumaControl = [0, 0]
estePrim = 1

i = 0
while i < numarGreutati:
count = 1
if greutati[i] == greutati[i+1]:
while greutati[i] == greutati[i+1] and i < numarGreutati:
count += 1
i += 1
aparitii.append(count)
numarApariti += 1
i += 1

for i in range(0, numarApariti // 3 * 3, 3):
elementeSumaControl[aparitii[i] % 2 == aparitii[i + 1] % 2 and aparitii[i] % 2 == aparitii[i + 2] % 2] += 1

numarControl = elementeSumaControl[0] + elementeSumaControl[1] * 10

if numarControl % 2 == 0:
estePrim = (numarControl == 2)
else:
for d in range(3, int(numarControl ** 0.5) + 1, 2):
if numarControl % d == 0:
estePrim = 0
break

print(numarControl, file=sys.stdout)
print(estePrim, file=sys.stdout)

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

1443 - Control 2

2024-02-05T11:00:19Z

Raul:

Gigel a primit spre păstrare un set de <code>n</code> cutii de greutăţi nu neapărat distincte. El a cântărit cutiile şi pentru fiecare greutate distinctă a notat pe o foaie, în ordine crescătoare a greutăţilor, numărul de cutii cu greutatea respectivă.

Deoarece fratele său mai mic avea prostul obicei să se joace cu numerele scrise de el pe foaie, Gigel s-a gândit să calculeze un „număr de control” după următorul algoritm: începând de la primul număr a grupat numerele de apariţii ale greutăţilor câte trei (dacă îi rămân numere negrupate la sfârşit, le ignoră). Dacă într-un grup sunt numai numere pare sau numai impare notează grupul cu cifra <code>1</code>, altfel îl notează cu cifra <code>0</code>. Din şirul astfel obţinut, se formează un număr care are ca valoare cifra zecilor egală cu numărul de valori <code>1</code> şi cifra unităţilor egală cu numărul de valori <code>0</code>, obţinându-se astfel „numărul de control”.

= Cerința =
Citind greutăţile cutiilor, să se determine „numărul de control” şi să se verifice dacă este număr prim.

= Date de intrare =
Pe prima linie a fişierului de intrare <code>control2.in</code> se găseşte numărul natural <code>n</code>, iar pe următoarele <code>n</code> linii câte un număr natural, reprezentând greutăţile celor <code>n</code> cutii.

= Date de ieșire =
Fişierul <code>control2.out</code> va conţine pe prima linie „numărul de control”, urmat, pe linia a doua, de valoarea <code>0</code> sau <code>1</code>. Pe linia a doua se va afişa <code>1</code> dacă numărul este prim, respectiv <code>0</code> în caz contrar.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* fiecare greutate este un număr natural, mai mic sau egal cu <code>200</code>

= Exemplu: =
<code>control2.in</code>
21
1
3
2
6
2
6
2
8
9
8
8
9
10
8
11
18
11
12
14
15
17
<code>control2.out</code>
31
1

=== Explicație ===
După ordonare se obţine şirul: <code>1 2 2 2 3 6 6 8 8 8 8 9 9 10 11 11 12 14 15 17 18</code>

Se obţine apoi
.
Din valorile <code>1 1 0 1</code> se obţine numărul de control 31, care este număr prim.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

def main():
sys.stdin = open('control2.in', 'r')
sys.stdout = open('control2.out', 'w')

numarGreutati = int(input())
greutati = list(map(int, input().split()))
greutati.sort()

aparitii = []
numarApariti = 0
numarControl = 0
elementeSumaControl = [0, 0]
estePrim = 1

i = 0
while i < numarGreutati:
count = 1
if greutati[i] == greutati[i+1]:
while greutati[i] == greutati[i+1] and i < numarGreutati:
count += 1
i += 1
aparitii.append(count)
numarApariti += 1
i += 1

for i in range(0, numarApariti // 3 * 3, 3):
elementeSumaControl[aparitii[i] % 2 == aparitii[i + 1] % 2 and aparitii[i] % 2 == aparitii[i + 2] % 2] += 1

numarControl = elementeSumaControl[0] + elementeSumaControl[1] * 10

if numarControl % 2 == 0:
estePrim = (numarControl == 2)
else:
for d in range(3, int(numarControl ** 0.5) + 1, 2):
if numarControl % d == 0:
estePrim = 0
break

print(numarControl, file=sys.stdout)
print(estePrim, file=sys.stdout)

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

1443 - Control 2

2024-02-05T10:58:46Z

Raul: Pagină nouă: Gigel a primit spre păstrare un set de <code>n</code> cutii de greutăţi nu neapărat distincte. El a cântărit cutiile şi pentru fiecare greutate distinctă a notat pe o foaie, în ordine crescătoare a greutăţilor, numărul de cutii cu greutatea respectivă. Deoarece fratele său mai mic avea prostul obicei să se joace cu numerele scrise de el pe foaie, Gigel s-a gândit să calculeze un „număr de control” după următorul algoritm: începând de la primul num...

Gigel a primit spre păstrare un set de <code>n</code> cutii de greutăţi nu neapărat distincte. El a cântărit cutiile şi pentru fiecare greutate distinctă a notat pe o foaie, în ordine crescătoare a greutăţilor, numărul de cutii cu greutatea respectivă.

Deoarece fratele său mai mic avea prostul obicei să se joace cu numerele scrise de el pe foaie, Gigel s-a gândit să calculeze un „număr de control” după următorul algoritm: începând de la primul număr a grupat numerele de apariţii ale greutăţilor câte trei (dacă îi rămân numere negrupate la sfârşit, le ignoră). Dacă într-un grup sunt numai numere pare sau numai impare notează grupul cu cifra <code>1</code>, altfel îl notează cu cifra <code>0</code>. Din şirul astfel obţinut, se formează un număr care are ca valoare cifra zecilor egală cu numărul de valori <code>1</code> şi cifra unităţilor egală cu numărul de valori <code>0</code>, obţinându-se astfel „numărul de control”.

= Cerința =
Citind greutăţile cutiilor, să se determine „numărul de control” şi să se verifice dacă este număr prim.

= Date de intrare =
Pe prima linie a fişierului de intrare <code>control2.in</code> se găseşte numărul natural <code>n</code>, iar pe următoarele <code>n</code> linii câte un număr natural, reprezentând greutăţile celor <code>n</code> cutii.

= Date de ieșire =
Fişierul <code>control2.out</code> va conţine pe prima linie „numărul de control”, urmat, pe linia a doua, de valoarea <code>0</code> sau <code>1</code>. Pe linia a doua se va afişa <code>1</code> dacă numărul este prim, respectiv <code>0</code> în caz contrar.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* fiecare greutate este un număr natural, mai mic sau egal cu <code>200</code>

= Exemplu: =
<code>control2.in</code>
21
1
3
2
6
2
6
2
8
9
8
8
9
10
8
11
18
11
12
14
15
17
<code>control2.out</code>
31
1

=== Explicație ===
După ordonare se obţine şirul: <code>1 2 2 2 3 6 6 8 8 8 8 9 9 10 11 11 12 14 15 17 18</code>

Se obţine apoi
.
Din valorile <code>1 1 0 1</code> se obţine numărul de control 31, care este număr prim.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

def main():
sys.stdin = open('control2.in', 'r')
sys.stdout = open('control2.out', 'w')

numarGreutati = int(input())
greutati = list(map(int, input().split()))
greutati.sort()

aparitii = []
numarApariti = 0
numarControl = 0
elementeSumaControl = [0, 0]
estePrim = 1

i = 0
while i < numarGreutati:
count = 1
if greutati[i] == greutati[i+1]:
while greutati[i] == greutati[i+1] and i < numarGreutati:
count += 1
i += 1
aparitii.append(count)
numarApariti += 1
i += 1

for i in range(0, numarApariti // 3 * 3, 3):
elementeSumaControl[aparitii[i] % 2 == aparitii[i + 1] % 2 and aparitii[i] % 2 == aparitii[i + 2] % 2] += 1

numarControl = elementeSumaControl[0] + elementeSumaControl[1] * 10

if numarControl % 2 == 0:
estePrim = (numarControl == 2)
else:
for d in range(3, int(numarControl ** 0.5) + 1, 2):
if numarControl % d == 0:
estePrim = 0
break

print(numarControl, file=sys.stdout)
print(estePrim, file=sys.stdout)

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

1697 - Cod 1

2024-02-01T14:55:22Z

Raul: Pagină nouă: Ionel și Georgel sunt colegi de clasă și doresc să facă schimb de fișiere prin email. Fiecare dintre ei își arhivează fișierele cu câte o parolă. Fiecare copil își construiește parola pe baza unui șir format din <code>N</code> numere naturale. Numerele din șir care se folosesc efectiv pentru construirea parolelor sunt '''doar''' cele divizibile cu numerele din mulțimea <code>{2,3,4,5,6,7,8,9,10,11,12,13,14,15}</code>. Copiii numără câte din valorile din...

Ionel și Georgel sunt colegi de clasă și doresc să facă schimb de fișiere prin email. Fiecare dintre ei își arhivează fișierele cu câte o parolă. Fiecare copil își construiește parola pe baza unui șir format din <code>N</code> numere naturale.

Numerele din șir care se folosesc efectiv pentru construirea parolelor sunt '''doar''' cele divizibile cu numerele din mulțimea <code>{2,3,4,5,6,7,8,9,10,11,12,13,14,15}</code>. Copiii numără câte din valorile din șir sunt divizibile cu fiecare din aceste numere.

Parola folosită de Ionel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea <code>{2,3,4,5,6,7,8,9}</code>. Parola folosită de Georgel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea <code>{10,11,12,13,14,15}</code>.

= Cerința =
Scrieţi un program care citește șirul celor <code>N</code> numere și determină:

# câte numere din șir nu se vor folosi în construirea parolelor celor doi copii;
# parola construită de Ionel;
# parola construită de Georgel.

= Date de intrare =
Fișierul de intrare <code>cod1.in</code> conține pe prima linie un număr natural <code>P</code>. Pentru toate testele de intrare, numărul <code>P</code> poate avea doar valoarea <code>1</code>, <code>2</code> sau <code>3</code>. Pe a doua linie numărul natural <code>N</code>, iar pe a treia linie, <code>N</code> numere naturale separate prin câte un caracter <code>#</code>.

= Date de ieșire =
Dacă valoarea lui <code>P</code> este <code>1</code>, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire <code>cod1.out</code> va conţine pe prima linie un număr natural nenul reprezentând câte numere din șir nu s-au folosit la construirea parolelor sau <code>0</code> dacă nu există astfel de numere.

Dacă valoarea lui <code>P</code> este <code>2</code>, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire <code>cod1.out</code> va conţine pe prima linie un număr natural reprezentând parola construită de Ionel.

Dacă valoarea lui <code>P</code> este <code>3</code>, se va rezolva numai punctul 3) din cerințe. În acest caz, fişierul de ieşire <code>cod1.out</code> va conţine pe prima linie un număr natural reprezentând parola construită de Georgel.

= Restricții și precizări =

* <code>0 < N ≤ 100 000</code>
* <code>2 ≤</code> numărul de cifre ale unui număr <code>≤ 100</code>
* Se garantează că toate parolele pe care copiii le vor obține sunt nenule
* În fișierul de intrare ultimul număr nu este urmat de caracterul <code>#</code>
* 16% din teste conțin doar numere formate din cel mult <code>9</code> cifre
* Pentru rezolvarea corectă a cerinţei 1 se obțin 20 de puncte, pentru rezolvarea corectă a cerinţei 2 se obțin 40 de puncte iar pentru rezolvarea corectă a cerinţei 3 se obțin 40 de puncte

= Exemplul 1 =
<code>cod1.in</code>
1
6
10#20#12#34#15#23
<code>cod1.out</code>
1

== Încărcare soluție ==

=== Lipește codul aici ===

3014 - Ceva cu Liste

2024-02-01T14:51:46Z

Raul: Pagină nouă: Se dau <code>2</code> liste, <code>L1</code> și <code>L2</code>. <code>L1</code> e formata din bile, iar <code>L2</code> din numere. La început, în lista <code>L1</code> sunt <code>N</code> bile. Lista <code>L2</code> conține mereu <code>M</code> numere. O iterație presupune modificarea listei <code>L1</code> în felul următor: se scot instantaneu și în același timp toate bilele din lista <code>L1</code> aflate pe pozițiile date de elementele din lista <code>L2</cod...

Se dau <code>2</code> liste, <code>L1</code> și <code>L2</code>. <code>L1</code> e formata din bile, iar <code>L2</code> din numere. La început, în lista <code>L1</code> sunt <code>N</code> bile. Lista <code>L2</code> conține mereu <code>M</code> numere. O iterație presupune modificarea listei <code>L1</code> în felul următor: se scot instantaneu și în același timp toate bilele din lista <code>L1</code> aflate pe pozițiile date de elementele din lista <code>L2</code>. O bilă este pe poziția <code>i</code> dacă înaintea bilei, în lista <code>L1</code>, se află <code>i-1</code> bile. Astfel, la fiecare iterație, <code>L1</code> se modifică, dar <code>L2</code> '''NU''' se modifică. Iterațiile se pot aplica până când în lista <code>L1</code> nu se mai găsesc bile sau până când nu se mai pot scoate bile din <code>L1</code>.

De menționat ca unele bile își schimbă poziția pe parcursul efectuării iterațiilor. De exemplu, dacă <code>L1=[$,$,$]</code> și <code>L2=[1]</code>, după prima iterație bila de pe poziția <code>1</code> va fi scoasă din lista <code>L1</code> și bilele de pe pozițiile <code>2</code> și <code>3</code> vor ajunge pe pozițiile <code>1</code> și respectiv <code>2</code>. În a doua iterație, prima bilă se va scoate (cea care inițial a fost bila de pe poziția <code>2</code>) iar bila de pe poziția <code>2</code> (inițial <code>3</code>) trece pe prima poziție. În ultima iterație bila de pe poziția <code>1</code> se scoate (inițial <code>3</code>) și lista devine goală.

= Cerință =
Să se determine numărul de iterații care se pot efectua.

= Date de intrare =
Fișierul de intrare <code>cevaculiste.in</code> conține pe prima linie două numere naturale nenule <code>N</code> și <code>M</code>, reprezentând lungimea listei <code>L1</code> și respectiv lungimea listei <code>L2</code>. Pe următoarea linie se află <code>M</code> numere în ordine crescătoare reprezentând elementele listei <code>L2</code>.

= Date de ieșire =
Fișierul de ieșire <code>cevaculiste.out</code> trebuie să conțină răspunsul pentru cerință, adică numărul de iterații care se pot efectua până când nu mai putem face nicio ștergere.

= Restricții și precizări =

* <code>1 ≤ N ≤ 10^18</code>
* <code>1 ≤ M ≤ 10^5</code>
* <code>1 ≤ L2[i] ≤ 10^18</code>
* Elementele listei <code>L2</code> sunt distincte.
* Pentru teste în valoare de <code>20</code> de puncte <code>N ≤ 2*10^4 , M ≤ 10^4</code>
* Pentru alte teste în valoare de <code>30</code> de puncte <code>N ≤ 10^7 , M ≤10^5</code>
* Problema va fi evaluată pe teste în valoare de <code>90</code> de puncte
* Se vor acorda <code>10</code> puncte pe exemple

= Exemplu =
<code>cevaculiste.in</code>
10 3
1 3 5
<code>cevaculiste.out</code>
5

= Explicație =
Notăm: <code>$</code> ca bilă și ca bilă ce se va scoate în momentul

efectuării următoarei iterații.

Avem la început <code>L1: [$,$,$,$,$,$,$,$,$,$]</code>

Înainte de prima iterație: <code>[ ,$, ,$, ,$,$,$,$,$]</code>

După prima iterație și înainte de a <code>2</code>-a: <code>[ ,$, ,$, ,$,$]</code>

După a <code>2</code>-a iterație și înainte de a <code>3</code>-a: <code>[ ,$, ,$]</code>

După a <code>3</code>-a iterație și înainte de a <code>4</code>-a: <code>[ ,$]</code>

După a <code>4</code>-a iterație și înainte de a <code>5</code>-a: <code>[ ]</code>

După a <code>5</code>-a iterație: <code>[]</code>

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
# Framework: None
# Technology stack: None

fin = open("cevaculiste.txt", "r")
fout = open("cevaculiste.txt", "w")

n, m = map(int, fin.readline().split())
v = [0] * 100001
c = 0

for i in range(1, m + 1):
v[i] = int(fin.readline())

while m:
if v[m] <= n:
c += (n - v[m]) // m + 1
n -= ((n - v[m]) // m + 1) * m
# Simply skip the ones I don't need
while m and v[m] > n:
m -= 1

fout.write(str(c))
fin.close()
fout.close()
</syntaxhighlight>

2301 - Secv

2024-02-01T14:47:43Z

Raul: Pagină nouă: Se consideră două numerele naturale <code>K</code> și <code>S</code> și un șir de <code>N</code> numere naturale <code>a[1]</code>, <code>a[2]</code>,…, <code>a[N]</code>. O secvenţă de lungime <code>K</code> este un subşir format din <code>K</code> elemente aflate pe poziţii consecutive în şir: <code>a[i]</code>, <code>a[i+1]</code>,.., <code>a[i+k-1]</code>. Parcurgând șirul de la stânga la dreapta, începând cu primul element, se elimină prima secvență...

Se consideră două numerele naturale <code>K</code> și <code>S</code> și un șir de <code>N</code> numere naturale <code>a[1]</code>, <code>a[2]</code>,…, <code>a[N]</code>. O secvenţă de lungime <code>K</code> este un subşir format din <code>K</code> elemente aflate pe poziţii consecutive în şir: <code>a[i]</code>, <code>a[i+1]</code>,.., <code>a[i+k-1]</code>. Parcurgând șirul de la stânga la dreapta, începând cu primul element, se elimină prima secvență de lungime <code>K</code>, cu suma elementelor strict mai mare decât numărul <code>S</code>. În urma ștergerii șirul va avea <code>N-K</code> elemente: <code>a[1]</code>, <code>a[2]</code>,…, <code>a[N-K]</code>. Operația de ștergere continuă după aceleași reguli până când nu mai există secvențe care pot fi eliminate.

= Cerința =
Să se scrie un program care citind numerele <code>N</code>, <code>K</code>, <code>S</code> și cele <code>N</code> elemente din șir rezolvă cerințele:

1) Determină numărul secvențelor care se vor elimina respectând condiția din enunț.

2) Considerând că în șirul citit nu sunt posibile eliminări de secvențe conform condiției din enunț, programul determină numărul de elemente <code>a[i]</code> din șir cu proprietatea următoare: ștergerea lui <code>a[i]</code> conduce la obținerea unui șir în care se mai poate elimina cel puțin o secvență de <code>K</code> elemente cu sumă strict mai mare ca <code>S</code>.

= Date de intrare =
Fișierul de intrare <code>secv.in</code> conține pe prima linie un număr natural <code>P</code>; numărul <code>P</code> poate avea doar valoarea <code>1</code> sau valoarea <code>2</code>. A doua linie conține, în această ordine, separate prin câte un spațiu, numerele <code>N</code>, <code>K</code> și <code>S</code>. A treia linie conține, în ordine elementele șirului, despărțite prin câte un spațiu.

= Date de ieșire =
Dacă valoarea lui <code>P</code> este <code>1</code>, se va rezolva numai '''cerinta 1)'''. În acest caz, fişierul de ieşire <code>secv.out</code> va conține pe prima linie un număr natural reprezentând numărul secvențelor eliminate.

Dacă valoarea lui <code>P</code> este <code>2</code>, se va rezolva numai '''cerinta 2)'''. În acest caz, fişierul de ieşire <code>secv.out</code> va conține pe prima linie un număr natural reprezentând numărul elementelor din șir care au proprietatea că ștergerea fiecăruia în parte ar genera un șir în care se mai pot elimina cel puțin o secvență de <code>K</code> elemente cu sumă strict mai mare ca <code>S</code>.

= Restricții și precizări =

* <code>0 < N ≤ 1 000 000</code> și <code>K ≤ N</code>
* <code>0 < S ≤ 1 000 000 000</code>
* <code>0 ≤ a[1], a[2],...,a[N] ≤ 1.000</code>

= Exemplul 1: =
<code>secv.in</code>
1
14 3 7
1 2 1 3 1 4 5 2 1 4 1 8 2 3
<code>secv.out</code>
3

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

MAXN = 1000001
A = [0] * MAXN
B = [0] * MAXN
N = 0
K = 0
S = 0
P = 0
i = 0

def solve1():
ul = 0
Nr = 0
global i
for i in range(1, N + 1):
B[ul + 1] = B[ul] + A[i] # sume partiale
ul += 1
if ul >= K and B[ul] - B[ul - K] > S:
Nr += 1
ul -= K
print(Nr)

def solve2():
ul = 0
global i
for i in range(1, N + 1):
B[ul + 1] = B[ul] + A[i]
ul += 1
if ul >= K and B[ul] - B[ul - K] > S:
print(ul - K + 1, end=' ')
ul -= K

def solve3():
pr = 1
ul = 0
Nr = 0
global i
for i in range(1, N + 1):
A[i] += A[i - 1]
for i in range(1, N + 1):
if i + K <= N:
while pr <= ul and A[i + K] - A[i - 1] >= A[B[ul] + K] - A[B[ul] - 1]:
ul -= 1
B[ul + 1] = i
ul += 1
if A[B[pr] + K] - A[B[pr] - 1] - (A[i] - A[i - 1]) > S:
Nr += 1
if B[pr] == i - K:
pr += 1
print(Nr)

def main():
sys.stdin = open('secv.in', 'r')
sys.stdout = open('secv.out', 'w')
global N, K, S, P, i
P = int(input())
N, K, S = map(int, input().split())
A[1:N+1] = map(int, input().split())
if P == 1:
solve1()
if P == 2:
solve3()

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

2131 - Ghiozdan

2024-01-31T16:44:42Z

Raul: Pagină nouă: = Cerința = Iulică este acasă și trebuie să ajungă la patinoar. Patinoarul se află la exact <code>d</code> km de mers pe jos, astfel încât, dacă am considera un sistem de coordonate, casa lui Iulică se află în punctul <code>0</code> și patinoarul se află în punctul <code>d</code>. Între parc și patinoar există <code>k</code> magazine din care se poate cumpăra pâine, magazine situate la <code>a[i]</code> km (<code>1 <= i <= k</code>) față de casa lui I...

= Cerința =
Iulică este acasă și trebuie să ajungă la patinoar. Patinoarul se află la exact <code>d</code> km de mers pe jos, astfel încât, dacă am considera un sistem de coordonate, casa lui Iulică se află în punctul <code>0</code> și patinoarul se află în punctul <code>d</code>.

Între parc și patinoar există <code>k</code> magazine din care se poate cumpăra pâine, magazine situate la <code>a[i]</code> km (<code>1 <= i <= k</code>) față de casa lui Iulică, în aceeași direcție în care se află patinoarul. Fiind foarte departe, Iulică nu poate ajunge foarte repede la patinoar. Astfel, înainte să plece, mama lui Iulică îi da un ghiozdan care poate căra cel mult <code>g</code> pâini, inițial cu <code>g</code> pâini în el. Știind că Iulică poate mânca o pâine sau poate să stea nemâncat pe parcursul unui km, și că poate sta nemâncat maximum <code>t</code> km pe întreg traseul, aflați capacitatea minimă <code>g</code> pe care o poate avea ghiozdanul, astfel încât Iulică să poată ajunge la patinoar fără să moară de foame. Iulică îşi poate umple ghiozdanul de la fiecare magazin gratuit.

= Date de intrare =
Fișierul de intrare <code>ghiozdan.in</code> conține pe prima linie trei numere naturale <code>d</code>, <code>k</code>, <code>t</code>, separate prin câte un spațiu, fiecare având semnificațiile din enunț. Linia a doua conține <code>k</code> numere naturale <code>a[i]</code> (<code>1 <= i <= k</code>), în ordine crescătoare, reprezentând distanța de la casa lui Iulică la magazinul <code>i</code>.

= Date de ieșire =
Fișierul de ieșire <code>ghiozdan.out</code> conține pe prima linie un singur număr natural reprezentând capacitatea <code>g</code> minimă a ghiozdanului.

= Restricții și precizări =

* <code>1 <= d <= 10000000</code>
* <code>0 <= k <= 100000</code>
* <code>1 <= a[i] <= d, 1 <= i <= k</code>
* <code>0 <= t <= d</code>
* <code>20%</code> din teste vor avea valoarea <code>t = 0</code>

= Exemplu: =
<code>ghiozdan.in</code>
6 1 2
3
<code>ghiozdan.out</code>
2

=== Explicație ===
Se observă că dacă ghiozdanul putea căra maximum o pâine, Iulică nu ar fi putut ajunge la patinoar.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
mport sys

sys.stdin = open("ghiozdan.in", "r")
sys.stdout = open("ghiozdan.out", "w")

NMax = 100002

d, k, t = map(int, input().split())
a = [0] * (NMax + 1)
a[0] = 0
for i in range(1, k + 1):
a[i] = int(input())
a[k + 1] = d

def OK(dim):
drum_ramas = t
for i in range(1, k + 1):
if a[i] - a[i - 1] > dim:
drum_ramas -= (a[i] - a[i - 1] - dim)
if drum_ramas < 0:
return 0
return 1

def cautbin(lo, hi):
while lo <= hi:
mid = (lo + hi) // 2
ok1 = OK(mid)
ok2 = OK(mid - 1)
if ok1 == 1 and ok2 == 0:
return mid
elif ok1 == 1:
hi = mid - 1
elif ok2 == 0:
lo = mid + 1
return 0

G = cautbin(0, d)
print(G)
</syntaxhighlight>

3326 - Turneu1

2024-01-31T16:41:09Z

Raul: Pagină nouă: = Cerință = Impresarul unei formații de muzică trebuie să primească oferte de spectacole și eventual anulări de spectacole din diferite orașe. Orașele sunt codificate prin numerele <code>1</code> , <code>2</code> ,.., <code>n</code> (<code>1 ≤ n ≤ 20</code>) și fiecare oraș poate organiza cel mult un spectacol. Impresarul ține legătura cu organizatorii de spectacole din aceste orașe și actualizează în permanență datele obținute. Prin fax el primește...

= Cerință =
Impresarul unei formații de muzică trebuie să primească oferte de spectacole și eventual anulări de spectacole din diferite orașe. Orașele sunt codificate prin numerele <code>1</code> , <code>2</code> ,.., <code>n</code> (<code>1 ≤ n ≤ 20</code>) și fiecare oraș poate organiza cel mult un spectacol. Impresarul ține legătura cu organizatorii de spectacole din aceste orașe și actualizează în permanență datele obținute. Prin fax el primește <code>m</code> (<code>m ≤ 100</code>) mesaje, care pot fi de unul din cele două tipuri:

<code>D</code>

<code>nr</code>

sau

<code>N</code>

<code>nr</code>

Cu semnificațiile: pentru primul mesaj se dorește organizarea unui concert în orașul <code>nr</code>, iar pentru a-l doilea mesaj se dorește anularea spectacolului din orașul <code>nr</code> . Un mesaj este format din exact două linii.

Se cere:

a) Să se afișeze orașele în care va concerta formația de muzică (pe aceeași linie cu un spațiu între ele).

b) Să se afișeze orașul (sau orașele dacă sunt mai multe, pe aceeași linie cu un spațiu între ele) în care organizatorii sunt cei mai nedeciși (adică au anulat și propus organizarea de spectacol în orașul lor de cele mai multe ori).

c) Să se afișeze numărul de orașe care nu au trimis nici un mesaj impresarului.

= Date de intrare =
Programul citește de la tastatură numărul <code>n m</code>, cele <code>m</code> mesaje: un caracter care poate sa fie <code>'D'</code> sau <code>'N'</code> și un număr natural <code>a</code>.

= Date de ieșire =
Programul afișează pe prima linie orașele în care va concerta formația, pe următoarea linie orașele în care organizatorii sunt cei mai indeciși și pe ultima linie numărul de orașe care nu au trimis nici un mesaj impresarului.

= Restricții și precizări =

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

= Exemplu: =
'''Intrare'''
5 6
D
2
D
3
N
3
D
3
D
5
N
2
'''Ieșire'''
3 5
3
2

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
f = [0]*101
f1 = [0]*101

def main():
n, m = map(int, input().split())
for i in range(1, m+1):
c, a = input().split()
a = int(a)
f1[a] += 1
if c == 'D':
f[a] += 1
else:
f[a] -= 1
maxx = 0
cnt1 = 0
for i in range(1, n+1):
if f1[i] == 0:
cnt1 += 1
if f[i] > 0:
print(i, end=' ')
if f1[i] > maxx:
maxx = f1[i]
print()
for i in range(1, n+1):
if f1[i] == maxx:
print(i, end=' ')
print()
print(cnt1)

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

2976 - maxim7

2024-01-31T16:37:58Z

Raul:

Dintr-un șir format din <code>N</code> cifre, numerotate de la <code>1</code> la <code>N</code>, Ionel ia exact <code>M</code> cifre aflate pe poziții consecutive. El lipește cifrele luate sau le amestecă și apoi le lipește pentru a obține cu ele un număr cât mai mare.

= Cerința =
Cunoscând <code>N</code>, <code>M</code> și cele <code>N</code> cifre din șir, să se determine:

1) cel mai mare număr care se poate obține din primele <code>M</code> dintre cele <code>N</code> cifre date;

2) de unde va lua Ionel <code>M</code> cifre aflate pe poziții consecutive pentru a obține un număr maxim; dacă sunt mai multe poziții corespunzătoare unui număr maxim, alegerea se va face astfel încât numărul format din cifrele rămase, în ordinea în care erau, să fie cât mai mare posibil; dacă și în acest caz există mai multe soluții, se alege poziția maximă.

= Date de intrare =
Din fișierul <code>maxim.in</code> se citesc: <code>P</code> de pe prima linie, reprezentând cerința problemei (<code>1</code> sau <code>2</code>), <code>N</code> și <code>M</code> de pe a doua linie, despărțite printr-un spațiu, cu semnificația din enunț, iar de pe linia a treia, se citesc cele <code>N</code> cifre, despărțite prin câte un spațiu.

= Date de ieșire =
În fișierul <code>maxim.out</code> se scrie:

- pentru <code>P = 1</code>: numărul maxim care se poate obține cu ajutorul primelor <code>M</code> cifre dintre cele <code>N</code> date, fără spații între cifrele numărului;

- pentru <code>P = 2</code>: un număr reprezentând poziția cerută.

= Restricții și precizări =

* <code>M</code>, <code>N</code> numere naturale, <code>1 ≤ N ≤ 500000</code>, <code>1 ≤ M ≤ 1000</code>, <code>M < N</code>
* Cele <code>N</code> valori de pe linia a treia sunt numere naturale între <code>0</code> și <code>9</code>
* Secvența de <code>N</code> cifre poate să înceapă cu cel mult <code>M - 1</code> cifre nule.
* <code>30</code> de puncte se vor obține cu rezolvarea cerinței <code>1</code>, iar <code>60</code> de puncte se vor obține cu rezolvarea cerinței <code>2</code>.
* Pentru <code>50%</code> dintre teste, <code>N < 1000</code> și <code>M < 10</code>.
* În concurs s-au acordat <code>10</code> puncte din oficiu. Aici se acordă pentru exemplele din enunț.

= Exemplul 1: =
<code>maxim.in</code>
1
10 3
7 2 8 1 0 0 4 7 8 1
<code>maxim.out</code>
872

=== Explicație ===
Se rezolvă cerința <code>1</code>. Cu primele trei cifre dintre cele <code>10</code> cifre date se pot forma numerele: <code>728</code>, <code>782</code>, <code>287</code>, <code>278</code>, <code>827</code>, <code>872</code>, cel mai mare fiind <code>872</code>.

= Exemplul 2: =
<code>maxim.in</code>
2

10 3
7 2 8 1 0 0 4 7 8 1
<code>maxim.out</code>
7

=== Explicație ===
Se rezolvă cerința <code>2</code>. Alegând cifrele începând de la poziția a <code>7</code>-a (cifrele <code>4</code>, <code>7</code> și <code>8</code>), se va forma numărul <code>874</code>, care este cel mai mare posibil.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import array as arr

dim = 500008
v = arr.array('h', [0] * dim)

w = [0] * 10
W = [0] * 10

def main():
with open("maxim.in", "r") as f, open("maxim.out", "w") as g:
N, i, j, poz, M, x, z, k, ii = 0, 0, 0, 0, 0, 0, 0, 0, 0
ok = 1
p = int(f.readline())

input_data = f.readline().split()
N = int(input_data[0])
M = int(input_data[1])

v[1:N+1] = map(int, f.readline().split())

for i in range(1, N+1):
x = v[i]
w[x] += 1

if p == 1:
if w[0] == M:
g.write("0")
else:
for j in range(9, -1, -1):
for i in range(1, w[j]+1):
g.write(str(j))

if p == 2:
for j in range(10):
W[j] = w[j]

for i in range(M+1, N+1):
x = v[i]
w[x] += 1
z = v[i-M]
w[z] -= 1
ok = 1
for j in range(9, 0, -1):
if W[j] != w[j]:
if w[j] > W[j]:
ok = 2
W = w[:]
poz = i - M + 1
else:
ok = 0
break
if ok == 1:
poz = i - M + 1

g.write(str(poz))

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

2976 - maxim7

2024-01-31T16:36:55Z

Raul:

Dintr-un șir format din <code>N</code> cifre, numerotate de la <code>1</code> la <code>N</code>, Ionel ia exact <code>M</code> cifre aflate pe poziții consecutive. El lipește cifrele luate sau le amestecă și apoi le lipește pentru a obține cu ele un număr cât mai mare.

= Cerința =
Cunoscând <code>N</code>, <code>M</code> și cele <code>N</code> cifre din șir, să se determine:

1) cel mai mare număr care se poate obține din primele <code>M</code> dintre cele <code>N</code> cifre date;

2) de unde va lua Ionel <code>M</code> cifre aflate pe poziții consecutive pentru a obține un număr maxim; dacă sunt mai multe poziții corespunzătoare unui număr maxim, alegerea se va face astfel încât numărul format din cifrele rămase, în ordinea în care erau, să fie cât mai mare posibil; dacă și în acest caz există mai multe soluții, se alege poziția maximă.

= Date de intrare =
Din fișierul <code>maxim.in</code> se citesc: <code>P</code> de pe prima linie, reprezentând cerința problemei (<code>1</code> sau <code>2</code>), <code>N</code> și <code>M</code> de pe a doua linie, despărțite printr-un spațiu, cu semnificația din enunț, iar de pe linia a treia, se citesc cele <code>N</code> cifre, despărțite prin câte un spațiu.

= Date de ieșire =
În fișierul <code>maxim.out</code> se scrie:

- pentru <code>P = 1</code>: numărul maxim care se poate obține cu ajutorul primelor <code>M</code> cifre dintre cele <code>N</code> date, fără spații între cifrele numărului;

- pentru <code>P = 2</code>: un număr reprezentând poziția cerută.

= Restricții și precizări =

* <code>M</code>, <code>N</code> numere naturale, <code>1 ≤ N ≤ 500000</code>, <code>1 ≤ M ≤ 1000</code>, <code>M < N</code>
* Cele <code>N</code> valori de pe linia a treia sunt numere naturale între <code>0</code> și <code>9</code>
* Secvența de <code>N</code> cifre poate să înceapă cu cel mult <code>M - 1</code> cifre nule.
* <code>30</code> de puncte se vor obține cu rezolvarea cerinței <code>1</code>, iar <code>60</code> de puncte se vor obține cu rezolvarea cerinței <code>2</code>.
* Pentru <code>50%</code> dintre teste, <code>N < 1000</code> și <code>M < 10</code>.
* În concurs s-au acordat <code>10</code> puncte din oficiu. Aici se acordă pentru exemplele din enunț.

= Exemplul 1: =
<code>maxim.in</code>
1
10 3
7 2 8 1 0 0 4 7 8 1
<code>maxim.out</code>
872

=== Explicație ===
Se rezolvă cerința <code>1</code>. Cu primele trei cifre dintre cele <code>10</code> cifre date se pot forma numerele: <code>728</code>, <code>782</code>, <code>287</code>, <code>278</code>, <code>827</code>, <code>872</code>, cel mai mare fiind <code>872</code>.

= Exemplul 2: =
<code>maxim.in</code>
2
<syntaxhighlight lang="python" line="1">
import array as arr

dim = 500008
v = arr.array('h', [0] * dim)

w = [0] * 10
W = [0] * 10

def main():
with open("maxim.in", "r") as f, open("maxim.out", "w") as g:
N, i, j, poz, M, x, z, k, ii = 0, 0, 0, 0, 0, 0, 0, 0, 0
ok = 1
p = int(f.readline())

input_data = f.readline().split()
N = int(input_data[0])
M = int(input_data[1])

v[1:N+1] = map(int, f.readline().split())

for i in range(1, N+1):
x = v[i]
w[x] += 1

if p == 1:
if w[0] == M:
g.write("0")
else:
for j in range(9, -1, -1):
for i in range(1, w[j]+1):
g.write(str(j))

if p == 2:
for j in range(10):
W[j] = w[j]

for i in range(M+1, N+1):
x = v[i]
w[x] += 1
z = v[i-M]
w[z] -= 1
ok = 1
for j in range(9, 0, -1):
if W[j] != w[j]:
if w[j] > W[j]:
ok = 2
W = w[:]
poz = i - M + 1
else:
ok = 0
break
if ok == 1:
poz = i - M + 1

g.write(str(poz))

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

10 3
7 2 8 1 0 0 4 7 8 1
<code>maxim.out</code>
7

=== Explicație ===
Se rezolvă cerința <code>2</code>. Alegând cifrele începând de la poziția a <code>7</code>-a (cifrele <code>4</code>, <code>7</code> și <code>8</code>), se va forma numărul <code>874</code>, care este cel mai mare posibil.

== Încărcare soluție ==

=== Lipește codul aici ===

2976 - maxim7

2024-01-31T16:35:36Z

Raul: Pagină nouă: Dintr-un șir format din <code>N</code> cifre, numerotate de la <code>1</code> la <code>N</code>, Ionel ia exact <code>M</code> cifre aflate pe poziții consecutive. El lipește cifrele luate sau le amestecă și apoi le lipește pentru a obține cu ele un număr cât mai mare. = Cerința = Cunoscând <code>N</code>, <code>M</code> și cele <code>N</code> cifre din șir, să se determine: 1) cel mai mare număr care se poate obține din primele <code>M</code> dintre cele <c...

Dintr-un șir format din <code>N</code> cifre, numerotate de la <code>1</code> la <code>N</code>, Ionel ia exact <code>M</code> cifre aflate pe poziții consecutive. El lipește cifrele luate sau le amestecă și apoi le lipește pentru a obține cu ele un număr cât mai mare.

= Cerința =
Cunoscând <code>N</code>, <code>M</code> și cele <code>N</code> cifre din șir, să se determine:

1) cel mai mare număr care se poate obține din primele <code>M</code> dintre cele <code>N</code> cifre date;

2) de unde va lua Ionel <code>M</code> cifre aflate pe poziții consecutive pentru a obține un număr maxim; dacă sunt mai multe poziții corespunzătoare unui număr maxim, alegerea se va face astfel încât numărul format din cifrele rămase, în ordinea în care erau, să fie cât mai mare posibil; dacă și în acest caz există mai multe soluții, se alege poziția maximă.

= Date de intrare =
Din fișierul <code>maxim.in</code> se citesc: <code>P</code> de pe prima linie, reprezentând cerința problemei (<code>1</code> sau <code>2</code>), <code>N</code> și <code>M</code> de pe a doua linie, despărțite printr-un spațiu, cu semnificația din enunț, iar de pe linia a treia, se citesc cele <code>N</code> cifre, despărțite prin câte un spațiu.

= Date de ieșire =
În fișierul <code>maxim.out</code> se scrie:

- pentru <code>P = 1</code>: numărul maxim care se poate obține cu ajutorul primelor <code>M</code> cifre dintre cele <code>N</code> date, fără spații între cifrele numărului;

- pentru <code>P = 2</code>: un număr reprezentând poziția cerută.

= Restricții și precizări =

* <code>M</code>, <code>N</code> numere naturale, <code>1 ≤ N ≤ 500000</code>, <code>1 ≤ M ≤ 1000</code>, <code>M < N</code>
* Cele <code>N</code> valori de pe linia a treia sunt numere naturale între <code>0</code> și <code>9</code>
* Secvența de <code>N</code> cifre poate să înceapă cu cel mult <code>M - 1</code> cifre nule.
* <code>30</code> de puncte se vor obține cu rezolvarea cerinței <code>1</code>, iar <code>60</code> de puncte se vor obține cu rezolvarea cerinței <code>2</code>.
* Pentru <code>50%</code> dintre teste, <code>N < 1000</code> și <code>M < 10</code>.
* În concurs s-au acordat <code>10</code> puncte din oficiu. Aici se acordă pentru exemplele din enunț.

= Exemplul 1: =
<code>maxim.in</code>
1
10 3
7 2 8 1 0 0 4 7 8 1
<code>maxim.out</code>
872

=== Explicație ===
Se rezolvă cerința <code>1</code>. Cu primele trei cifre dintre cele <code>10</code> cifre date se pot forma numerele: <code>728</code>, <code>782</code>, <code>287</code>, <code>278</code>, <code>827</code>, <code>872</code>, cel mai mare fiind <code>872</code>.

= Exemplul 2: =
<code>maxim.in</code>
2
<syntaxhighlight lang="python" line="1">
import array as arr

dim = 500008
v = arr.array('h', [0] * dim)

w = [0] * 10
W = [0] * 10

with open("maxim.in", "r") as f, open("maxim.out", "w") as g:
N, i, j, poz, M, x, z, k, ii = 0, 0, 0, 0, 0, 0, 0, 0, 0
ok = 1
p = int(f.readline())

input_data = f.readline().split()
N = int(input_data[0])
M = int(input_data[1])

v[1:N+1] = map(int, f.readline().split())

for i in range(1, N+1):
x = v[i]
w[x] += 1

if p == 1:
if w[0] == M:
g.write("0")
else:
for j in range(9, -1, -1):
for i in range(1, w[j]+1):
g.write(str(j))

if p == 2:
for j in range(10):
W[j] = w[j]

for i in range(M+1, N+1):
x = v[i]
w[x] += 1
z = v[i-M]
w[z] -= 1
ok = 1
for j in range(9, 0, -1):
if W[j] != w[j]:
if w[j] > W[j]:
ok = 2
W = w[:]
poz = i - M + 1
else:
ok = 0
break
if ok == 1:
poz = i - M + 1

g.write(str(poz))
</syntaxhighlight>

10 3
7 2 8 1 0 0 4 7 8 1
<code>maxim.out</code>
7

=== Explicație ===
Se rezolvă cerința <code>2</code>. Alegând cifrele începând de la poziția a <code>7</code>-a (cifrele <code>4</code>, <code>7</code> și <code>8</code>), se va forma numărul <code>874</code>, care este cel mai mare posibil.

== Încărcare soluție ==

=== Lipește codul aici ===