Page 16 - MATINF Nr. 1

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

Pe linia a doua se afl˘a N, M, separate printr-un spat , iu, iar pe linia urm˘atoare numerele
x 1 , x 2 , . . . , x M separate prin cˆate un spat , iu.

Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire cuburi.out se va scrie un num˘ar ce reprezint˘a num˘arul
maxim de cuburi pe care le poate pune ˆın [M/2] cutii.

Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.

ˆ
In acest caz, ˆın fis , ierul de ies , ire cuburi.out se va scrie num˘arul de moduri diferite ˆın care
se pot as , eza cuburile ˆın cutii. Num˘arul va fi afis , at modulo 60013.

Restrict , ii s , i preciz˘ari

• 1≤N≤1000

• 1≤M≤1000

• 0≤x 1 + x 2 + ... + x M ≤N

• x modulo y reprezint˘a restul ˆımp˘art , irii lui x la y

• Pentru rezolvarea corect˘a a fiec˘arei cerint , e se acord˘a 50% din punctaj

Exemple
cuburi.in cuburi.out Explicat , ie
1 2 p = 1
4 2 Cutia cea mai mare cont , ine 2 cu-
1 2 buri.
cuburi.in cuburi.out Explicat , ie
2 12 p = 2
4 2 La cerint , a 2 num˘arul de modalit˘at , i
1 2 de as , ezare a cuburilor este 12.

Timp maxim de execut , ie: 0.2 secunde/test.
Memorie total˘a disponibil˘a 8 MB, din care 2 MB pentru stiv˘a.

Doru Anastasiu Popescu, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti

Solut , ie

Cerint , a 1
Se ordoneaz˘a descresc˘ator vectorul x s , i se calculeaz˘a s = x 1 + x 2 + ... + x [M/2] . Apoi se
afis , eaz˘a s.

Cerint , a 2

Num˘arul c˘autat este C(N, x 1 ) · C(N − x 1 , x 2 ) · . . . · C(N − (x 1 + ... + x M−1 ), x M ) modulo
60013. Combin˘arile din produs se calculeaz˘a folosind triunghiul lui Pascal modulo 60013.