Bitnami MediaWiki - User contributions [en]

1730 - S Stabil

2024-01-04T21:18:58Z

Corjuc Eunice: Pagină nouă: Numim număr sstabil orice număr natural care este format dintr-o singură cifră sau care are suma oricăror două cifre vecine strict mai mare decât nouă. Asupra oricărui număr care nu este sstabil se pot efectua operaţii de înlocuire a oricăror două cifre vecine care au suma strict mai mică decât zece cu o cifră egală cu suma lor. Operaţiile de înlocuire pot fi aplicate, în acelaşi condiţii, şi asupra numerelor rezultate după fiecare înlocuire, de c...

Numim număr sstabil orice număr natural care este format dintr-o singură cifră sau care are suma oricăror două cifre vecine strict mai mare decât nouă.

Asupra oricărui număr care nu este sstabil se pot efectua operaţii de înlocuire a oricăror două cifre vecine care au suma strict mai mică decât zece cu o cifră egală cu suma lor.

Operaţiile de înlocuire pot fi aplicate, în acelaşi condiţii, şi asupra numerelor rezultate după fiecare înlocuire, de câte ori este nevoie, până când se obţine un număr sstabil.

De exemplu, <code>291</code> este număr sstabil deoarece <code>2+9>9</code> şi <code>9+1>9</code>, iar <code>183</code> nu este sstabil pentru că <code>1+8<10</code>. Din numărul <code>2453</code>, efectuând o singură înlocuire, putem obţine <code>653</code> sau <code>293</code> (număr sstabil) sau <code>248</code>. Numărul <code>653</code>, nefiind sstabil, permite o nouă operaţie de înlocuire, obţinând astfel numărul <code>68</code>, care este sstabil. Analog, din numărul <code>248</code> se poate obţine numărul sstabil <code>68</code>.

= Cerința =
Scrieţi un program care să determine cel mai mare număr natural sstabil care se poate obţine dintr-un număr natural dat, aplicând una sau mai multe operaţii de înlocuire de tipul menţionat.

= Date de intrare =
Fişierul de intrare <code>input.txt</code> conţine pe prima linie un număr natural <code>n</code>, reprezentând numărul de cifre al numărului dat, iar pe linia a doua, separate prin câte un spaţiu, cifrele acestui număr.

= Date de ieșire =
Fişierul de ieşire <code>output.txt</code> va conţine pe o linie numărul sstabil maxim obţinut.

= Restricții și precizări =

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

== Exemplul 1 ==
input.txt:

5

1 0 4 5 1

output.txt:

191

Explicație:

10451 → 1091 → 191.

== Exemplul 2 ==
input.txt:

5

5 2 8 3 2

output.txt:

785

Explicație:

<code>52832 → 7832 → 785</code>.

== Exemplul 3 ==
input.txt:

9999999999999

1 2 3 4 5

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(1<=n<=1000000):
print("Constrangeri neindeplinite")
exit()

with open("input.txt", "r") as input_file, open("output.txt", "w") as output_file:
n = int(input_file.readline())
ver(n)
a = list(map(int, input_file.readline().split()))
b = [0] * 1000005

k = 0
r = n

while r > 0:
j = r
s = 0

while j > 0 and s < 10:
s += a[j - 1]
j -= 1

k += 1

if s < 10:
b[k] = s
r = j
else:
if k == 1:
p = r
t = a[p - 1]

while s - t >= 10:
p -= 1
t += a[p - 1]

b[k] = t
r = p - 1
else:
p = r
t = a[p - 1]

while s - t > 9 or t + b[k - 1] < 10:
p -= 1
t += a[p - 1]

b[k] = t
r = p - 1

for i in range(k, 0, -1):
print(b[i], end="", file=output_file)

</syntaxhighlight>

1656 - Unu Zero

2024-01-04T20:53:57Z

Corjuc Eunice: Pagină nouă: Se consideră un şir format din <code>N+2</code> cifre binare, care conţine cel puţin o cifră <code>1</code> şi cel puţin trei cifre <code>0</code>; prima şi ultima cifră a şirului sunt <code>0</code>. Numim <code>1-secvenţă</code> o succesiune formată numai din cifre <code>1</code>, aflate pe poziţii consecutive în acest şir, delimitată de câte o cifră <code>0</code>. Corina construieşte un astfel de şir, în care numărul de cifre <code>1</code> ale fi...

Se consideră un şir format din <code>N+2</code> cifre binare, care conţine cel puţin o cifră <code>1</code> şi cel puţin trei cifre <code>0</code>; prima şi ultima cifră a şirului sunt <code>0</code>.

Numim <code>1-secvenţă</code> o succesiune formată numai din cifre <code>1</code>, aflate pe poziţii consecutive în acest şir, delimitată de câte o cifră <code>0</code>.

Corina construieşte un astfel de şir, în care numărul de cifre <code>1</code> ale fiecărei <code>1-secvenţe</code> să fie cuprins între două numere naturale date, <code>p</code> şi <code>q</code> (<code>p ≤ q</code>).

= Cerința =
Scrieţi un program care să determine un număr natural <code>K</code>, egal cu restul împărţirii la <code>666013</code> a numărului de şiruri distincte, de tipul celui construit de Corina.

= Date de intrare =
Fişierul de intrare <code>input.txt</code> conţine pe prima linie numărul natural <code>N</code>, iar pe cea de a doua linie numerele naturale <code>p</code> şi <code>q</code> ( <code>p ≤ q</code> ), separate printr-un spaţiu.

= Date de ieșire =
Fişierul de ieşire <code>output.txt</code> va conţine pe prima linie numărul natural <code>K</code> cerut.

= Restricții și precizări =

* <code>1 ≤ p ≤ q < N < 1.000.000</code>

== Exemplul 1 ==
input.txt:

5

2 3

output.txt:

8

Explicație:

<code>0000110</code>

<code>0001100</code>

<code>0001110</code>

<code>0011000</code>

<code>0011100</code>

<code>0110000</code>

<code>0110110</code>

<code>0111000</code>

== Exemplul 2 ==
input.txt:

999999999

2 3

Output:

Constrangeri neindeplinite

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

def ver(n, p, q):
if not(1<=n<=1000000):
print("Constrangeri neindeplinite")
exit()
if not(1<=p<=1000000):
print("Constrangeri neindeplinite")
exit()
if not(1<=q<=1000000):
print("Constrangeri neindeplinite")
exit()
if not(p>=q):
print("Constrangeri neindeplinite")
exit()
if not(q>=n):
print("Constrangeri neindeplinite")
exit()

def main():
with open("input.txt", "r") as in_file, open("output.txt", "w") as out_file:

n=int(in_file.readline().strip())
a, b = map(int, in_file.readline().split())

ver(n,a, b)

z = [0] * (n + 1)
s = [0] * (n + 1)
u = [0] * (n + 1)

z[0] = 1
s[0] = 1

for i in range(1, n + 1):
z[i] = z[i - 1] + u[i - 1] # daca punem 0
z[i] %= mod

if i - a >= 0:
if i - b - 1 >= 0:
u[i] = s[i - a] - s[i - b - 1]
else:
u[i] = s[i - a]

if u[i] < 0:
u[i] += mod
u[i] %= mod

s[i] = s[i - 1] + z[i]
s[i] %= mod

result = (z[n] + u[n] - 1 + (z[n] + u[n] - 1 < 0) * mod) % mod
out_file.write(str(result) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

1537 - 7 Segmente

2024-01-04T20:47:01Z

Corjuc Eunice: Pagină nouă: Un indicator cu <code>7</code> segmente este un dispozitiv de afişaj electronic destinat afişării unei cifre zecimale. Aceste dispozitive sunt utilizate pe scară largă în ceasuri digitale, contoare electronice şi alte aparate, pentru afişarea informaţiilor numerice. Cele <code>7</code> segmente au fost notate cu literele <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code>, <code>e</code>, <code>f</code>, <code>g</code>, după modelul din figura de mai jos....

Un indicator cu <code>7</code> segmente este un dispozitiv de afişaj electronic destinat afişării unei cifre zecimale. Aceste dispozitive sunt utilizate pe scară largă în ceasuri digitale, contoare electronice şi alte aparate, pentru afişarea informaţiilor numerice. Cele <code>7</code> segmente au fost notate cu literele <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code>, <code>e</code>, <code>f</code>, <code>g</code>, după modelul din figura de mai jos.

Proiectarea diverselor sisteme de afişaj trebuie să ţină cont şi de puterea necesară pentru afişarea unei cifre. Pentru aprinderea unui segment este necesară o putere de <code>1</code> mW. Astfel, în funcţie de cifra afişată, dispozitivul necesită o putere egală cu numărul de segmente aprinse la afişarea cifrei respective. Puterea necesară pentru afişarea unui număr natural este egală cu suma puterilor necesare afişării fiecăreia dintre cifrele sale.

= Cerința =
Să se scrie un program care citeşte două numere naturale nenule <code>n</code> şi <code>p</code>, (numărul <code>n</code> având toate cifrele nenule)şi calculează:

* numărul natural <code>k</code> reprezentând puterea necesară pentru afişarea numărului <code>n</code>;
* cel mai mare număr natural <code>t</code>, format numai din cifre nenule, mai mic sau egal decât <code>n</code>, care necesită pentru afişare o putere de cel mult <code>p</code> mW.

= Date de intrare =
Prima linie a fişierului de intrare <code>input.txt conţine</code> două numere naturale nenule <code>n</code> şi <code>p</code>, (numărul <code>n</code> având toate cifrele nenule), despărţite printr-un spaţiu, cu semnificaţia de mai sus.

= Date de ieșire =
Fişierul de ieşire <code>output.txt</code> va conţine pe o singură linie, cele două numere naturale nenule <code>k</code> şi <code>t</code> (numărul <code>t</code> având toate cifrele nenule), separate printr-un spaţiu, cu semnificaţia de mai sus.

= Restricții și precizări =

* <code>1 ≤ n < 10**19</code>;
* <code>2 ≤ p ≤ 150</code>;

== Exemplul 1 ==
input.txt:

7654 12

output.txt:

18 7511

Explicație:

Numărul n este <code>7654</code>; puterea necesară pentru afişare este <code>3</code> + <code>6</code> + <code>5</code> + <code>4</code> = <code>18</code> mW, iar cel mai mare număr, mai mic sau egal cu <code>7654</code>, format numai din cifre nenule, care necesită pentru afişare o putere de cel mult <code>12</code> mW, este <code>7511</code>.

== Exemplul 2 ==
input.txt:

7654 9999

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n,p):
if not(1<=n<=10**19):
print("Constrangeri neindeplinite")
exit()
if not(2<=p<=150):
print("Constrangeri neindeplinite")
exit()

def main():
with open("input.txt", "r") as f, open("output.txt", "w") as g:
v = [0] * 20
t = [0] * 20
p = 0

pw = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

ver(n,p)

pc = 0
i = 0
nc = 0
aux = 0
dmin = 0
dmax = 0
cifra = 0
egalcif = 1

v[0] = 0
i = 0
while n > 0:
i += 1
v[i] = n % 10
case_dict = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
pc += case_dict.get(n % 10, 0)
n //= 10
v[0] = i
g.write(f"{pc} ")

for i in range(1, v[0] // 2 + 1):
aux = v[i]
v[i] = v[v[0] + 1 - i]
v[v[0] + 1 - i] = aux

nc = p // 2
nc = min(nc, v[0])

for i in range(1, nc + 1):
t[i] = 1

p = p - 2 * nc
t[0] = nc
cc = 1
egalcif = 1
while p > 0 and cc <= t[0]:
dmin = 10
cifra = 1
dmax = 0

for i in range(2, 10):
if t[0] == v[0] and egalcif == 1:
if i <= v[cc] and abs(i - v[cc]) <= dmin and p - pw[i] + pw[1] >= 0:
cifra = i
dmin = abs(i - v[cc])
if t[0] < v[0] or egalcif == 0:
if i >= dmax and p - pw[i] + pw[1] >= 0:
cifra = i
dmax = i

if v[cc] - cifra != 0:
egalcif = 0

p += pw[1]
p -= pw[cifra]
t[cc] = cifra
cc += 1

for i in range(1, t[0] + 1):
g.write(str(t[i]))

g.write("\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0965 - Joc 3

2024-01-04T20:40:41Z

Corjuc Eunice: Pagină nouă: Rareş şi Bogdan vor să facă mişcare în aer liber aşa că s-au gândit la un nou joc. Pe terenul de fotbal, ei au desenat două cercuri concentrice (cu acelaşi centru) şi au împărţit pista cuprinsă între cele două cercuri în <code>n</code> sectoare congruente, ca în desenul de mai jos unde <code>n=16</code>. Ei au etichetat cele n sectoare cu numerele distincte de la <code>1</code> la <code>n</code>, în ordinea acelor de ceasornic. Au stabilit ca jocul să...

Rareş şi Bogdan vor să facă mişcare în aer liber aşa că s-au gândit la un nou joc.

Pe terenul de fotbal, ei au desenat două cercuri concentrice (cu acelaşi centru) şi au împărţit pista cuprinsă între cele două cercuri în <code>n</code> sectoare congruente, ca în desenul de mai jos unde <code>n=16</code>.

Ei au etichetat cele n sectoare cu numerele distincte de la <code>1</code> la <code>n</code>, în ordinea acelor de ceasornic. Au stabilit ca jocul să se desfăşoare astfel:

* Se vor aşeza amândoi în sectorul numerotat cu <code>1</code>, spate în spate.
* Prin sărituri executate simultan în anumite sectoare, copii se vor deplasa pe pistă în sensuri contrare. Bogdan se va deplasa în sensul acelor de ceasornic iar Rareş în sensul contrar. Copii vor executa un număr egal de sărituri.
* O săritură a lui Bogdan are efect deplasarea acestuia din sectorul curent, în sensul acelor de ceasornic, direct în cel de-al <code>x</code>-lea sector de pe pistă. De exemplu, dacă <code>n=16</code> şi <code>x=2</code> atunci, pornind din sectorul <code>1</code>, Bogdan se va deplasa sărind succesiv, în această ordine, în sectoarele etichetate cu: <code>3,5,7,9,...</code>
* O săritură a lui Rareş are efect deplasarea acestuia din sectorul curent, în sens contrar acelor de ceasornic, direct în cel de-al <code>y</code>-lea sector de pe pistă. De exemplu, dacă <code>n=16</code> şi <code>y=3</code> atunci, pornind din sectorul <code>1</code>, Rareş se va deplasa sărind succesiv, în această ordine, în sectoarele: <code>14,11,8,5,...</code>
* Jocul se termină când cei doi copii ajung în urma săriturilor într-un acelaşi sector de pe pistă sau dacă unul din cei doi copii ajunge pentru a doua oară într-un acelaşi sector.

= Cerința =
Scrieţi un program care să citească cele trei numere naturale nenule <code>n</code>, <code>x</code> şi <code>y</code>, şi apoi să determine:

a) numărul <code>t</code> al sectoarelor de pe pistă prin care nu trece niciunul din cei doi copii în urma săriturilor executate până la terminarea jocului;

b) numărul <code>s</code> de sărituri executate de fiecare copil până la terminarea jocului;

c) etichetele <code>b</code> şi <code>r</code> ale sectoarelor în care ajung cei doi copii la terminarea jocului (Bogdan ajunge la finalul jocului în sectorul cu eticheta <code>b</code>, iar Rareş în cel cu eticheta <code>r</code>).

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține conţine pe prima linie trei numere naturale <code>n</code>, <code>x</code> şi <code>y</code>, separate prin câte un spaţiu, cu semnificaţia din enunţ.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie cele patru numere naturale determinate de program: <code>t</code>, <code>s</code>, <code>b</code> şi <code>r</code>, separate prin câte un spaţiu, în această ordine, cu semnificaţia din enunţ.

= Restricții și precizări =

* <code>20 ≤ n ≤ 30000</code>

== Exemplul 1 ==
input.txt:

16 2 3

output.txt:

4 8 1 9

Explicație:

Cei doi copii, executând simultan sărituri, trec până la terminarea jocului prin sectoarele:

Jocul se termină după <code>s=8</code> sărituri deoarece Bodgan ajunge din nou în sectorul cu eticheta cu <code>b=1</code>. La finalul jocului Rareş se află în sectorul cu eticheta cu <code>r=9</code>. Cei doi copii nu au trecut prin <code>t=4</code> sectoare ale căror etichete sunt: <code>4,6,10,16</code>.

== Exemplul 2 ==
input.txt:

16 6 2

output.txt:

12 2 13 13

Explicație:

Cei doi copii, executând simultan sărituri, trec până la terminarea jocului prin sectoarele:

Jocul se termină după <code>s=2</code> sărituri deoarece Bodgan şi Rareş ajung amândoi în sectorul cu eticheta cu <code>b=r=13</code>. Cei doi copii nu au trecut prin <code>t=12</code> sectoare ale căror etichete sunt: <code>2,3,4,5,6,8,9,10,11,12,14,16</code>.

== Exemplul 3 ==
input.txt:

99999999999 6 2

Output:

Constrangeri neindeplinite

== Rezolvare: ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(20<=n<=30000):
print("Constrangeri neindeplinite")
exit()

def main():
with open("input.txt", "r") as f:
with open("output.txt", "w") as g:
v = [0] * 40001
n, x, y = map(int, f.readline().split())
ver(n)
t = 0
s = 0
b = 1
r = 1
v[1] = 11
t = n - 1

while True:
s += 1
b += x
r -= y

if r < 1:
r += n

if b > n:
b -= n

if v[b] == 0:
t -= 1

if v[r] == 0 and b != r:
t -= 1

v[b] += 1
v[r] += 10

if b == r or v[r] // 10 == 2 or v[b] % 10 == 2:
break

g.write(f"{t} {s} {b} {r}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2192 - Talent

2024-01-04T20:33:57Z

Corjuc Eunice: Pagină nouă: ''Românii au talent!'' Atraşi de marele premiu oferit de organizatorii concursului ''Românii au talent'', la preselecţia organizată la Piatra Neamţ au venit foarte mulţi români să demonstreze că au talent. La înscriere, fiecare participant a primit câte un număr de concurs, reprezentat de un număr natural nenul. Unii dintre participanţi pot avea statut special, fiind admişi direct în semifinale, ca urmare a rezultatelor deosebite obţinute la ediţiile anter...

''Românii au talent!'' Atraşi de marele premiu oferit de organizatorii concursului ''Românii au talent'', la preselecţia organizată la Piatra Neamţ au venit foarte mulţi români să demonstreze că au talent.

La înscriere, fiecare participant a primit câte un număr de concurs, reprezentat de un număr natural nenul. Unii dintre participanţi pot avea statut special, fiind admişi direct în semifinale, ca urmare a rezultatelor deosebite obţinute la ediţiile anterioare, numărul de concurs primit de aceştia având proprietatea că toate cifrele lui pot fi aranjate astfel încăt să formeze un număr palindrom.

Printre numerele de concurs primite de participanţii cu statut special, există numere care au în scrierea lor zecimală un număr maxim de cifre distincte. Cel mai mic dintre aceste numere reprezintă numărul de concurs al participantului VIP.

= Cerinta =
Scrieţi un program care citeşte numărul natural <code>n</code> (reprezentând numărul de participanţi înscrişi la concurs), <code>n</code> numere naturale (reprezentând numerele de concurs ale celor n participanţi) şi determină:

a) numărul <code>x</code> de participanţi admişi direct în semifinale;

b) numărul <code>y</code> de concurs al participantului <code>VIP</code>, dacă există un astfel de participant printre cei înscrişi.

= Date de intrare =
Fişierul <code>input.txt</code> conţine pe prima linie numărul n de participanţi, iar pe fiecare dintre următoarele n linii câte un număr natural reprezentând numărul de concurs al unui participant.

= Date de ieșire =
Fişierul <code>output.txt</code> va conţine pe prima linie cele două valori <code>x</code> şi <code>y</code>, separate printr-un singur spaţiu, în această ordine. Dacă nu există participanţi admişi direct în semifinală, atunci prima linie a fişierului va conţine două valori nule, separate printr-un singur spaţiu: <code>0 0</code>.

== Restricții și precizări ==
• <code>0 <n ≤ 15000</code>

== Exemplul 1 ==
input.txt:

8

17864

9900

90321

4704

351

83181

46476

7432

output.txt:

3 46476

Explicație:

Sunt <code>3</code> participanţi calificaţi direct în semifinală. Numerele lor de concurs sunt numere ale căror cifre pot fi aranjate astfel încât să formeze un palindrom : <code>9900</code>(format din <code>2</code> cifre distincte), <code>83181</code> (format din <code>3</code> cifre distincte) şi <code>46476</code> (format din <code>3</code> cifre distincte). Dintre acestea, cel mai mic număr format dintr-un număr maxim de cifre distincte este <code>46476</code> reprezentând numărul de concurs al participantului <code>VIP</code>.

== Exemplul 2 ==
input.txt:

999999999999999

17864

9900

90321

4704

351

83181

46476

7432

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(1<=n<=15000):
print("Constrangeri neindeplinite")
exit()

with open("input.txt", "r") as f:
with open("output.txt", "w") as g:
x = 0
vip = 0
p = 0
c = [0] * 10
maxd = 0
d = 0

def pali(x):
global maxd, d
k = 0
nen = 0
d = 0
for i in range(10):
c[i] = 0
while x:
c[x % 10] += 1
nen += (x % 10 != 0)
x = x // 10
for i in range(10):
k += (c[i] % 2 != 0)
d += (c[i] != 0)
if nen == 1 and c[0] != 0:
return 0
return k < 2

n = int(f.readline().strip())
ver(n)
for _ in range(n):
x = int(f.readline().strip())
if pali(x):
p += 1
if not vip or maxd < d or (maxd == d and x < vip):
vip = x
maxd = d

g.write(f"{p} {vip}\n")

</syntaxhighlight>

2179 - Max 3

2024-01-04T20:28:11Z

Corjuc Eunice: Pagină nouă: Fie <code>n</code> un număr natural nenul şi un şir de <code>n</code> numere naturale nenule, fiecare număr din şir având cel mult <code>3</code> cifre. Şirul dat se <code>„maximizează”</code> prin aplicarea următoarelor transformări: T1: Fiecare număr <code>y</code> din şir este înlocuit cu cel mai mare număr care se poate obţine prin aranjarea tuturor cifrelor lui <code>y</code>. De exemplu, pentru <code>y=102</code>, prin aranjarea cifrelor, se obţin n...

Fie <code>n</code> un număr natural nenul şi un şir de <code>n</code> numere naturale nenule, fiecare număr din şir având cel mult <code>3</code> cifre. Şirul dat se <code>„maximizează”</code> prin aplicarea următoarelor transformări:

T1: Fiecare număr <code>y</code> din şir este înlocuit cu cel mai mare număr care se poate obţine prin aranjarea tuturor cifrelor lui <code>y</code>. De exemplu, pentru <code>y=102</code>, prin aranjarea cifrelor, se obţin numerele: <code>12, 21, 102, 120, 201, 210,</code> cel mai mare număr fiind <code>210</code>. Astfel, <code>y</code> se va înlocui în şir cu numărul <code>210</code>.

T2: Se schimbă ordinea numerelor din şirul obţinut după aplicarea transformării <code>T1</code> astfel încât numărul <code>x</code> obţinut prin alipirea tuturor numerelor din şir, în ordinea în care apar după schimbare, să fie cel mai mare posibil.

De exemplu,pentru <code>n=3</code> şi şirul: <code>12, 132, 102,</code>după aplicarea transformării <code>T1</code> noul şir este format din numerele: <code>21, 321, 210</code>. Din acest şir, se pot obţine, prin schimbarea ordinii numerelor, următoarele <code>6</code> şiruri:

1) <code>21, 321, 210</code>;

2) <code>21, 210, 321</code>;

3) <code>321, 21, 210</code>;

4) <code>321, 210, 21</code>;

5) <code>210, 21, 321</code>;

6) <code>210, 321, 21</code>;

Numerele care rezultă prin alipirea numerelor din fiecare şir obţinut sunt:

1) <code>21321210</code>;

2) <code>21210321</code>;

3) <code>32121210</code>;

4) <code>32121021</code>;

5) <code>21021321</code>;

6) <code>21032121</code>.

După aplicarea transformării <code>T2</code>, şirul „maximizat” este: <code>321, 21, 210</code> deoarece cel mai mare număr dintre cele <code>6</code> obţinute este <code>x=32121210</code>.

= Cerința =
Scrieţi un program care să citească numărul natural nenul <code>n</code> şi cele <code>n</code> numere naturale nenule din şir şi care să determine:

a) cel mai mare număr <code>m</code> din şirul de numere obţinut în urma aplicării transformării <code>T1</code>;

b) numărul <code>x</code> obţinut prin alipirea numerele din şirul „maximizat” rezultat în urma aplicării transformării <code>T2</code>.

= Date de intrare =
Fişierul de intrare <code>input.txt</code> conţine două linii. Pe prima linie este scris numărul natural nenul <code>n</code>, iar pe a doua linie sunt scrise cele <code>n</code> numere naturale nenule din şir, separate prin câte un spaţiu.

= Date de ieșire =
Fişierul de ieşire <code>output.txt</code> va conţine:

− pe prima linie numărul natural <code>m</code>, reprezentând cel mai mare număr din şirul de numere obţinut în urma aplicării transformării <code>T1</code>;

− pe a doua linie numărul natural <code>x</code>, reprezentând numărul obţinut prin alipirea numerelor din şirul „maximizat”, rezultat în urma aplicării transformării <code>T2</code>.

= Restricții și precizări =
• Numărul <code>n</code> este număr natural <code>2 ≤ n ≤ 3500</code>

== Exemplul 1 ==
input.txt:

9

34 23 9 43 21 67 121 79 213

output.txt:

321

9977643433232121211

Explicație:

După aplicarea transformării <code>T1</code>, şirul devine: <code>43, 32, 9, 43, 21, 76, 211, 97, 321</code>. Cel mai mare număr din acest şir este <code>m=321</code>. După aplicarea transformării <code>T2</code>, şirul maximizat este: <code>9, 97, 76, 43, 43, 32, 321, 21, 211</code> iar numărul <code>x=9977643433232121211</code>

== Exemplul 2 ==
input.txt:

9999999

34 23 9 43 21 67 121 79 213

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(2<=n<=3500):
print("Constrangeri neindeplinite")
exit()

def main():
with open("input.txt", "r") as f:
n = int(f.readline().strip())
ver(n)
v = [0] * 3502
maxi = -1
freq = [0] * 1000

for line in f:
v = list(map(int, line.split()))

for i in range(0, n):
aux = v[i]
nrc = 0
nr = 0

while aux:
nrc += 1
aux //= 10

cif = [0] * (nrc + 1)
cnt = 0
aux = v[i]

while aux:
cnt += 1
cif[cnt] = aux % 10
aux //= 10

cif[1:cnt+1] = sorted(cif[1:cnt+1])

while cnt:
nr *= 10
nr += cif[cnt]
cnt -= 1

v[i] = nr

if v[i] > maxi:
maxi = v[i]

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

with open("output.txt", "w") as g:
g.write(str(maxi) + "\n")

for i in range(9, -1, -1):
while freq[i]:
g.write(str(i))
freq[i] -= 1

for j in range(i * 10 + 9, i * 10, -1):
while freq[j]:
g.write(str(j))
freq[j] -= 1

for k in range(j * 10 + 9, j * 10, -1):
while freq[k]:
g.write(str(k))
freq[k] -= 1

if __name__ == "__main__":
main()

</syntaxhighlight>

0980 - Sir 4

2024-01-04T19:25:01Z

Corjuc Eunice: Pagină nouă: Se consideră şirul de numere naturale: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21,... Se grupează numerele din şir astfel încât prima grupă, numerotată cu <code>1</code>, este formată din primul număr din şir (<code>1</code>), a doua grupă, numerotată cu <code>2</code>, este formată din următoarele două numere din şir (<code>3,5</code>), a treia grupă, numerotată cu <code>3</code>, este formată din următoarele trei numere din şir (<code>7,9,11</code>),…, a...

Se consideră şirul de numere naturale:
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21,...
Se grupează numerele din şir astfel încât prima grupă, numerotată cu <code>1</code>, este formată din primul număr din şir (<code>1</code>), a doua grupă, numerotată cu <code>2</code>, este formată din următoarele două numere din şir (<code>3,5</code>), a treia grupă, numerotată cu <code>3</code>, este formată din următoarele trei numere din şir (<code>7,9,11</code>),…, a <code>n</code>-a grupă din şir, numerotată cu <code>n</code>, este formată din următoarele n numere din şir, etc.

= Cerinţe =
Deduceţi regula după care sunt generaţi termenii şirului şi scrieţi un program care să citească numerele naturale <code>p</code>, <code>n</code> şi <code>k</code> şi care să determine:

a) al câtelea număr din şir are valoarea <code>p</code>;

b) cel mai mare număr natural palindrom care poate fi obţinut folosindu-se cifrele tuturor numerelor din grupa a <code>n</code>-a a şirului dat, nu neapărat toate aceste cifre;

c) numărul grupei cu proprietatea că suma tuturor numerelor conţinute de aceasta este egală cu numărul <code>k</code>, dacă există o astfel de grupă.

= Date de intrare =
Programul citește de la tastatură, în acestă ordine, trei numere naturale <code>p</code>, <code>n</code> şi <code>k</code>.

= Date de ieșire =
Programul va afișa pe ecran, în această ordine:

* o valoare naturală reprezentând al câtelea număr din şir are valoarea <code>p</code>.
* cel mai mare număr natural palindrom care poate fi obţinut folosindu-se cifrele tuturor numerelor din grupa a <code>n</code>-a a şirului dat, nu neapărat toate aceste cifre.
* numărul grupei cu proprietatea că suma tuturor numerelor conţinute de aceasta este egală cu numărul <code>k</code>; dacă nu există o astfel de grupă se va scrie numărul <code>0</code>

= Restricții și precizări =

* Numerele <code>p</code>, <code>n</code> şi <code>k</code> sunt naturale
* <code>1 ≤ p ≤ 2.000.001</code>, <code>p</code> număr natural impar
* <code>1 ≤ n ≤ 50</code>
* <code>1 ≤ k ≤ 2.000.000.000</code>

== Exemplul 1 ==
Input:

19 5 125

Output:

10

22922

5

Explicație:

* În şir, valoarea <code>19</code> apare pe poziţia <code>10</code>, aceşti <code>10</code> termeni termeni fiind: <code>1,3,5,7,9,11,13,15,17,19</code>.
* Numerele din grupa a <code>5</code>-a sunt scrise cu ajutorul a <code>1</code> cifră de <code>1</code>, <code>5</code> cifre de <code>2</code>, <code>1</code> de <code>3</code>, <code>1</code> de <code>5</code>, <code>1</code> de <code>7</code>, <code>1</code> de <code>9</code>. Ce mai mare palindrom care se poate scrie cu aceste cifre este <code>22922</code>.
* Grupa <code>5</code> are suma egală cu <code>k</code> (<code>21+23+25+27+29=125</code>).

== Exemplul 2 ==
Input:

999999999999999 5 125

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_valid_input(p, n, k):
return (1 <= p <= 2000001) and (p % 2 == 1) and (1 <= n <= 50) and (1 <= k <= 2000000000)

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

if not is_valid_input(p,n,k):
print("Constrangeri neindeplinite")
exit()

print((p + 1) // 2)

# palindrom
cifre = [0] * 10
for i in range(n * n - n + 1, n * n - n + 1 + 2 * n, 2):
aux = i
while aux:
cifre[aux % 10] += 1
aux //= 10

result = []
for i in range(9, -1, -1):
result.extend([str(i)] * (cifre[i] // 2))
for i in range(9, -1, -1):
if cifre[i] % 2 == 1:
result.append(str(i))
break
for i in range(10):
result.extend([str(i)] * (cifre[i] // 2))

print("".join(result))
# palindrom

cbr = round(k ** (1 / 3))
if cbr ** 3 == k:
print(cbr)
else:
print(0)

</syntaxhighlight>

1709 - Asort

2024-01-04T19:06:04Z

Corjuc Eunice: Pagină nouă: Se consideră un număr natural par <code>N</code> și șirul ordonat crescător <code>X</code> format din primele <code>N</code> numere naturale nenule: <code>X[1] = 1</code>, <code>X[2] = 2</code>, …., <code>X[N] = N</code>. Pozițiile numerelor din șir se pot modifica doar conform regulii <code>A</code>,după cum urmează: * dacă <code>X[1]</code> este număr impar, atunci se interschimbă <code>X[1]</code> cu <code>X[2]</code>, <code>X[3]</code> cu <code>X[4]</code...

Se consideră un număr natural par <code>N</code> și șirul ordonat crescător <code>X</code> format din primele <code>N</code> numere naturale nenule:

<code>X[1] = 1</code>, <code>X[2] = 2</code>, …., <code>X[N] = N</code>.

Pozițiile numerelor din șir se pot modifica doar conform regulii <code>A</code>,după cum urmează:

* dacă <code>X[1]</code> este număr impar, atunci se interschimbă <code>X[1]</code> cu <code>X[2]</code>, <code>X[3]</code> cu <code>X[4]</code>, …, <code>X[N-1]</code> cu <code>X[N]</code>;
* dacă <code>X[1]</code> este par atunci se interschimbă <code>X[2]</code> cu <code>X[3]</code>, <code>X[4]</code> cu <code>X[5]</code>, …, <code>X[N-2]</code> cu <code>X[N-1]</code>, iar <code>X[N]</code> cu <code>X[1]</code>.

Aplicând de <code>R</code> ori regula <code>A</code> șirului <code>X</code> se transformă șirul dat într-un șir “A sortat”.

= Cerința =
Cunoscându-se numerele naturale <code>N</code>, <code>R</code>, <code>K</code> și <code>T</code>, scrieți un program care să determine:

1) Numărul situat pe poziția <code>K</code> în șirul “ <code>A</code> sortat” obținut prin aplicarea de <code>R</code> ori a regulii “ <code>A</code> ” șirului <code>X</code>.

2) Predecesorul și succesorul numărului <code>T</code> în șirul “ <code>A</code> sortat” .

= Date de intrare =
Fişierul de intrare <code>input.txt</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 a fișierului <code>asort.in</code> conține în această ordine, patru numere naturale <code>N</code>, <code>R</code>, <code>K</code> și

T, separate prin câte un spațiu.

= Date de ieșire =

* Dacă valoarea lui <code>P</code> este <code>1</code>, atunci se va rezolva numai cerința 1). În acest caz, fişierul de ieşire <code>output.txt</code> va conţine pe prima linie un număr natural reprezentând numărul de pe poziția <code>K</code> din șirul <code>A</code> sortat.
* Dacă valoarea lui <code>P</code> este <code>2</code>, atunci se va rezolva numai cerința 2). În acest caz, fişierul de ieşire <code>output.txt</code> va conține pe prima linie două numere naturale, separate printr-un singur spațiu, reprezentând, în această ordine, predecesorul și succesorul numărului <code>T</code>.

= Restricții și precizări =

* <code>6 < N < 1 000 000 000</code>
* <code>1 < R < 1 000 000 000</code>

== Exemplul 1 ==
input.txt

1

6 2 3 4

output.txt:

1

Explicație:

Se rezolvă cerința 1. <code>N=6</code>, <code>R=2</code>, <code>K=3</code> și <code>T=4</code>

<code>X[1] X[2] X[3] X[4] X[5] X[6]</code>

Șirul <code>X</code> inițial <code>1 2 3 4 5 6</code>

Șirul după prima aplicare a regulii “ <code>A</code>” <code>2 1 4 3 6 5</code>

Șirul asortat, obținut după a doua aplicare a regulii “A” <code>5 4 1 6 3 2</code>

În șirul “asortat”, pe poziția <code>K=3</code> se află valoarea 1 care se va scrie pe prima linie a fișierului <code>output.txt</code>

== Exemplul 2 ==
input.txt:

2

6 2 3 4

output.txt:

5 1

Explicație:

Se rezolvă cerința 2. <code>N=6</code>, <code>R=2</code>, <code>K=3</code> și <code>T=4</code>

Șirul <code>X</code> inițial <code>1 2 3 4 5 6</code>

Șirul după prima aplicare a regulii “A” <code>2 1 4 3 6 5</code>

Șirul asortat, obținut după a doua aplicare a regulii “A” <code>5 4 1 6 3 2</code>

În șirul “asortat”, predecesorul numărului <code>T=4</code> este <code>5</code>, iar succesorul este <code>1</code>. Numerele <code>5</code> și <code>1</code> se vor scrie pe prima linie a fișierului <code>output.txt</code>, în această ordine.

== Exemplul 3 ==
input.txt

1

99999999999999 2 3 4

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n,r):
if not(6<=n<=1000000000):
print("Constrangeri neindeplinite")
exit()
if not(1<=r<=1000000000):
print("Constrangeri neindeplinite")
exit()

def numar_poz(k):
global n, r
nrc = 0
if r == 0:
return k
if r % 2 != 0:
if k % 2 != 0:
nrc = (r + k) % n
else:
nrc = (n + k - r) % n
else:
if k % 2 == 0:
nrc = (r + k) % n
else:
nrc = (n + k - r) % n
if nrc == 0:
nrc = n
return nrc

def main():
global n, r, t
with open("input.txt", "r") as input_file, open("output.txt", "w") as output_file:
p = int(input_file.readline())
n, r, k, t = map(int, input_file.readline().split())
ver(n,r)
r = r % n
if p == 1:
output_file.write(str(numar_poz(k)) + '\n')
else:
pozt = (n + t - r) % n if t % 2 == 0 else (t + r) % n
if pozt == 0:
pozt = n
if pozt == 1:
poz_pred, poz_succ = n, 2
elif pozt == n:
poz_pred, poz_succ = n - 1, 1
else:
poz_pred, poz_succ = pozt - 1, pozt + 1
pred = numar_poz(poz_pred)
succ = numar_poz(poz_succ)
output_file.write(str(pred) + " " + str(succ) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

1559 - Minge

2024-01-04T18:53:10Z

Corjuc Eunice: Pagină nouă: <code>N</code> copii, numerotați de la <code>1</code> la <code>N</code>, se aşează în cerc, unul lângă altul, în ordinea crescătoare a numerelor lor, copilul cu numărul <code>N</code> ajungând să fie situat lângă copilul cu numărul <code>1</code>. Un copil din cerc are o minge. El o aruncă unui alt copil din cerc. Acesta o aruncă și el unui alt copil din cerc care nu a atins vreodată mingea, … șamd. Fiecare aruncare este notată printr-o pereche de numer...

<code>N</code> copii, numerotați de la <code>1</code> la <code>N</code>, se aşează în cerc, unul lângă altul, în ordinea crescătoare a numerelor lor, copilul cu numărul <code>N</code> ajungând să fie situat lângă copilul cu numărul <code>1</code>.

Un copil din cerc are o minge. El o aruncă unui alt copil din cerc. Acesta o aruncă și el unui alt copil din cerc care nu a atins vreodată mingea, … șamd. Fiecare aruncare este notată printr-o pereche de numere naturale distincte <code>(X,Y)</code> cu semnificația că copilul cu numărul <code>X</code> aruncă mingea copilului cu numărul <code>Y</code> care nu a mai atins mingea până în acel moment.

= Cerințe =
Cunoscându-se numerele <code>N</code>, <code>K</code> și cele <code>K</code> perechi de numere corespunzătoare celor <code>K</code> aruncări să se determine:

1) Numărul copiilor care nu ating niciodată mingea.

2) Traseul parcurs de minge plecând de la copilul care are mingea la începutul jocului, până la copilul care nu mai aruncă mingea.

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

– pe prima linie, un număr natural <code>p</code>; pentru toate testele de intrare, <code>p</code> poate avea doar valoarea <code>1</code> sau valoarea <code>2</code>;

– pe a doua linie, cele două numere naturale <code>N K</code>, separate printr-un spațiu.

– pe fiecare dintre următoarele <code>K</code> linii (câte una pentru fiecare aruncare), câte o pereche de numere naturale <code>X Y</code>, separate printr-un spațiu, cu semnificația: copilul cu numărul <code>X</code> aruncă mingea copilului cu numărul <code>Y</code>.

= 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, fişierul <code>output.txt</code> va conţine pe prima linie un număr natural reprezentând numărul copiilor care nu ating niciodată mingea

– 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 <code>ouput.txt</code> va conţine pe prima linie, traseul parcurs de minge plecând de la copilul care are mingea la începutul jocului, până la copilul care nu mai aruncă mingea; traseul este descris prin șirul numerelor copiilor care ating mingea, separate prin câte un spațiu, în ordinea în care este aruncată mingea.

= Restricții și precizări =

* <code>6 ≤ N ≤ 10000</code>
* <code>1 ≤ K ≤ N-1</code>

== Exemplul 1 ==
input.txt:

1

7 4

4 3

2 6

3 1

6 4

output.txt:

2

Explicație:

<code>p=1</code>. Se rezolvă doar cerința <code>1</code>. Sunt <code>N=7</code> copii. Se fac <code>K=4</code> aruncări. Sunt <code>2</code> copii care nu ating mingea, cei cu numerele <code>5</code> și <code>7</code>.

== Exemplul 2 ==
input.txt:

2

7 4

4 3

2 6

3 1

6 4

output.txt:

2 6 4 3 1

Explicație:

<code>p=2</code>. Se rezolvă doar cerința <code>2</code>. Sunt <code>N=7</code> copii. Se fac <code>K=4</code> aruncări.

Traseul parcurs de minge pornește de la copilul cu numărul <code>2</code> și se termină la copilul cu numărul <code>1</code> este: <code>2 6 4 3 1</code>, deoarece se fac aruncările: <code>(2,6),(6,4),(4,3),(3,1)</code>

== Exemplul 3 ==
input.txt:

2

99999999 4

4 3

2 6

3 1

6 4

Ouput:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n,m):
if not(6<=n<=10000):
print("Constrangeri neindeplinite")
exit()
if not(1<=m<=n-1):
print("Constrangeri neindeplinite")
exit()

with open("input.txt", 'r') as fin, open("output.txt", 'w') as fout:
freq = [0] * 10001
col1 = [0] * 10001
col2 = [0] * 10001

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

ver(n,m)

if t == 1:
for _ in range(m):
x, y = map(int, fin.readline().split())
freq[x] += 1
freq[y] += 1

nr = sum(1 for i in range(1, n + 1) if freq[i] == 0)
fout.write(str(nr))
elif t == 2:
for _ in range(m):
x, y = map(int, fin.readline().split())
freq[x] = y
col1[x] += 1
col2[y] += 1

start, finish = 0, 0
for i in range(1, 10001):
if col1[i] > 0 and col2[i] == 0:
start = i
if col2[i] > 0 and col1[i] == 0:
finish = i

z = start
fout.write(str(start) + ' ')
while freq[z] != finish:
fout.write(str(freq[z]) + ' ')
z = freq[z]

fout.write(str(finish))

</syntaxhighlight>

0601 - Dreptunghiuri

2024-01-04T18:36:49Z

Corjuc Eunice: Pagină nouă: = Cerința = Se consideră într-un reper cartezian <code>n</code> puncte cu coordonate pozitive. Prin fiecare punct se desenează o dreaptă verticală și una orizontală. Să se determine câte dreptunghiuri cu interioarele disjuncte s-au format prin intermediul acestor drepte şi al axelor de coordonate. = Date de intrare = Fișierul de intrare <code>input.txt</code> conține pe prima linie numărul <code>n</code>; următoarele <code>n</code> linii conțin câte două nu...

= Cerința =
Se consideră într-un reper cartezian <code>n</code> puncte cu coordonate pozitive. Prin fiecare punct se desenează o dreaptă verticală și una orizontală. Să se determine câte dreptunghiuri cu interioarele disjuncte s-au format prin intermediul acestor drepte şi al axelor de coordonate.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numărul <code>n</code>; următoarele <code>n</code> linii conțin câte două numere <code>x y</code>, reprezentând coordonatele punctelor.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie numărul <code>C</code>, reprezentând valoarea cerută.

= Restricții și precizări =

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

== Exemplul 1 ==
input.txt:

4

1 0

2 4

4 2

1 2

output.txt:

6

== Exemplul 2 ==
input.txt:

9999999

1 0

3 4

4 2

1 2

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(1<=n<=1000):
print("Constrangeri neindeplinite")
exit()

with open("input.txt", 'r') as fin, open("output.txt", 'w') as fout:
n = int(fin.readline())
ver(n)
a = [0] * (n + 1)
b = [0] * (n + 1)

for i in range(1, n + 1):
a[i], b[i] = map(int, fin.readline().split())

for i in range(1, n):
for j in range(i + 1, n + 1):
if a[i] > a[j]:
a[i], a[j] = a[j], a[i]
if b[i] > b[j]:
b[i], b[j] = b[j], b[i]

cnt1 = 0
cnt2 = 0

for i in range(1, n + 1):
if a[i] != a[i - 1]:
cnt1 += 1
if b[i] != b[i - 1]:
cnt2 += 1

fout.write(str(cnt1 * cnt2))

</syntaxhighlight>

1840 - P Max

2024-01-04T18:32:00Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dau <code>n</code> numere naturale, fie acestea <code>A1, A2,..., An</code> și <code>Xi</code> cel mai mic număr care are aceiași factori primi in descompunere ca şi <code>Ai</code>, unde <code>1≤i≤n</code>. Aflați produsul <code>X1 * X2 *...* Xn</code>. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere naturale, separate prin spații. = Date de ieșire = Programul va afișa pe ecran num...

= Cerința =
Se dau <code>n</code> numere naturale, fie acestea <code>A1, A2,..., An</code> și <code>Xi</code> cel mai mic număr care are aceiași factori primi in descompunere ca şi <code>Ai</code>, unde <code>1≤i≤n</code>. Aflați produsul <code>X1 * X2 *...* Xn</code>.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere naturale, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>P</code>, reprezentand numărul cerut.

= Restricții și precizări =

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

== Exemplul 1 ==
Input:

2

45

20

Output:

150

Explicație:

<code>45 = 5 * 3 * 3, 20 = 2 * 2 * 5</code>. Cel mai mic număr care are factorii <code>3</code> și <code>5</code> in descompunere este <code>15</code>, iar cu factorii <code>2</code> și <code>5</code> este <code>10</code>.

<code>15 * 10 = 150</code>.

== Exemplul 2 ==
Input:

999999999

45

20

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(1<=n<=1000):
print("Constrangeri neindeplinite")
exit()

rez = [0] * 100002
p = [0] * 1002

rez[0] = 1
rez[1] = 1

n = int(input())
ver(n)
for k in range(1, n + 1):
p[k] = 1
x = int(input())
d = 2
while x != 1:
if x % d == 0:
p[k] *= d
while x % d == 0:
x //= d
if d == 2:
d = 3
else:
d += 2
if d * d > x:
d = x

for i in range(1, n + 1):
t = 0
j = 1
while j <= rez[0]:
cif = t + p[i] * rez[j]
rez[j] = cif % 10
t = cif // 10
j += 1
while t:
rez[0] += 1
rez[rez[0]] = t % 10
t //= 10

for i in range(rez[0], 0, -1):
print(rez[i], end="")

</syntaxhighlight>

0634 - Repetare

2024-01-04T18:28:16Z

Corjuc Eunice: Pagină nouă: = Cerința = Gigel are un șir cu <code>n</code> elemente, numere naturale. Plictisit, el construiește un nou șir, prin scrierea repetată a valorilor șirului dat. De exemplu, dacă șirul inițial este <code>(2 3 1 5)</code>, scriindu-l de <code>3</code> ori se obține șirul: <code>(2 3 1 5 2 3 1 5 2 3 1 5)</code>. Maleficul Costel elimină sau chiar schimbă unele valori din șirul al doilea. Acum Gigel vă pune la dispoziție două șiruri de numere naturale și roag...

= Cerința =
Gigel are un șir cu <code>n</code> elemente, numere naturale. Plictisit, el construiește un nou șir, prin scrierea repetată a valorilor șirului dat. De exemplu, dacă șirul inițial este <code>(2 3 1 5)</code>, scriindu-l de <code>3</code> ori se obține șirul: <code>(2 3 1 5 2 3 1 5 2 3 1 5)</code>.

Maleficul Costel elimină sau chiar schimbă unele valori din șirul al doilea. Acum Gigel vă pune la dispoziție două șiruri de numere naturale și roagă să stabiliți dacă al doilea șir poate obține prin scrierea repetată a primului șir și eliminarea unor elemente iar în caz afirmativ care este numărul minim de repetări ale primului șir prin care se poate obține șirul al doilea.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numărul <code>n</code> – numărul de elemente ale primului șir, iar pe a doua linie <code>n</code> numere naturale separate prin spații, reprezentând elementele primului șir. Linia a treia conține numărul <code>m</code> – numărul de elemente ale celui de-al doilea șir, iar a patra linie conține <code>m</code> numere naturale separate prin spații, reprezentând elementele șir șirului al doilea.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie numărul <code>C</code>, reprezentând numărul minim de repetări ale primului șir prin care se poate obține ale doilea șir, sau valoarea <code>IMPOSIBIL</code> dacă al doilea șir nu poate fi obținut prin scrierea repetată a primului șir și eliminarea unor valor..

= Restricții și precizări =

* <code>1 ≤ n , m ≤ 1000</code>

== Exemplul 1 ==
input.txt:

4

2 3 1 5

7

2 5 3 1 5 3 1

output.txt:

3

Explicație:

Prin repetarea de trei ori a primului șir se obține șirul <code>2 3 1 5 2 3 1 5 2 3 1 5</code> Prin eliminarea, în ordine a valorilor <code>3 1 2 2 5</code> se obține șirul al doilea. Repetând șirul dat de mai puțin de trei ori, oricum a elimina valori din șirul rezultat nu se poate obține al doilea șir.

== Exemplul 2 ==
input.txt:

9999999

2 3 1 5

7

2 5 3 1 5 3 1

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n,m):
if not(1<=n<=1000):
print("Constrangeri neindeplinite")
exit()
if not(1<=m<=1000):
print("Constrangeri neindeplinite")
exit()

with open("input.txt", 'r') as fin, open("output.txt", 'w') as fout:
n = int(fin.readline())
ver(n,10)
a = list(map(int, fin.readline().split()))
m = int(fin.readline())
ver(10,m)
b = list(map(int, fin.readline().split()))

cnt = 1
ok = True
i, j = 0, 0

while j < m and ok:
ivechi = i
marit = False
while i < n and a[i] != b[j]:
i += 1
if i == n:
i = 0
cnt += 1
marit = True
while i < ivechi and a[i] != b[j]:
i += 1

if i == ivechi and marit:
# nu l-am gasit pe b[j] in a[], nu se poate
ok = False
else:
i += 1
j += 1

if ok:
fout.write(str(cnt))
else:
fout.write("IMPOSIBIL")

</syntaxhighlight>

0606 - Culori

2024-01-04T18:23:10Z

Corjuc Eunice: Pagină nouă: = Cerința = Gigel a primit de la bunicul său un trenuleț electric cu <code>n</code> vagoane colorate în diverse culori, identificate prin numere întregi. Gigel consideră că trenul este frumos colorat dacă toate vagoanele colorate la fel sunt învecinate. Acum vă roagă să-i spuneți cu câte culori diferite au fost colorate vagoanele și dacă trenul este frumos colorat. = Date de intrare = Fișierul de intrare <code>input.txt</code> conține pe prima linie număru...

= Cerința =
Gigel a primit de la bunicul său un trenuleț electric cu <code>n</code> vagoane colorate în diverse culori, identificate prin numere întregi. Gigel consideră că trenul este frumos colorat dacă toate vagoanele colorate la fel sunt învecinate. Acum vă roagă să-i spuneți cu câte culori diferite au fost colorate vagoanele și dacă trenul este frumos colorat.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale nenule, reprezentând în ordine culorile vagoanelor din care este compus trenulețul.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie numărul <code>C</code> de culori diferite, iar pe a doua linie mesajul <code>DA</code> sau <code>NU</code>, după cum trenul este sau nu frumos colorat.

= Restricții și precizări =

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

== Exemplul 1 ==
input.txt:

5

2 2 1 6 6

output.txt:

3

DA

== Exemplul 2 ==
input.txt:

5

2 2 6 2 6

output.txt:

2

NU

== Exemplul 3 ==
input.txt:

9999999999

1 2 3

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(1<=n<=1000):
print("Constrangeri neindeplinite")
exit()

with open("input.txt", 'r') as fin, open("output.txt", 'w') as fout:
n = int(fin.readline())
ver(n)
v = list(map(int, fin.readline().split()))
c = [0] * 1005
nrc = 1
c[1] = v[0]
frumos = True

for i in range(1, n):
if v[i] != v[i - 1]:
poz = 0
for j in range(1, nrc + 1):
if c[j] == v[i]:
poz = j
break
if poz == 0:
nrc += 1
c[nrc] = v[i]
else:
frumos = False

fout.write(str(nrc) + "\n")
if frumos:
fout.write("DA")
else:
fout.write("NU")

</syntaxhighlight>

1718 - Gen Pascal

2024-01-04T18:18:31Z

Corjuc Eunice: Pagină nouă: Se consideră Triunghiul lui Pascal definit astfel: Primul rând conține numărul 1, iar celelalte numere se formează prin însumarea celor două numere de deasupra sa, considerând toate elementele din exteriorul triunghiului ca fiind egale cu <code>0</code>. Prin ''Triunghiul lui Pascal Generalizat'' se înțelege un triunghi care se formează la fel ca ''Triunghiul lui Pascal'' (fiecare număr se obține prin însumarea celor două numere de deasupra sa), numai că prim...

Se consideră Triunghiul lui Pascal definit astfel: Primul rând conține numărul 1, iar celelalte numere se formează prin însumarea celor două numere de deasupra sa, considerând toate elementele din exteriorul triunghiului ca fiind egale cu <code>0</code>.

Prin ''Triunghiul lui Pascal Generalizat'' se înțelege un triunghi care se formează la fel ca ''Triunghiul lui Pascal'' (fiecare număr se obține prin însumarea celor două numere de deasupra sa), numai că primul rând va fi considerat liber, iar cele două valori de pe al doilea rând vor fi precizate.

= Cerința =
Dându-se numerele naturale nenule <code>n</code> și <code>m</code> situate pe al doilea rând al ''Triunghiului lui Pascal Generalizat'' și un număr <code>L</code>, să se calculeze suma tuturor numerelor aflate pe linia <code>L</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code>,iar pe a doua linie numărul <code>L</code>.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie numărul <code>S</code>, reprezentând suma cerută.

= Restricții și precizări =

* <code>n,m ≤ 100</code>
* <code>2 ≤ L ≤ 2000</code>

== Exemplul 1 ==
input.txt:

1 2

6

output.txt:

48

Explicație:

Pentru valorile <code>n = 1</code> și <code>m = 2</code> se construiește următorul triunghi :
X - rândul 1 este liber
1 2 -rândul 2 cu valorile date
1 3 2
1 4 5 2
1 5 9 7 2
1 6 14 16 9 2 rândul cerut, 6.
Suma elementelor de pe rândul al șaselea este <code>48</code>.

== Exemplul 2 ==
input.txt:

9999999 2

6

Output:

Constrangeri neindeplinite

0563 - Fast Food 1

2024-01-04T18:01:15Z

Corjuc Eunice: Pagină nouă: = Cerința = Fast-food-ul de la colțul străzii are <code>n</code> clienți. Pentru fiecare client se cunoaște momentul în care intră în fast-food și momentul în care iese, ambele fiind exprimate în minute, numărate de la începutul perioadei de funcționare. Gigel, patronul acestui fast-food, dorește să afle care este numărul maxim de clienți aflați simultan în restaurant. = Date de intrare = Programul citește de la tastatură numerele <code>n</code>, iar ap...

= Cerința =
Fast-food-ul de la colțul străzii are <code>n</code> clienți. Pentru fiecare client se cunoaște momentul în care intră în fast-food și momentul în care iese, ambele fiind exprimate în minute, numărate de la începutul perioadei de funcționare. Gigel, patronul acestui fast-food, dorește să afle care este numărul maxim de clienți aflați simultan în restaurant.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code>, iar apoi <code>n</code> perechi de numere naturale <code>x y</code> , reprezentând montul intrării, respectiv momentul ieșirii fiecărui client din restaurant.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>P</code>, reprezentând valoarea cerută.

= Restricții și precizări =

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

== Exemplul 1 ==
Input:

5

5 7

10 11

10 13

6 8

7 9

Output:

3

Explicație:

La momentul <code>7</code> în restaurant se află <code>3</code> persoane.

== Exemplul 2 ==
99999999999999

5 7

10 11

10 13

6 8

7 9

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(1<=n<=1000):
print("Constrangeri neindeplinite")
exit()

n = int(input())
ver(n)
v = [0] * 10005

hmax = 0
hmin = 10005

for _ in range(n):
x, y = map(int, input().split())
if x < hmin:
hmin = x
if y > hmax:
hmax = y
for j in range(x, y + 1):
v[j] += 1

max_val = v[hmin]
for i in range(hmin, hmax + 1):
if max_val < v[i]:
max_val = v[i]

print(max_val)

</syntaxhighlight>

3497 - Progresie Geom

2024-01-04T17:57:13Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă o progresie geometrică cu primul termen <code>x</code>, cu rația egală cu , unde <code>[p]</code> reprezintă partea întreagă a numărului real <code>p</code>. Afișați al <code>n</code>-lea termen. = Date de intrare = Programul citește de la tastatură numerele <code>x a b n</code>. = Date de ieșire = Programul va afișa pe ecran numărul <code>Z</code>, reprezentând al <code>n</code>-lea termen al progresiei. = Restricții și precizări = *...

= Cerința =
Se dă o progresie geometrică cu primul termen <code>x</code>, cu rația egală cu , unde <code>[p]</code> reprezintă partea întreagă a numărului real <code>p</code>. Afișați al <code>n</code>-lea termen.

= Date de intrare =
Programul citește de la tastatură numerele <code>x a b n</code>.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>Z</code>, reprezentând al <code>n</code>-lea termen al progresiei.

= Restricții și precizări =

* <code>x, a, b</code> au maximum <code>10.000</code> de cifre
* <code>n</code> este cel mult <code>10.000</code>

== Exemplul 1 ==
Input:

1 5 2 11

Output:

1024

== Exemplul 2 ==
Input:

1 5 2 9999999999

Output:

Input invalid. Asigurați-vă că x, a, b au cel mult 10.000 de cifre și n este cel mult 10.000.

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

def verify_input(x, a, b, n):
if len(str(x)) > 10000 or len(str(a)) > 10000 or len(str(b)) > 10000 or n > 10000:
return False
return True

def main():
x = int(input("Introduceți primul termen x: "))
a = int(input("Introduceți a: "))
b = int(input("Introduceți b: "))
n = int(input("Introduceți n: "))

if not verify_input(x, a, b, n):
print("Input invalid. Asigurați-vă că x, a, b au cel mult 10.000 de cifre și n este cel mult 10.000.")
return

# Calcularea [ab]
ratio = a // b

# Calcularea al n-lea termen al progresiei
result = x * (ratio ** (n - 1))

print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3522 - Nr Div Huge

2024-01-04T17:51:38Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dau <code>N</code> perechi de numere <code>n k</code>. Pentru fiecare pereche să se calculeze numărul de divizori al lui . = Date de intrare = Fișierul de intrare <code>input.txt</code> conține pe prima linie numărul <code>N</code>, iar pe următoarele <code>N</code> linii <code>N</code> perechi de numere <code>n</code> și <code>k</code> separate printr-un spațiu. = Date de ieșire = Fișierul de ieșire <code>output.txt</code> va conține pe linia <c...

= Cerința =
Se dau <code>N</code> perechi de numere <code>n k</code>. Pentru fiecare pereche să se calculeze numărul de divizori al lui .

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numărul <code>N</code>, iar pe următoarele <code>N</code> linii <code>N</code> perechi de numere <code>n</code> și <code>k</code> separate printr-un spațiu.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe linia <code>i</code>, <code>1 ≤ i ≤ N</code>, numărul <code>D</code>, reprezentând numărul de divizori al lui <code>P</code>, calculat pentru perechea cu numărul <code>i</code>. Pentru că acesta poate fi foarte mare se va afișa modulo <code>1.000.000.007</code>.

= Restricții și precizări =

* <code>1 ≤ N ≤ 15.000</code>

== Exemplul 1 ==
input.txt:

2

2 3

4 4

output.txt:

8

20

Explicație:

Pentru prima pereche: <code>P=54</code>, iar <code>54</code> are <code>8</code> divizori.

Pentru cea de-a doua pereche: <code>P=2560</code>, iar <code>2560</code> are <code>20</code> divizori

== Exemplul 2 ==
input.txt:

999999999

2 3

4 4

Output:

Conditii neideplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(1<=n<=15000):
print("Conditii neideplinite")
exit()

def precalculation():
global prime, nrp
prime = []
nrp = 0
ciur = [0] * 31630

for i in range(3, 31626, 2):
if ciur[i] == 0:
for j in range(i * i, 31626, 2 * i):
ciur[j] = 1
prime.append(i)
nrp += 1

def nrdivkn(N, m):
P = 1
p = 0

while N % 2 == 0:
N //= 2
p += 1

p = (p * m) % mod
P = (P * p) % mod

for d in range(nrp):
if prime[d] * prime[d] > N:
break
while N % prime[d] == 0:
p = 0
while N % prime[d] == 0:
p += 1
N //= prime[d]
if p:
p = (p * m) % mod
p = (p + 1) % mod
P = (P * p) % mod

if N > 1:
p = 1
p = (p * m) % mod
p = (p + 1) % mod
P = (P * p) % mod

return P

def nrdivk1(N):
P = 1
p = 0
d = 0

while N % 2 == 0:
N //= 2
p += 1

p += 1
P = (P * p) % mod

for d in range(nrp):
if prime[d] * prime[d] > N:
break
p = 0
while N % prime[d] == 0:
p += 1
N //= prime[d]
if p:
p = (p + 1) % mod
P = (P * p) % mod

if N > 1:
P = (P * 2) % mod

return P

def nrdivkn_2(N, m):
P = 1
p = 0

while N % 2 == 0:
N //= 2
p += 1

p = (p * m) % mod
p = (p + 1) % mod
P = (P * p) % mod

for d in range(nrp):
if prime[d] * prime[d] > N:
break
p = 0
while N % prime[d] == 0:
p += 1
N //= prime[d]
if p:
p = (p * m) % mod
p = (p + 1) % mod
P = (P * p) % mod

if N > 1:
p = 1
p = (p * m) % mod
p = (p + 1) % mod
P = (P * p) % mod

return P

def nrdivk1_2(N):
P = 1
p = 0
d = 0

while N % 2 == 0:
N //= 2
p += 1

P = (P * p) % mod

for d in range(nrp):
if prime[d] * prime[d] > N:
break
p = 0
while N % prime[d] == 0:
p += 1
N //= prime[d]
if p:
p = (p + 1) % mod
P = (P * p) % mod

if N > 1:
P = (P * 2) % mod

return P

def solve(N, K):
global mod
if K % 2 == 0:
nr1 = nrdivkn(K, N + 1)
nr2 = nrdivk1(K + 1)
return (nr1 * nr2) % mod
else:
nr1 = nrdivkn_2(K, N + 1)
nr2 = nrdivk1_2(K + 1)
return (nr1 * nr2) % mod

def read_solve():
global mod
with open("input.txt", "r") as f, open("output.txt", "w") as g:
nr = int(f.readline())
ver(nr)
for _ in range(nr):
n, k = map(int, f.readline().split())
m = n + 1
result = solve(n, k)
g.write(str(result) + '\n')

mod = 1000000007
precalculation()
read_solve()

</syntaxhighlight>

0632 - Iepuri

2024-01-04T17:40:46Z

Corjuc Eunice: Pagină nouă: = Cerința = Gigel are <code>p</code> iepuri pe care vrea să-i distribuie în <code>n</code> cuști astfel încât: * toți iepurii să intre în cuști * fiecare cușcă să conțină cel puțin un iepure * să nu existe două cuști cu același număr de iepuri * diferența dintre numărul maxim de iepuri dintr-o cușcă și numărul minim de iepuri dintr-o cușcă să fie minimă Determinați o modalitate de distribuire a iepurilor în cuști care să respecte condiții...

= Cerința =
Gigel are <code>p</code> iepuri pe care vrea să-i distribuie în <code>n</code> cuști astfel încât:

* toți iepurii să intre în cuști
* fiecare cușcă să conțină cel puțin un iepure
* să nu existe două cuști cu același număr de iepuri
* diferența dintre numărul maxim de iepuri dintr-o cușcă și numărul minim de iepuri dintr-o cușcă să fie minimă

Determinați o modalitate de distribuire a iepurilor în cuști care să respecte condițiile de mai sus.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>p</code>.

= Date de ieșire =
Programul va afișa pe ecran <code>n</code> numere naturale, reprezentând numărul de iepuri din fiecare cușcă..

= Restricții și precizări =

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

== Exemplul 1 ==
Input:

3 10

Output:

2 3 5

== Exemplul 2 ==
Input:

999999999999 8

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n,p):
if not(1<=n<=100):
print("Constrangeri neindeplinite")
exit()
if not(1<=p<=1000000):
print("Constrangeri neindeplinite")
exit()

n, p = map(int, input().split())
ver(n,p)
v = [0] * 105

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

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

if p % n != 0:
k = p % n
i = n
while i > 0 and k:
v[i] += 1
i -= 1
k -= 1

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

</syntaxhighlight>

0819 - Generare 1

2024-01-04T17:37:00Z

Corjuc Eunice: Pagină nouă: = Cerința = Se consideră următoarele operații, care se aplică numerelor naturale: * <code>op 1</code> – se adaugă la număr cifra <code>4</code> – din <code>13</code> se obține <code>134</code> * <code>op 2</code> – se adaugă la număr cifra <code>0</code> – din <code>13</code> se obține <code>130</code> * <code>op 3</code> – dacă numărul este par, se împarte la <code>2</code> – din <code>20</code> se obține <code>10</code> Dându-se un număr natur...

= Cerința =
Se consideră următoarele operații, care se aplică numerelor naturale:

* <code>op 1</code> – se adaugă la număr cifra <code>4</code> – din <code>13</code> se obține <code>134</code>
* <code>op 2</code> – se adaugă la număr cifra <code>0</code> – din <code>13</code> se obține <code>130</code>
* <code>op 3</code> – dacă numărul este par, se împarte la <code>2</code> – din <code>20</code> se obține <code>10</code>

Dându-se un număr natural <code>n</code>, să se determine un șir de operații dintre cele de mai sus prin care, pornind de la valoarea <code>4</code>, se ajunge la <code>n</code>.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>.

= Date de ieșire =
Programul va afișa pe ecran un șir de valori din mulțimea <code>{1,2,3}</code>, astfel încât, aplicând în ordine operațiile corespunzătoare se ajunge de la valoarea <code>4</code> la valoarea <code>n</code>.

= Restricții și precizări =

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

== Exemplul 1 ==
Input:

5

Output:

3 3 2 3

Explicație:

Pornim de la <code>4</code>. Se aplica <code>op 3</code> și se obține <code>2</code>; se aplică <code>op 3</code> și se obține <code>1</code>; se aplică <code>op 2</code> și se obține <code>10</code>; se aplică <code>op 3</code> și se obține <code>5</code>.

== Exemplul 2 ==
Input:

9999999999999

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not(1<=n<=100000):
print("Constrangeri neindeplinite")
exit()

v = [0] * 10000
op = [0] * 10000
nv = 0

# 1 -> se adauga 4
# 2 -> se adauga 0
# 3 -> se imparte la 2, daca este par

n = int(input())
ver(n)
gata = False
nv += 1
v[nv] = n

while not gata:
if n == 4:
gata = True
else:
if n % 10 == 4:
nv += 1
op[nv] = 1
n //= 10
elif n % 10 == 0:
nv += 1
op[nv] = 2
n //= 10
else:
nv += 1
op[nv] = 3
n *= 2
v[nv] = n

for i in range(nv, 1, -1):
print(op[i], end=" ")

</syntaxhighlight>

0655 - Transf

2024-01-04T17:30:31Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dau două șiruri <code>a</code> și <code>b</code> cu câte <code>n</code> elemente, numere naturale din mulțimea <code>{1,2}</code>. Se dorește transformarea șirului <code>a</code> în șirul <code>b</code>, având la dispoziție următoarele operații: * interschimbarea a două elemente * înlocuirea unui element <code>1</code> cu <code>2</code> sau a unui element <code>2</code> cu <code>1</code>. Determinați pentru cele două șiruri numărul minim d...

= Cerința =
Se dau două șiruri <code>a</code> și <code>b</code> cu câte <code>n</code> elemente, numere naturale din mulțimea <code>{1,2}</code>. Se dorește transformarea șirului <code>a</code> în șirul <code>b</code>, având la dispoziție următoarele operații:

* interschimbarea a două elemente
* înlocuirea unui element <code>1</code> cu <code>2</code> sau a unui element <code>2</code> cu <code>1</code>.

Determinați pentru cele două șiruri numărul minim de operații prin care se transformă șirul <code>a</code> în șirul <code>b</code>.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, apoi cele <code>n</code> elemente ale șirului <code>a</code>, apoi cele <code>n</code> elemente ale șirului <code>b</code>.

= Date de ieșire =
Programul va afișa pe ecran numărul minim ce operații <code>C</code>.

= Restricții și precizări =

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

== Exemplul 1 ==
Input:

5

2 2 1 1 2

2 2 2 1 1

Output:

1

Explicație:

Prin interschimbarea în primul șir a elementului de pe poziția <code>3</code> cu cel de pe poziția <code>5</code> se obține al doilea șir.

== Exemplul 2 ==
Input:

999999999999

Output:

Conditii neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n):
if not (1<=n<=1000):
print("Conditii neindeplinite")
exit()

n = int(input())
ver(n)
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cnt1 = 0
cnt2 = 0

for i in range(1, n + 1):
if a[i - 1] != b[i - 1]:
if a[i - 1] == 1:
cnt1 += 1
else:
cnt2 += 1

result = max(cnt1, cnt2)
print(result)

</syntaxhighlight>

1728 - K Sum Dif

2024-01-04T17:26:44Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă un vector cu <code>n</code> elemente și un număr <code>k</code>. Se construiește un nou vector, cu <code>n-1</code> elemente, ale cărui elemente vor fi diferenţa dintre suma și modulul diferenţei a două elemente alăturate din primul vector. Apoi se construiește un alt vector, după aceeași regulă, ș. a. m. d. Afișați suma elementelor celui de-al <code>k-1</code>-lea vector construit prin această metodă. = Date de intrare = Programul ci...

= Cerința =
Se dă un vector cu <code>n</code> elemente și un număr <code>k</code>.

Se construiește un nou vector, cu <code>n-1</code> elemente, ale cărui elemente vor fi diferenţa dintre suma și modulul diferenţei a două elemente alăturate din primul vector.

Apoi se construiește un alt vector, după aceeași regulă, ș. a. m. d.

Afișați suma elementelor celui de-al <code>k-1</code>-lea vector construit prin această metodă.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code>, <code>k</code> și <code>n</code> numere naturale.

= Date de ieșire =
Programul va afișa pe ecran suma cerută.

= Restricții și precizări =

* <code>1 ≤ n ≤ 10000</code>
* cele <code>n</code> elemente ale vectorului vor fi mai mici decât <code>1000</code>
* <code>k≤50</code>

== Exemplul 1 ==
Input:

6 3

5 2 4 9 3 1

Output:

32

Explicație:

Prelucrarea primului element al noului vector se face astfel: <code>(5+2)-(5-2)=4</code> ,

Elementele primului vector construit vor fi: <code>4 4 8 6 2</code> .

Elementele celui de-al 2-lea vector construit vor fi: <code>8 8 12 4</code> , iar suma lor va fi <code>32</code> .

== Exemplul 2 ==
Input:

99999999 1

5 2 4 9 3 1

Output:

Conditions not met.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_conditions(n, k, v):
if 1 <= n <= 10000 and k <= 50 and all(0 <= x < 1000 for x in v):
return True
return False

n, k = map(int, input().split())
v = list(map(int, input().split()))

if verify_conditions(n, k, v):
while k > 1:
for i in range(n - 1):
v[i] += (v[i + 1] - abs(v[i] - v[i + 1]))
n -= 1
k -= 1

s = sum(v[:n])
print(s)
else:
print("Conditions not met.")

</syntaxhighlight>

2767 - Masterpiece 003

2024-01-04T17:20:09Z

Corjuc Eunice: Pagină nouă: = Cerința = Se consideră două numere naturale <code>n</code> și <code>k</code>. Se consideră <code>P = { p1</code> <code>, p2</code> <code>, p3</code> <code>… pk</code> <code>}</code> , șirul primelor <code>k</code> numere prime. Se consideră mulțimea <code>S = { x | x = p1e1</code> <code>* p2e2</code> <code>* … * pkek</code> <code>}</code> unde <code>e1</code> <code>, e2</code> <code>, e3</code> <code>… ek</code> sunt numere naturale. Să se afișeze în...

= Cerința =
Se consideră două numere naturale <code>n</code> și <code>k</code>.

Se consideră <code>P = { p1</code> <code>, p2</code> <code>, p3</code> <code>… pk</code> <code>}</code> , șirul primelor <code>k</code> numere prime.

Se consideră mulțimea <code>S = { x | x = p1e1</code> <code>* p2e2</code> <code>* … * pkek</code> <code>}</code> unde <code>e1</code> <code>, e2</code> <code>, e3</code> <code>… ek</code> sunt numere naturale.

Să se afișeze în ordine crescătoare primele <code>n</code> elemente mulțimii <code>S</code>.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>k</code>.

= Date de ieșire =
Programul afișează pe ecran, în ordine crescătoare, separate prin câte un spațiu, primele <code>n</code> elemente ale mulțimii <code>S</code>.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100000</code>
* <code>1 ≤ k ≤ 10</code>

== Exemplul 1 ==
Input:

40 5

Output:

1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 33 35 36 40 42 44 45 48 49 50 54 55 56 60 63

Explicație:

Oricare dintre numerele afișate conțin în descompunerea lor în factori primi doar factori din mulțimea <code>{2, 3, 5, 7, 11}</code>.

Din șirul afișat lipsesc numerele care au în descompunerea lor în factori primi și alte numere în afară de <code>2, 3, 5, 7, 11</code>. De exemplu numărul <code>26</code> nu va fi afișat pentru că, în decompunerea lui apare factorul <code>13</code>.

== Exemplul 2 ==
Input:

40 99

Output:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify(n, k):
if not (1<=n<=100000):
print("Constrangeri neindeplinite")
exit()
if not (1<=k<=10):
print("Constrangeri neindeplinite")
exit()

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

verify(n,k)

s = [0] * (n + 1)
p = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
d = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
c = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

s[1] = 1

for i in range(2, n + 1):
minim = c[1]
for j in range(1, k + 1):
if c[j] < minim:
minim = c[j]

s[i] = minim

for j in range(1, k + 1):
if c[j] == minim:
d[j] += 1
c[j] = s[d[j]] * p[j]

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

</syntaxhighlight>

1102 - Bile 2

2024-01-04T17:09:03Z

Corjuc Eunice: Pagină nouă: Pe o masă cad <code>n</code> bile săltăreţe. Fiecare este lăsată să cadă liber de la o înălţime <code>h</code>, diferită pentru fiecare bilă. Toate bilele cad simultan, cu o viteză constantă <code>(1m/s)</code> . În momentul în care bila <code>i</code> atinge masa, tendinţa ei va fi să se ridice în aer până la înălţimea <code>h - k</code>, după care aceasta cade din nou. De fiecare dată când o bilă atinge masa, aceasta va tinde să urce la o înl...

Pe o masă cad <code>n</code> bile săltăreţe. Fiecare este lăsată să cadă liber de la o înălţime <code>h</code>, diferită pentru fiecare bilă. Toate bilele cad simultan, cu o viteză constantă <code>(1m/s)</code> .

În momentul în care bila <code>i</code> atinge masa, tendinţa ei va fi să se ridice în aer până la înălţimea <code>h - k</code>, după care aceasta cade din nou. De fiecare dată când o bilă atinge masa, aceasta va tinde să urce la o înlăţime cu <code>k</code> mai mică decât cea la care a urcat anterior. Dupa multe sărituri, bilele pot obosi şi nu vor mai sări. Când bilele sar în sus, vor urca tot cu aceeaşi viteza constantă.

Dându-se <code>h</code> şi <code>k</code> pentru fiecare dintre cele <code>n</code> bile, să se răspundă la <code>m</code> întrebări de forma: La ce înălţime faţă de masă se va afla bila <code>x</code> în momentul <code>t</code> ?

= Date de intrare =
Fişierul de intrare <code>input.txt</code> conţine pe prima linie 2 numere naturale <code>n</code> şi <code>m</code>. Pe următoarele <code>n</code> linii se află o pereche de numere, <code>h</code> şi <code>k</code> . Următoarele <code>m</code> linii vor conţine <code>2</code> numere naturale <code>x</code> şi <code>t</code> cu semnificaţiile de mai sus.

= Date de ieşire =
În fişierul de ieşire <code>output.txt</code> se vor afişa <code>m</code> linii, răspunsurile la cele <code>m</code> întrebări.

= Restricţii =

* <code>1 ≤ n, m ≤ 100.000</code>

== Exemplul 1 ==
input.txt:

2 3

5 1

8 2

1 4

1 7

2 16

output.txt:

1

2

4

Explicație:

Bila <code>1</code> cade de la înălţimea <code>5</code> timp de <code>4</code> secunde apoi se opreşte la înălţimea <code>1</code>.

Bila <code>1</code> cade de la înălţimea <code>5</code> şi atinge pământul, iar în cele <code>2</code> secunde rămase ajunge la înălţimea <code>2</code>.

Bila <code>2</code> cade de la înălţimea <code>8</code>, atinge pământul şi apoi ajunge la noua sa înălţime maximă, <code>6</code>, în <code>14</code> secunde. în cele <code>2</code> secunde rămase, bila apucă să coboare la înălţimea <code>4</code>.

== Exemplul 2 ==
input.txt:

999999999999 3

5 1

8 2

1 4

1 7

2 16

Output:

Constraints not met!

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_constraints(n, m):
return 1 <= n <= 100000 and 1 <= m <= 100000

def main():
with open("input.txt", "r") as fin, open("output.txt", "w") as fout:
N = 100005
h = [0] * N
k = [0] * N

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

if not verify_constraints(n, m):
print("Constraints not met!")
return

for i in range(1, n + 1):
h[i], k[i] = map(int, fin.readline().split())

for _ in range(m):
x, t = map(int, fin.readline().split())

crt = h[x]
height = h[x]

if t <= h[x]:
fout.write(f"{h[x] - t}\n")
continue

t -= h[x]
height = 0
crt -= k[x]

while t and crt:
if t <= crt:
height += t
t = 0
else:
t -= crt
height = crt

if not t:
break

if t <= crt:
height -= t
t = 0
else:
t -= crt
height = 0

crt = max(0, crt - k[x])

fout.write(f"{height}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3775 - Prosum

2024-01-04T16:49:30Z

Corjuc Eunice: Pagină nouă: Se dau <code>N</code> numere naturale <code>a[1], a[2], ..., a[N]</code> şi un număr natural nenul <code>M</code>. = Cerința = Să se determine numărul perechilor de indici <code>(i, j)</code>, cu <code>i < j</code>, cu proprietatea că numărul <code>a[i]*a[j]+a[i]+a[j]</code> este divizibil cu <code>M</code>. = Date de intrare = Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele naturale <code>N</code> şi <code>M</code>, iar pe următoarea l...

Se dau <code>N</code> numere naturale <code>a[1], a[2], ..., a[N]</code> şi un număr natural nenul <code>M</code>.

= Cerința =
Să se determine numărul perechilor de indici <code>(i, j)</code>, cu <code>i < j</code>, cu proprietatea că numărul <code>a[i]*a[j]+a[i]+a[j]</code> este divizibil cu <code>M</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele naturale <code>N</code> şi <code>M</code>, iar pe următoarea linie cele <code>N</code> numere naturale <code>a[1], a[2], ..., a[N]</code>, separate prin spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie numărul perechilor de indici <code>(i, j)</code>, cu <code>i < j</code>, cu proprietatea că numărul <code>a[i]*a[j]+a[i]+a[j]</code> este divizibil cu <code>M</code>.

= Restricții și precizări =

* <code>2 ≤ N ≤ 100.000</code>
* <code>0 ≤ a[i] ≤ 1018</code>, pentru orice <code>i∈{1, 2, ..., N}</code>
* <code>1 ≤ M ≤ 1017</code>

== Exemplul 1 ==
input.txt:

4 13

6 15 6 1

output.txt:

2

Explicație:

Există două perechi de indici având proprietatea cerută, <code>(1,4)</code> şi <code>(3,4)</code>, deoarece avem <code>6*1+6+1=13</code>, care este divizibil cu <code>M=13</code>.

== Exemplul 2 ==
input.txt:

99999999999999 13

6 15 6 1

Output:

Invalid input. Please check the constraints.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_valid_input(N, M, numbers):
if not (2 <= N <= 100000):
return False
if not (1 <= M <= 10**17):
return False
if not all(0 <= a_i <= 10**18 for a_i in numbers):
return False
return True

def count_pairs_with_property(N, M, numbers):
count = 0
for i in range(N):
for j in range(i + 1, N):
if (numbers[i] * numbers[j] + numbers[i] + numbers[j]) % M == 0:
count += 1
return count

def main():
with open("input.txt", "r") as fin:
N, M = map(int, fin.readline().split())
numbers = list(map(int, fin.readline().split()))

if not is_valid_input(N, M, numbers):
print("Invalid input. Please check the constraints.")
return

result = count_pairs_with_property(N, M, numbers)

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

if __name__ == "__main__":
main()

</syntaxhighlight>

3401 - Spp

2024-01-04T03:43:19Z

Corjuc Eunice: Pagină nouă: După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr <code>x</code>, iar altul un număr <code>y</code> mai mare sau egal cu <code>x</code>. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la <code>x</code> și <code>y</code>. Voi trebuie să rezolvați ceva asemănător, doar că știți numai ce zice primul și ultimul băiat. Pentru a-i verifica dacă...

După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr <code>x</code>, iar altul un număr <code>y</code> mai mare sau egal cu <code>x</code>. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la <code>x</code> și <code>y</code>. Voi trebuie să rezolvați ceva asemănător, doar că știți numai ce zice primul și ultimul băiat. Pentru a-i verifica dacă greșesc la calcule, în schimb, trebuie să găsiți numărul pe care l-ar putea spune al doilea.

Formal, pentru două numere <code>x</code> și <code>y</code> se definește <code>SPP(x,y) = x2</code> <code>+ (x+1)2</code> <code>+...+ y2</code> (suma pătratelor perfecte de la <code>x</code> la <code>y</code>).

Se dau <code>Q</code> întrebări de tipul <code>x p</code> și se cere cel mai mic <code>y</code> mai mare sau egal ca <code>x</code> pentru care <code>SPP(x,y) ≥ p2</code>.

= Cerința =
Să se calculeze pentru fiecare întrebare <code>p</code> minimum, pentru care relația este satisfăcută.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie un număr natural <code>Q</code>. Pe liniile <code>2</code>, <code>3</code>, …, <code>Q+1</code> se află câte o pereche <code>x p</code> care satisface restricțiile.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține răspunsul la fiecare întrebare.

= Restricții și precizări =

* <code>Q ≤ 100.000</code>

== Exemplul 1 ==
input.txt:

2

1 5

10 19

output.txt:

4

12

Explicație:

1^2 + 2^2 + 3^2 + 4^2 = 30 >= 5^2

10^2 + 11^2 + 12^2 = 365 >= 19^2

== Exemplul 2 ==
input.txt:

9999999999999

1 5

10 19

Output:

Error: Q is not within the valid range (1 <= Q <= 100,000)

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

def verify_constraints(Q):
if not (1 <= Q <= 100000):
sys.exit("Error: Q is not within the valid range (1 <= Q <= 100,000)")

with open("input.txt", "r") as f, open("output.txt", "w") as g:
Q = int(f.readline())
verify_constraints(Q)
queries = [tuple(map(int, f.readline().split())) for _ in range(Q)]

for x, p in queries:
def binarys(x, st, dr, pp):
sol = 0
px = (1 * x * (x + 1) * (2 * x + 1)) // 6
while st <= dr:
mid = (st + dr) // 2
py = (1 * mid * (mid + 1) * (2 * mid + 1)) // 6

if py - px >= pp:
sol = mid
dr = mid - 1
else:
st = mid + 1
return sol

y = binarys(x - 1, x, x + 1500000, 1 * p * p)
g.write(str(y) + '\n')

</syntaxhighlight>

2960 - Abx

2024-01-04T03:36:03Z

Corjuc Eunice: Pagină nouă: Un număr natural <code>n</code> se numește putere dacă există două numere naturale <code>a</code>, <code>b</code>, <code>a ≥ 1</code>, <code>b ≥ 2</code> astfel încât . De exemplu, numerele <code>32</code> , <code>169</code> , <code>1</code> sunt puteri ( , , ), iar <code>72</code> , <code>2000</code> și <code>31</code> nu sunt puteri. Se citesc numerele naturale <code>N</code> , <code>M</code> și un șir de <code>N</code> numere naturale din intervalul <c...

Un număr natural <code>n</code> se numește putere dacă există două numere naturale <code>a</code>, <code>b</code>, <code>a ≥ 1</code>, <code>b ≥ 2</code> astfel încât . De exemplu, numerele <code>32</code> , <code>169</code> , <code>1</code> sunt puteri ( , , ), iar <code>72</code> , <code>2000</code> și <code>31</code> nu sunt puteri.

Se citesc numerele naturale <code>N</code> , <code>M</code> și un șir de <code>N</code> numere naturale din intervalul <code>[1,M]</code>.

= Cerința =
Pentru fiecare din cele <code>N</code> numere determinați câte un număr natural din intervalul <code>[1,M]</code>, cu proprietatea că este o putere și pentru orice altă putere <code>p</code> din intervalul <code>[1,M]</code> este îndeplinită condiția , unde <code>|x|</code> reprezintă valoarea absolută a lui <code>x</code> (modulul).

Dacă există două puteri egal depărtate de se va alege puterea cea mai mică. De exemplu pentru numărul <code>26</code>, dintre puterile <code>25</code> și <code>27</code> va fi ales numărul <code>25</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie două numere <code>N</code> și <code>M</code>, iar pe fiecare dintre următoarele <code>N</code> linii se găsește câte un număr natural (<code>1 ≤ i ≤ N</code>), cu semnificația de mai sus. 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>output.txt</code> va conține <code>N</code> linii, pe fiecare linie <code>i</code> (<code>1 ≤ i ≤ N</code>) aflându-se numărul natural cu semnificația din enunț.

= Restricții și precizări =

* 1<=n<=5000
* 10<=m<=10^18

== Exemplul 1 ==
input.txt:

8 1000

345

99

999

500

123

124

99

256

output.txt:

343

100

1000

512

121

125

100

256

Explicație:

343 = 7^3

100 = 10^2

1000 = 10^3

512 = 2^9

121 = 11^2

125 = 5^3

100 = 10^2

256 = 2^8

== Exemplul 2 ==
input.txt:

999999999999 1000

345

99

999

500

123

124

99

256

Output:

Error: n is not within the valid range (1 <= n <= 5000)

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

def verify_constraints(n, m):
if not (1 <= n <= 5000):
sys.exit("Error: n is not within the valid range (1 <= n <= 5000)")

if not (10 <= m <= 10**18):
sys.exit("Error: m is not within the valid range (1 <= m <= 10^18)")

def lgput(x, y):
ans = 1
aux = x
p = 1
while p <= y:
if y & p:
ans *= aux
aux *= aux
p <<= 1
return ans

def cautb(x, put):
st = 1
dr = int(x ** (1 / put))
while st <= dr:
mij = (st + dr) // 2
if lgput(mij, put) > x:
dr = mij - 1
else:
st = mij + 1
return dr

with open("input.txt", "r") as f, open("output.txt", "w") as g:
n, m = map(int, f.readline().split())
verify_constraints(n, m)
a_values = [int(f.readline()) for _ in range(n)]

for a in a_values:
sol = 0
dif = m + 100

for j in range(2, 61):
y = cautb(a, j)
z = lgput(y, j)

if abs(a - z) <= dif and z <= m:
sol = z
dif = abs(a - z)

z = lgput(y + 1, j)

if abs(a - z) < dif and z <= m:
sol = z
dif = abs(a - z)

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

</syntaxhighlight>

2455 - Plaja 2

2024-01-04T03:16:41Z

Corjuc Eunice: Pagină nouă: Zizi îşi va petrece concediul în această vară într-o frumoasă staţiune de la Marea Neagră. Acolo va sta <code>N</code> zile. Zilele sunt numerotate de la <code>1</code> la <code>N</code>. În fiecare dintre cele <code>N</code> zile de concediu, ea intenţionează să facă plajă un număr cât mai mare de unităţi de timp. Va trebui să ţină seama totuşi de prognoza meteo, care este nefavorabilă în <code>K</code> dintre cele <code>N</code> zile, respectiv î...

Zizi îşi va petrece concediul în această vară într-o frumoasă staţiune de la Marea Neagră. Acolo va sta <code>N</code> zile. Zilele

sunt numerotate de la <code>1</code> la <code>N</code>. În fiecare dintre cele <code>N</code> zile de concediu, ea intenţionează să facă plajă un număr cât

mai mare de unităţi de timp. Va trebui să ţină seama totuşi de prognoza meteo, care este nefavorabilă în <code>K</code> dintre cele <code>N</code> zile, respectiv în zilele <code>z[1]</code>, <code>z[2]</code>, …, <code>z[k]</code>. În fiecare dintre aceste <code>K</code> zile va ploua sau va fi prea mult soare, iar Zizi va trebui să-şi limiteze timpii de plajă la cel mult <code>t[1]</code>, <code>t[2]</code>, …, <code>t[k]</code> unităţi de timp. De asemenea, din motive de confort fizic, Zizi doreşte ca diferenţa în valoare absolută a timpilor de plajă între oricare două zile consecutive să nu depăşească <code>T</code>.

= Cerința =
Cunoscând zilele <code>z[1]</code>, <code>z[2]</code>, …, <code>z[k]</code> în care există limitările <code>t[1]</code>, <code>t[2]</code>, …, <code>t[k]</code> pentru timpul de plajă şi valoarea <code>T</code>, să se determine numărul maxim de unităţi de timp pe care Zizi le poate petrece la plajă într-o singură zi dintre cele <code>N</code> zile de concediu.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie trei numere naturale <code>N</code>, <code>K</code> şi <code>T</code> separate printr-un spaţiu, reprezentând numărul de zile de concediu, numărul de zile în care există limitări pentru timpul de plajă şi diferenţa maximă

admisă a timpilor de plajă pentru oricare două zile consecutive. Pe fiecare dintre următoarele <code>K</code> linii se află câte două numere <code>z</code> şi <code>t</code>, despărțite printr-un spațiu, reprezentând numărul de ordine al unei zile cu limitări pentru timpul de plajă, respectiv limita de timp pentru ziua respectivă. Valorile <code>z[1]</code>, <code>z[2]</code>, …, <code>z[k]</code> sunt în ordine strict crescătoare.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie un singur număr natural <code>tmax</code>, reprezentând numărul maxim de

unităţi de timp pe care Zizi le poate petrece făcând plajă într-una din cele <code>N</code> zile de concediu.

= Restricții și precizări =

* <code>1 ≤ N ≤ 1 000 000 000</code>
* <code>1 ≤ K ≤ 100 000</code>

== Exemplul 1 ==
input.txt:

3 1 3

1 2

output.txt:

8

Explicație:

În prima zi timpul de plajă este limitat la <code>2</code> unități de timp. În ziua a doua timpul maxim de plajă este <code>2 + 3</code>, iar în ziua a treia, timpul maxim este <code>2 + 3 + 3 = 8</code> unități de timp.

== Exemplul 2 ==
input.txt:

5 2 11

2 2

4 5

output.txt:

16

Explicație:

În ziua <code>2</code> timpul de plajă este limitat la <code>2</code> unități de timp, iar în zilele <code>1</code> și <code>3</code> nu există limitare. Atunci timpul maxim de plajă pentru zilele <code>1</code> sau <code>3</code> este <code>2 + 11 = 13</code>. În ziua <code>4</code> timpul de plajă este limitat la <code>5</code> unități de timp, iar în ziua <code>5</code> nu există limitare. Deci în ziua <code>5</code> timpul maxim de plajă este <code>5 + 11 = 16</code>.

== Exemplul 3 ==
input.txt:

99999999999999999999 2 11

2 2

4 5

Output:

Error: N is not within the valid range (1 <= N <= 1,000,000,000)

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
# prof. Constantin Galatan
# solutie O(K * log T)

import sys

def verify_constraints(N, K):
if not (1 <= N <= 1000000000):
sys.exit("Error: N is not within the valid range (1 <= N <= 1,000,000,000)")

if not (1 <= K <= 100000):
sys.exit("Error: K is not within the valid range (1 <= K <= 100,000)")

def try_time(t0, i):
return d[i + 1] - d[i] >= (t0 - t[i] + T - 1) // T + (t0 - t[i + 1] + T - 1) // T

input_file = open("input.txt", "r")
output_file = open("output.txt", "w")

N, K, T = map(int, input_file.readline().split())
verify_constraints(N, K)

d = [0] * (K + 1)
t = [0] * (K + 1)

for i in range(1, K + 1):
d[i], t[i] = map(int, input_file.readline().split())

for i in range(1, K):
t[i + 1] = min(t[i + 1], t[i] + (d[i + 1] - d[i]) * T)

for i in range(K - 1, 0, -1):
t[i] = min(t[i], t[i + 1] + (d[i + 1] - d[i]) * T)

res = 0
for i in range(1, K):
l, r = max(t[i], t[i + 1]), 1 * N * T
tmp = 0
while l <= r:
m = (l + r) // 2
if try_time(m, i):
l = m + 1
tmp = m
else:
r = m - 1
res = max(res, tmp)

res = max(res, max(t[K] + (N - d[K]) * T, t[1] + (d[1] - 1) * T))
output_file.write(str(res))

input_file.close()
output_file.close()

</syntaxhighlight>

2453 - Rosii Mici

2024-01-04T02:25:20Z

Corjuc Eunice: Pagină nouă: Dan este un mare pasionat al fructelor, printre preferatele sale fiind strugurii şi pepenii. Însă recent şi-a descoperit și pasiunea pentru legume, în special pentru roşii, dar mai ales roşiile mici. Spre norocul lui, grădina bunicului este plină de roşii. Grădina are forma unei matrice cu <code>N</code> linii și <code>M</code> coloane cu elemente numere naturale, nu neapărat distincte, unde fiecare element din matrice reprezintă dimensiunea unei roşii. Matric...

Dan este un mare pasionat al fructelor, printre preferatele sale fiind strugurii şi pepenii. Însă recent şi-a descoperit și pasiunea pentru legume, în special pentru roşii, dar mai ales roşiile mici. Spre norocul lui, grădina bunicului este plină de roşii. Grădina are forma unei matrice cu <code>N</code> linii și <code>M</code> coloane cu elemente numere naturale, nu neapărat distincte, unde fiecare element din matrice reprezintă dimensiunea unei roşii. Matricea are proprietatea că oricare coloană are valorile ordonate crescător de sus în jos, adică de la prima spre ultima linie. Bunicul său îi cere să rezolve <code>Q</code> sarcini. Pentru fiecare sarcină, Dan primeşte un număr natural <code>x</code> şi trebuie să găsească o submatrice de arie maximă care începe de pe linia <code>1</code> a matricei care reprezintă grădina şi are toate elementele mai mici sau egale decât <code>x</code>. Pentru determinarea submatricei cerute, Dan are voie să mute toate valorile unei coloane în fața oricărei alte coloane. De asemenea, îi este permis să facă oricâte mutări de tipul acesta.

= Cerința =
Să se calculeze aria maximă a unei submatrice care respectă specificațiile din enunț, pentru fiecare din cele <code>Q</code> sarcini date de către bunic.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie trei numere naturale <code>N</code>, <code>M</code> și <code>Q</code> separate printr-un spaţiu, având semnificația din enunț. Pe fiecare dintre următoarele <code>N</code> linii se află câte <code>M</code> numere naturale despărțite prin câte un spațiu, reprezentând valorile matricei. Pe următoarele <code>Q</code> linii se află câte un număr natural <code>x</code>, reprezentând dimensiunea unei roşii.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe primele <code>Q</code> linii câte un număr natural, reprezentând aria maximă cerută

pentru fiecare sarcină, în ordinea în care acestea apar în fișierul de intrare.

= Restricții și precizări =

* <code>1 ≤ N, M ≤ 1000</code>
* <code>1 ≤ Q ≤ 100 000</code>
* <code>1 ≤ A[i][j] ≤ N * M</code>, <code>1 ≤ i ≤ N</code>, <code>1 ≤ j ≤ M</code>

== Exemplul 1 ==
input.txt:

3 4 3

1 9 6 2

1 10 10 4

7 15 10 6

6

10

9

output.txt:

4

9

6

Explicație:

Pentru rezolvarea primei sarcini Dan mută prima coloană în fața celei de a patra obținând matricea:

<code>9 6 1 2</code>

<code>10 10 1 4</code>

<code>15 10 7 6</code>

Alege apoi submatricea cu colțul stânga sus în <code>(1,3)</code> și colțul dreapta jos în <code>(2,4)</code>. Aria acesteia este <code>4</code>.

Pentru rezolvarea celei de a doua sarcini, Dan mută prima coloană în fața celei de a treia obținând matricea:

<code>9 1 6 2</code>

<code>10 1 10 4</code>

<code>15 7 10 6</code>

Soluția este submatricea cu colțul stânga sus în <code>(1,2)</code> și colțul dreapta jos în <code>(3,4)</code>. Aria acesteia este <code>9</code>.

Pentru rezolvarea celei de a treia sarcini, Dan mută ultima coloană în fața primei coloane, obținând matricea:

<code>2 1 9 6</code>

<code>4 1 10 10</code>

<code>6 7 15 10</code>

Soluția este submatricea cu colțul stânga sus în <code>(1,1)</code> și colțul dreapta jos în <code>(3,2)</code>. Aria acesteia este <code>6</code>.

== Exemplul 2 ==
input.txt:

9999999 4 3

1 9 6 2

1 10 10 4

7 15 10 6

6

10

9

Output:

ValueError: Error: 1 <= n <= 1000

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_constraints(n, m, q):
if not (1 <= n <= 1000):
raise ValueError("Error: 1 <= n <= 1000")
if not (1 <= m <= 1000):
raise ValueError("Error: 1 <= m <= 1000")
if not (1 <= q <= 100000):
raise ValueError("Error: 1 <= q <= 100000")

def main():
def read_int():
return int(fin.readline().strip())

with open("input.txt", "r") as fin, open("output.txt", "w") as fout:
n, m, q = map(int, fin.readline().split())
verify_constraints(n, m, q)

positions = [[] for _ in range(n * m + 5)]
minn = [0] * m
height = [0] * (m + 1)
sum_ = [0] * (n + 1)
ans = [0] * (n * m + 5)
sol = 0

for i in range(n):
row = list(map(int, fin.readline().split()))
for j in range(m):
x = row[j]
if not (minn[j] <= x):
raise ValueError("Error: minn[j] <= x")
minn[j] = x
positions[x].append(j)

for val in range(1, n * m + 1):
for j in positions[val]:
height[j] += 1
sum_[height[j]] += 1
sol = max(sol, sum_[height[j]] * height[j])
ans[val] = sol

for i in range(1, n * m + 1):
ans[i] = max(ans[i - 1], ans[i])

for _ in range(q):
x = read_int()
fout.write(str(ans[x]) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3747 - Bile 4

2024-01-04T01:42:37Z

Corjuc Eunice: Pagină nouă: = Enunț = Presupunem că avem două cutii notate <code>A</code> și <code>B</code>. Cutia <code>A</code> conține <code>N</code> bile numerotate cu numerele naturale distincte: <code>0</code>, <code>1</code>, <code>2</code>, . . . , <code>N − 1</code>. Cutia <code>B</code> este goală. Spunem că o bilă dintr-o cutie este <code>bila specială</code> a acestei cutii dacă numărul <code>X</code> cu care este numerotată această bilă este egal cu media aritmetică a nume...

= Enunț =
Presupunem că avem două cutii notate <code>A</code> și <code>B</code>. Cutia <code>A</code> conține <code>N</code> bile numerotate cu numerele naturale distincte: <code>0</code>, <code>1</code>, <code>2</code>, . . . , <code>N − 1</code>. Cutia <code>B</code> este goală.

Spunem că o bilă dintr-o cutie este <code>bila specială</code> a acestei cutii dacă numărul <code>X</code> cu care este numerotată această bilă este egal cu media aritmetică a numerelor celorlalte bile din cutie.

La un moment dat, cineva mută bila cu numărul <code>K</code> din cutia <code>A</code> în cutia <code>B</code>.

Vi se cere să alegeți alte <code>K</code> bile, din cutia <code>A</code>, pe care să le mutați în cutia <code>B</code> astfel încât cutia <code>B</code> să conțină <code>K + 1</code> bile, iar bila cu numărul <code>K</code> să fie bila specială a cutiei <code>B</code>.

= Cerința =
Scrieți un program care citește numerele <code>N</code> și <code>K</code>, apoi determină:

# dacă, înainte să fie mutate bile din cutia <code>A</code> în cutia <code>B</code>, există o bilă specială în cutia <code>A</code>; în caz afirmativ, programul determină numărul <code>X</code> cu care este numerotată această bilă specială;
# cel mai mic (în sens lexicografic) șir strict crescător al numerelor celor <code>K</code> bile care pot fi mutate din cutia <code>A</code> în cutia <code>B</code> astfel încât bila cu numărul <code>K</code> să fie bila specială a cutiei <code>B</code>;
# cel mai mare (în sens lexicografic) șir strict crescător al numerelor celor <code>K</code> bile care pot fi mutate din cutia <code>A</code> în cutia <code>B</code> astfel încât bila cu numărul <code>K</code> să fie bila specială a cutiei <code>B</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie trei numere naturale <code>C</code>, <code>N</code> și <code>K</code>, separate prin câte un spațiu. <code>C</code> reprezintă cerința care trebuie rezolvată (<code>1</code>, <code>2</code> sau <code>3</code>), iar <code>N</code> și <code>K</code> au semnificația din enunț.

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

* dacă <code>C = 1</code>, pe prima linie, numărul natural X reprezentând numârul bilei speciale din cutia <code>A</code> sau valoarea <code>−1</code> dacă cutia <code>A</code> nu conține o astfel de bilă (reprezentând răspunsul la cerința <code>1</code>);
* dacă <code>C = 2</code>, pe prima linie, un șir strict crescător de <code>K</code> numere naturale, separate prin câte un spațiu (reprezentând răspunsul la cerința <code>2</code>);
* dacă <code>C = 3</code>, pe prima linie, un șir strict crescător de <code>K</code> numere naturale, separate prin câte un spațiu (reprezentând răspunsul la cerința <code>3</code>).

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>
* numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât <code>1.000.000.000</code>
* <code>N</code> număr natural, <code>4 ≤ N ≤ 100000</code>
* <code>K</code> număr natural, <code>2 ≤ K ≤ N/2</code>

== Exemplul 1 ==
input.txt:

1 9 3

output.txt:

4

Explicație:

Se rezolvă cerința <code>1</code>.

<code>N = 9</code>. Avem <code>9</code> bile inscript, ionate cu <code>0, 1, 2, 3, 4, 5, 6, 7, 8</code>.

Bila specială este <code>X = 4</code> deoarece: <code>X = (0 + 1 + 2 + 3 + 5 + 6 + 7 + 8)/8 = 32/8 = 4</code>

== Exemplul 2 ==
input.txt:

1 3 3

output.txt:

-1

Explicație:

Se rezolvă cerința <code>1</code>.

<code>N = 8</code>. Se va scrie în fișierul de ieșire valoarea <code>−1</code> deoarece cutia <code>A</code> nu conține nicio bilă specială.

== Exemplul 3 ==
input.txt:

9999999 8 3

Ouput:

ValueError: Invalid value for C

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
# Function to validate input constraints
def validate_input_constraints(C, N, K):
if not (1 <= C <= 3):
raise ValueError("Invalid value for C")
if not (4 <= N <= 100000):
raise ValueError("Invalid value for N")
if not (2 <= K <= N // 2):
raise ValueError("Invalid value for K")

# Open input and output files
fin = open("input.txt", "r")
fout = open("output.txt", "w")

# Read input values
C, N, K = map(int, fin.readline().split())

# Validate input constraints
validate_input_constraints(C, N, K)

# Function to write the result to the output file
def write_result(s):
fout.write(" ".join(map(str, s)) + '\n')

# Function for case 1
def c1():
if N % 2 == 1:
fout.write(str((N - 1) // 2) + '\n')
else:
fout.write("-1\n")

# Function for case 2
def c2():
K_square = K * K
S = 0
s = [0] * K

for i in range(K - 1):
s[i] = i
S += s[i]

if K_square - S <= N - 1:
s[K - 1] = K_square - S
write_result(s)
return

s[K - 1] = K - 1
S += s[K - 1]

dif = K_square - S
g = dif // (N - K)
rest = dif % (N - K)

for i in range(1, g + 1):
s[K - i] += (N - K)

if s[K - (g + 1)] + rest != K:
s[K - (g + 1)] += rest
else:
s[K - (g + 1)] += (rest + 1)
s[K - g] -= 1

write_result(s)

# Function for case 3
def c3():
s = [0] * K

if K % 2 == 0:
# K is even
m = K // 2
for i in range(K):
s[i] = m
m += 1
if m == K:
m += 1
write_result(s)
return

# K is odd
M = K // 2
s[0] = M
s[K - 1] = 2 * K + 1 - s[0]
s[M] = K - 1

for i in range(1, M):
s[i] = M + i
s[K - 1 - i] = 2 * K - s[i]

write_result(s)

# Main program
if C == 1:
c1()
elif C == 2:
c2()
elif C == 3:
c3()

# Close input and output files
fin.close()
fout.close()

</syntaxhighlight>

4184 - Bac Nume

2024-01-04T01:18:14Z

Corjuc Eunice: Pagină nouă: = Cerința = Scrieți subprogramul <code>FNume</code> cu următorul antet: def FNume(s) = Restricții și precizări = * Numele funcției va fi <code>FNume</code> = Exemplu: = După apelul <code>FNume("David Popovici")</code>, se va afișa <code>Popovici2022</code>. == Rezolvare == <syntaxhighlight lang="python3" line="1"> def FNume(s): # Verificare dacă șirul de intrare nu este gol if not s: return "" # Descompunem numele și prenumele nume, p...

= Cerința =
Scrieți subprogramul <code>FNume</code> cu următorul antet:
def FNume(s)

= Restricții și precizări =

* Numele funcției va fi <code>FNume</code>

= Exemplu: =
După apelul <code>FNume("David Popovici")</code>, se va afișa <code>Popovici2022</code>.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def FNume(s):
# Verificare dacă șirul de intrare nu este gol
if not s:
return ""

# Descompunem numele și prenumele
nume, prenume = s.split()

# Concatenăm numele de familie și adăugăm "2022"
return f"{nume}2022"

# Exemplu de utilizare:
nume_complet = "David Popovici"
rezultat = FNume(nume_complet)
print(f"Numele complet: {rezultat}")

</syntaxhighlight>

4061 - Lant Q

2024-01-04T00:26:41Z

Corjuc Eunice: Pagină nouă: = Cerinţa = Se dă un graf neorientat cu n vârfuri și un număr natural <code>q</code>. Să se determine toate lanțurile elementare formate din cel puțin o muchie, cu extremitatea finală în vârful <code>q</code>. = Date de intrare = Fişierul de intrare <code>input.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>...

= Cerinţa =
Se dă un graf neorientat cu n vârfuri și un număr natural <code>q</code>. Să se determine toate lanțurile elementare formate din cel puțin o muchie, cu extremitatea finală în vârful <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>input.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Pe ultima linie se află numărul <code>q</code>.

= Date de ieşire =
Fişierul de ieşire <code>output.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitatea finală în vârful <code>q</code>, fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu. Dacă graful nu conține niciun lanț elementar format din cel puțin o muchie, cu extremitatea finală în vârful <code>q</code>, atunci se va afișa <code>NU EXISTA</code>.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ q ≤ n</code>
* <code>1 ≤ i, j ≤ n</code>
* muchiile se pot repeta în fișierul de intrare

== Exemplul 1 ==
input.txt:

5 8

1 4

1 3

3 5

4 5

2 4

1 2

4 2

3 4

5

output.txt:

1 2 4 3 5

1 2 4 5

1 3 4 5

1 3 5

1 4 3 5

1 4 5

2 1 3 4 5

2 1 3 5

2 1 4 3 5

2 1 4 5

2 4 1 3 5

2 4 3 5

2 4 5

3 1 2 4 5

3 1 4 5

3 4 5

3 5

4 1 3 5

4 2 1 3 5

4 3 5

4 5

== Exemplul 2 ==
input.txt:

99999 8

1 4

1 3

3 5

4 5

2 4

1 2

4 2

3 4

5

Ouput:

Constraint violation: 1 ≤ n ≤ 20

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_constraints(n):
if not (1 <= n <= 20):
print("Constraint violation: 1 ≤ n ≤ 20 and 1 ≤ q ≤ n")
exit()

def is_edge_chain(chain):
for i in range(len(chain) - 1):
if not graph[chain[i]][chain[i + 1]]:
return False
return True

def find_elementary_chains(v, end_vertex, path):
path.append(v)
if v == end_vertex and len(path) > 1:
chains.append(path.copy())
else:
for neighbor in range(1, n + 1):
if graph[v][neighbor] and neighbor not in path:
find_elementary_chains(neighbor, end_vertex, path)
path.pop()

def write_chains_to_file(chains, output_file):
if not chains:
output_file.write("NU EXISTA\n")
else:
chains.sort()
for chain in chains:
output_file.write(" ".join(map(str, chain)) + '\n')

if __name__ == "__main__":
with open("input.txt", "r") as fin, open("output.txt", "w") as fout:
n, m = map(int, fin.readline().split())

verify_constraints(n)

graph = [[False] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
a, b = map(int, fin.readline().split())
graph[a][b] = graph[b][a] = True

end_vertex = int(fin.readline().strip())

chains = []
for start_vertex in range(1, n + 1):
if start_vertex != end_vertex:
find_elementary_chains(start_vertex, end_vertex, [])

write_chains_to_file(chains, fout)

</syntaxhighlight>

1318 - Bipartit 1 Mare

2024-01-03T22:40:07Z

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

= Cerința =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>. Să se verifice dacă graful este bipartit.

= Date de intrare =
Fişierul de intrare <code>input.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieșire =
Fişierul de ieşire <code>output.txt</code> va conţine pe prima linie mesajul <code>DA</code>, dacă graful este bipartit, respectiv <code>NU</code> în caz contrar.

Dacă mesajul este <code>DA</code> , următoarele două linii vor conţine două mulţimi care formează partiţia vârfurilor. Elementele fiecărei mulţimi vor fi afişate în ordine crescătoare, separate prin exact un spaţiu. Prima mulţime va fi cea care conţine vârful <code>1</code>.

= Restricții și precizări =

* <code>1 < n ≤ 100 - atentie</code>
* <code>1 ≤ i , j ≤ n</code>
* se recomanda utilizarea metodei backtracking
* muchiile se pot repeta

== Exemplul 1 ==
input.txt:

7 6

1 4

1 6

6 5

3 2

3 5

3 7

output.txt:

DA

1 2 5 7

3 4 6

== Exemplul 2 ==
input.txt

99999999 6

1 4

1 6

6 5

3 2

3 5

3 7

Output:

Constraint violation: 1 < n ≤ 100

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

def verify_constraints():
if not (1 < n <= 100):
print("Constraint violation: 1 < n ≤ 100")
exit()

def bf_iterative():
global prim, ultim, varf
while prim <= ultim:
varf = c[prim]
for k in range(1, n + 1):
if a[varf][k] == 1 and viz[k] == 0:
ultim += 1
c[ultim] = k
viz[k] = 1
prim += 1

if __name__ == "__main__":
a = [[0] * 101 for _ in range(101)]
c = [0] * 101
viz = [0] * 101
s = [0] * 101

prim, ultim, varf = 0, 0, 0
n, m = 0, 0
ok = 1

with open("input.txt", "r") as f:
n, m = map(int, f.readline().split())
verify_constraints()
for _ in range(m):
x, y = map(int, f.readline().split())
a[x][y] = a[y][x] = 1

with open("output.txt", "w") as g:
verify_constraints()

for nd in range(1, n + 1):
if viz[nd] == 0:
for k in range(1, n + 1):
c[k] = 0
viz[k] = 0

prim, ultim = 1, 1
viz[nd] = 1
c[prim] = nd
bf_iterative()

for k in range(1, ultim):
for j in range(k + 1, ultim + 1):
if a[c[k]][c[j]] == 1:
if s[c[k]] == 0 and s[c[j]] == 0:
s[c[k]] = 1
s[c[j]] = -1
elif s[c[k]] != 0 and s[c[j]] == 0:
s[c[j]] = -1 * s[c[k]]
elif s[c[k]] == s[c[j]] and s[c[k]] != 0 and s[c[j]] != 0:
ok = 0

if ok == 0:
g.write("NU")
else:
g.write("DA\n")
for i in range(1, n + 1):
if s[i] == 1:
g.write(str(i) + ' ')
g.write('\n')
for i in range(1, n + 1):
if s[i] == -1:
g.write(str(i) + ' ')

</syntaxhighlight>

3282 – Transform1

2024-01-03T21:37:59Z

Corjuc Eunice: Pagină nouă: Fie un șir <code>a = a1</code>, <code>a2</code>, …, <code>aN</code> de numere naturale, nu neapărat distincte, cuprinse între <code>1</code> și <code>N</code>. Fie de asemenea două numere naturale <code>x</code> și <code>y</code>. Se definește operația <code>transform(i)</code> astfel: se determină valoarea <code>w = 1 + (x * i + y * ai) mod N</code>, apoi toate elementele egale cu <code>ai</code> din secvența <code>ai</code>, <code>ai+1</code>, …, <code>aN</cod...

Fie un șir <code>a = a1</code>, <code>a2</code>, …, <code>aN</code> de numere naturale, nu neapărat distincte, cuprinse între <code>1</code> și <code>N</code>. Fie de asemenea două numere naturale <code>x</code> și <code>y</code>. Se definește operația <code>transform(i)</code> astfel: se determină valoarea <code>w = 1 + (x * i + y * ai) mod N</code>, apoi toate elementele egale cu <code>ai</code> din secvența <code>ai</code>, <code>ai+1</code>, …, <code>aN</code> își modifică valoarea în <code>w</code>. De exemplu, pentru șirul <code>a=1, 7, 1, 7, 3, 4, 7</code>, <code>x = 4</code>, <code>y = 5</code>, operația <code>transform(4)</code> înseamnă că <code>w = 1+(4*4+5*7) mod 7 = 3</code>, deci șirul devine <code>1</code>, <code>7</code>, <code>1</code>, <code>3</code>, <code>3</code>, <code>4</code>, <code>3</code> (toate elementele de la poziția <code>4</code> la <code>7</code> și egale cu <code>7</code> s-au modificat în <code>3</code>). După fiecare operație de tip transform se calculează suma elementelor șirului obținut.

= Cerința =
Să se determine suma maximă care s-a obținut în șirul <code>a</code> efectuând pe rând asupra șirului operațiile <code>transform(1)</code>, <code>transform(2)</code>, …, <code>transform(N)</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele naturale <code>N</code>, <code>x</code> și <code>y</code>. Pe linia a doua se găsesc, separate prin spațiu, elementele șirului <code>a</code>.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie un singur număr natural reprezentând suma maximă obținută.

= Restricții și precizări =

* <code>3 ≤ N ≤ 256.000</code>
* <code>1 ≤ x, y ≤ N</code>

== Exemplul 1 ==
input.txt:

7 4 5

1 7 1 7 3 4 7

ouput.txt:

35

Explicație:

După <code>transform(1)</code>, în care w = 3, șirul devine <code>3</code>, <code>7</code>, <code>3</code>, <code>7</code>, <code>3</code>, <code>4</code>, <code>7</code> care are suma <code>34</code>.

După <code>transform(2)</code>, în care <code>w = 2</code>, șirul devine <code>3</code>, <code>2</code>, <code>3</code>, <code>2</code>, <code>3</code>, <code>4</code>, <code>2</code> care are suma <code>19</code>.

După <code>transform(3)</code>, în care <code>w = 7</code>, șirul devine <code>3</code>, <code>2</code>, <code>7</code>, <code>2</code>, <code>7</code>, <code>4</code>, <code>2</code> care are suma <code>27</code>.

După <code>transform(4)</code>, în care <code>w = 6</code>, șirul devine <code>3</code>, <code>2</code>, <code>7</code>, <code>6</code>, <code>7</code>, <code>4</code>, <code>6</code> care are suma <code>35</code>.

După <code>transform(5)</code>, în care <code>w = 7</code>, șirul devine <code>3</code>, <code>2</code>, <code>7</code>, <code>6</code>, <code>7</code>, <code>4</code>, <code>6</code> care are suma <code>35</code>.

După <code>transform(6)</code>, în care <code>w = 3</code>, șirul devine <code>3</code>, <code>2</code>, <code>7</code>, <code>6</code>, <code>7</code>, <code>3</code>, <code>6</code> care are suma <code>34</code>.

După <code>transform(7)</code>, în care <code>w = 3</code>, șirul devine <code>3</code>, <code>2</code>, <code>7</code>, <code>6</code>, <code>7</code>, <code>3</code>, <code>3</code> care are suma <code>31</code>.

Suma maximă care s-a obținut este <code>35</code>.

== Exemplul 2 ==
input.txt:

999999999 4 5

1 7 1 7 3 4 7

Output:

Invalid input. Please make sure 3 ≤ N ≤ 256000 and 1 ≤ x, y ≤ N.

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

def validate_input(n, x, y):
if 3 <= n <= 256000 and 1 <= x <= n and 1 <= y <= n:
return True
return False

def main():
with open("input.txt", "r") as input_file, open("output.txt", "w") as output_file:
n, x, y = map(int, input_file.readline().split())
a = list(map(int, input_file.readline().split()))

if not validate_input(n, x, y):
print("Invalid input. Please make sure 3 ≤ N ≤ 256000 and 1 ≤ x, y ≤ N.")
return

S = 0
Rad = [0] * N
Val = [0] * N
tata = [0] * N
Card = [0] * N

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

for i in range(n, 0, -1):
if not Rad[a[i - 1]]:
Rad[a[i - 1]] = i
Val[i] = a[i - 1]
tata[i] = Rad[a[i - 1]]
Card[a[i - 1]] += 1

Sol = 0
for i in range(1, n + 1):
nod = i
while nod != tata[nod]:
nod = tata[nod]
val1 = Val[nod]
val2 = 1 + (i * x + val1 * y) % n
rad2 = Rad[val2]

if val1 == val2:
Card[val1] -= 1
if Card[val1] == 0:
Val[nod] = 0
Rad[val1] = 0
else:
S = S + Card[val1] * (val2 - val1)
Card[val2] = Card[val2] + Card[val1] - 1
Card[val1] = 0

if nod < rad2:
tata[nod] = rad2
Rad[val2] = rad2
Val[rad2] = val2
Rad[val1] = 0
Val[nod] = 0
else:
tata[rad2] = nod
Rad[val2] = nod
Val[nod] = val2
Rad[val1] = 0
Val[rad2] = 0

tata[i] = 0
Sol = max(Sol, S)

output_file.write(str(Sol))

if __name__ == "__main__":
main()

</syntaxhighlight>

3133 – Arbori nr

2024-01-03T21:22:26Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă un arbore cu <code>n</code> noduri şi rădăcina <code>r</code>, nodurile fiind etichetate cu numerele de la <code>1</code> la <code>n</code>. Se cere să se afle pentru fiecare nod <code>i</code>, câte noduri din subarborele cu rădăcina <code>i</code> au eticheta mai mică decât <code>i</code>. = Date de intrare = Fișierul de intrare <code>arbori_nrIN.txt</code> conține pe prima linie numerele <code>n</code> şi <code>r</code>, iar pe următoarele...

= Cerința =
Se dă un arbore cu <code>n</code> noduri şi rădăcina <code>r</code>, nodurile fiind etichetate cu numerele de la <code>1</code> la <code>n</code>. Se cere să se afle pentru fiecare nod <code>i</code>, câte noduri din subarborele cu rădăcina <code>i</code> au eticheta mai mică decât <code>i</code>.

= Date de intrare =
Fișierul de intrare <code>arbori_nrIN.txt</code> conține pe prima linie numerele <code>n</code> şi <code>r</code>, iar pe următoarele <code>n-1</code> linii câte o pereche de numere <code>u</code> şi <code>v</code>, reprezentând faptul că între nodurile cu etichetele <code>u</code> şi <code>v</code> există o muchie.

= Date de ieșire =
Fișierul de ieșire <code>arbori_nrOUT.txt</code> va conține pe prima linie <code>n</code> numere naturale, al <code>i</code>-lea număr reprezentând numărul de noduri din subarborele cu eticheta <code>i</code>, ce au etichetele mai mici decât <code>i</code>.

= Restricții și precizări =

* <code>3 ≤ n ≤ 100.000</code>
* <code>1 ≤ u,v ≤ n</code>, distincte

== Exemplul 1 ==
arbori_nrIN.txt:

5 2

2 3

5 4

5 1

2 5

arbori_nrOUT.txt:

0 1 0 0 2

Explicație:

În arbore <code>1,3,4</code> sunt frunze, deci au câte <code>0</code> noduri în subarborii cu rădăcinile <code>1, 3</code> respectiv <code>5</code>, <code>2</code> are în subarbore nodul <code>1</code> cu eticheta mai mică decât <code>2</code>, <code>5</code> are în subarbore două noduri cu etichetele mai mici decât <code>5</code>, nodurile <code>1</code> şi <code>4</code>.

== Exemplul 2 ==
arbori_nrIN.txt:

999999999 2

2 3

5 4

5 1

2 5

Output:

Error: n should be between 3 and 100000 (inclusive).

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def validate_conditions(n):
if not (3 <= n <= 100000):
print("Error: n should be between 3 and 100000 (inclusive).")
return False

return True

def update(aib, pos, val):
while pos <= len(aib):
aib[pos] += val
pos += pos & -pos

def query(aib, pos):
sum_val = 0
while pos > 0:
sum_val += aib[pos]
pos -= pos & -pos
return sum_val

def dfs1(node, dad, G, aib, aiblant, rez, lant):
update(aib, node, 1)
update(aiblant, node, 1)
rez[node] += query(aib, node - 1)
for next_node in G[node]:
if next_node != dad:
dfs1(next_node, node, G, aib, aiblant, rez, lant)
update(aiblant, node, -1)
lant[node] = query(aiblant, node)

def dfs2(node, dad, G, aib, rez):
update(aib, node, 1)
rez[node] += query(aib, node - 1)
for next_node in G[node][::-1]:
if next_node != dad:
dfs2(next_node, node, G, aib, rez)

def main():
with open("arbori_nrIN.txt", "r") as f:
n, r = map(int, f.readline().split())
if not validate_conditions(n):
return
u, v = 0, 0 # Initialize u and v
G = [[] for _ in range(n + 1)]
rez = [0] * (n + 1)
lant = [0] * (n + 1)
aib = [0] * (4 * n + 1)
aiblant = [0] * (4 * n + 1)
for _ in range(n - 1):
x, y = map(int, f.readline().split())
G[x].append(y)
G[y].append(x)
# Update u and v based on the first edge
if u == 0:
u, v = x, y

dfs1(r, 0, G, aib, aiblant, rez, lant)

for i in range(4 * n):
aib[i] = 0

dfs2(r, 0, G, aib, rez)

with open("arbori_nrOUT.txt", "w") as g:
for i in range(1, n + 1):
g.write(f"{i - rez[i] + lant[i] - 1} ")

if __name__ == "__main__":
main()

</syntaxhighlight>

3126 – Arbori in graf

2024-01-03T21:10:14Z

Corjuc Eunice: Pagină nouă: = Cerința = În judeţul lui Dorel sunt <code>n</code> localităţi legate între ele prin <code>m</code> drumuri. Dorel e interesat să afle în câte moduri se pot alege <code>n-1</code> drumuri din cele <code>m</code> date, astfel încât folosind aceste drumuri să se poată ajunge de la orice localitate la oricare alta. = Date de intrare = Fișierul de intrare <code>arbori_in_grafIN.txt</code> conține pe prima linie numerele <code>n</code> şi <code>m</code>, iar pe u...

= Cerința =
În judeţul lui Dorel sunt <code>n</code> localităţi legate între ele prin <code>m</code> drumuri. Dorel e interesat să afle în câte moduri se pot alege <code>n-1</code> drumuri din cele <code>m</code> date, astfel încât folosind aceste drumuri să se poată ajunge de la orice localitate la oricare alta.

= Date de intrare =
Fișierul de intrare <code>arbori_in_grafIN.txt</code> conține pe prima linie numerele <code>n</code> şi <code>m</code>, iar pe următoarele <code>m</code> linii câte o pereche de numere distincte de la <code>1</code> la <code>n</code>, reprezentând două localităţi între care există drum.

= Date de ieșire =
Fișierul de ieșire <code>arbori_in_grafOUT.txt</code> va conține pe prima linie numărul de moduri cerut, modulo <code>1.000.000.007</code>.

= Restricții și precizări =

* <code>2 ≤ n ≤ 50</code>
* <code>0 ≤ m ≤ n(n-1)/2</code>

== Exemplul 1 ==
arbori_in_grafIN.txt:

2 1

1 2

arbori_in_grafOUT.txt:

1

== Exemplul 2 ==
arbori_in_grafIN.txt:

99999999999 1

1 2

Output:

Invalid input! Please check the conditions: 2 ≤ n ≤ 50 and 0 ≤ m ≤ n(n-1)/2

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

def gcd(x, y, a, b):
if b == 0:
x, y = 1, 0
else:
gcd(x, y, b, a % b)
aux = x
x = y
y = aux - y * (a // b)

def inverse(x):
ins, inv = 0, 0
gcd(inv, ins, x, MOD)
if inv <= 0:
inv = MOD + inv % MOD
return inv

def determinant(a, n):
semn = 1

for i in range(1, n):
if a[i][i] == 0:
for j in range(i + 1, n + 1):
if a[j][i] != 0:
a[i], a[j] = a[j], a[i]
semn *= -1
break

if not a[i][i]:
return 0

for j in range(i + 1, n + 1):
if a[i][i] < 0:
a[i][i] += MOD
p = (-a[j][i] * inverse(a[i][i])) % MOD
if p < 0:
p += MOD
for k in range(i, n + 1):
a[j][k] = (a[j][k] + p * a[i][k]) % MOD
if a[j][k] < 0:
a[j][k] += MOD

pp = 1
for i in range(1, n + 1):
pp = (pp % MOD * a[i][i] % MOD) % MOD
return pp * semn

def validate_input(n, m):
return 2 <= n <= 50 and 0 <= m <= n * (n - 1) // 2

def main():
with open("arbori_in_grafIN.txt", "r") as f:
n, m = map(int, f.readline().split())

if not validate_input(n, m):
print("Invalid input! Please check the conditions: 2 ≤ n ≤ 50 and 0 ≤ m ≤ n(n-1)/2")
return

a = [[0] * 51 for _ in range(51)]
for _ in range(m):
x, y = map(int, f.readline().split())
a[x][y] = -1
a[y][x] = -1
a[x][x] += 1
a[y][y] += 1

det = determinant(a, n - 1)

with open("arbori_in_grafOUT.txt", "w") as g:
g.write(str(det))

if __name__ == "__main__":
main()

</syntaxhighlight>

3339 – Disjoint1

2024-01-03T21:01:52Z

Corjuc Eunice: Pagină nouă: Se consideră un graf cu <code>N</code> noduri numerotate de la <code>1</code> la <code>N</code> și <code>M</code> operații de trei tipuri: * <code>1 x y</code> – se adaugă în graf muchia <code>(x, y)</code>. Dacă muchia există deja, operația nu se efectuează * <code>2 x y</code> – întrebare: nodurile <code>x</code> și <code>y</code> se află sau nu în aceeași componentă conexă? * <code>3</code> – întrebare: care este numărul maxim de noduri dintr-o com...

Se consideră un graf cu <code>N</code> noduri numerotate de la <code>1</code> la <code>N</code> și <code>M</code> operații de trei tipuri:

* <code>1 x y</code> – se adaugă în graf muchia <code>(x, y)</code>. Dacă muchia există deja, operația nu se efectuează
* <code>2 x y</code> – întrebare: nodurile <code>x</code> și <code>y</code> se află sau nu în aceeași componentă conexă?
* <code>3</code> – întrebare: care este numărul maxim de noduri dintr-o componentă conexă?

= Cerința =
Trebuie să răspundeți la toate întrebările de tip <code>2</code> și <code>3</code>.

= Date de intrare =
Programul citește de la tastatură numerele <code>N</code> și <code>M</code>, iar pe următoarele <code>M</code> linii se află operațiile date fie prin trei valori de forma <code>op x y</code> (pentru operațiile de tip <code>1</code> și <code>2</code>), fie printr-o singură valoare <code>3</code> (pentru operațiile de tip <code>3</code>).

= Date de ieșire =
Programul va afișa pe ecran, pe câte o linie, răspunsul la fiecare întrebare de tip <code>2</code> și <code>3</code>. Dacă la o întrebare <code>2 x y</code> răspunsul este afirmativ, adică <code>x</code> și <code>y</code> se află în aceeași componentă conexă, atunci veți afișa <code>DA</code>, iar în caz contrar veți afișa <code>NU</code>.

= Restricții și precizări =

* <code>3 ≤ N ≤ 32.000</code>
* <code>3 ≤ M ≤ 300.000</code>
* va exista cel puțin o operație de fiecare tip.

== Exemplul 1 ==
Input:

6 6

1 1 4

1 3 6

2 4 6

1 1 3

2 4 6

3

Output:

NU

DA

4

== Exemplul 2 ==
Input:

99999999 6

1 1 4

1 3 6

2 4 6

1 1 3

2 4 6

3

Output:

Invalid input. Please ensure that 3 ≤ N ≤ 32,000 and 3 ≤ M ≤ 300,000.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_conditions(N, M):
return 3 <= N <= 32000 and 3 <= M <= 300000

class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
self.rank = [0] * (n + 1)
self.size = [1] * (n + 1)
self.max_size = 1

def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]

def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)

if root_x != root_y:
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
self.size[root_x] += self.size[root_y]
self.max_size = max(self.max_size, self.size[root_x])
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1

def main():
N = int(input())
M = int(input())

if not verify_conditions(N, M):
print("Invalid input. Please ensure that 3 ≤ N ≤ 32,000 and 3 ≤ M ≤ 300,000.")
return

union_find = UnionFind(N)

for _ in range(M):
input_values = input().split()
operation = int(input_values[0])

if operation == 1:
x, y = int(input_values[1]), int(input_values[2])
union_find.union(x, y)
elif operation == 2:
x, y = int(input_values[1]), int(input_values[2])
result = "DA" if union_find.find(x) == union_find.find(y) else "NU"
print(result)
elif operation == 3:
print(union_find.max_size)

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

3127 – Arbori xor

2024-01-03T20:29:56Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă un arbore cu <code>n</code> noduri, în care fiecare muchie are asociat un număr natural. Se cere răspunsul la <code>Q</code> întrebări de forma: dacă <code>u</code> şi <code>v</code> sunt două noduri din arbore, care este valoarea <code>xor</code> a tuturor numerelor asociate muchiilor situate pe lanţul ce uneşte <code>u</code> şi <code>v</code>? = Date de intrare = Fișierul de intrare <code>arbori_xorIN.txt</code> conține pe prima linie nume...

= Cerința =
Se dă un arbore cu <code>n</code> noduri, în care fiecare muchie are asociat un număr natural. Se cere răspunsul la <code>Q</code> întrebări de forma: dacă <code>u</code> şi <code>v</code> sunt două noduri din arbore, care este valoarea <code>xor</code> a tuturor numerelor asociate muchiilor situate pe lanţul ce uneşte <code>u</code> şi <code>v</code>?

= Date de intrare =
Fișierul de intrare <code>arbori_xorIN.txt</code> conține pe prima linie numerele <code>n</code> şi <code>Q</code>, pe următoarele <code>n-1</code> linii câte o pereche de numere naturale ce reprezintă extremităţile unei muchii din arbore urmată de un număr natural ce reprezintă valoarea muchiei, iar pe următoarele <code>Q</code> linii câte o pereche de numere naturale ce reprezintă nodurile pentru care se cere <code>xor</code>-ul valorilor de pe lanţul ce le uneşte .

= Date de ieșire =
Fișierul de ieșire <code>arbori_xorOUT.txt</code> va conține pe primele <code>Q</code> linii răspunsurile la cele <code>Q</code> cerinţe.

= Restricții și precizări =

* <code>2 ≤ n ≤ 10.000</code>
* <code>1 ≤ Q ≤ 500.000</code>
* valorile asociate muchiilor sunt numere naturale cel mult egale cu <code>10.000</code>

== Exemplul 1 ==
arbori_xorIN.txt:

5 2

1 2 7

1 3 4

3 4 1

4 5 13

1 5

3 2

arbori_xorOUT.txt:

8

3

Explicație: Pentru prima cerinţă avem <code>4 ^ 1 ^ 13 = 8</code>, iar pentru a doua <code>4 ^ 7 = 3</code>.

== Exemplul 2 ==
arbori_xorIN.txt:

99999999 2

1 2 7

1 3 4

3 4 1

4 5 13

1 5

3 2

Output:

Input conditions not satisfied.

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

def bfs(nod):
global coada, s, t
coada.append(nod)
while coada:
nod = coada.popleft()
for i in range(len(L[nod])):
vecin, cost = L[nod][i]
if t[nod] == vecin:
continue
coada.append(vecin)
t[vecin] = nod
s[vecin] = s[nod] ^ cost

def query(a, b):
return s[a] ^ s[b]

def verify_conditions(n, q):
if 2 <= n <= 10000 and 1 <= q <= 500000:
return True
else:
return False

fin = open("arbori_xorIN.txt", "r")
fout = open("arbori_xorOUT.txt", "w")

coada = deque()
L = [[] for _ in range(10009)]
s = [0] * 10009
t = [0] * 10009

n, q = map(int, fin.readline().split())

if not verify_conditions(n, q):
print("Input conditions not satisfied.")
fin.close()
fout.close()
exit()

for _ in range(n-1):
x, y, z = map(int, fin.readline().split())
L[x].append((y, z))
L[y].append((x, z))

bfs(1)

for _ in range(q):
a, b = map(int, fin.readline().split())
fout.write(str(query(a, b)) + '\n')

fin.close()
fout.close()

</syntaxhighlight>

0653 – Firmă1

2024-01-03T15:42:21Z

Corjuc Eunice: Pagină nouă: = Cerința = Într-o firmă sunt <code>n</code> angajați, numerotați de la <code>1</code> la <code>n</code>, organizați ierarhic, astfel că fiecare angajat are un șef direct, cu excepția directorului general, care nu are șef. Fiecare angajat al firmei are un salariu cunoscut, exprimat printr-un număr natural. În firmă funcționează un sistem de recompensare a angajaților astfel încât câștigul fiecărui salariat este egal cu salariul său la care se adaugă med...

= Cerința =
Într-o firmă sunt <code>n</code> angajați, numerotați de la <code>1</code> la <code>n</code>, organizați ierarhic, astfel că fiecare angajat are un șef direct, cu excepția directorului general, care nu are șef. Fiecare angajat al firmei are un salariu cunoscut, exprimat printr-un număr natural. În firmă funcționează un sistem de recompensare a angajaților astfel încât câștigul fiecărui salariat este egal cu salariul său la care se adaugă media aritmetică a câștigurilor subordonaților săi direcți. Excepție fac angajații care nu au subordonați direcți, pentru care câștigul este egal cu salariul.

Determinați care este câștigul directorului general al firmei.

= Date de intrare =
Fișierul de intrare <code>firma1IN.txt</code> conține pe prima linie numărul de angajați <code>n</code>.

Pe linia a doua se află <code>n</code> numere naturale, reprezentând structura ierarhică a firmei: al <code>k</code>-lea număr din șir precizează care este șeful direct al angajatului cu numărul de ordine <code>k</code>. Pentru directorul general valoarea corespunzătoare este <code>0</code>.

Linia a treia conține, în ordine, salariile celor <code>n</code> angajați.

= Date de ieșire =
Fișierul de ieșire <code>firma1OUT.txt</code> va conține pe prima linie numărul <code>C</code>, reprezentând câștigul directorului general.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* salariul fiecărui angajat este un număr natural nenul cel mult egal cu <code>1000</code>
* media aritmetică a câștigurilor subordonaților fiecărui angajat se aproximează prin adaos, astfel încât să fie număr natural

== Exemplul 1 ==
firma1IN.txt:

8

4 3 0 3 2 1 2 1

2 6 4 3 7 3 1 5

firma1OUT.txt:

14

== Exemplul 2 ==
firma1IN.txt:

101

4 3 0 3 2 1 2 1

2 6 4 3 7 3 1 5

Output:

Input necorespunzator

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare(n, v):
if 1>n or 101<=n:
return False
for i in range(len(v)):
if v[i] < 0 or v[i] > 1000:
return False
return True

n = 0
t = [0] * 105
salariu = [0] * 105
castig = [0] * 105

def dfs(k):
global castig
s = 0
cnt = 0
for i in range(1, n + 1):
if t[i] == k:
dfs(i)
cnt += 1
s += castig[i]
if cnt > 0:
if s % cnt == 0:
s //= cnt
else:
s = s // cnt + 1
castig[k] = s + salariu[k]

if __name__ == "__main__":
with open("firma1IN.txt", "r") as fin:
n = int(fin.readline())
t[1:n+1] = map(int, fin.readline().split())
salariu[1:n+1] = map(int, fin.readline().split())
if not verificare(n, salariu):
print("Input necorespunzator")
exit()

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

dfs(r)

with open("firma1OUT.txt", "w") as fout:
fout.write(str(castig[r]))

</syntaxhighlight>

0645 – Det Drum3

2024-01-03T15:29:32Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri în care fiecare nod are asociată o valoare numerică. Determinați drumul de la rădăcină la un nod terminal pentru care suma valorilor asociate nodurilor este maximă. = Date de intrare = Fișierul de intrare <code>detdrum3IN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri în care fiecare nod are asociată o valoare numerică. Determinați drumul de la rădăcină la un nod terminal pentru care suma valorilor asociate nodurilor este maximă.

= Date de intrare =
Fișierul de intrare <code>detdrum3IN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. Pe următoarea linie se află, în ordine, valorile asociate nodurilor din arbore.

= Date de ieșire =
Fișierul de ieșire <code>detdrum3OUT.txt</code> va conține pe prima linie suma maxima determinată, iar pe a doua linie nodurile care alcătuiesc drumul determinat, separate printr-un spațiu. Dacă există mai multe noduri terminale pentru care suma valorilor nodurilor situate pe drumul de la rădăcină la nod este maximă, se va afișa drumul spre nodul cu numărul de ordine minim.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* valorile asociate nodurile din arbore sunt numere naturale mai mici decât <code>1000</code>

== Exemplul 1 ==
detdrum3IN.txt:

8

4 3 0 3 2 1 4 1

2 5 2 1 3 5 3 1

detdtrum3OUT.txt:

10

3 2 5

== Exemplul 2 ==
detdrum3IN.txt:

101

4 3 0 3 2 1 4 1

2 5 2 1 3 5 3 1

Output:

Input necorespunzator

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare(n, v):
if 1>n or 101<=n:
return False
for i in range(len(v)):
if v[i] < 0 or v[i] > 1000:
return False
return True

with open("detdrum3IN.txt") as f:
n = int(next(f))
t = [0] + list(map(int, next(f).split()))
v = [0] + list(map(int, next(f).split()))
if not verificare(n,v):
print("Input necorespunzator")
exit()

result = []
maxim = float("-inf")
for i in range(1, n + 1):
c = 0

for x in t[1:]:
if x == i:
c += 1

if c == 0:
p = t[i]
s = v[i]

while p:
s += v[p]
p = t[p]

maxim = max(maxim, s)

with open("detdrum3OUT.txt", "w") as fout:
print(maxim, file=fout)

valid = False

for i in range(1, n + 1):
c = 0

for x in t[1:]:
if x == i:
c += 1

if c == 0:
p = t[i]
s = v[i]

while p:
s += v[p]
p = t[p]

if s == maxim and not valid:
valid = True
result.append(i)
p = t[i]
while p:
result.append(p)
p = t[p]

for x in result[::-1]:
print(x, end=" ", file=fout)
</syntaxhighlight>

0644 – Det Drum2

2024-01-03T15:04:41Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și doua noduri <code>p q</code>. Determinați drumul elementar de la nodul <code>p</code> la nodul <code>q</code>. = Date de intrare = Fișierul de intrare <code>detdrum2IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodurile <code>p q</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. = Date de ie...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și doua noduri <code>p q</code>. Determinați drumul elementar de la nodul <code>p</code> la nodul <code>q</code>.

= Date de intrare =
Fișierul de intrare <code>detdrum2IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodurile <code>p q</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații.

= Date de ieșire =
Fișierul de ieșire <code>detdrum2OUT.txt</code> va conține pe prima linie nodurile care alcătuiesc drumul determinat, separate printr-un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ k ≤ n</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>

== Exemplul 1 ==
detdrum2IN.txt:

7 2 5

4 1 7 0 7 7 1

detdrum2OUT.txt:

2 1 7 5

== Exemplul 2 ==
detdrum2IN.txt:

101 2 5

4 1 7 0 7 7 1

Output:

Error: n should be between 1 and 100 (inclusive).

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def validate_input(n, k):
if not (1 <= n <= 100):
print("Error: n should be between 1 and 100 (inclusive).")
return False
if not (1 <= k <= n):
print("Error: k should be between 1 and n (inclusive).")
return False
return True

with open("detdrum2IN.txt", "r") as infile:
n, p, q = map(int, infile.readline().split())
t = [0] + list(map(int, infile.readline().split()))
if not validate_input(n, p) or not validate_input(n, q):
exit()

v1, v2 = [], []

def afis(x, b):
if x != 0 and t[x] != 0:
b.append(x)
afis(t[x], b)

ok1, ok2 = 0, 0
afis(p, v1)
afis(q, v2)
nr1, nr2 = len(v1), len(v2)

for i in range(1, nr1 + 1):
for j in range(1, nr2 + 1):
if v1[i - 1] == v2[j - 1]:
ok1 = i
ok2 = j
break
with open("detdrum2OUT.txt", "w") as outfile:
for i in range(0, ok1):
outfile.write(f"{v1[i]} ")

for i in range(ok2 - 2, -1, -1):
outfile.write(f"{v2[i]} ")

</syntaxhighlight>

0643 – Det Drum1

2024-01-03T14:48:00Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Determinați drumul de la rădăcina arborelui la nodul <code>k</code>. = Date de intrare = Fișierul de intrare <code>detdrum1IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. = Date de ieșire = Fișierul de i...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Determinați drumul de la rădăcina arborelui la nodul <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>detdrum1IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații.

= Date de ieșire =
Fișierul de ieșire <code>detdrum1OUT.txt</code> va conține pe prima linie nodurile care alcătuiesc drumul determinat, separate printr-un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ k ≤ n</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>

== Exemplul 1 ==
detdrum1IN.txt:

7 2

4 1 7 0 7 7 1

detdrum1OUT.txt:

4 1 2

== Exemplul 2 ==
detdrum1IN.txt:

101 2

4 1 7 0 7 7 1

Output:

Invalid input. Please check the conditions.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_valid_input(n, k):
return 1 <= n <= 100 and 1 <= k <= n

with open("detdrum1IN.txt", "r") as infile, open("detdrum1OUT.txt", "w") as outfile:
n, k = map(int, infile.readline().split())

if not is_valid_input(n, k):
print("Invalid input. Please check the conditions.")
else:
t = [0] + list(map(int, infile.readline().split()))

def detdrum(nod):
if nod == 0:
return
detdrum(t[nod])
outfile.write(str(nod) + " ")

detdrum(k)

</syntaxhighlight>

0642 – Det Drum

2024-01-02T21:28:54Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Determinați drumul de la nodul <code>k</code> la rădăcina arborelui. = Date de intrare = Fișierul de intrare <code>detdrumIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. = Date de ieșire = Fișierul de ie...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Determinați drumul de la nodul <code>k</code> la rădăcina arborelui.

= Date de intrare =
Fișierul de intrare <code>detdrumIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații.

= Date de ieșire =
Fișierul de ieșire <code>detdrumOUT.txt</code> va conține pe prima linie nodurile care alcătuiesc drumul determinat, separate printr-un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ k ≤ n</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>

== Exemplul 1 ==
detdrumIN.txt:

7 2

4 1 7 0 7 7 1

detdrumOUT.txt:

2 1 4

== Exemplul 2 ==
detdrumIN.txt:

101 2

4 1 7 0 7 7 1

detdrumOUT.txt:

Invalid input. Constraints not satisfied.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_constraints(n, k):
return 1 <= n <= 100 and 1 <= k <= n

def solve_detdrum(n, k, t):
a = [0] * 101
rad = 0

for i in range(1, n + 1):
if t[i - 1] == 0:
rad = i
a[i] = t[i - 1]

result = []

def afis(x, a):
nonlocal result
if x != 0 and t[x - 1]:
result.append(x)
afis(t[x - 1], a)

afis(k, a)
result.append(rad)
return result

if __name__ == "__main__":
with open("detdrumIN.txt", "r") as infile, open("detdrumOUT.txt", "w") as outfile:
n, k = map(int, infile.readline().split())

if not verify_constraints(n, k):
outfile.write("Invalid input. Constraints not satisfied.")
else:
t = list(map(int, infile.readline().split()))

result = solve_detdrum(n, k, t)

outfile.write(" ".join(map(str, result)))

</syntaxhighlight>

0651 – Sum Sub Max

2024-01-02T21:12:38Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați nodurile <code>p</code> din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>p</code> este maximă. = Date de intrare = Fișierul de intrare <code>sumsubmaxIN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe a doua linie se află vec...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați nodurile <code>p</code> din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>p</code> este maximă.

= Date de intrare =
Fișierul de intrare <code>sumsubmaxIN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe a doua linie se află vectorul de tați al arborelui, valorile fiind separate prin spații. Pe linia a treia se află, în ordine, valorile asociate nodurilor din arbore, separate și ele prin spații.

= Date de ieșire =
Fișierul de ieșire <code>sumsubmaxOUT.txt</code> va conține, în ordine crescătoare, nodurile <code>p</code> din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>p</code> este maximă, separate printr-un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* valorile asociate nodurilor din arbore sunt numere întregi din intervalul <code>[-1000,1000]</code>

== Exemplul 1 ==
sumsubmaxIN.txt:

8

4 3 0 3 2 1 2 1

-3 2 -7 4 0 3 3 1

sumsubmaxOUT.txt:

2 4

Explicație:

În subarborii cu rădăcina în <code>2</code> și <code>4</code> suma valorilor asociate nodurilor este <code>5</code> și este maximă.

== Exemplul 2 ==
sumsubmaxIN.txt:

101

4 3 0 3 2 1 2 1

-3 2 -7 4 0 3 3 1

Output:

Invalid input. Please check the constraints.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_valid_input(n, t, val):
if not (1 <= n <= 100):
return False

if len(t) != n + 1 or len(val) != n + 1:
return False

for i in range(1, n + 1):
if not (-1000 <= val[i] <= 1000):
return False

return True

def dfs(k):
v[k] = 1
for i in range(1, n + 1):
if i < len(t) and t[i] == k and not v[i]:
dfs(i)

# Read input from file
with open("sumsubmaxIN.txt", "r") as fin:
n = int(fin.readline().strip())
t = [0] + list(map(int, fin.readline().split())) # Adjust for 1-based indexing
val = [0] + list(map(int, fin.readline().split())) # Adjust for 1-based indexing

# Check input constraints
if not is_valid_input(n, t, val):
print("Invalid input. Please check the constraints.")
exit()

smax = [0] * (n + 1)

# Perform DFS and calculate sum of values for each subtree
for i in range(1, n + 1):
v = [0] * (n + 1)
dfs(i)
for j in range(1, n + 1):
if j < len(v) and v[j] == 1:
smax[i] += val[j]

# Find the maximum sum
ma = max(smax)

# Write output to file
with open("sumsubmaxOUT.txt", "w") as fout:
for i in range(1, n + 1):
if smax[i] == ma:
fout.write(f"{i} ")

</syntaxhighlight>

0931 - Sortare Unghi

2024-01-02T20:52:53Z

Corjuc Eunice: Pagină nouă: = Cerința = Se dau puncte distincte în plan. Asociem fiecărui punct semidreapta care pornește din originea sistemului de coordonate și trece prin acel punct. Să se afișeze punctele în ordine crescătoare a unghiului pe care semidreapta asociată îl face cu semidreapta spre plus infinit a axei <code>OX</code>. Dacă două unghiuri sunt egale se va afișa punctul cel mai apropiat de origine. = Date de intrare = Fișierul de intrare <code>sortareunghiIN.txt</code> con...

= Cerința =
Se dau puncte distincte în plan. Asociem fiecărui punct semidreapta care pornește din originea sistemului de coordonate și trece prin acel punct. Să se afișeze punctele în ordine crescătoare a unghiului pe care semidreapta asociată îl face cu semidreapta spre plus infinit a axei <code>OX</code>. Dacă două unghiuri sunt egale se va afișa punctul cel mai apropiat de origine.

= Date de intrare =
Fișierul de intrare <code>sortareunghiIN.txt</code> conține pe prima linie <code>n</code>, reprezentând numărul de puncte. Pe următoarele <code>n</code> linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui punct.

= Date de ieșire =
Fișierul de ieșire <code>sortareunghiOUT.txt</code> va conține <code>n</code> linii cu câte două numere separate prin câte un spațiu, reprezentând abscisa respectiv ordonata câte unui punct, în ordinea cerută.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* Numerele din fișierul de intrare sunt întregi cuprinse între <code>-1001</code> și <code>1001</code>.
* Unghiurile sunt în intervalul <code>[0,360)</code>.

== Exemplul 1 ==
sortareunghiIN.txt:

3

1 1

-1 -1

-1 1

sortareunghiOUT.txt:

1 1

-1 1

-1 -1

== Exemplul 2 ==
sortareunghiIN.txt:

101

1 1

-1 -1

-1 1

Output:

Error: n should be between 1 and 100.

Exiting due to constraint violations.

== Ex ==

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

class Element:
def __init__(self, x, y):
self.x = x
self.y = y

def check_constraints(n, elements):
if not 1 <= n <= 100:
print("Error: n should be between 1 and 100.")
return False

for elem in elements:
if not -1001 <= elem.x <= 1001 or not -1001 <= elem.y <= 1001:
print("Error: Element coordinates should be between -1001 and 1001.")
return False

return True

def distance(a):
return a.x ** 2 + a.y ** 2

def read_elements():
elements = []

try:
with open("sortareunghiIN.txt", "r") as file:
n = int(file.readline())
for _ in range(n):
line = file.readline().strip()
if line:
x, y = map(int, line.split())
elements.append(Element(x, y))
except ValueError:
print("Error: Incorrect input format.")
return 0, []

return n, elements

def print_elements(elements):
with open("sortareunghiOUT.txt", "w") as file:
for elem in elements:
file.write(f"{elem.x} {elem.y}\n")

def angle(a):
if a.x > 0 and a.y > 0:
return 1.0 * a.y / a.x
elif a.x < 0 and a.y > 0:
return 10000 + 1.0 * (-a.x) / a.y
elif a.x < 0 and a.y < 0:
return 20000 + 1.0 * a.y / a.x
elif a.x > 0 and a.y < 0:
return 30000 + 1.0 * a.x / (-a.y)
elif a.x == 0:
if a.y > 0:
return 10000
else:
return 30000
elif a.y == 0:
if a.x > 0:
return 0
else:
return 20000

def compare(a, b):
return angle(a) < angle(b) or (angle(a) == angle(b) and distance(a) < distance(b))

def main():
n, elements = read_elements()

if n > 0 and check_constraints(n, elements):
elements.sort(key=lambda x: (angle(x), distance(x)))
print_elements(elements)
else:
print("Exiting due to constraint violations.")

if __name__ == "__main__":
main()

</syntaxhighlight>

2751 - BB Security

2024-01-02T19:54:43Z

Corjuc Eunice: Pagină nouă: Domnul <code>X</code> lucrează la BB Security ca paznic. Deoarece în România sunt foarte puțini hoți, acesta s-a gândit într-o zi să calculeze distanța dintre fiecare doi stâlpi de îngrădire din instituția pe care o păzește. Fiecare doi stâlpi de îngrădire sunt legați printr-un cablu rezistent, care, de obicei nu stă întins la maximum. Din cauză ca în instituție se găsesc mulți stâlpi, domnul <code>X</code> vă provoacă pe voi să calculați ce...

Domnul <code>X</code> lucrează la BB Security ca paznic.

Deoarece în România sunt foarte puțini hoți, acesta s-a gândit într-o zi să calculeze distanța dintre fiecare doi stâlpi de îngrădire din instituția pe care o păzește. Fiecare doi stâlpi de îngrădire sunt legați printr-un cablu rezistent, care, de obicei nu stă întins la maximum.

Din cauză ca în instituție se găsesc mulți stâlpi, domnul <code>X</code> vă provoacă pe voi să calculați ce și-a propus el.

= Cerința =
Se dă un număr <code>n</code> și <code>n</code> triplete de forma <code>l</code>, <code>c</code>, <code>h</code>, reprezentând lungimea egala a doi stâlpi, lungimea cablului dintre acestea și înălțimea la care atârnă cablul față de podea.

Se cere să se afle distanța dintre fiecare doi stâlpi.

Fiecare rezultat va fi afișat pe cate un rând nou.

= Date de intrare =
Programul citește de la tastatură un număr <code>n</code> și apoi <code>n</code> triplete de forma <code>l</code>, <code>c</code>, <code>h</code>, cu semnificația de mai sus.

= Date de ieșire =
Programul va afișa pe linia <code>n</code> a ecranului un număr de forma <code>x</code> care reprezintă lungimea dintre cei doi stâlpi, corespunzătoare datelor de pe linia <code>n+1</code> din consola de citire, cu exact două zecimale, indiferent de caz, rotunjind a doua zecimală în comparație cu cea de-a treia, sau, dacă a doua zecimală este <code>5</code>, zecimala a doua va crește cu o unitate doar dacă există încă una sau mai multe zecimale după cea de-a treia și măcar una din ele este <code>> 0</code> (vezi Restricții).

= Restricții și precizări =

* <code>1 ≤ n ≤ 100.000</code>;
* cele <code>n</code> numere citite vor fi mai mici decât <code>1.000.000</code>;
* <code>n, l, c, h</code> sunt numere naturale;
* este garantat că pentru orice triplet citit există un număr <code>0 ≤ x ≤ c</code>;
* cea de-a doua zecimala se rotunjește de obicei după cea de-a treia (ex. <code>49.4376</code> se va afișa ca <code>49.44</code>);
* ∀ <code>a</code>| <code>a</code> ∈ ℕ, acesta se va afișa ca <code>a.00</code> (ex. <code>50</code> se va afișa ca <code>50.00</code>);
* Atenție! <code>23.455 = 23.45 , 23.45501 = 23.46</code>.

== Exemplul 1 ==
Input:

2

60 100 20

100 50 100

Output:

49.44

50.00

Explicație:

Pentru primul triplet lungimea dintre cei doi stâlpi este <code>49.44</code>, iar pentru al doilea cablul este întins la maximum și lungimea dintre cei doi stâlpi este <code>50.00</code>.

== Exemplul 2 ==
Input:

1

34 7.2 9.1

Output:

Numerele trebuie să fie naturale.

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

def verifica_conditii(n, tests):
results = []

for i in range(n):
l, c, h = tests[i]

# Verificare dacă numerele sunt naturale
if not all(map(lambda x: x.is_integer() and x >= 0, [l, c, h])):
results.append("Numerele trebuie să fie naturale.")
continue

if h == l:
results.append(f"{int(c):.2f}")
elif c / 2 + h == l:
results.append("0.00")
else:
a = ((c**2 / 4) - (l - h)**2) / (2 * (l - h))
t1 = 2 * a * math.log(math.sqrt((c**2 / 4) / (a**2) + 1) + (c / 2) / a)

# Rotunjirea valorilor conform specificațiilor
rounded_t1 = round(t1, 2)
if rounded_t1.is_integer():
results.append(f"{int(rounded_t1)}.00")
else:
results.append(f"{rounded_t1:.2f}")

return results

def main():
n = int(input())
tests = []

for _ in range(n):
l, c, h = map(float, input().split())
tests.append((l, c, h))

results = verifica_conditii(n, tests)
for result in results:
print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

2636 - Noduri Izolate

2024-01-02T19:32:34Z

Corjuc Eunice: /* Exemplul 2 */

= Cerința =
Se dau două numere <code>n</code> și <code>m</code>. Aflați care este numărul minim și numărul maxim de noduri izolate într-un graf neorientat cu <code>n</code> noduri și <code>m</code> muchii în care nu există o muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.

= Date de intrare =
Programul citește de la tastatură numerele <code>n m</code>.

= Date de ieșire =
Programul va afișa pe ecran numerele <code>a</code> și <code>b</code>, reprezentând numărul minim, respectiv numărul maxim de noduri izolate într-un graf neorientat cu <code>n</code> noduri și <code>m</code> muchii în care nu există o muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100.000</code>
* 0<=m<=n*(n-1)/2

= Exemplul 1 =
Input:

4 2

Output:

0 1

Explicație:

Se poate construi un graf fără noduri izolate, cu muchiile <code>(1,2)</code> și <code>(3,4)</code>. Pentru a obține un nod izolat, putem construi un graf cu muchiile <code>(1,2)</code> și <code>(1,3)</code>.

== Exemplul 2 ==
Input:

99999999 2

Output:

Restrictiile nu sunt indeplinite.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_restrictions(n, m):
return 1 <= n <= 100000 and 0 <= m <= n * (n - 1) // 2

def calculate_isolated_nodes(n, m):
# Verifică restricțiile
if not check_restrictions(n, m):
print("Restrictiile nu sunt indeplinite.")
return None

# Numărul minim de noduri izolate
min_isolated_nodes = 0

# Numărul maxim de noduri izolate
max_isolated_nodes = max(0, min(n - m, 1))

return min_isolated_nodes, max_isolated_nodes

if __name__ == "__main__":
n = int(input("Introduceti numarul de noduri (n): "))
m = int(input("Introduceti numarul de muchii (m): "))

result = calculate_isolated_nodes(n, m)

if result is not None:
min_isolated, max_isolated = result
print(f"Numarul minim de noduri izolate: {min_isolated}")
print(f"Numarul maxim de noduri izolate: {max_isolated}")

</syntaxhighlight>

0471 - Bipartit

2023-12-16T15:25:41Z

Corjuc Eunice: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>, precum si o mulțime <code>A</code> de vârfuri ale grafului. Considerăm mulțimea <code>B</code> formată din vărfurile grafului care nu aparțin lui <code>A</code>. Să se verifice dacă graful este bipartit peste partiția formată din mulțimile <code>A</code> și <code>B</code>. = Date de intrare = Fişierul de intrare <code>bipartitI...

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>, precum si o mulțime <code>A</code> de vârfuri ale grafului. Considerăm mulțimea <code>B</code> formată din vărfurile grafului care nu aparțin lui <code>A</code>. Să se verifice dacă graful este bipartit peste partiția formată din mulțimile <code>A</code> și <code>B</code>.

= Date de intrare =
Fişierul de intrare <code>bipartitIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>. Urmează un număr <code>k</code>, apoi <code>k</code> numere naturale distincte cuprinse între <code>1</code> și <code>n</code>, reprezentând vârfurile din <code>A</code>.

= Date de ieşire =
Fişierul de ieşire <code>bipartitOUT.txt</code> va conţine pe prima linie mesajul <code>DA</code>, dacă graful este bipartit peste partiția formată din mulțimile <code>A</code> și <code>B</code>, respectiv <code>NU</code> în caz contrar.

= Restricţii şi precizări =

* <code>1 < k < n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* muchiile se pot repeta în fișierul de intrare

== Exemplul 1 ==
bipartitIN.txt:

7 6

1 4

1 6

6 5

3 2

3 5

3 7

3

4 6 3

bipartitOUT.txt:

DA

== Exemplul 2 ==
bipartitIN.txt:

999 6

1 4

1 6

6 5

3 2

3 5

3 7

3

4 6 3

Output:

Datele de intrare nu respectă restricțiile.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_bipartite(graph, vertices_in_a):
colors = {}
queue = []

for vertex in vertices_in_a:
colors[vertex] = 1
queue.append(vertex)

while queue:
current_vertex = queue.pop(0)

for neighbor in graph[current_vertex]:
if neighbor not in colors:
colors[neighbor] = -colors[current_vertex]
queue.append(neighbor)
elif colors[neighbor] == colors[current_vertex]:
return False

return True

def is_valid_input(n, m, k, edges):
if not (1 < k < n <= 100):
return False

for i, j in edges:
if not (1 <= i <= n and 1 <= j <= n):
return False

return True

# Citirea datelor de intrare din fișier
with open("bipartitIN.txt", "r") as input_file:
n, m = map(int, input_file.readline().split())
edges = [tuple(map(int, input_file.readline().split())) for _ in range(m)]

k = int(input_file.readline())
vertices_in_a = set(map(int, input_file.readline().split()))

# Verificare restricții pentru datele de intrare
if not is_valid_input(n, m, k, edges):
print("Datele de intrare nu respectă restricțiile.")
else:
# Inițializare graful
graph = {i: [] for i in range(1, n + 1)}

# Adăugare muchii în graf
for i, j in edges:
graph[i].append(j)
graph[j].append(i)

# Verificare dacă graful este bipartit
result = is_bipartite(graph, vertices_in_a)

# Scrierea rezultatului în fișierul de ieșire
with open("bipartitOUT.txt", "w") as output_file:
output_file.write("DA" if result else "NU")

</syntaxhighlight>

0466 - Gen Graf

2023-12-16T15:17:11Z

Corjuc Eunice: Pagină nouă: = Cerinţa = Se dă un număr natural <code>n</code>. Construiți toate grafurile neorientate cu <code>n</code> vârfuri. = Date de intrare = Fişierul de intrare <code>gengrafIN.txt</code> conţine pe prima linie numărul <code>n</code>. = Date de ieşire = Fişierul de ieşire <code>gengrafOUT.txt</code> va conţine pe prima linie numărul de grafuri generate <code>M</code>; urmează <code>M</code> matrice de adiacență ale acestor grafuri. Fiecare matrice va fi afișat...

= Cerinţa =
Se dă un număr natural <code>n</code>. Construiți toate grafurile neorientate cu <code>n</code> vârfuri.

= Date de intrare =
Fişierul de intrare <code>gengrafIN.txt</code> conţine pe prima linie numărul <code>n</code>.

= Date de ieşire =
Fişierul de ieşire <code>gengrafOUT.txt</code> va conţine pe prima linie numărul de grafuri generate <code>M</code>; urmează <code>M</code> matrice de adiacență ale acestor grafuri.

Fiecare matrice va fi afișată astfel: câte o linie a matricei pe o linie a fișierului, elementele de pe o linie fiind separate prin exact un spațiu. După fiecare matrice afișată se va găsi în fișier o linie goală.

= Restricţii şi precizări =

* <code>2 ≤ n ≤ 6</code>
* cele <code>M</code> matrice de adiacență construite pot fi afișate în orice ordine

== Exemplul 1 ==
gengrafIN.txt:

3

gengrafOUT.txt:

8

0 0 0

0 0 0

0 0 0

0 1 0

1 0 0

0 0 0

0 0 1

0 0 0

1 0 0

0 1 1

1 0 0

1 0 0

0 0 0

0 0 1

0 1 0

0 1 0

1 0 1

0 1 0

0 0 1

0 0 1

1 1 0

0 1 1

1 0 1

1 1 0

== Exemplul 2 ==
gengrafIN.txt:

7

Output:

Valoarea lui n nu respectă restricția 2 <= n <= 6.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def generate_graphs(n):
graphs = []
for i in range(2**(n*(n-1)//2)):
graph_matrix = [[0]*n for _ in range(n)]
idx = 0
for j in range(n):
for k in range(j+1, n):
graph_matrix[j][k] = graph_matrix[k][j] = (i >> idx) & 1
idx += 1
graphs.append(graph_matrix)
return graphs

def write_to_file(graphs, filename):
with open(filename, 'w') as file:
file.write(str(len(graphs)) + '\n')
for graph in graphs:
for row in graph:
file.write(' '.join(map(str, row)) + '\n')
file.write('\n')

def check_n_range(n):
return 2 <= n <= 6

if __name__ == "__main__":
with open('gengrafIN.txt', 'r') as input_file:
n = int(input_file.readline().strip())

if check_n_range(n):
graphs = generate_graphs(n)
write_to_file(graphs, 'gengrafOUT.txt')
else:
print("Valoarea lui n nu respectă restricția 2 <= n <= 6.")

</syntaxhighlight>

0421 - Graf Partial 1

2023-12-16T15:00:15Z

Corjuc Eunice:

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>. Din acest graf se elimină toate muchiile cu o extremitate de grad maxim și cealaltă extremitate de grad minim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut.

= Date de intrare =
Fişierul de intrare <code>graf_partial_1IN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Fişierul de ieşire <code>graf_partial_1OUT.txt</code> va conţine pe prime linie numărul de muchii eliminate, iar pe următoarele linii matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* muchiile se pot repeta în fișierul de intrare

== Exemplul 1 ==
graf_partial_1IN.txt:

6

1 3

2 3

2 4

4 3

5 3

4 5

3 1

6 4

graf_partial_1OUT.txt:

2

0 0 0 0 0 0

0 0 1 1 0 0

0 1 0 1 1 0

0 1 1 0 1 0

0 0 1 1 0 0

0 0 0 0 0 0

== Exemplul 2 ==
graf_partial_1IN.txt:

999

1 3

2 3

2 4

4 3

5 3

4 5

3 1

6 4

Output:

Restrictiile nu sunt indeplinite.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_input_restrictions(n, edges):
if not (1 <= n <= 100):
return False

for edge in edges:
i, j = edge
if not (1 <= i <= n) or not (1 <= j <= n):
return False

return True

def read_graph(filename):
with open(filename, 'r') as file:
n = int(file.readline())
edges = [tuple(map(int, line.split())) for line in file.readlines()]

if not check_input_restrictions(n, edges):
print("Restrictiile nu sunt indeplinite.")
return None

return n, edges
def read_graph(filename):
with open(filename, 'r') as file:
n = int(file.readline())
edges = [tuple(map(int, line.split())) for line in file.readlines()]
return n, edges

def write_output(filename, result):
with open(filename, 'w') as file:
file.write(str(result['num_edges_removed']) + '\n')
for row in result['adjacency_matrix']:
file.write(' '.join(map(str, row)) + '\n')

def build_adjacency_matrix(n, edges):
adjacency_matrix = [[0] * n for _ in range(n)]
for edge in edges:
i, j = edge
adjacency_matrix[i-1][j-1] = adjacency_matrix[j-1][i-1] = 1
return adjacency_matrix

def calculate_degrees(adjacency_matrix):
degrees = [sum(row) for row in adjacency_matrix]
return degrees

def eliminate_edges(adjacency_matrix, degrees):
max_degree = max(degrees)
min_degree = min(degrees)

max_degree_nodes = [i for i in range(len(degrees)) if degrees[i] == max_degree]
min_degree_nodes = [i for i in range(len(degrees)) if degrees[i] == min_degree]

edges_removed = 0
for i in max_degree_nodes:
for j in min_degree_nodes:
if adjacency_matrix[i][j] == 1:
adjacency_matrix[i][j] = adjacency_matrix[j][i] = 0
edges_removed += 1

return edges_removed

if __name__ == "__main__":
input_filename = "graf_partial_1IN.txt"
output_filename = "graf_partial_1OUT.txt"

graph_data = read_graph(input_filename)

if graph_data is not None:
n, edges = graph_data

adjacency_matrix = build_adjacency_matrix(n, edges)
degrees = calculate_degrees(adjacency_matrix)

num_edges_removed = eliminate_edges(adjacency_matrix, degrees)

result = {
'num_edges_removed': num_edges_removed,
'adjacency_matrix': adjacency_matrix
}

write_output(output_filename, result)

</syntaxhighlight>

0431 - Graf Complet

2023-12-16T14:59:27Z

Corjuc Eunice: Pagină nouă: = Cerinţa = Se dau mai multe grafuri neorientate, prin matricea de adiacență. Să se verifice despre fiecare graf dacă este complet. = Date de intrare = Fişierul de intrare <code>graf_completIN.txt</code> conţine pe prima linie numărul de grafuri <code>G</code>. Pentru fiecare dintre cele <code>G</code> grafuri se dă <code>n</code> și apoi matricea de adiacență, formată din <code>n</code> linii și <code>n</code> coloane. = Date de ieşire = Fişierul de ieşire...

= Cerinţa =
Se dau mai multe grafuri neorientate, prin matricea de adiacență. Să se verifice despre fiecare graf dacă este complet.

= Date de intrare =
Fişierul de intrare <code>graf_completIN.txt</code> conţine pe prima linie numărul de grafuri <code>G</code>. Pentru fiecare dintre cele <code>G</code> grafuri se dă <code>n</code> și apoi matricea de adiacență, formată din <code>n</code> linii și <code>n</code> coloane.

= Date de ieşire =
Fişierul de ieşire <code>graf_completOUT.txt</code> va conţine <code>G</code> linii. Pe fiecare dintre ele se va afla mesajul <code>DA</code> sau <code>NU</code>, după cum graful corespunzător este sau nu complet.

= Restricţii şi precizări =

* <code>1 ≤ G ≤ 5</code>
* <code>1 ≤ n ≤ 50</code>

== Exemplul 1 ==
graf_completIN.txt:

2

3

0 1 1

1 0 1

1 1 0

4

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

graf_completOUT.txt:

DA

NU

== Exemplul 2 ==
graf_completIN.txt:

99

3

0 1 1

1 0 1

1 1 0

4

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

Output:

Restrictii neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def este_graf_complet(matrice_adiacenta):
n = len(matrice_adiacenta)
for i in range(n):
for j in range(n):
if i != j and matrice_adiacenta[i][j] == 0:
return False
return True

def verifica_restrictii(G, n):
return 1 <= G <= 5 and 1 <= n <= 50

def main():
with open("graf_completIN.txt", "r") as f_in, open("graf_completOUT.txt", "w") as f_out:
G = int(f_in.readline().strip())

for _ in range(G):
n = int(f_in.readline().strip())
if not verifica_restrictii(G,n):
print("Restrictii neindeplinite")
return
matrice_adiacenta = []
for _ in range(n):
linie = list(map(int, f_in.readline().split()))
matrice_adiacenta.append(linie)

rezultat = "DA" if este_graf_complet(matrice_adiacenta) else "NU"
f_out.write(rezultat + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>