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

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).

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>