RebecaBud: Pagină nouă: == Enunt == Numărul 1 poate fi scris în diverse moduri ca sumă de fracţii cu numărătorul 1 şi numitorul o putere a lui 2. De exemplu: '''1 = 1/2 + 1/2 = 1/2 + 1/4 + 1/8 + 1/8 = 1/8 + 1/4 + 1/2 + 1/8''' Două scrieri nu sunt considerate distincte dacă folosesc aceleaşi fracţii scrise în altă ordine. În exemplul de mai sus ultimele două scrieri nu sunt distincte. == Cerinţa == Pentru N – număr natural nenul să se determine: a) O modalitate de scriere a num...

2024-06-03T16:57:49Z

Pagină nouă: == Enunt == Numărul 1 poate fi scris în diverse moduri ca sumă de fracţii cu numărătorul 1 şi numitorul o putere a lui 2. De exemplu: '''1 = 1/2 + 1/2 = 1/2 + 1/4 + 1/8 + 1/8 = 1/8 + 1/4 + 1/2 + 1/8''' Două scrieri nu sunt considerate distincte dacă folosesc aceleaşi fracţii scrise în altă ordine. În exemplul de mai sus ultimele două scrieri nu sunt distincte. == Cerinţa == Pentru N – număr natural nenul să se determine: a) O modalitate de scriere a num...

New page

== Enunt ==
Numărul 1 poate fi scris în diverse moduri ca sumă de fracţii cu numărătorul 1 şi numitorul o putere a lui 2. De exemplu:

'''1 = 1/2 + 1/2 = 1/2 + 1/4 + 1/8 + 1/8 = 1/8 + 1/4 + 1/2 + 1/8'''

Două scrieri nu sunt considerate distincte dacă folosesc aceleaşi fracţii scrise în altă ordine. În exemplul de mai sus ultimele două scrieri nu sunt distincte.
== Cerinţa ==
Pentru N – număr natural nenul să se determine:
a) O modalitate de scriere a numărului 1 ca sumă de exact N fracţii cu numărătorul 1 şi numitorul o putere a lui 2.
b) Numărul de scrieri distincte a numărului 1 ca sumă de exact N fracţii cu numărătorul 1 şi numitorul o putere a lui 2. Deoarece acest număr poate fi foarte mare acest număr trebuie calculat modulo 100003.
== Date de intrare ==
Fişierul de intrare fractii2.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
Pe a doua linie se găseşte un singur număr N natural – reprezentând numărul de fracţii
== Date de ieșire ==
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerinţă. În acest caz, în fişierul de ieşire fractii2.out se vor scrie, pe o singură linie, N numere naturale separate prin câte un spaţiu reprezentând cei N exponenţi ai lui 2 din scrierea solicitată în prima cerinţă. Astfel, dacă numerele afişate sunt m1,m2,…,mn
atunci există scrierea 1=12m1+12m2+…+12mn
.
Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerinţă. În acest caz, în fişierul de ieşire fractii2.out se va scrie un număr natural reprezentând răspunsul la a doua cerinţă, adică numărul de scrieri distincte a numărului 1 ca sumă de N fracţii cu numărătorul 1 şi numitorul o putere a lui 2 (modulo 100003).

Restricţii
== Restricţii şi precizări ==
* '''2 ≤ N ≤ 2000'''
* Pentru prima cerinţă se acordă 20% din punctaj.
* Pentru a doua cerinţă de acordă 80% din punctaj.
* Rezultatul pentru a doua cerinţă trebuie afişat modulo 100003
== Exemplul 1 ==
; fractii2.in

1
4
; fractii2.out

2 2 2 2
<br>

== Exemplul 2 ==
; fractii2.in

2
4
; fractii2.out

2
== Explicaţie ==
Primul exemplu:

1 = 1/2 + 1/4 + 1/8 + 1/8 = 1/4 + 1/4 + 1/4 + 1/4
Răspunsul corespunde celei de-a doua scrieri dar există şi alte variante corecte de răspuns. De exemplu, 3 1 2 3 se consideră răspuns corect.
Atenţie! Pentru acest test se va afişa doar rezultatul la cerinţa a).

Al doilea exemplu:

1 = 1/2 + 1/4 + 1/8 + 1/8 = 1/4 + 1/4 + 1/4 + 1/4

Acestea sunt singurele scrieri distincte.
Atenţie! Pentru acest test se va afişa doar rezultatul la cerinţa b).
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def write_fractions(N):
exponents = [1] * N
return exponents

def count_distinct_writings(N):
MOD = 100003
if N == 2:
return 1

dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N):
for j in range(i, N + 1):
dp[j] = (dp[j] + dp[j - i]) % MOD

return dp[N]

def main():
with open("fractii2.in", "r") as fin:
p = int(fin.readline())
N = int(fin.readline())

if p == 1:
with open("fractii2.out", "w") as fout:
exponents = write_fractions(N)
fout.write(" ".join(map(str, exponents)))
elif p == 2:
with open("fractii2.out", "w") as fout:
distinct_writings = count_distinct_writings(N)
fout.write(str(distinct_writings % 100003))

if __name__ == "__main__":
main()

</syntaxhighlight>

1022 - Fractii 2 - Revision history