Fișierul intrare/ieșire | fractii2.in, fractii2.out | Sursă | OJI 2014, clasele 11-12 |
---|---|---|---|
Autor | Adrian Panaete | Adăugată de | Alexandru Valeanu • AlexandruValeanu |
Timp de execuție pe test | 0.25 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Fracții2 (clasele 11-12)
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:
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ță
Pentru N – număr natural nenul să se determine:
- 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.
- 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ță.
- 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
- 1 ≤ N ≤ 5000
- Rezultatul pentru a doua cerință trebuie afișat modulo 100003
Exemple
fractii2.in | fractii2.out |
---|---|
1 4 |
2 2 2 2 |
2 4 |
2 |