Editing 1022 - Fractii 2

== 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>