.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » fractii2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
fractii2


Timp maxim de execuţie / test:
0.5s
Memorie totala disponibilă / stivă:
64MB / 16MB

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 un număr natural nenul N să se determine:
1. 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.
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 cerinţa 1. Î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



Dacă valoarea lui p este 2, se va rezolva numai cerinţa 2. Î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

2 ≤ N ≤ 2000

Exemple

fractii2.infractii2.outExplicaţii
1 4 2 2 2 2 p=1



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 1.
2 4 2 p=2



Acestea sunt singurele scrieri distincte.
Atenţie! Pentru acest test se va afişa doar rezultatul la cerinţa 2.

autor: Prof. Adrian Panaete
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la OJI 2014: arrows, tcif, imprimanta, munte3, ferma1, triunghi6, cartite, cool, pseudobil, martisoare, piramide, patrat1, schi1
De acelaşi autor: butoane, risipa, mofocarburi, cover1, codarb, trifoi, albine2, nkd, transform, 2sah
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor