Page 10 - MATINF Nr. 13-14

10 D.A. Popescu, C. B˘alc˘au, D. Constantin

Solut , ie

Cerint , a 1 ( 20 puncte)

Num˘arul de echipe este egal cu num˘arul de submult , imi nevide ale unei mult , imi cu N
N
elemente, deci este 2 − 1.
Cerint , a 2 ( 80 puncte)

N
N
Num˘arul c˘autat este 4 − 3 N+1 + 3 · 2 − 1 (folosind Principul includerii s , i excluderii sau
numerele lui Stirling de spet ,a a doua). Acest num˘ar il calcul˘am modulo 7919.
Problema 2 - submultprime
Se d˘a un num˘ar natural N. Vom nota cu P mult , imea numerelor prime mai mici sau egale
cu N. Dorim s˘ determin˘am cea mai mare sum˘ a unei submult , imi cu [card(P)/2] elemente din
a
a
mult , imea P, precum s , i num˘arul de submult , imi nevide ale lui P, modulo 7919.
Cerint , e
a
Cunoscˆand N, se cere s˘ se determine:
1. cea mai mare sum˘a a unei submult , imi a lui P cu [card(P)/2] elemente;
2. num˘arul de submult , imi nevide ale lui P, modulo 7919.

Date de intrare
Pe primele dou˘a linii ale fis , ierului de intrare submultprime.in se g˘asesc dou˘a numere
naturale, C s , i respectiv N, reprezentˆand num˘arul cerint , ei ce se va rezolva (1 sau 2), respectiv
num˘arul din enunt , .
Date de ies , ire
Pe prima linie a fis , ierului de ies , ire submultprime.out se va afis , a un singur num˘ar natural,
corespunz˘ator rezolv˘arii cerint , ei C din fis , ierul de intrare.

Restrict , ii s , i preciz˘ari

1. 1 ≤ N ≤ 1000000.
2. Pentru o mult , ime M, card(M) reprezint˘ num˘arul de elemente ale lui M.
a
a
3. Pentru rezolvarea corect˘ 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

submultprime.in submultprime.out
1 12
10
2 15
10

Explicat , ii

Avem P = {2, 3, 5, 7}. Suma cea mai mare pentru o submult , ime cu dou˘a elemente este
5 + 7 = 12. Num˘arul de submult , imi nevide ale lui P este 15.
Timp maxim de execut , ie: 5 secunde/test.
Memorie total˘ disponibil˘a: 2 MB.
a