problema/fractii2

Fractii2

<de adaugat continut>

== include(page="template/taskheader" task_id="fractii2") ==
 
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:
 
<tex> 1 = \frac{1}{2} + \frac{1}{2} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} = \frac{1}{8} + \frac{1}{4} + \frac{1}{2} + \frac{1}{8} </tex>
 
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.
 
h2. Cerinţă
 
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$.
 
h2. 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.
 
h2. 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 <tex>m_1,m_2,..., m_N </tex>  atunci există scrierea  <tex>1= \frac {1}{2^(m_1)} + \frac{1}{2^(m_2)} +...+ \frac{1}{2^(m_N)}</tex>
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)$.
 
 
h2. Restricţii
 
* $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$
 
 
h2. Exemplu
 
table(example). |_. fractii2.in |_. fractii2.out |
| 1
4
| 2 2 2 2
|
| 2
4
| 2
|
 
h3. Explicaţie
 
Primul exemplu:
 
<tex> 1 = \frac{1}{2} + \frac{1}{4} + \frac {1}{8} + \frac{1}{8} = \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4}</tex>
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:
 
<tex> 1 = \frac{1}{2} + \frac{1}{4} + \frac {1}{8} + \frac{1}{8} = \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4}</tex>
 
Acestea sunt singurele scrieri distincte.
**Atenţie! Pentru acest test se va afişa doar rezultatul la cerinţa b).**
 
 
== include(page="template/taskfooter" task_id="fractii2") ==
 

public

task: fractii2

9948