https://wiki.universitas.ro/api.php?action=feedcontributions&feedformat=atom&user=MraaBitnami MediaWiki - User contributions [en]2026-05-01T20:50:08ZUser contributionsMediaWiki 1.42.1https://wiki.universitas.ro/index.php?title=3982_-_Descp2&diff=94463982 - Descp22024-01-11T18:35:54Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x.<br />
<br />
==Cerința==<br />
Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare kx_desc.in conține pe prima linie trei valori naturale nenule reprezentând numerele n, k şi x.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire kx_desc.out va conține o singură valoare reprezentând restul împărţirii numărului de kx-descompuneri distincte la numărul 10007.<br />
<br />
==Restricții și precizări==<br />
Pentru 20% din teste 0 < n ≤ 200; pentru celelalte 80% din teste, 200 < n ≤ 10000;<br />
1 ≤ x, k ≤ n<br />
==Exemplul 1==:<br />
kx_desc.in<br />
<br />
20 2 3<br />
kx_desc.out<br />
<br />
8<br />
==Explicație==<br />
Numărul de kx-descompuneri în acest caz este 8. Acestea sunt formate din numerele 1 şi 19; 2 şi 18; 3 şi 17; 4 şi 16; 5 şi 15; 6 şi 14; 7 şi 13; 8 şi 12.<br />
<br />
==Exemplul 2==:<br />
kx_desc.in<br />
<br />
2000 19 7<br />
kx_desc.out<br />
<br />
3184<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 10007<br />
<br />
def kx_descompuneri(n, k, x):<br />
<br />
dp = [[0] * (x + 1) for _ in range(n + 1)]<br />
dp[0][0] = 1<br />
for i in range(1, n + 1):<br />
for j in range(1, min(i, k) + 1):<br />
for l in range(x + 1):<br />
dp[i][l] = (dp[i][l] + dp[i - j][l - 1]) % MOD<br />
rezultat = 0<br />
for i in range(n - k * x + 1, n + 1):<br />
rezultat = (rezultat + dp[i][x]) % MOD<br />
return rezultat<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n, k, x = map(int, input().split())<br />
# Calculăm rezultatul și îl afișăm<br />
rezultat = kx_descompuneri(n, k, x)<br />
print(rezultat)<br />
python kx_desc.py < kx_desc.in<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3828_-_D_Caesar_Queries&diff=94453828 - D Caesar Queries2024-01-11T18:35:13Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
După ce Julius Caesar l-a învins pe Pompey în bătălia de la Pharsalus , acesta decide să țină un festin în cinstea soldaților săi loilai . El are q scenarii posibile pt oaspeți definite printr o pereche (n,k) care înseamnă că fiecare dintre cei n invitați pot alege unul dintre cele k feluri de mâncare . Deoarece Julius Caesar a plătit cei mai buni bucătari pentru a prepara mancarea , el își dorește ca fiecare fel de mâncare să fi fost ales de minimum un invitat. O configurație este un șir de n numere a , al i-lea soldat a ales felul a(i) . Câte configurații distincte există care să îndeplinească cerințele marelui Julius Caesar ? Două șiruri sunt distincte dacă diferă prin cel puțin o poziție.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare caesar.in conține pe prima linie un număr q care reprezintă numărul de scenarii la care trebuie să răspundeți urmate de q linii , pe fiecare aflându-se o pereche (n , k) reprezentatnd numărul de invitați , respectiv numărul de feluri de mâncare disponibile.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire caesar.out conține pe q linii răspunsul pentru fiecare scenariu modulo 666013.<br />
<br />
==Restricții și precizări==<br />
Q <= 100.000 , N <= 2000 K <= 2000 pentru orice query.<br />
Pentru 20 puncte Q = 1.<br />
Pentru alte 20 de puncte N , K <= 200.<br />
Exemplu:<br />
caesar.in<br />
<br />
1<br />
2 2<br />
caesar.out<br />
<br />
2<br />
caesar.in<br />
<br />
1<br />
5 4<br />
caesar.out<br />
<br />
240<br />
==Explicație==<br />
În primul exemplu , dacă notăm cu 1 primul fel de mâncare și cu 2 al doilea fel de mâncare , atunci configurațiile bune sunt : 12 și 21 ( primul soldat poate alege ori primul ori al doilea fel de mâncare , iar al doilea alege felul de mâncare pe care nu l-a ales primul soldat pentru că toate felurile de mâncare să fie alese de cel puțin un soldat )<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 666013<br />
<br />
def numar_configuratii(n, k):<br />
<br />
total_aranjamente = pow(k, n, MOD)<br />
aranjamente_fara_un_fel = pow(k-1, n, MOD)<br />
rezultat = (total_aranjamente - aranjamente_fara_un_fel) % MOD<br />
return rezultat<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim numărul de scenarii<br />
q = int(input())<br />
# Pentru fiecare scenariu, citim valorile și calculăm rezultatul<br />
for _ in range(q):<br />
n, k = map(int, input().split())<br />
rezultat = numar_configuratii(n, k)<br />
print(rezultat)<br />
<br />
python caesar.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3827_-_C_Bombs&diff=94443827 - C Bombs2024-01-11T18:34:36Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Le Quack vrea să bombardeze un oraș având N bombe numerotate de la 1...N. Dacă el detonează bombă cu valorea i atunci va putea să detoneze doar bombe încă nedetonate cu valori mai mici decât i. În cazul în care nu mai există astfel de bombe , poate detona orice bombă nedetonata. Le Quack va da numărul N și vrea să îi spuneți în câte moduri poate detona toate cele N bombe după regulă descrisă anterior.<br />
<br />
==Date de intrare==<br />
Inputul conține un număr natural n , reprezentând numărul de bombe pe care le are Le Quack.<br />
<br />
==Date de ieșire==<br />
Outputul conține răspunsul modulo 666013.<br />
<br />
==Restricții și precizări==<br />
N ≤ 2000.<br />
Pentru teste în valoare de 10p, N ≤ 9.<br />
Pentru restul testelor în valoare de 90p, N ≤ 2000.<br />
==Exemplu==:<br />
bombs.in<br />
<br />
2<br />
bombs.out<br />
<br />
2<br />
bombs.in<br />
<br />
3<br />
bombs.out<br />
<br />
5<br />
==Explicație==<br />
În primul exemplu, configurațiile posibile sunt: [1 , 2] și [2 , 1].<br />
În al doilea exemplu, configurațiile posibile sunt: [1 , 2 , 3] , [3 , 2 , 1] , [2 , 1 , 3] , [3 , 1 , 2] , [1 , 3 , 2]. Configurația [2 , 3 , 1] nu este bună, deoarece am luat bombă 3 înainte să termin toate bombele cu indici mai mici decât 2, ceea ce contrazice regula lui Le Quack.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 666013<br />
<br />
def numar_moduri_detonare(n):<br />
<br />
DP = [0] * (n + 1)<br />
DP[0] = 1<br />
for i in range(1, n + 1):<br />
for j in range(i):<br />
DP[i] = (DP[i] + DP[j]) % MOD<br />
return DP[n]<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n = int(input())<br />
# Calculăm rezultatul și afișăm rezultatul<br />
rezultat = numar_moduri_detonare(n)<br />
print(rezultat)<br />
<br />
<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3639_-_Subset_Fight&diff=94433639 - Subset Fight2024-01-11T18:34:02Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Un război se apropie, va trebui să ajuți combatanții să afle șansele lor de victorie.<br />
<br />
Se dă un vector cu n numere naturale, unde v[i] reprezintă numărul de valori egale cu i. Un scenariu în care omenirea câștigă e un scenariu în care suma numerelor dintr-o submulțime este multiplu de n.<br />
<br />
De exemplu, dacă vectorul din enunț este 1 2 3, valorile pe care le avem de fapt sunt 1 2 2 3 3 3, valori pe care le putem nota ca facând parte dintr-un nou vector, vectorul a, iar numărul de valori pe care îl avem este egal cu x = v[1]+v[2]+...+v[n].<br />
<br />
Astfel, trebuie să aflați câte din cele 2x<br />
submulțimi ale vectorului a au suma multiplu de n, modulo 109+7<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, unde v[i] reprezintă numărul de valori egale cu i.<br />
<br />
=Date de ieșire==<br />
Programul va afișa pe ecran răspunsul cerut.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 100<br />
cele n numere citite vor fi mai mici decât 200000<br />
Pentru 20 de puncte, suma numerelor din vector nu va depăși 20.<br />
Pentru 60 de puncte, suma numerelor din vector nu va depăși 100000.<br />
==Exemplu==:<br />
Intrare<br />
<br />
3<br />
1 1 1<br />
Ieșire<br />
<br />
4<br />
==Exemplu== 2<br />
Intrare<br />
<br />
5<br />
69 420 1017 128 953<br />
Ieșire<br />
<br />
985611225<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 10**9 + 7<br />
<br />
def numar_submultimi(n, v):<br />
<br />
# Inițializăm tabelul DP cu 0<br />
DP = [[0] * n for _ in range(2)]<br />
# Setăm valoarea inițială pentru submulțimile vide<br />
DP[0][0] = 1<br />
for i in range(1, n + 1):<br />
# Trecem la o nouă matrice DP (pară/impară)<br />
current = i % 2<br />
previous = 1 - current<br />
for j in range(n):<br />
# Copiem valorile din matricea anterioară<br />
DP[current][j] = DP[previous][j]<br />
# Actualizăm matricea curentă adăugând valorile corespunzătoare din vector<br />
DP[current][(j + i) % n] = (DP[current][(j + i) % n] + DP[previous][j]) % MOD<br />
return DP[n % 2][0] - 1<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n = int(input())<br />
v = list(map(int, input().split()))<br />
# Calculăm rezultatul și afișăm rezultatul<br />
rezultat = numar_submultimi(n, v)<br />
print(rezultat)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3240_-_Sequences&diff=94423240 - Sequences2024-01-11T18:33:28Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Să se calculeze numărul de șiruri crescătoare de lungime n, cu numere de la 1 la m, în care fiecare element apare de cel mult k ori.<br />
<br />
==Date de intrare==<br />
De la intrarea standard se citesc numerele întregi n, m și k, separate prin spațiu.<br />
<br />
==Date de ieșire==<br />
La ieșirea standard programul va afișa numărul de șiruri descrise în enunț.<br />
<br />
==Restricții și precizări==<br />
0 < n < 31<br />
0 < m < 31<br />
0 < k < 31<br />
==Exemplu==:<br />
Intrare<br />
<br />
3 4 2<br />
Ieșire<br />
<br />
16<br />
==Explicație==<br />
Explicație. Șirurile sunt: (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), (1,3,3), (1,3,4), (1,4,4), (2,2,3), (2,2,4), (2,3,3), (2,3,4), (2,4,4), (3,3,4), (3,4,4).<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def numar_siruri(n, m, k):<br />
<br />
# Funcție auxiliară pentru calculul coeficientului binomial<br />
def comb(n, r):<br />
result = 1<br />
for i in range(r):<br />
result = (result * (n - i)) // (i + 1)<br />
return result<br />
# Funcție recursivă pentru generarea numărului de șiruri<br />
def count_sequences(current_element, current_count, current_index):<br />
if current_index == n:<br />
return 1<br />
total_sequences = 0<br />
for i in range(current_element, m + 1):<br />
if current_count + 1 <= k:<br />
total_sequences += count_sequences(i, current_count + 1, current_index + 1)<br />
total_sequences += count_sequences(current_element, 0, current_index + 1)<br />
return total_sequences<br />
return count_sequences(1, 0, 0)<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n, m, k = map(int, input().split())<br />
# Calculăm rezultatul și afișăm rezultatul<br />
rezultat = numar_siruri(n, m, k)<br />
print(rezultat)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3821_-_Magic_Digits&diff=94413821 - Magic Digits2024-01-11T18:32:59Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Le Quack , mare fan al Lord Of The Rings , dar și al vrăjitoriei , află de la Gandalf că cifrele magice sunt { 1,2,3,4,5,6,7,8,9 } , cifra 0 este prea asemănătoare cu ochiul lui Sauron , fiind astfel considerată malefica. Le Quack iubeste aceste cifre magice încât le-a studiat mai atent și a observat că acestea pot forma numere de diferite lungimi ( ex : 1124 , 312 , 91235 ). Pentru fiecare număr format cu cifre magice definim gradul de frumusete ca fiind suma dintre frecvența minima a unei cifre magice și frecvența maxima a unei cifre magice care se găsește în număr. Formal , dacă construim un vector f , unde f[i] este numărul de apariții ale cifrei i și se șterg toate valorile pentru care f[i] = 0 , atunci min(f) + max(f) = k , unde k este gradul de frumusețe al numărului. De exemplu , pentru numărul 131 gradul de frumusețe este 1+2 = 3. Le Quack își pune următoarea întrebare : Câte numere de n cifre au gradul de frumusețe egal cu k ?<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură pe prima linie un număr N reprezentând lungimea numerelor care trebuie numărate și k , gradul de frumusețe al lor.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul cerut modulo 666013.<br />
<br />
==Restricții și precizări==<br />
N <= 300.<br />
K <= 2*N.<br />
Pentru 10 puncte N <= 6.<br />
Pentru alte 10 puncte , K > N.<br />
Pentru restul de 80 de puncte , K <= N , N > 6 si N <= 300.<br />
Nu uitați că cifra 0 nu poate fi folosită !<br />
==Exemplu==:<br />
Intrare<br />
<br />
2 2<br />
Ieșire<br />
<br />
72<br />
Intrare<br />
<br />
3 2<br />
Ieșire<br />
<br />
504<br />
==Explicație==<br />
În primul exemplu , sunt 72 de numere de lungime 2 cu gradul de frumusețe 2. câteva dintre acestea<br />
sunt : 13 , 14 , 32.<br />
În al doilea exemplu sunt 504 numere de lungime 3 cu gradul de frumusețe 2. Câteva dintre acestea<br />
sunt : 132 , 152 , 512.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 666013<br />
<br />
def numere_grad_frumusete(N, k):<br />
<br />
# Funcție auxiliară pentru calculul coeficientului binomial<br />
def comb(n, r):<br />
result = 1<br />
for i in range(r):<br />
result = (result * (n - i)) % MOD<br />
result = (result * pow(i + 1, MOD - 2, MOD)) % MOD<br />
return result<br />
# Funcție recursivă pentru generarea numărului de aranjamente<br />
def count_arrangements(digit_counts, current_k):<br />
if current_k < 0:<br />
return 0<br />
if current_k == 0:<br />
# Calculăm numărul de moduri în care putem aranja cifrele<br />
result = 1<br />
for count in digit_counts:<br />
result = (result * comb(N, count)) % MOD<br />
return result<br />
total_arrangements = 0<br />
for i in range(1, 10):<br />
# Adăugăm cifra i și continuăm recursiv<br />
new_digit_counts = digit_counts[:]<br />
new_digit_counts.append(i)<br />
total_arrangements = (total_arrangements + count_arrangements(new_digit_counts, current_k - 1)) % MOD<br />
return total_arrangements<br />
return count_arrangements([], k)<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
N, k = map(int, input().split())<br />
# Calculăm rezultatul și afișăm rezultatul modulo MOD<br />
rezultat = numere_grad_frumusete(N, k)<br />
print(rezultat)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3571_-_Tango&diff=94403571 - Tango2024-01-11T18:32:20Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>Un tango este format din fraze muzicale, fiecare dintre acestea având 8 timpi muzicali. Timpii muzicali au aceeaşi durată. La fel de importantă ca melodia unui tango este şi dansul asociat ei. Mişcările efectuate în timpul dansului se numesc figuri. Succesiunea de figuri efectuate în timpul dansului formează o coregrafie. Două coregrafii se consideră diferite dacă succesiunea figurilor care le alcătuiesc este diferită. O coregrafie frumoasă asociată unui tango are particularitatea următoare: atunci când se termină o frază muzicală trebuie să se termine şi o figură.<br />
<br />
D şi S se pregătesc pentru primul lor concurs de dans şi ei lucreaza momentan la coregrafia de tango. Chiar dacă va fi primul lor concurs, ei deja ştiu n figuri de dans şi au calculat pentru fiecare dintre aceste figuri câţi timpi muzicali durează. Fiindcă le place foarte mult să danseze împreună, ei vor să pregătească o coregrafie frumoasă pentru o piesă care durează exact k timpi muzicali.<br />
<br />
==Cerința==<br />
Determinaţi numărul coregrafiilor frumoase modulo 999983 pentru o piesă, care: durează exact k timpi muzicali, respectă condiţiile de mai sus şi sunt formate doar din cele n figuri cunoscute de D şi S (mai este prea puţin timp până la concurs, ca ei să inveţe şi figuri noi).<br />
<br />
==Date de intrare==<br />
Pe prima linie a fişierului de intrare tango.in se află numerele naturale nenule n şi k, separate printr-un singur spaţiu. Pe a doua linie se află exact n numere separate prin câte un spaţiu, reprezintând lungimile figurilor.<br />
<br />
==Date de ieșire==<br />
În fişierul de ieşire tango.out se va afişa numărul de coregrafii posibile modulo 999983.<br />
<br />
==Restricții și precizări==<br />
n ≤ 100 000.<br />
k ≤ 2 000 000 000.<br />
k va fi întotdeauna divizibil cu 8.<br />
1 ≤ lungimea unei figuri ≤ 8.<br />
Pentru 30% din teste va exista o singură figură de o anumită lungime.<br />
Pentru 50% din teste n ≤ 30.<br />
Pentru 70% din teste lungimile figurilor vor fi numai valori din mulţimea {2, 4, 6, 8}.<br />
Prin a modulo b se înţelege restul împărţirii lui a la b.<br />
==Exemplu==:<br />
tango.in<br />
<br />
3 16<br />
1 1 8<br />
tango.out<br />
<br />
66049<br />
==Explicație==<br />
Sunt 16 timpi muzicali deci o coregrafie frumoasă se va dansa pe 16 / 8 = 2 fraze muzicale.<br />
Dacă notăm figurile cu litere, avem figura A de lungime 1, figura B de lungime 1 şi figura C de lungime 8. Prima frază muzicală poate fi alcătuită din orice secvenţă alcătuită din opt bucăţi de A sau B, deci în total 2^8 = 256 posibilităţi. Încă o posibilitate de alcătuire a primei fraze este printr-un singur C. Rezultă un total de 257 posibilităţi. Pentru a doua frază avem tot atâtea posibilităţi, deci în total există 257 * 257 = 66049 coregrafii frumoase posibile.<br />
Cum 66049 modulo 999983 = 66049, se obţine rezultatul 66049.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 999983<br />
<br />
def numar_coregrafii(n, k, lungimi_figuri):<br />
<br />
# Inițializăm lista dp cu 0-uri<br />
dp = [0] * (k + 1)<br />
# Există o singură modalitate de a avea coregrafia de lungime 0<br />
dp[0] = 1<br />
# Calculăm numărul de coregrafii<br />
for i in range(1, n + 1):<br />
for j in range(lungimi_figuri[i - 1], k + 1):<br />
dp[j] = (dp[j] + dp[j - lungimi_figuri[i - 1]]) % MOD<br />
return dp[k]<br />
<br />
if __name__ == "__main__":<br />
<br />
with open("tango.in", "r") as f:<br />
n, k = map(int, f.readline().split())<br />
lungimi_figuri = list(map(int, f.readline().split()))<br />
rezultat = numar_coregrafii(n, k, lungimi_figuri)<br />
with open("tango.out", "w") as g:<br />
g.write(str(rezultat) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3234_-_Pavare_3&diff=94393234 - Pavare 32024-01-11T18:31:33Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div><br />
Se dă un dreptunghi cu lungimea egală cu 2N centimetri și lățimea egală cu 3 centimetri.<br />
<br />
==Cerința==<br />
Să se determine numărul M al pavărilor distincte cu dale dreptunghiulare care au lungimea egală cu un centimetru și lățimea egală cu 2 centimetri.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare pavare.in conține pe prima linie numărul natural nenul N, reprezentând jumătatea lungimii dreptunghiului.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire pavare.out va conține pe prima linie numărul natural nenul, reprezentând numărul modalităților de a pava dreptunghiul.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 100<br />
==Exemplu==:<br />
pavare.in<br />
<br />
2<br />
pavare.out<br />
<br />
11<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 1000000007<br />
<br />
def numar_pavari(N):<br />
<br />
# Inițializăm lista dp cu 0-uri<br />
dp = [0] * (N + 1)<br />
# Prima poziție este 1, deoarece există o singură modalitate de a avea dreptunghiul nefragmentat<br />
dp[0] = 1<br />
# Calculăm numărul de modalități<br />
for i in range(1, N + 1):<br />
dp[i] = (3 * dp[i - 1]) % MOD<br />
if i >= 2:<br />
dp[i] = (dp[i] + dp[i - 2]) % MOD<br />
return dp[N]<br />
<br />
if __name__ == "__main__":<br />
<br />
with open("pavare.in", "r") as f:<br />
N = int(f.readline())<br />
rezultat = numar_pavari(N)<br />
with open("pavare.out", "w") as g:<br />
g.write(str(rezultat) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=0730_-_Minus_K&diff=94380730 - Minus K2024-01-11T18:30:51Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi – şi în care nu apar K semne – pe poziţii consecutive.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare minusk.in conţine pe prima linie 2 numere naturale separate printr-un spaţiu, N şi K, cu semnificaţia din enunţ.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire minusk.out va conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 2011.<br />
<br />
==Restricții și precizări==<br />
1 ≤ K ≤ N ≤ 1000000;<br />
pentru 30% dintre teste N ≤ 10<br />
pentru 70% dintre teste N ≤ 1000<br />
==Exemplu==:<br />
minusk.in<br />
<br />
4 2<br />
minusk.out<br />
<br />
8<br />
==Explicație==<br />
Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 2011<br />
<br />
def numar_siruri(N, K):<br />
<br />
# Inițializăm matricea dp cu 0-uri<br />
dp = [[0] * 2 for _ in range(N + 1)]<br />
# Prima coloană este 1, pentru că există un singur șir de lungime 0, și anume șirul vid<br />
dp[0][0] = 1<br />
# Calculăm numărul de șiruri<br />
for i in range(1, N + 1):<br />
# Dacă adăugăm + în șirul anterior, nu adăugăm un semn - pe poziția i<br />
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD<br />
# Dacă adăugăm - în șirul anterior, verificăm dacă am adăugat deja K semne - consecutive<br />
if i >= K:<br />
dp[i][1] = (dp[i - 1][0] - dp[i - K][1] + MOD) % MOD<br />
else:<br />
dp[i][1] = dp[i - 1][0]<br />
return (dp[N][0] + dp[N][1]) % MOD<br />
<br />
if __name__ == "__main__":<br />
<br />
with open("minusk.in", "r") as f:<br />
N, K = map(int, f.readline().split())<br />
rezultat = numar_siruri(N, K)<br />
with open("minusk.out", "w") as g:<br />
g.write(str(rezultat) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=4032_-_Zar_1&diff=94374032 - Zar 12024-01-11T18:29:56Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
În câte moduri se poate obține suma n aruncând cu zarul (În câte moduri poți să îl scrii pe n ca sumă de valori mai mici sau egale cu 6).<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul n.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran răspunsul la întrebarea din enunț.<br />
<br />
==Restricții și precizări==<br />
1≤n≤1018<br />
Rezultatul se va afișa modulo 109+7<br />
.<br />
==Exemplu==:<br />
Intrare<br />
<br />
8<br />
Ieșire<br />
<br />
125<br />
==Explicație==<br />
Câteva dintre posibilități ar fi 1 + 1 + 6, 2 + 5 + 1, 1 + 6 + 1 …<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 10**9 + 7<br />
<br />
def numar_moduri_suma(n):<br />
<br />
# Initializăm lista cu 0-uri<br />
dp = [0] * (n + 1)<br />
# Există o singură modalitate de a obține suma 0, adică nu aruncăm zarul<br />
dp[0] = 1<br />
# Calculăm numărul de moduri pentru fiecare sumă posibilă<br />
for i in range(1, n + 1):<br />
for j in range(1, 7):<br />
if i - j >= 0:<br />
dp[i] = (dp[i] + dp[i - j]) % MOD<br />
return dp[n]<br />
<br />
if __name__ == "__main__":<br />
<br />
n = int(input("Introduceți suma n: "))<br />
rezultat = numar_moduri_suma(n)<br />
print(rezultat)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3084_-_Cub_Dinamic&diff=94363084 - Cub Dinamic2024-01-11T18:29:14Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Se dă un tablou tridimensional, de dimensiune n<br />
x n<br />
x n<br />
, fiecare element reprezentând o camera. m<br />
dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele (i,j,k)<br />
te poți deplasa in camerele de coordonate (i+1,j,k)<br />
, (i,j+1,k)<br />
și (i,j,k+1)<br />
.<br />
<br />
Știind că pornești din camera cu coordonate (1,1,1)<br />
, se cere să se afișeze numărul de moduri modulo 1234567<br />
de a ajunge in camera de coordonate (n,n,n,)<br />
.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare cub_dinamic.in conține pe prima linie numerele n și m, iar pe următoarele m linii câte 3 numere reprezentând coordonatele camerelor blocate.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire cub_dinamic.out va conține pe prima linie numărul S, reprezentând numărul de moduri modulo 1234567<br />
de a ajunge din camera (1,1,1)<br />
în camera (n,n,n)<br />
.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 200<br />
1 ≤ coordonatele camerelor ≤ n<br />
0 ≤ m ≤ n*n*n<br />
Dacă nu se poate ajunge in camera (n,n,n)<br />
sau una dintre camerele (1,1,1)<br />
sau (n,n,n)<br />
este blocată, atunci se va afișa 0.<br />
==Exemplu==:<br />
cub_dinamic.in<br />
<br />
3 1<br />
2 2 2<br />
cub_dinamic.out<br />
<br />
54<br />
==Explicație==<br />
Există 54 de moduri de a ajunge din camera (1,1,1)<br />
în camera (n,n,n)<br />
fără a trece prin camere blocate.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 1234567<br />
<br />
def numar_moduri(n, m, camere_blocate):<br />
<br />
dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]<br />
# Inițializăm matricea cu 0-uri<br />
for i in range(n + 1):<br />
for j in range(n + 1):<br />
for k in range(n + 1):<br />
dp[i][j][k] = 0<br />
# Marcam camerele blocate cu -1<br />
for i, j, k in camere_blocate:<br />
dp[i][j][k] = -1<br />
# Dacă camera finală este blocată sau camera de plecare este blocată, returnăm 0<br />
if dp[1][1][1] == -1 or dp[n][n][n] == -1:<br />
return 0<br />
dp[1][1][1] = 1<br />
for i in range(1, n + 1):<br />
for j in range(1, n + 1):<br />
for k in range(1, n + 1):<br />
# Dacă camera este blocată, continuăm<br />
if dp[i][j][k] == -1:<br />
continue<br />
# Actualizăm modul în care putem ajunge în camerele adiacente<br />
if i + 1 <= n and dp[i + 1][j][k] != -1:<br />
dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD<br />
if j + 1 <= n and dp[i][j + 1][k] != -1:<br />
dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD<br />
if k + 1 <= n and dp[i][j][k + 1] != -1:<br />
dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % MOD<br />
return dp[n][n][n]<br />
<br />
if __name__ == "__main__":<br />
<br />
with open("cub_dinamic.in", "r") as f:<br />
n, m = map(int, f.readline().split())<br />
camere_blocate = [tuple(map(int, f.readline().split())) for _ in range(m)]<br />
rezultat = numar_moduri(n, m, camere_blocate)<br />
with open("cub_dinamic.out", "w") as g:<br />
g.write(str(rezultat) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2532_-_Cnt_Cif_Sum&diff=94352532 - Cnt Cif Sum2024-01-11T18:28:23Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Se dă un număr N și un număr S. Să se determine câte numere de N cifre au suma cifrelor S.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numerele N și S.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul C, reprezentând numărul de numere de N cifre având suma cifrelor S modulo 666013.<br />
<br />
==Restricții și precizări==<br />
1 ≤ N ≤ 1000<br />
1 ≤ S ≤ 9 * N<br />
==Exemplu==:<br />
Intrare<br />
<br />
2 3<br />
Ieșire<br />
<br />
3<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 666013<br />
<br />
def numere_suma(N, S):<br />
<br />
dp = [[0] * (S + 1) for _ in range(N + 1)]<br />
# Inițializăm prima coloană cu 1, deoarece există o singură modalitate de a obține suma 0<br />
for i in range(N + 1):<br />
dp[i][0] = 1<br />
# Calculăm numărul de moduri<br />
for i in range(1, N + 1):<br />
for j in range(1, S + 1):<br />
for k in range(10):<br />
if j - k >= 0:<br />
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD<br />
return dp[N][S]<br />
<br />
if __name__ == "__main__":<br />
<br />
N, S = map(int, input("Introduceți N și S separate prin spațiu: ").split())<br />
<br />
rezultat = numere_suma(N, S)<br />
<br />
print(rezultat)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=1824_-_Pitic&diff=94341824 - Pitic2024-01-11T18:27:56Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Enunt==<br />
Carmen, piticul de gradina vrea sa meargă în vizita la piticul Tulosba. Pentru a ajunge la Tulosba, Carmen trebuie sa meargă printr-o rețea de N galerii, fiecare alcătuită din M sectoare.<br />
<br />
Rețeaua poate fi reprezentată printr-un tablou cu N linii, numerotate de la 1 la N și M coloane, numerotate de la 1 la M . Carmen ocupă sectorul 1 al galeriei 1. Tulosba ocupă sectorul M al galeriei 1.<br />
La galeria n se termina rețeaua și începe gradina unde sunt niște copii răi care vor sa-l spargă pe Carmen cu bâtele de Baseball.<br />
<br />
Dacă sectorul curent a lui Carmen este (i,j), atunci se poate deplasa:<br />
<br />
La dreapta, ajungând în sectorul (i,j+1) .<br />
Pe diagonala la dreapta în sus, ajungând în sectorul (i-1,j+1).<br />
Pe diagonala la dreapta în jos, ajungând în sectorul (i+1,j+1).<br />
Cerința<br />
Sa se afișeze în câte moduri poate Carmen sa ajungă la Tulosba.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare pitic.in conține pe prima linie numerele n și m cu semnificația din problema.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire pitic.out va conține pe prima linie numărul S, reprezentând în câte moduri poate sa ajungă Carmen la Tulosba.<br />
<br />
==Restricții și precizări==<br />
Carmen nu poate sa coboare sub nivelul 1<br />
Carmen nu poate sa urce mai sus de nivelul n pentru ca o sa fie spart de copii<br />
1 ≤ n ≤ 43<br />
1 ≤ m ≤ 43<br />
==Exemplu==:<br />
pitic.in<br />
<br />
3 3<br />
pitic.out<br />
<br />
2<br />
pitic.in<br />
<br />
7 1<br />
pitic.out<br />
<br />
1<br />
pitic.in<br />
<br />
4 4<br />
pitic.out<br />
<br />
4<br />
==Explicație==<br />
Exemplul 1 : Piticul Carmen poate sa meargă de 2 ori la dreapta sau o dată pe diagonala în sus la dreapta și odată pe diagonala în jos la dreapta.<br />
<br />
Exemplul 2 : Piticul Carmen poate sa meargă doar la dreapta deoarece dacă urca pe nivelul 2 o sa ajungă în gradina.<br />
<br />
Exemplul 3 :<br />
Modul 1: Dreapta de 3 ori<br />
Modul 2: Diagonala sus, Diagonala jos, Dreapta<br />
Modul 3: Diagonala sus, Dreapta , Diagonala jos<br />
Modul 4: Dreapta, Diagonala sus, Diagonala jos<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def numar_moduri(n, m):<br />
<br />
dp = [[0] * (m + 1) for _ in range(n + 1)]<br />
# Inițializăm prima coloană cu 1, deoarece Carmen poate să ajungă în oricare dintre cele n niveluri pornind de la nivelul 1<br />
for i in range(1, n + 1):<br />
dp[i][1] = 1<br />
# Calculăm numărul total de moduri<br />
for j in range(2, m + 1):<br />
for i in range(1, n + 1):<br />
dp[i][j] = dp[i][j - 1] # Carmen merge la dreapta<br />
if i - 1 > 0:<br />
dp[i][j] += dp[i - 1][j - 1] # Carmen merge pe diagonala sus<br />
if i + 1 <= n:<br />
dp[i][j] += dp[i + 1][j - 1] # Carmen merge pe diagonala jos<br />
return sum(dp[i][m] for i in range(1, n + 1))<br />
<br />
if __name__ == "__main__":<br />
<br />
with open("pitic.in", "r") as f:<br />
n, m = map(int, f.readline().split())<br />
rezultat = numar_moduri(n, m)<br />
with open("pitic.out", "w") as g:<br />
g.write(str(rezultat) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3214_-_Dinamica_04&diff=94333214 - Dinamica 042024-01-11T18:27:32Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>Definim un număr natural ca fiind bun dacă toate cifrele impare se află înaintea celor pare. De exemplu, numerele 13424, 400, 1357 sunt bune, pe când 34010 nu este.<br />
<br />
==Cerința==<br />
Dându-se un număr natural nenul n, să se determine câte numere bune de n cifre există. Pentru că acest număr poate fi foarte mare, se va determina răspunsul modulo 123457.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul n.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul de numere bune de n cifre, modulo 123457.<br />
<br />
==Restricții și precizări==<br />
Pentru 70% din punctaj, 1 ≤ n ≤ 100.000<br />
Pentru 30% din punctaj, 100.001 ≤ n ≤ 1.000.000.000<br />
==Exemplu==:<br />
Intrare<br />
<br />
3<br />
Ieșire<br />
<br />
475<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 123457<br />
<br />
def numere_bune(n):<br />
<br />
# Inițializăm matricea dp cu 0-uri<br />
dp = [[0] * 2 for _ in range(n + 1)]<br />
# Pentru un singur caracter, avem 5 opțiuni (cifrele impare)<br />
dp[1][0] = 5<br />
dp[1][1] = 0<br />
# Calculăm numărul de numere bune pentru n caractere<br />
for i in range(2, n + 1):<br />
dp[i][0] = (dp[i - 1][0] * 5 + dp[i - 1][1] * 5) % MOD<br />
dp[i][1] = dp[i - 1][0]<br />
return (dp[n][0] + dp[n][1]) % MOD<br />
<br />
if __name__ == "__main__":<br />
<br />
n = int(input("Introduceți n: "))<br />
<br />
rezultat = numere_bune(n)<br />
<br />
print(rezultat)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2260_-_Dinamica_02&diff=94322260 - Dinamica 022024-01-11T18:27:06Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>Se consideră un număr natural nenul N.<br />
<br />
==Cerința==<br />
Să se determine numărul de cuvinte de lungime N formate doar din litere mici și cu proprietatea că nu pot exista trei litere alăturate identice. Pentru că acest număr poate fi foarte mare, se va determina modulo 777013.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul N.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul de cuvinte modulo 777013.<br />
<br />
==Restricții și precizări==<br />
1 ≤ N ≤ 1 000 000<br />
Cuvintele baaad și deeeeef au trei litere alăturate egale, pe când abbaa și xxyyxx nu au.<br />
==Exemplu==:<br />
Intrare<br />
<br />
2<br />
Ieșire<br />
<br />
676<br />
<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 777013<br />
<br />
def numar_cuvinte(N):<br />
<br />
# Inițializăm matricea dp cu 0-uri<br />
dp = [[0] * 2 for _ in range(N + 1)]<br />
# Pentru un singur caracter, avem 26 opțiuni (literele mici de la 'a' la 'z')<br />
dp[1][0] = 26<br />
dp[1][1] = 0<br />
# Calculăm numărul de cuvinte pentru N caractere<br />
for i in range(2, N + 1):<br />
dp[i][0] = (dp[i - 1][0] * 25 + dp[i - 1][1]) % MOD<br />
dp[i][1] = dp[i - 1][0]<br />
return (dp[N][0] + dp[N][1]) % MOD<br />
<br />
if __name__ == "__main__":<br />
<br />
N = int(input("Introduceți N: "))<br />
<br />
rezultat = numar_cuvinte(N)<br />
<br />
print(rezultat)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2259_-_Dinamica_01&diff=94312259 - Dinamica 012024-01-11T18:26:42Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>Se consideră un număr natural nenul N. Vom considera mulțimea A(N) a numerelor de N cifre nenule care au proprietatea că orice două cifre alăturate sunt de parități diferite. De exemplu 1472 este un număr din mulțimea A(4), dar 1567 nu este pentru că are cifrele alăturate 1 și 5 de aceeași paritate.<br />
<br />
==Cerința==<br />
Să se determine numărul de elemente ale mulțimii A(N). Pentru că acest număr poate fi foarte mare, se va determina modulo 30103.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul N.<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul S, reprezentând numărul modulo 30103 al elementelor mulțimii A(N).<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 100.000<br />
==Exemplu==:<br />
Intrare<br />
<br />
2<br />
Ieșire<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 30103<br />
<br />
def numar_elemente_multime(N):<br />
<br />
# Inițializăm matricea dp cu 0-uri<br />
dp = [[0] * 2 for _ in range(N + 1)]<br />
# Pentru un singur caracter, avem 9 opțiuni (de la 1 la 9)<br />
dp[1][0] = 9<br />
dp[1][1] = 0<br />
# Calculăm numărul de elemente pentru N cifre<br />
for i in range(2, N + 1):<br />
dp[i][0] = (dp[i - 1][0] * 9 + dp[i - 1][1]) % MOD<br />
dp[i][1] = dp[i - 1][0]<br />
return (dp[N][0] + dp[N][1]) % MOD<br />
<br />
if __name__ == "__main__":<br />
<br />
N = int(input("Introduceți N: "))<br />
<br />
rezultat = numar_elemente_multime(N)<br />
<br />
print(rezultat)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2882_-_No_Pals&diff=94302882 - No Pals2024-01-11T18:26:16Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Gioni este un elev foarte pasionat de informatică și îndrăgește în special problemele care se rezolvă cu tehnica programării dinamice. El are un număr natural n și vrea să știe pentru fiecare numar i de la 1 la n câte numere cu i cifre nu sunt palindromuri. Fiindcă acest număr poate să fie foarte mare, se cere afișarea lui modulo 666013.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare no_pals.in conține pe prima linie numărul n.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire no_pals.out va conține pe fiecare linie i, de la 1 la n, numărul de numere de i cifre care nu sunt palindromuri.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 100000<br />
Exemplu:<br />
no_pals.in<br />
<br />
3<br />
no_pals.out<br />
<br />
0<br />
81<br />
810<br />
==Explicație==<br />
Toate numerele de o cifra sunt palindromuri. Sunt 90 de numere de 2 cifre, dintre care 9 sunt palindromuri. Sunt 900 de numere de 3 cifre, dintre care 90 sunt palindromuri.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 666013<br />
<br />
def numere_nepalindromice(n):<br />
<br />
dp = [0] * (n + 1)<br />
dp[1] = 9 # Un singur caracter, 9 opțiuni ne-palindromice (de la 1 la 9)<br />
for i in range(2, n + 1):<br />
dp[i] = (dp[i - 1] * 9) % MOD # Numărul de opțiuni pentru i cifre<br />
return dp<br />
<br />
if __name__ == "__main__":<br />
<br />
with open("no_pals.in", "r") as f:<br />
n = int(f.readline().strip())<br />
rezultate = numere_nepalindromice(n)<br />
with open("no_pals.out", "w") as g:<br />
for rezultat in rezultate[1:]:<br />
g.write(str(rezultat) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2421_-_CalculSume&diff=94292421 - CalculSume2024-01-11T18:25:49Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Cu n numere naturale, a1,a2,…,an<br />
, se pot calcula următoarele sume:<br />
S1=a1+a2+…+an<br />
<br />
S2=a1⋅a2+a1⋅a3+…+an−1⋅an<br />
<br />
S3=a1⋅a2⋅a3+a1⋅a2⋅a4+…+an−2⋅an−1⋅an<br />
<br />
...<br />
Sn=a1⋅a2⋅…⋅an<br />
.<br />
<br />
Se dau două numere n<br />
și k<br />
și apoi n numere naturale a1,a2,…,an<br />
. Se cere să se calculeze suma Sk<br />
.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare calculsume.in conține pe prima linie două numere n și k separate printr-un spațiu, urmate, pe a doua linie de n numere naturale separate de asemenea, prin spații.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire calculsume.out va conține rezultatul cerut.<br />
<br />
==Restricții și precizări==<br />
1 ≤ k ≤ n ≤ 100<br />
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 101<br />
pentru că sumele cerute pot avea valori foarte mari, se cere să se afișeze restul împărțirii acestora la 9973<br />
Exemplul 1:<br />
calculsume.in<br />
<br />
3 1<br />
1 2 3 <br />
calculsume.out<br />
<br />
6<br />
Exemplul 2:<br />
calculsume.in<br />
<br />
3 2 <br />
1 2 3<br />
calculsume.out<br />
<br />
11<br />
Exemplul 3:<br />
calculsume.in<br />
<br />
3 3<br />
1 2 3 <br />
calculsume.out<br />
<br />
6<br />
==Explicație==<br />
Cele 3 exemple citesc câte un set de date de intrare, pentru fiecare se va afișa rezultatul cerut.<br />
<br />
S 1 = 1 + 2 + 3, deci suma S1 este 6<br />
<br />
S 2 =1*2+1*3+2*3, deci suma S2 este 11<br />
<br />
S 3 =1*2*3, deci suma S3 este 6.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 9973<br />
<br />
def calculeaza_suma_k(n, k, numere):<br />
<br />
sume = [0] * (k + 1)<br />
for i in range(1, n + 1):<br />
for j in range(k, 0, -1):<br />
sume[j] = (sume[j] + numere[i - 1] * sume[j - 1]) % MOD<br />
<br />
return sume[k]<br />
<br />
if __name__ == "__main__":<br />
<br />
with open("calculsume.in", "r") as f:<br />
n, k = map(int, f.readline().split())<br />
numere = list(map(int, f.readline().split()))<br />
rezultat = calculeaza_suma_k(n, k, numere)<br />
with open("calculsume.out", "w") as g:<br />
g.write(str(rezultat) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3990_-_Dinamica_09&diff=94283990 - Dinamica 092024-01-11T18:25:21Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Se dă un număr natural nenul n. Să se determine numărul de numere de n cifre din mulțimea {1, 2, 3, 4} care nu au două cifre alăturate egale și care au proprietatea că sunt divizibile cu 2. Pentru că acest număr poate fi foarte mare, se va calcula modulo 123457.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul n,.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul cerut, modulo 123457.<br />
<br />
Restricții și precizări<br />
Pentru 80 de puncte, 1 ≤ n ≤ 10.000<br />
Pentru alte 20 de puncte, 100.000.000 ≤ n ≤ 1.000.000.000<br />
==Exemplu==:<br />
Intrare<br />
<br />
2<br />
Ieșire<br />
<br />
6<br />
==Explicație==<br />
Numerele sunt 12, 14, 24, 32, 34, 42.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def count_numbers(n):<br />
<br />
mod = 123457<br />
# Inițializare vector dp<br />
dp = [[0] * 4 for _ in range(n + 1)]<br />
for i in range(1, 4):<br />
dp[1][i] = 1<br />
# Calcul numărul de numere<br />
for i in range(2, n + 1):<br />
dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % mod<br />
dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % mod<br />
dp[i][3] = (dp[i - 1][1] + dp[i - 1][2]) % mod<br />
result = (dp[n][1] + dp[n][2] + dp[n][3]) % mod<br />
return result<br />
Citire date de intrare<br />
<br />
n = int(input())<br />
<br />
Calcul și afișare rezultat<br />
<br />
result = count_numbers(n) print(result)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3661_-_Dinamica_05&diff=94273661 - Dinamica 052024-01-11T18:24:53Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Se dau numerele naturale n și p. Să se determine:<br />
a) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că aceste cuvinte nu pot avea două litere alăturate identice, indiferent că sunt mari sau mici (cuvintele baArda sau fEEric au două litere alăturate identice).<br />
b) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că nu pot apărea două litere mari pe poziții alăturate.<br />
c) numărul cuvintelor de lungime n formate doar din litere mici și cu proprietatea că au cel mult p vocale (vocalele fiind: a, e, i, o, u)<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numerele n și p.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran trei numere: X, Y și Z, separate prin spațiu, care vor reprezenta răspunsurile la cele trei cerințe. Pentru că aceste numere pot fi foarte mari, se vor determina modulo 123457<br />
<br />
==Restricții și precizări==<br />
1 ≤ p < n ≤ 1.000<br />
==Exemplu==:<br />
Intrare<br />
<br />
2 1<br />
Ieșire<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def count_words(n, p):<br />
<br />
mod = 123457<br />
# a) Numărul cuvintelor fără două litere identice alăturate<br />
dp_a = [[0] * 2 for _ in range(n + 1)]<br />
dp_a[1][0] = 26 # o literă mică<br />
dp_a[1][1] = 26 # o literă mare<br />
for i in range(2, n + 1):<br />
dp_a[i][0] = (dp_a[i - 1][0] + dp_a[i - 1][1]) % mod<br />
dp_a[i][1] = dp_a[i - 1][0]<br />
X = (dp_a[n][0] + dp_a[n][1]) % mod<br />
# b) Numărul cuvintelor fără două litere mari consecutive<br />
dp_b = [0] * (n + 1)<br />
dp_b[1] = 52 # o literă mică sau mare<br />
for i in range(2, n + 1):<br />
dp_b[i] = dp_b[i - 1] * 2 - dp_b[i - 2]<br />
Y = dp_b[n]<br />
# c) Numărul cuvintelor mici cu cel mult p vocale<br />
dp_c = [[0] * (p + 1) for _ in range(n + 1)]<br />
dp_c[1][0] = 25 # o literă mică fără vocală<br />
for i in range(2, n + 1):<br />
dp_c[i][0] = (dp_c[i - 1][0] * 25) % mod<br />
for j in range(1, min(i, p) + 1):<br />
dp_c[i][j] = (dp_c[i - 1][j] * 25 + dp_c[i - 1][j - 1]) % mod<br />
Z = sum(dp_c[n][:p + 1]) % mod<br />
return X, Y, Z<br />
Citire date de intrare<br />
<br />
n, p = map(int, input().split())<br />
<br />
Calcul și afișare rezultat<br />
<br />
result = count_words(n, p) print(*result)<br />
<br />
<br />
2600 2028 651<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3217_-_Trepte_2.2&diff=94263217 - Trepte 2.22024-01-11T18:24:27Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial se afla treapta 1)<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numerele n și k.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.<br />
<br />
==Restricții și precizări==<br />
1 < n ≤ 1.000.000;<br />
1 ≤ k ≤ n - 1;<br />
deoarece numărul va fi prea mare sa va afișa modulo 9001;<br />
la început, persoana se află pe treapta 1.<br />
==Exemplul 1==:<br />
Intrare<br />
<br />
2 2<br />
Ieșire<br />
<br />
1<br />
==Explicație==<br />
Există o soluție, aceea când sare direct pe treapta 2.<br />
<br />
==Exemplul 2==:<br />
Intrare<br />
<br />
4 2<br />
Ieșire<br />
<br />
3<br />
==Explicație==<br />
Prima: 1 -> 2 -> 3 -> 4<br />
A doua: 1 -> 2 -> 4<br />
A treia: 1 -> 3 -> 4<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def numar_moduri_urcare_trepte(n, k):<br />
<br />
mod = 9001<br />
# Inițializare vector dp<br />
dp = [0] * (n + 1)<br />
dp[1] = 1<br />
# Calcul numărul de moduri<br />
for i in range(1, n + 1):<br />
for j in range(1, k + 1):<br />
if i + j <= n:<br />
dp[i + j] = (dp[i + j] + dp[i]) % mod<br />
return dp[n]<br />
Citire date de intrare<br />
<br />
n, k = map(int, input().split())<br />
<br />
Calcul și afișare rezultat<br />
<br />
result = numar_moduri_urcare_trepte(n, k) print(result)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=1991_-_Trepte_2&diff=94251991 - Trepte 22024-01-11T18:23:55Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial este pe treapta 1)<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numerele n și k.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.<br />
<br />
==Restricții și precizări==<br />
1 < n ≤ 100.000<br />
1 ≤ k ≤ n - 1<br />
deoarece numărul va fi prea mare sa va afișa modulo 9001.<br />
==Exemplul 1==:<br />
Intrare<br />
<br />
2 2<br />
Ieșire<br />
<br />
1<br />
Explicație<br />
Există o soluție, aceea când sare direct pe treapta 2.<br />
<br />
==Exemplul 2==:<br />
Intrare<br />
<br />
4 2<br />
Ieșire<br />
<br />
3<br />
==Explicație==<br />
Prima: 1 -> 2 -> 3 -> 4<br />
A doua: 1 -> 2 -> 4<br />
A treia: 1 -> 3 -> 4<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def numar_moduri_urcare_trepte(n, k):<br />
<br />
mod = 9001<br />
# Inițializare vector dp<br />
dp = [0] * (n + 1)<br />
dp[1] = 1<br />
# Calcul numărul de moduri<br />
for i in range(1, n + 1):<br />
for j in range(1, k + 1):<br />
if i + j <= n:<br />
dp[i + j] = (dp[i + j] + dp[i]) % mod<br />
return dp[n]<br />
Citire date de intrare<br />
<br />
n, k = map(int, input().split())<br />
<br />
Calcul și afișare rezultat<br />
<br />
result = numar_moduri_urcare_trepte(n, k) print(result)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2487_-_countbits&diff=94242487 - countbits2024-01-11T18:23:28Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>Se consideră un șir de numere naturale f[1], f[2], …, f[n]. Fiecărui element al șirului i se calculează numărul biților de 1 din reprezentarea în baza 2. De exemplu, numărul 15 are 4 biți de 1 în baza 2.<br />
<br />
==Cerința==<br />
Să se determine numărul total de biți de 1 al tuturor numerelor din șir.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare countbits.in conține pe prima linie numerele n, A, B, C, D, E, unde n este numărul elementelor șirului. Șirul se va genera astfel: f[1] = A, f[2] = B, apoi pentru orice i = 3..n, f[i] = 1 + (f[i-2] * C + f[i-1] * D) % E.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire countbits.out va conține pe prima linie un singur număr, reprezentând numărul total de biți de 1 al tuturor numerelor din șir.<br />
<br />
==Restricții și precizări==<br />
3 ≤ n ≤ 15 000 000<br />
3 ≤ A, B, C, D ≤ 100 000 000<br />
3 ≤ E ≤ 1 000 000 000<br />
Atenție la generarea elementelor șirului<br />
==Exemplu==:<br />
countbits.in<br />
<br />
4 7 11 15 19 8999<br />
countbits.out<br />
<br />
17<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def count_set_bits(num):<br />
<br />
count = 0<br />
while num:<br />
count += num & 1<br />
num >>= 1<br />
return count<br />
Citire date de intrare<br />
<br />
with open("countbits.in", "r") as file:<br />
<br />
n, A, B, C, D, E = map(int, file.readline().split())<br />
Generare șir și calcul număr total de biți de 1<br />
<br />
total_bits = 0 f = [A, B] for i in range(3, n + 1):<br />
<br />
next_element = 1 + (f[i - 2] * C + f[i - 1] * D) % E<br />
f.append(next_element)<br />
total_bits += count_set_bits(next_element)<br />
Scrierea rezultatului în fișierul de ieșire<br />
<br />
with open("countbits.out", "w") as file:<br />
<br />
file.write(str(total_bits) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2332_-_primXXL&diff=94232332 - primXXL2024-01-11T18:23:02Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Se dau n numere naturale şi un număr natural k. Aflaţi câte dintre numerele date îl divid pe k! ( k factorial).<br />
<br />
==Date de intrare==<br />
Fișierul de intrare primxxl.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule separate prin spații.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire primxxl.out va conține pe prima linie numărul d, reprezentând numărul numerelor de pe a doua linie a fișierului de intrare care îl divid pe k!.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 10.000<br />
1 ≤ k ≤ 1.000.000<br />
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000<br />
Exemplu:<br />
primxxl.in<br />
<br />
3 5<br />
20 3 14<br />
primxxl.out<br />
<br />
2<br />
==Explicație==<br />
Avem k!=5!=120, iar dintre numerele date 20 şi 3 îl divid pe 120, deci două numere.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def factorial(k):<br />
<br />
result = 1<br />
for i in range(2, k + 1):<br />
result *= i<br />
return result<br />
Citire date de intrare<br />
<br />
with open("primxxl.in", "r") as file:<br />
<br />
n, k = map(int, file.readline().split())<br />
numbers = list(map(int, file.readline().split()))<br />
Calcularea factorialului lui k<br />
<br />
k_factorial = factorial(k)<br />
<br />
Numărarea câtor dintre numerele date îl divid pe k!<br />
<br />
count = sum(1 for num in numbers if k_factorial % num == 0)<br />
<br />
Scrierea rezultatului în fișierul de ieșire<br />
<br />
with open("primxxl.out", "w") as file:<br />
<br />
file.write(str(count) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3315_-_Eratostene3&diff=94223315 - Eratostene32024-01-11T18:22:30Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==Cerința==<br />
Se dau n numere naturale. Pentru fiecare număr aflaţi câţi divizori liberi de pătrate are acesta.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare eratostene4.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire eratostene4.out va conține pe prima linie, pentru fiecare număr din fişierul de intrare, numărul divizorilor liberi de pătrate ai acestuia.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 100.000<br />
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000<br />
un număr natural se numeşte liber de pătrate dacă nu se divide cu pătratul unui număr prim<br />
==Exemplu==:<br />
eratostene4.in<br />
<br />
3<br />
20 8 5<br />
eratostene4.out<br />
<br />
4 2 2<br />
==Explicație==<br />
Divizorii lui 20, liberi de pătrate, sunt: 1, 2, 5, 10.<br />
Divizorii lui 8, liberi de pătrate, sunt: 1, 2.<br />
Divizorii lui 5, liberi de pătrate, sunt: 1, 5.<br />
==Rezolvare==<br />
<br />
<syntaxhighlight lang="python3" line="1"><br />
def ciurul_lui_eratostene(limit):<br />
<br />
primes = []<br />
is_prime = [True] * (limit + 1)<br />
is_prime[0] = is_prime[1] = False<br />
for i in range(2, int(limit**0.5) + 1):<br />
if is_prime[i]:<br />
primes.append(i)<br />
for j in range(i * i, limit + 1, i):<br />
is_prime[j] = False<br />
for i in range(int(limit**0.5) + 1, limit + 1):<br />
if is_prime[i]:<br />
primes.append(i)<br />
return primes<br />
<br />
def numar_divizori_liberi_de_patrate(numar, primes):<br />
<br />
count = 1 # 1 este divizorul liber de pătrate<br />
for prime in primes:<br />
if prime * prime > numar:<br />
break<br />
exponent = 0<br />
while numar % prime == 0:<br />
numar //= prime<br />
exponent += 1<br />
count *= (exponent + 1)<br />
if numar > 1:<br />
count *= 2 # numărul însuși și 1<br />
return count - 2 # eliminăm divizorul 1 și numărul însuși<br />
Citire date de intrare<br />
<br />
with open("eratostene4.in", "r") as file:<br />
<br />
n = int(file.readline().strip())<br />
numbers = list(map(int, file.readline().split()))<br />
Calcularea divizorilor primi<br />
<br />
max_number = max(numbers) primes = ciurul_lui_eratostene(max_number)<br />
<br />
Calcularea și afișarea rezultatelor<br />
<br />
with open("eratostene4.out", "w") as file:<br />
<br />
for numar in numbers:<br />
result = numar_divizori_liberi_de_patrate(numar, primes)<br />
file.write(str(result) + " ")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2211_-_True&diff=94212211 - True2024-01-11T18:21:47Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>Să considerăm o matrice cu N linii şi N coloane cu elemente numere naturale. În această matrice trebuie să plasăm două ture, în poziţii distincte. Spunem că un element al matricei este atacat dacă se află pe aceeaşi linie sau pe aceeaşi coloană cu una dintre cele două ture. Elementele din poziţiile celor două ture nu sunt considerate atacate.<br />
Turele vor fi plasate astfel încât suma elementelor atacate să fie cât mai mare.<br />
==Cerința==<br />
Scrieţi un program care să determine suma elementelor atacate (maximă posibil).<br />
<br />
==Date de intrare==<br />
Fișierul de intrare ture.in va conţine pe prima linie un număr natural N, cu semnificaţia din enunţ. Pe fiecare dintre următoarele N linii se află câte N numere naturale, reprezentând elementele matricei.<br />
==Date de ieșire==<br />
Fișierul de ieșire ture.out va conţine o singură linie pe care va fi scrisă suma maximă.<br />
<br />
==Restricții și precizări==<br />
2 ≤ N ≤ 100<br />
Elementele matricei sunt numere naturale mai mici sau egale cu 255<br />
==Exemplu==:<br />
ture.in<br />
5 <br />
4 2 2 3 3 <br />
4 2 1 4 0 <br />
1 3 4 0 1 <br />
4 3 0 2 3 <br />
0 0 3 0 4 <br />
ture.out<br />
40<br />
==Explicație==<br />
Prima tură va fi plasată în poziţia (4,3), iar cea de a doua tură va fi plasată în poziţia (2,5).<br />
<br />
==Rezolvare==<br />
<br />
<syntaxhighlight lang="python3" line="1"><br />
def find_max_attack_sum(matrix):<br />
<br />
n = len(matrix)<br />
max_sum = 0<br />
for i in range(n):<br />
for j in range(n):<br />
for k in range(i + 1, n):<br />
for l in range(j + 1, n):<br />
# Calculează suma elementelor atacate de turele plasate la (i, j) și (k, l)<br />
attack_sum = sum(matrix[i][col] for col in range(n)) + sum(matrix[row][j] for row in range(n))<br />
attack_sum -= matrix[i][j] + matrix[k][l] # eliminăm dublurile<br />
# Actualizează suma maximă<br />
max_sum = max(max_sum, attack_sum)<br />
return max_sum<br />
Citire date de intrare<br />
<br />
with open("ture.in", "r") as file:<br />
<br />
n = int(file.readline().strip())<br />
matrix = [list(map(int, file.readline().split())) for _ in range(n)]<br />
Găsește suma maximă a elementelor atacate<br />
<br />
result = find_max_attack_sum(matrix)<br />
<br />
Scrie rezultatul în fișierul de ieșire<br />
<br />
with open("ture.out", "w") as file:<br />
<br />
file.write(str(result) + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2863_-_Pyk&diff=94202863 - Pyk2024-01-11T18:21:14Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>==pyk==<br />
Fie k, n și y trei numere naturale. Fie X un șir format din n numere naturale: x1,x2,x3,…,xn. Fie P produsul numerelor y,x1,x2,x3,…,xn, adică P=y×x1×x2×x3×…×xn. Numărul P este o “k-putere” dacă există un număr natural z astfel încât P=zk.<br />
<br />
==Cerinta==<br />
Scrieți un program care să citească numerele k,n,x1,x2,x3,…,xn<br />
și care să determine:<br />
<br />
1. cel mai mic și cel mai mare număr din șirul X ce sunt formate doar din cifre identice;<br />
2. descompunerea în factori primi a celui mai mic număr natural y (y ≥ 2) cu proprietatea că numărul P=y×x1×x2×x3×…×xn<br />
este o “k-putere”.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare pyk.in conține:<br />
<br />
pe prima linie, un număr natural C, reprezentând cerința din problemă care trebuie rezolvată (1 sau 2);<br />
pe a doua linie, numerele naturale k și n, separate printr-un singur spațiu;<br />
pe a treia linie, cele n numere naturale x1,x2,x3,…,xn, separate prin câte un singur spaţiu.<br />
<br />
==Date de ieșire==<br />
Dacă C=1, atunci prima linie a fişierului de ieşire pyk.out va conține două numere naturale, separate printr-un<br />
singur spațiu, reprezentând răspunsul la cerința 1 a problemei. Dacă nu există astfel de numere, prima linie a<br />
fișierului va conține valoarea 1.<br />
<br />
Dacă C=2, atunci fișierul de ieşire pyk.out va conține:<br />
<br />
pe prima linie, un număr natural m reprezentând numărul de factori primi distincți din descompunerea în<br />
factori primi a numărului y, determinat la rezolvarea cerinței 2;<br />
pe fiecare dintre următoarele m linii (câte o linie pentru fiecare factor prim din descompunerea în factori primi<br />
a lui y), câte două valori F şi E, separate printr-un singur spaţiu, reprezentând factorul prim F și exponentul<br />
E al acestui factor din descompunerea în factori primi a lui y.<br />
Scrierea în fișier a acestor factori primi se va face în ordinea crescătoare a valorii lor.<br />
<br />
==Restricții și precizări==<br />
2 ≤ n ≤ 50.000<br />
2 ≤ k ≤ 100<br />
2 ≤ x1,x2,x3,…,xn<br />
≤ 10.000<br />
2 ≤ y<br />
pentru rezolvarea corectă a cerinței 1 se acordă 10 puncte;<br />
pentru rezolvarea corectă a cerinței 2 se acordă 90 puncte.<br />
<br />
==Exemplu==:<br />
pyk.in :<br />
1<br />
2 7<br />
122 1111 5 4 88 123 999<br />
pyk.out :<br />
4 1111 <br />
==Explicație==<br />
Cerința este 1, k=2, n=7. Numerele din șirul X formate doar din cifre identice sunt: 1111, 5, 4, 88, 999. Cel mai mic număr dintre acestea este 4, iar cel mai mare este 1111.<br />
<br />
pyk.in :<br />
2<br />
3 6<br />
12 5 60 125 4 36<br />
pyk.out :<br />
3<br />
2 1<br />
3 2<br />
5 1<br />
==Explicație==<br />
Cerința este 2, k=3, n=6. Produsul celor 6 numere din șir este: 12*5*60*125*4*36=64800000. y=90 este cea mai mică valoare pentru care P = 90 * 64800000 = 18003 devine o “k-putere“. Descompunerea în factori primi a lui y conține m=3 factori<br />
primi: 21×32×51.<br />
<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def factorize(num):<br />
<br />
factors = {}<br />
i = 2<br />
while i * i <= num:<br />
while num % i == 0:<br />
if i not in factors:<br />
factors[i] = 0<br />
factors[i] += 1<br />
num //= i<br />
i += 1<br />
if num > 1:<br />
factors[num] = 1<br />
return factors<br />
<br />
def k_power_factors(k, numbers):<br />
<br />
product = 1<br />
for num in numbers:<br />
product *= num<br />
factors = factorize(product)<br />
k_factors = {key: value * k for key, value in factors.items()}<br />
return k_factors<br />
<br />
def identical_digits_numbers(numbers):<br />
<br />
identical_numbers = [num for num in numbers if len(set(str(num))) == 1]<br />
return identical_numbers<br />
Citire date de intrare<br />
<br />
C = int(input()) k, n = map(int, input().split()) numbers = list(map(int, input().split()))<br />
<br />
if C == 1:<br />
<br />
identical_numbers = identical_digits_numbers(numbers)<br />
if identical_numbers:<br />
print(min(identical_numbers), max(identical_numbers))<br />
else:<br />
print("1")<br />
<br />
elif C == 2:<br />
<br />
k_factors = k_power_factors(k, numbers)<br />
distinct_factors = sorted(k_factors.keys())<br />
print(len(distinct_factors))<br />
for factor in distinct_factors:<br />
exponent = k_factors[factor]<br />
print(factor, exponent)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=1812_-_Litere_Gen_1&diff=94191812 - Litere Gen 12024-01-11T18:18:07Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Scrieți un program care citeşte o valoare naturală impară pentru n şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n litere mici care îndeplinesc următoarele proprietăţi:<br />
<br />
- încep şi se termină cu a;<br />
- oricare două litere alăturate dintr-o combinaţie sunt consecutive în alfabet.<br />
Astfel, pentru n=5, combinaţiile afişate sunt, în ordine, următoarele: ababa, abcba.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul n, impar.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran, pe rânduri separate, combinaţiile care îndeplinesc proprietăţile cerute.<br />
<br />
==Restricții și precizări==<br />
3 ≤ n ≤ 25<br />
==Exemplu==:<br />
Intrare<br />
<br />
5<br />
Ieșire<br />
<br />
ababa<br />
abcba<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def generate_combinations(current, n):<br />
<br />
if len(current) == n:<br />
print("".join(current))<br />
return<br />
if not current:<br />
current.append('a')<br />
generate_combinations(current, n)<br />
current.pop()<br />
<br />
for char in range(ord('b'), ord('a') + n):<br />
current.append(chr(char))<br />
generate_combinations(current, n)<br />
current.pop()<br />
Citirea datelor de intrare<br />
<br />
n = int(input("Introduceți n (număr impar): "))<br />
<br />
if n % 2 == 0:<br />
<br />
print("Numărul introdus trebuie să fie impar.")<br />
<br />
else:<br />
<br />
# Generarea și afișarea combinațiilor<br />
generate_combinations([], n)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3945_-_Fazan_Max&diff=94183945 - Fazan Max2024-01-11T18:17:27Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se dau n cuvinte distincte formate din litere mici. Afișați șirul format dintr-un număr maxim de cuvinte distincte dintre cele date, care respectă regula jocului Fazan. La jocul Fazan o succesiune de două cuvine a și b se consideră corectă dacă ultimele două litere din cuvântul a sunt identice cu primele două din b. De exemplu, cuvintele fazan și anterior sunt corecte în această ordine.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul n și apoi n cuvinte, separate prin spații sau scrise pe rânduri separate.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran cuvintele care formează șirul cerut, separate prin câte un spațiu.<br />
Dacă există mai multe șiruri formate dintr-un număr maxim de cuvinte, se va afișa cel mai mic lexicografic.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 30<br />
cele n cuvinte sunt formate din litere mici, au lungimea cel puțin 2 și cel mult 20 și sunt distincte.<br />
==Exemplu==:<br />
Intrare<br />
<br />
7<br />
dor ana nasture repede alina diana decis<br />
Ieșire<br />
<br />
alina nasture repede decis<br />
Explicație<br />
<br />
Există mai multe soluții de lungime maximă, dar cea afișată este minimă lexicografic. Celelalte soluții sunt:<br />
<br />
ana nasture repede decis<br />
diana nasture repede decis<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def backtracking(current_path, remaining_words, result):<br />
<br />
if not remaining_words:<br />
# Verificăm dacă șirul format este mai lung sau la fel de lung ca rezultatul curent<br />
if len(current_path) > len(result):<br />
return current_path<br />
elif len(current_path) == len(result):<br />
# Verificăm dacă șirul curent este lexicografic mai mic<br />
current_str = " ".join(current_path)<br />
result_str = " ".join(result)<br />
if current_str < result_str:<br />
return current_path<br />
else:<br />
return result<br />
else:<br />
return result<br />
last_word = current_path[-1] if current_path else None<br />
for word in remaining_words:<br />
if last_word is None or last_word[-2:] == word[:2]:<br />
new_path = current_path + [word]<br />
new_remaining = remaining_words.copy()<br />
new_remaining.remove(word)<br />
result = backtracking(new_path, new_remaining, result)<br />
return result<br />
Citirea datelor de intrare<br />
<br />
n = int(input()) words = input().split()<br />
<br />
Sortăm cuvintele pentru a îmbunătăți eficiența algoritmului<br />
<br />
words.sort()<br />
<br />
Inițializăm rezultatul cu primul cuvânt<br />
<br />
initial_word = words.pop(0) result = backtracking([initial_word], words, [])<br />
<br />
Afișăm rezultatul<br />
<br />
print(" ".join(result))<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3415_-_Vector_Div&diff=94173415 - Vector Div2024-01-11T18:16:44Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se da un vector cu n elemente. Asupra fiecărui element putem efectua 2 tipuri de operații: să-l adunăm sau să-l scădem cu 1. La final, fiecare element trebuie să fie divizor al elementului următor. Adică, v[i] îl divide pe v[i + 1], oricare ar fi 1 ≤ i < n. Știind că ultimul element nu poate fi modificat, aflați numărul minim de operații pentru ca vectorul să îndeplinească condiția dată.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul minim de operații.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 10<br />
cele n numere citite vor fi mai mici sau egale cu 1.000.000<br />
==Exemplu==:<br />
Intrare<br />
<br />
4<br />
2 8 4 10<br />
Ieșire<br />
<br />
5<br />
==Explicație==<br />
Un exemplu de vector care respectă condiția este 1 5 5 10.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def min_operations(n, values):<br />
<br />
max_value = max(values)<br />
dp = [[float('inf')] * (max_value + 1) for _ in range(n)]<br />
# Inițializăm prima coloană a matricei dp<br />
for j in range(1, max_value + 1):<br />
dp[0][j] = min(abs(values[0] - j), j - 1)<br />
for i in range(1, n):<br />
for j in range(1, max_value + 1):<br />
for k in range(1, max_value + 1):<br />
if j % k == 0:<br />
dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(values[i] - j))<br />
# Alegem minimul din ultima linie a matricei dp<br />
result = min(dp[n - 1])<br />
return result<br />
Citim input-ul<br />
<br />
n = int(input()) values = list(map(int, input().split()))<br />
<br />
Calculăm rezultatul<br />
<br />
result = min_operations(n, values)<br />
<br />
Afișăm rezultatul<br />
<br />
print(result)<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=1357_-_Plus_Minus&diff=94161357 - Plus Minus2024-01-11T18:15:57Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Fie n un număr natural.<br />
Să se determine toate posibilitățile de alegere a semnelor + și - pentru care<br />
n = (+|-) 12 + (+|-) 22 + ... + (+|-) n2<br />
<br />
==Date de intrare==<br />
Fișierul de intrare plusminus.in conține pe prima linie numărul n.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire plusminus.out va conține pe fiecare linie o succesiune de n semne + sau - , separate prin câte un spațiu, reprezentând câte o soluție a problemei. Dacă nu există soluție, atunci fișierul de ieșire va conține pe prima linie mesajul IMPOSIBIL.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 23<br />
șirurile se vor afișa în ordine lexicografica; caracterul - este considerat mai mic decăt caracterul +<br />
==Exemplu==:<br />
plusminus.in<br />
<br />
9<br />
plusminus.out<br />
<br />
- - + - + - + + - <br />
+ - - + - - + - +<br />
+ + - - + + - - +<br />
+ + + + - + - - +<br />
==Explicație==<br />
Sunt 4 posibilități:<br />
1) 9 = -12 – 22 + 32 – 42 + 52 – 62 + 72 + 82 – 92<br />
2) 9 = +12 – 22 – 32 + 42 – 52 – 62 + 72 – 82 + 92<br />
3) 9 = +12 + 22 – 32 – 42 + 52 + 62 – 72 – 82 + 92<br />
4) 9 = +12 + 22 + 32 + 42 – 52 + 62 – 72 – 82 + 92<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def solve_plus_minus(n, signs, current_sum, current_expression, result):<br />
<br />
if len(current_expression) == n:<br />
if current_sum == 0:<br />
result.append(" ".join(current_expression))<br />
return<br />
for sign in signs:<br />
new_sum = current_sum + sign * (current_expression[-1] + 1) ** 2<br />
if new_sum <= n:<br />
solve_plus_minus(n, signs, new_sum, current_expression + [sign], result)<br />
<br />
def plus_minus(n):<br />
<br />
signs = [-1, 1] # -1 pentru minus, 1 pentru plus<br />
result = []<br />
# Inițial, începem cu primul termen, care este întotdeauna un plus<br />
solve_plus_minus(n, signs, 1, [1], result)<br />
if not result:<br />
result.append("IMPOSIBIL")<br />
return result<br />
Citim input-ul<br />
<br />
with open("plusminus.in", "r") as f:<br />
<br />
n = int(f.readline().strip())<br />
Calculăm rezultatul<br />
<br />
result = plus_minus(n)<br />
<br />
Scriem rezultatul în fișierul de ieșire<br />
<br />
with open("plusminus.out", "w") as f:<br />
<br />
for line in result:<br />
f.write(line + "\n")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3605_-_Desc_Prime&diff=94153605 - Desc Prime2024-01-11T18:14:40Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se dă un număr natural nenul S. Să se determine numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, precum și o modalitate de a-l scrie pe S ca sumă de cât mai multe numere prime distincte.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul S.<br />
<br />
==Date de ieșire==<br />
Programul va afișa la ecran pe prima linie numărul nrSol, reprezentând numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, iar pe a doua linie o modalitate de a-l scrie pe S ca sumă de cât mai multe numere prime distincte. Dacă sunt mai multe soluții, se va afișa cea minimă lexicografic, iar numerele prime din soluție se vor scrie în ordine crescătoare.<br />
<br />
==Restricții și precizări==<br />
1 ≤ S ≤ 100<br />
==Exemplu==:<br />
Intrare<br />
<br />
20<br />
Ieșire<br />
<br />
4<br />
2 5 13<br />
==Explicație==<br />
Sunt patru soluții: 3 17, 2 5 13, 7 13, 2 7 11. Dintre acestea, soluția care are cele mai multe numere prime și este minimă lexicografic este 2 5 13.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def is_prime(num):<br />
<br />
if num < 2:<br />
return False<br />
for i in range(2, int(num**0.5) + 1):<br />
if num % i == 0:<br />
return False<br />
return True<br />
<br />
def generate_primes(limit):<br />
<br />
primes = []<br />
for i in range(2, limit + 1):<br />
if is_prime(i):<br />
primes.append(i)<br />
return primes<br />
<br />
def sum_of_primes(S, primes):<br />
<br />
solutions = []<br />
def backtrack(target, path, start):<br />
if target == 0:<br />
solutions.append(path[:])<br />
return<br />
for i in range(start, len(primes)):<br />
if primes[i] > target:<br />
break<br />
path.append(primes[i])<br />
backtrack(target - primes[i], path, i + 1)<br />
path.pop()<br />
backtrack(S, [], 0)<br />
return solutions<br />
<br />
if __name__ == "__main__":<br />
<br />
try:<br />
S = int(input("Introduceți S: "))<br />
<br />
primes = generate_primes(S)<br />
solutions = sum_of_primes(S, primes)<br />
print(len(solutions))<br />
if solutions:<br />
print(" ".join(map(str, solutions[0])))<br />
except ValueError:<br />
print("Introduceți un număr natural.")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=0344_-_Paranteze&diff=94140344 - Paranteze2024-01-11T18:13:54Z<p>Mraa: </p>
<hr />
<div>==Cerinţa==<br />
Se dă un număr natural par n. Generați toate șirurile de n paranteze rotunde care se închid corect.<br />
<br />
==Date de intrare==<br />
Fişierul de intrare paranteze.in conţine pe prima linie numărul n.<br />
<br />
==Date de ieşire==<br />
Fişierul de ieşire paranteze.out va conţine pe fiecare linie câte un șir de n paranteze rotunde care se închid corect. Șirurile vor fi afișate în ordine lexicografică, considerând paranteza deschisa ( mai mică decât paranteza închisă ).<br />
<br />
==Restricţii şi precizări==<br />
1 ≤ n ≤ 20, număr natural par<br />
==Exemplu==:<br />
paranteze.in<br />
<br />
6<br />
paranteze.out<br />
<br />
((()))<br />
(()())<br />
(())()<br />
()(())<br />
()()()<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def generate_parentheses(n, current, open_count, close_count):<br />
<br />
if open_count == close_count == n:<br />
print("".join(current))<br />
return<br />
if open_count < n:<br />
generate_parentheses(n, current + ['('], open_count + 1, close_count)<br />
if close_count < open_count:<br />
generate_parentheses(n, current + [')'], open_count, close_count + 1)<br />
<br />
if __name__ == "__main__":<br />
<br />
try:<br />
n = int(input("Introduceți n (număr natural par): "))<br />
<br />
if n % 2 == 0:<br />
generate_parentheses(n, [], 0, 0)<br />
else:<br />
print("Introduceți un număr par.")<br />
except ValueError:<br />
print("Introduceți un număr natural par.")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=0322_-_Partitii_Numar_2&diff=94130322 - Partitii Numar 22024-01-11T18:13:16Z<p>Mraa: </p>
<hr />
<div>==Cerinţa==<br />
Se dă un număr natural n şi un număr m. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de cel puţin m numere naturale distincte.<br />
<br />
==Date de intrare==<br />
Fişierul de intrare partitiinumar2.in conţine pe prima linie numerele n şi m.<br />
<br />
==Date de ieşire==<br />
Fişierul de ieşire partitiinumar2.out va conţine pe pe fiecare linie câte un şir de numere naturale ordonate strict crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este n şi sunt cel puţin m numere în fiecare şir. Şirurile vor fi afişate în ordine lexicografică.<br />
<br />
==Restricţii şi precizări==<br />
1 ≤ m < n ≤ 40<br />
==Exemplu==:<br />
partitiinumar2.in<br />
<br />
10 3<br />
partitiinumar2.out<br />
<br />
1 2 3 4 <br />
1 2 7 <br />
1 3 6 <br />
1 4 5 <br />
2 3 5 <br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def partitii(n, m, current, start):<br />
if n == 0 and len(current) >= m:<br />
print(" ".join(map(str, current)))<br />
return<br />
for i in range(start, n + 1):<br />
partitii(n - i, m, current + [i], i + 1)<br />
<br />
if __name__ == "__main__":<br />
<br />
try:<br />
n, m = map(int, input("Introduceți n și m: ").split())<br />
<br />
partitii(n, m, [], 1)<br />
except ValueError:<br />
print("Introduceți valori numerice valide.")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=0324_-_Partitii_Numar_4&diff=94120324 - Partitii Numar 42024-01-11T18:12:32Z<p>Mraa: </p>
<hr />
<div>==Cerinţa=<br />
Se dă un =umăr natural n şi o mulţime cu m elemente, numere naturale nenule. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de termeni din acea mulţime.<br />
<br />
==Date de intrare==<br />
Fişierul de intrare partitiinumar4.in conţine pe prima linie numerele n şi m, iar pe a doua linie m numere naturale distincte, separate prin câte un spaţiu, reprezentând elementele mulţimii.<br />
<br />
==Date de ieşire==<br />
Fişierul de ieşire partitiinumar4.out va conţine pe pe fiecare linie câte un şir de numere naturale din mulţimea dată, ordonate crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este n. Şirurile vor fi afişate în ordine lexicografică.<br />
<br />
==Restricţii şi precizări==<br />
1 ≤ m < n ≤ 40<br />
numerele de pe a doua linie a fişierului de intrare sunt mai mici decât n<br />
==Exemplu==:<br />
partitiinumar4.in<br />
<br />
10 3<br />
3 2 6<br />
partitiinumar4.out<br />
<br />
2 2 2 2 2 <br />
2 2 3 3 <br />
2 2 6 <br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def partitii(n, m, set_nums, current, start):<br />
<br />
if n == 0:<br />
print(" ".join(map(str, current)))<br />
return<br />
for i in range(start, m):<br />
if set_nums[i] <= n:<br />
partitii(n - set_nums[i], m, set_nums, current + [set_nums[i]], i)<br />
<br />
if __name__ == "__main__":<br />
<br />
try:<br />
n, m = map(int, input("Introduceti n și m: ").split())<br />
set_nums = list(map(int, input("Introduceti elementele multimii: ").split()))<br />
<br />
set_nums.sort() # Sortăm mulțimea pentru a respecta ordinea lexicografică<br />
partitii(n, m, set_nums, [], 0)<br />
except ValueError:<br />
print("Introduceti valori numerice valide.")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=1322_-_Partitii_Nr&diff=94111322 - Partitii Nr2024-01-11T18:11:44Z<p>Mraa: </p>
<hr />
<div>==Cerinţa==<br />
Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale ordonate crescător astfel încât diferența dintre doi termeni consecutivi ai sumei să fie cel puțin 2.<br />
<br />
==Date de intrare==<br />
Fişierul de intrare partitiinr.in conţine pe prima linie numărul n.<br />
<br />
==Date de ieşire==<br />
Fişierul de ieşire partitiinr.out va conţine pe pe fiecare linie câte un şir de numere naturale ordonate crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este n, iar diferența dintre oricare doi termeni consecutivi este cel puțin 2. Şirurile vor fi afişate în ordine lexicografică.<br />
<br />
==Restricţii şi precizări==<br />
1 ≤ n ≤ 100<br />
==Exemplu==:<br />
partitiinr.in<br />
<br />
15<br />
partitiinr.out<br />
<br />
1 3 11 <br />
1 4 10 <br />
1 5 9 <br />
1 6 8 <br />
1 14 <br />
2 4 9 <br />
2 5 8 <br />
2 13 <br />
3 5 7 <br />
3 12 <br />
4 11 <br />
5 10 <br />
6 9 <br />
15 <br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def partitii(n, current, start):<br />
<br />
if n == 0:<br />
print(" ".join(map(str, current)))<br />
return<br />
for i in range(start, n + 1):<br />
partitii(n - i, current + [i], i + 2)<br />
<br />
if __name__ == "__main__":<br />
<br />
try:<br />
n = int(input("Introduceti valoarea lui n: "))<br />
partitii(n, [], 1)<br />
except ValueError:<br />
print("Introduceti un numar natural valid.")<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3604_-_Sum_Cifs&diff=94103604 - Sum Cifs2024-01-11T18:11:01Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Dându-se un număr natural nenul S, să se afișeze în ordine crescătoare toate numerele naturale cu cifre distincte care au suma cifrelor egală cu S.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul S.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran pe câte o linie și în ordine crescătoare numerele de cifre distincte care au suma cifrelor egală cu S. Dacă problema nu are nicio soluție, atunci se va afișa doar valoarea -1.<br />
<br />
==Restricții și precizări==<br />
1 ≤ S ≤ 44<br />
==Exemplu==:<br />
Intrare<br />
<br />
4<br />
Ieșire<br />
<br />
4<br />
13<br />
31<br />
40<br />
103<br />
130<br />
301<br />
310<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def cifre_distincte(numar):<br />
<br />
return len(set(str(numar))) == len(str(numar))<br />
<br />
def genereaza_permutari(cifre, suma_dorita, permutare_curenta=[]):<br />
<br />
if sum(permutare_curenta) == suma_dorita:<br />
numar = int("".join(map(str, permutare_curenta)))<br />
if cifre_distincte(numar):<br />
print(numar)<br />
elif sum(permutare_curenta) < suma_dorita:<br />
for cifra in cifre:<br />
genereaza_permutari(cifre, suma_dorita, permutare_curenta + [cifra])<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citirea sumei dorite<br />
S = int(input())<br />
# Cifrele disponibile pentru permutare<br />
cifre = list(range(1, 10))<br />
# Generarea și afișarea permutărilor<br />
genereaza_permutari(cifre, S)<br />
# Afisarea -1 daca nu exista solutie<br />
if cifre_distincte(S):<br />
print(-1)<br />
<br />
python sum_cifre_distincte.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3170_-_Plata_3&diff=94093170 - Plata 32024-01-11T18:10:12Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile, știind că se pot folosi oricâte bancnote de orice tip.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numerele n și S, apoi valorile v[1] v[2] ... v[n] ale bancnotelor.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran n numere, reprezentând o modalitate de plată a sumei S. Fiecare număr x[i] va reprezenta numărul de bancnote de valoarea x[i] folosite pentru plata sumei S.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 6<br />
1 ≤ S ≤ 1000<br />
1 ≤ v[i] ≤ 100<br />
oricare variantă corectă de plată a sumei S va fi luată în considerare<br />
pentru toate seturile de date există soluție<br />
==Exemplu==:<br />
Intrare<br />
<br />
5 375<br />
1 5 10 50 100<br />
Ieșire<br />
<br />
5 2 1 1 3 <br />
==Observații==<br />
Există și alte soluții valide.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def plata_bancnote(n, S, valori):<br />
<br />
rezultat = [0] * n<br />
suma_ramasa = S<br />
for i in range(n - 1, -1, -1):<br />
bancnote_folosite = suma_ramasa // valori[i]<br />
rezultat[i] = bancnote_folosite<br />
suma_ramasa -= bancnote_folosite * valori[i]<br />
return rezultat<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citire date de intrare<br />
n, S = map(int, input().split())<br />
valori = list(map(int, input().split()))<br />
# Calcul și afișare rezultat<br />
rezultat = plata_bancnote(n, S, valori)<br />
print(*rezultat)<br />
<br />
python plata_bancnote_flexibil.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3169_-_Plata_2&diff=94083169 - Plata 22024-01-11T18:09:29Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Pentru fiecare tip de bancnote se știe numărul de bancnote disponibile c[1] c[2] ... c[n]. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile, astfel încât să se folosească cel puțin o bancnotă de fiecare tip.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numerele n și S, apoi valorile v[1] v[2] ... v[n] ale bancnotelor și apoi c[1] c[2] ... c[n].<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran n numere, reprezentând o modalitate de plată a sumei S. Fiecare număr x[i] va reprezenta numărul de bancnote de valoarea x[i] folosite pentru plata sumei S.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 6<br />
1 ≤ S ≤ 1000<br />
1 ≤ v[i] ≤ 100<br />
1 ≤ c[i] ≤ 10<br />
oricare variantă corectă de plată a sumei S va fi luată în considerare<br />
pentru toate seturile de date există soluție<br />
==Exemplu==:<br />
Intrare<br />
<br />
5 375<br />
1 5 10 50 100<br />
6 3 4 6 1<br />
Ieșire<br />
<br />
5 2 1 5 1 <br />
==Explicație==<br />
Se folosesc cinci bancnote de 1 leu, două de 5 lei, una de 10 lei, cinci de 50 de lei și una de 100 de lei: 5 * 1 + 2 * 10 + 5 * 50 + 1 * 100 = 375.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def plata_bancnote(n, S, valori, cantitati):<br />
<br />
rezultat = [0] * n<br />
suma_ramasa = S<br />
for i in range(n - 1, -1, -1):<br />
bancnote_folosite = min(suma_ramasa // valori[i], cantitati[i])<br />
rezultat[i] = bancnote_folosite<br />
suma_ramasa -= bancnote_folosite * valori[i]<br />
return rezultat<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citire date de intrare<br />
n, S = map(int, input().split())<br />
valori = list(map(int, input().split()))<br />
cantitati = list(map(int, input().split()))<br />
# Calcul și afișare rezultat<br />
rezultat = plata_bancnote(n, S, valori, cantitati)<br />
print(*rezultat)<br />
<br />
python plata_bancnote.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3197_-_Partitii_Nr_2&diff=94073197 - Partitii Nr 22024-01-11T18:08:49Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale ordonate strict crescător astfel încât diferența dintre doi termeni consecutivi ai sumei să fie cel mult 2.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul n.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran pe fiecare linie câte un șir de numere naturale ordonate strict crescător, separate prin câte un spațiu. Suma numerelor din fiecare șir este n, iar diferența dintre oricare doi termeni consecutivi este cel mult 2. Șirurile vor fi afișate în ordine lexicografică.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 300<br />
==Exemplu==:<br />
Intrare<br />
<br />
21<br />
Ieșire<br />
<br />
1 2 3 4 5 6 <br />
1 2 4 6 8 <br />
1 3 4 6 7 <br />
2 3 4 5 7 <br />
3 4 6 8 <br />
3 5 6 7 <br />
5 7 9 <br />
6 7 8 <br />
10 11 <br />
21 <br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def partitii(n):<br />
<br />
def backtracking(curent, suma, start):<br />
if suma == n:<br />
solutii.append(list(curent))<br />
return<br />
for i in range(start, n - suma + 1):<br />
if len(curent) == 0 or abs(curent[-1] - i) <= 2:<br />
curent.append(i)<br />
backtracking(curent, suma + i, i + 1)<br />
curent.pop()<br />
solutii = []<br />
backtracking([], 0, 1)<br />
return solutii<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n = int(input())<br />
# Calculăm și afișăm rezultatul<br />
rezultat = partitii(n)<br />
for solutie in rezultat:<br />
print(*solutie)<br />
<br />
python partitiinumar2.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=0321_-_Partitii_Numar_1&diff=94060321 - Partitii Numar 12024-01-11T18:08:02Z<p>Mraa: </p>
<hr />
<div>==Cerinţa==<br />
Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale distincte.<br />
<br />
==Date de intrare==<br />
Fişierul de intrare partitiinumar1.in conţine pe prima linie numărul n.<br />
<br />
==Date de ieşire==<br />
Fişierul de ieşire partitiinumar1.out va conţine pe pe fiecare linie câte un şir de numere naturale ordonate strict crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este n. Şirurile vor fi afişate în ordine lexicografică.<br />
<br />
==Restricţii şi precizări==<br />
1 ≤ n ≤ 40<br />
==Exemplu==:<br />
partitiinumar1.in<br />
<br />
10<br />
partitiinumar1.out<br />
<br />
1 2 3 4 <br />
1 2 7 <br />
1 3 6 <br />
1 4 5 <br />
1 9 <br />
2 3 5 <br />
2 8 <br />
3 7 <br />
4 6 <br />
10 <br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def partitii(n):<br />
<br />
def backtracking(curent, suma, start):<br />
if suma == n:<br />
solutii.append(list(curent))<br />
return<br />
for i in range(start, n - suma + 1):<br />
curent.append(i)<br />
backtracking(curent, suma + i, i + 1)<br />
curent.pop()<br />
solutii = []<br />
backtracking([], 0, 1)<br />
return solutii<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n = int(input())<br />
# Calculăm și afișăm rezultatul<br />
rezultat = partitii(n)<br />
for solutie in rezultat:<br />
print(*solutie)<br />
<br />
python partitiinumar1.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=4036_-_KDivnn&diff=94054036 - KDivnn2024-01-11T18:07:19Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se dau n şi k numere naturale nenule. Determinaţi cel mai mare număr natural de cel mult k cifre care divide pe nn.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numerele n şi k.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran numărul cerut.<br />
<br />
==Restricții și precizări==<br />
2 ≤ n ≤ 10.000.000<br />
1 ≤ k ≤ 12<br />
==Exemplu==:<br />
Intrare<br />
<br />
6 3<br />
Ieșire<br />
<br />
972<br />
==Explicație==<br />
Cel mai mare număr de trei cifre care divide pe 66 este 972.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def cel_mai_mare_divizor_nn(n, k):<br />
<br />
# Inițializăm cel mai mare număr cu k cifre<br />
cel_mai_mare_numar = 10**k - 1<br />
# Cautăm cel mai mare număr care să fie divizibil cu nn<br />
while cel_mai_mare_numar >= 0:<br />
if cel_mai_mare_numar % (n * n) == 0:<br />
return cel_mai_mare_numar<br />
cel_mai_mare_numar -= 1<br />
return -1 # Dacă nu găsim un astfel de număr, returnăm -1<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n, k = map(int, input().split())<br />
# Apelăm funcția și afișăm rezultatul<br />
rezultat = cel_mai_mare_divizor_nn(n, k)<br />
print(rezultat)<br />
<br />
python divizor_nn.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3995_-_Partitii_Numar_6&diff=94043995 - Partitii Numar 62024-01-11T18:06:29Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale impare distincte.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul natural n.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe câte linie a ecranului câte un șir de numere naturale impare ordonate strict crescător, separate prin câte un spațiu. Suma numerelor din fiecare șir este n. Șirurile vor fi afișate în ordine lexicografică.<br />
<br />
Dacă nu există nicio modalitate de a-l scrie pe n ca sumă de numere naturale impare distincte se va afișa mesajul imposibil.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 40<br />
==Exemplu==:<br />
Intrare<br />
<br />
16<br />
Ieșire<br />
<br />
1 3 5 7 <br />
1 15 <br />
3 13 <br />
5 11 <br />
7 9 <br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def generare_siruri(n, suma_curenta, sir_parcial, ultimul_numar):<br />
<br />
# Verificăm dacă am atins suma dorită<br />
if suma_curenta == n:<br />
print(*sir_parcial)<br />
return<br />
elif suma_curenta > n:<br />
return<br />
# Generăm numere impare și continuăm recursiv<br />
for i in range(ultimul_numar + 2, n + 1, 2):<br />
generare_siruri(n, suma_curenta + i, sir_parcial + [i], i)<br />
<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n = int(input())<br />
# Apelăm funcția pentru a afișa șirurile<br />
generare_siruri(n, 0, [], 0)<br />
# Verificăm dacă nu există nicio modalitate de a-l scrie pe n ca sumă de numere naturale impare distincte<br />
if n % 2 == 0:<br />
print("imposibil")<br />
<br />
python sumaNImpareDistincte.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3994_-_Partitii_Numar_5&diff=94033994 - Partitii Numar 52024-01-11T18:05:50Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale pare.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numărul natural n.<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe câte linie a ecranului câte un șir de numere naturale pare ordonate crescător, separate prin câte un spațiu. Suma numerelor din fiecare șir este n. Șirurile vor fi afișate în ordine lexicografică.<br />
<br />
Dacă nu există nicio modalitate de a-l scrie pe n ca sumă de numere naturale pare se va afișa mesajul imposibil.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 40<br />
==Exemplu==:<br />
Intrare<br />
<br />
10<br />
Ieșire<br />
2 2 2 2 2 <br />
2 2 2 4 <br />
2 2 6 <br />
2 4 4 <br />
2 8 <br />
4 6 <br />
10<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def generare_siruri(n, suma_curenta, sir_parcial):<br />
<br />
# Verificăm dacă am atins suma dorită<br />
if suma_curenta == n:<br />
print(*sir_parcial)<br />
return<br />
elif suma_curenta > n:<br />
return<br />
# Generăm numere pare și continuăm recursiv<br />
for i in range(2, n + 1, 2):<br />
generare_siruri(n, suma_curenta + i, sir_parcial + [i])<br />
<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n = int(input())<br />
# Apelăm funcția pentru a afișa șirurile<br />
generare_siruri(n, 0, [])<br />
# Verificăm dacă nu există nicio modalitate de a-l scrie pe n ca sumă de numere naturale pare<br />
if n % 2 != 0:<br />
print("imposibil")<br />
<br />
python sumaNNumerePare.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=2245_-_Plata_1&diff=94022245 - Plata 12024-01-11T18:05:08Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Pentru fiecare tip de bancnote se știe numărul de bancnote disponibile c[1] c[2] ... c[n]. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile.<br />
<br />
==Date de intrare==<br />
Programul citește de la tastatură numerele n și S, apoi valorile v[1] v[2] ... v[n] ale bancnotelor și apoi c[1] c[2] ... c[n].<br />
<br />
==Date de ieșire==<br />
Programul va afișa pe ecran n numere, reprezentând o modalitate de plată a sumei S. Fiecare număr x[i] va reprezenta numărul de bancnote de valoarea x[i] folosite pentru plata sumei S.<br />
<br />
==Restricții și precizări==<br />
1 ≤ n ≤ 6<br />
1 ≤ S ≤ 1000<br />
1 ≤ v[i] ≤ 100<br />
1 ≤ c[i] ≤ 10<br />
oricare variantă corectă de plată a sumei S va fi luată în considerare<br />
pentru toate seturile de date există soluție<br />
==Exemplu==:<br />
Intrare<br />
<br />
5 375<br />
1 5 10 50 100<br />
6 3 4 6 1<br />
Ieșire<br />
<br />
5 0 2 5 1<br />
==Explicație==<br />
Se folosesc cinci bancnote de 1 leu, două de 10 lei, cinci de 50 de lei și una de 100 de lei: 5 * 1 + 2 * 10 + 5 * 50 + 1 * 100 = 375.<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def plata_bancnote(n, S, valori, cantitati):<br />
<br />
rezultat = [0] * n<br />
suma_actuala = 0<br />
for i in range(n - 1, -1, -1):<br />
while suma_actuala + valori[i] <= S and cantitati[i] > 0:<br />
suma_actuala += valori[i]<br />
cantitati[i] -= 1<br />
rezultat[i] += 1<br />
return rezultat<br />
<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n, S = map(int, input().split())<br />
valori = list(map(int, input().split()))<br />
cantitati = list(map(int, input().split()))<br />
# Apelăm funcția pentru a obține rezultatul<br />
rezultat = plata_bancnote(n, S, valori, cantitati)<br />
# Afișăm rezultatul<br />
print(*rezultat)<br />
<br />
python plata_bancnote.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=1356_-_N_Sir&diff=94011356 - N Sir2024-01-11T18:03:07Z<p>Mraa: </p>
<hr />
<div>==Cerința==<br />
Fie n un număr natural.<br />
Să se determine toate șirurile a de k numere naturale nu neapărat distincte: 1 ≤ a1, a2,...,ak ≤ n, astfel încât:<br />
1) 1 = 1/a1+ 1/a2+...+ 1/ak<br />
2) n = a1 + a2 +...+ ak<br />
<br />
==Date de intrare==<br />
Fișierul de intrare nsir.in conține pe prima linie numărul n.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire nsir.out va conține pe fiecare linie câte un șir determinat, în ordine lexicografică. Dacă nu poate fi generat un astfel de șir, atunci se va scrie valoarea 0 pe prima linie a fișierului de ieșire.<br />
<br />
==Restricții și precizări==<br />
5 ≤ n ≤ 75<br />
se admite că cerința 1) este satisfăcută dacă: | 1/a1 + 1/a2 + … + 1/ak – 1 |<10-5<br />
==Exemplu==:<br />
nsir.in<br />
<br />
33<br />
nsir.out<br />
<br />
3 3 9 9 9<br />
3 5 5 5 15<br />
==Explicație==<br />
Se observă că<br />
1) 1 = 1/3+1/3+1/9+1/9+1/9 și 33 = 3+3+9+9+9<br />
2) 1 = 1/3+1/5+1/5+1/5+1/15 și 33 = 3+5+5+5+15<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def backtracking(n, k, target_sum, current_sum, current_sequence, result):<br />
<br />
if k == 0:<br />
if current_sum == target_sum:<br />
result.append(list(current_sequence))<br />
return<br />
for i in range(1, min(n, target_sum - current_sum) + 1):<br />
current_sequence.append(i)<br />
backtracking(n, k - 1, target_sum, current_sum + i, current_sequence, result)<br />
current_sequence.pop()<br />
<br />
<br />
def find_sequences(n):<br />
<br />
result = []<br />
for k in range(2, n + 1):<br />
backtracking(n, k, n, 0, [], result)<br />
return result<br />
<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim numărul n din fișierul de intrare<br />
with open("nsir.in", "r") as f:<br />
n = int(f.readline().strip())<br />
# Găsim și afișăm șirurile în fișierul de ieșire<br />
sequences = find_sequences(n)<br />
with open("nsir.out", "w") as g:<br />
if not sequences:<br />
g.write("0\n")<br />
else:<br />
for sequence in sequences:<br />
g.write(" ".join(map(str, sequence)) + "\n")<br />
<br />
python nsir.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=0323_-_Partitii_Numar_3&diff=94000323 - Partitii Numar 32024-01-11T17:47:11Z<p>Mraa: </p>
<hr />
<div>==Cerinţa==<br />
Se dă un număr natural n şi un interval [a,b]. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale din intervalul [a,b].<br />
<br />
==Date de intrare==<br />
Fişierul de intrare partitiinumar3.in conţine pe prima linie numerele n, a şi b.<br />
<br />
==Date de ieşire==<br />
Fişierul de ieşire partitiinumar3.out va conţine pe pe fiecare linie câte un şir de numere naturale din intervalul [a,b], ordonate crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este n. Şirurile vor fi afişate în ordine lexicografică.<br />
<br />
==Restricţii şi precizări==<br />
1 ≤ a < b < n ≤ 40<br />
==Exemplu==:<br />
partitiinumar3.in<br />
<br />
10 2 4<br />
partitiinumar3.out<br />
<br />
2 2 2 2 2 <br />
2 2 2 4 <br />
2 2 3 3 <br />
2 4 4 <br />
3 3 4 <br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def partitii_n(n, a, b, solutie):<br />
<br />
if n == 0:<br />
print(" ".join(map(str, solutie)))<br />
return<br />
for i in range(a, min(b + 1, n + 1)):<br />
partitii_n(n - i, i, b, solutie + [i])<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim numerele n, a și b din fișierul de intrare<br />
with open("partitiinumar3.in", "r") as f:<br />
n, a, b = map(int, f.readline().split())<br />
# Apelăm funcția de partizionare și afișăm rezultatul în fișierul de ieșire<br />
with open("partitiinumar3.out", "w") as g:<br />
partitii_n(n, a, b, [])<br />
<br />
python partitiinumar3.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=0319_-_Suma_35&diff=93990319 - Suma 352024-01-11T17:46:27Z<p>Mraa: </p>
<hr />
<div>==Cerinţa==<br />
Se dă un număr natural nenul n. Să se determine toate modalităţile distincte de descompunere a numărului n în sumă de 3 şi 5.<br />
<br />
==Date de intrare==<br />
Fişierul de intrare suma35.in conţine pe prima linie numărul n.<br />
<br />
==Date de ieşire==<br />
Fişierul de ieşire suma35.out va conţine, în ordine lexicografică, toate modalităţile de descompunere a lui n în suma de 3 şi 5. Elementele fiecărei descompuneri vor fi scrie pe câte o linie a fişierului şi separate printr-un spaţiu.<br />
<br />
==Restricţii şi precizări==<br />
1 ≤ n ≤ 1000<br />
pentru fiecare dintre valorile lui n folosite în fişierele de test există cel puţin o soluţie<br />
în fiecare descompunere elementele vor fi aranjate crescător<br />
==Exemplu==:<br />
suma35.in<br />
<br />
40<br />
suma35.out<br />
<br />
3 3 3 3 3 3 3 3 3 3 5 5 <br />
3 3 3 3 3 5 5 5 5 5 <br />
5 5 5 5 5 5 5 5 <br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
def descompunere_35(n, solutie):<br />
<br />
if n == 0:<br />
print(" ".join(map(str, solutie)))<br />
return<br />
if n >= 3:<br />
descompunere_35(n - 3, solutie + [3])<br />
if n >= 5:<br />
descompunere_35(n - 5, solutie + [5])<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim numărul n din fișierul de intrare<br />
with open("suma35.in", "r") as f:<br />
n = int(f.readline().strip())<br />
# Apelăm funcția de descompunere și afișăm rezultatul în fișierul de ieșire<br />
with open("suma35.out", "w") as g:<br />
descompunere_35(n, [])<br />
<br />
python suma35.py<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=3982_-_Descp2&diff=93983982 - Descp22024-01-11T17:45:24Z<p>Mraa: /* Rezolvare */</p>
<hr />
<div>Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x.<br />
<br />
==Cerința==<br />
Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare kx_desc.in conține pe prima linie trei valori naturale nenule reprezentând numerele n, k şi x.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire kx_desc.out va conține o singură valoare reprezentând restul împărţirii numărului de kx-descompuneri distincte la numărul 10007.<br />
<br />
==Restricții și precizări==<br />
Pentru 20% din teste 0 < n ≤ 200; pentru celelalte 80% din teste, 200 < n ≤ 10000;<br />
1 ≤ x, k ≤ n<br />
==Exemplul 1==:<br />
kx_desc.in<br />
<br />
20 2 3<br />
kx_desc.out<br />
<br />
8<br />
==Explicație==<br />
Numărul de kx-descompuneri în acest caz este 8. Acestea sunt formate din numerele 1 şi 19; 2 şi 18; 3 şi 17; 4 şi 16; 5 şi 15; 6 şi 14; 7 şi 13; 8 şi 12.<br />
<br />
==Exemplul 2==:<br />
kx_desc.in<br />
<br />
2000 19 7<br />
kx_desc.out<br />
<br />
3184<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3"><br />
MOD = 10007<br />
<br />
def kx_descompuneri(n, k, x):<br />
<br />
dp = [[0] * (x + 1) for _ in range(n + 1)]<br />
dp[0][0] = 1<br />
for i in range(1, n + 1):<br />
for j in range(1, min(i, k) + 1):<br />
for l in range(x + 1):<br />
dp[i][l] = (dp[i][l] + dp[i - j][l - 1]) % MOD<br />
rezultat = 0<br />
for i in range(n - k * x + 1, n + 1):<br />
rezultat = (rezultat + dp[i][x]) % MOD<br />
return rezultat<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n, k, x = map(int, input().split())<br />
# Calculăm rezultatul și îl afișăm<br />
rezultat = kx_descompuneri(n, k, x)<br />
print(rezultat)<br />
python kx_desc.py < kx_desc.in<br />
</syntaxhighlight></div>Mraahttps://wiki.universitas.ro/index.php?title=4284_-_Kx_Desc&diff=93974284 - Kx Desc2024-01-11T17:43:48Z<p>Mraa: </p>
<hr />
<div>Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x.<br />
<br />
==Cerința==<br />
Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.<br />
<br />
==Date de intrare==<br />
Fișierul de intrare kx_desc.in conține pe prima linie trei valori naturale nenule reprezentând numerele n, k şi x.<br />
<br />
==Date de ieșire==<br />
Fișierul de ieșire kx_desc.out va conține o singură valoare reprezentând restul împărţirii numărului de kx-descompuneri distincte la numărul 10007.<br />
<br />
==Restricții și precizări==<br />
Pentru 20% din teste 0 < n ≤ 200; pentru celelalte 80% din teste, 200 < n ≤ 10000;<br />
1 ≤ x, k ≤ n<br />
==Exemplul 1==:<br />
kx_desc.in<br />
<br />
20 2 3<br />
kx_desc.out<br />
<br />
8<br />
==Explicație==<br />
Numărul de kx-descompuneri în acest caz este 8. Acestea sunt formate din numerele 1 şi 19; 2 şi 18; 3 şi 17; 4 şi 16; 5 şi 15; 6 şi 14; 7 şi 13; 8 şi 12.<br />
<br />
==Exemplul 2==:<br />
kx_desc.in<br />
<br />
2000 19 7<br />
kx_desc.out<br />
<br />
3184<br />
==Rezolvare==<br />
<syntaxhighlight lang="python3" line="1"><br />
MOD = 10007<br />
<br />
def kx_descompuneri(n, k, x):<br />
<br />
dp = [[0] * (x + 1) for _ in range(n + 1)]<br />
for i in range(x + 1):<br />
dp[i][i] = 1<br />
for i in range(x + 1, n + 1):<br />
for j in range(1, x + 1):<br />
dp[i][j] = (dp[i - 1][j - 1] + dp[i - x - 1][j]) % MOD<br />
rezultat = 0<br />
for i in range(n - x + 1, n + 1):<br />
rezultat = (rezultat + dp[i][x]) % MOD<br />
return rezultat<br />
<br />
if __name__ == "__main__":<br />
<br />
# Citim datele de intrare<br />
n, k, x = map(int, input().split())<br />
# Calculăm rezultatul și îl afișăm<br />
rezultat = kx_descompuneri(n, k, x)<br />
print(rezultat)<br />
<br />
<br />
</syntaxhighlight></div>Mraa