Page 11 - MATINF Nr. 13-14

Concursul de Informatic˘ Programming Day 11
a

Solut , ie

Cerint , a 1 ( 20 puncte)

Folosind Ciurul lui Eratostene se determin˘a ˆın vectorul x = (x[1], ..., x[k]) numerele prime
a
mai mici sau egale cu N, ˆın ordine cresc˘atoare. Se calculeaz˘ suma ultimelor [k/2] numere din
a
a
vectorul x s , i se afis , eaz˘ aceast˘ sum˘a.
Cerint , a 2 ( 80 puncte)

k
Num˘arul c˘autat este 2 − 1, modulo 7919, unde k este determinat la cerint , a 1.
Clasele a XI-a s , i a XII-a

Problema 1 - numarare

Ric˘ este elev ˆın clasa a XII-a s , i dores , te s˘ devin˘ student la informatic˘a. Pentru acest lucru
a
a
a
se preg˘ates , te s˘ dea bacalaureatul la informatic˘a. Recapitulˆand principalele not , iuni din teoria
a
grafurilor, a g˘asit dou˘a probleme de num˘arare. Pentru N dat, la prima problem˘a trebuie s˘a
determine num˘arul de grafuri neorientate cu N noduri ˆın care nodul 1 este terminal, iar la a
doua problem˘a trebuie s˘a determine num˘arul de arbori cu nodul 1 nod terminal, iar gradul
a
nodului 2 s˘ fie cel put , in 2. Nodurile grafurilor s , i arborilor sunt etichetate cu 1, 2, . . . , N.
Cerint , e
Cunoscˆand N, s˘a se determine:
1. num˘arul de grafuri neorientate cu N noduri ˆın care nodul 1 este terminal, modulo 7919;
2. num˘arul de arbori cu nodul 1 nod terminal, iar gradul nodului 2 este cel put , in 2, modulo
7919.

Date de intrare
Pe prima linie a fis , ierului de intrare numarare.in se g˘ases , te C, num˘arul cerint , ei (1 sau 2),
iar pe linia a doua N.

Date de ies , ire
Pe prima linie a fis , ierului de ies , ire numarare.out se va afis , a un singur num˘ar natural, ce
reprezint˘ r˘aspunsul corespunz˘ator cerint , ei ce trebuie rezolvat˘a.
a
Restrict , ii s , i preciz˘ari
1. 1 ≤ N ≤ 15000.
a
2. m modulo k reprezint˘ restul ˆımp˘art , irii lui m la k.
3. Pentru rezolvarea corect˘a a cerint , ei 1 se vor acorda 20 de puncte.
4. Pentru rezolvarea corect˘a a cerint , ei 2 se vor acorda 80 de puncte.

Exemplu

numarare.in numarare.out
1 4
3
2 5
4

Timp maxim de execut , ie: 1.4 secunde/test.
Memorie total˘ disponibil˘a: 4 MB.
a