Fişierul intrare/ieşire:points2.in, points2.outSursăConcurs Shumen juniori 2010
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Points 2 (clasele 8-9)

În cele din urmă Ivan a fost acceptat la universitate! După un an obositor de pregătire pentru examenele de intrare, s-a hotărît să-şi ia o vacanţă lungă. Din păcate vacanţa de vară a fost scurtă şi nu i-a ajuns pentru o odihnă adecvată, dar el nu s-a descurajat. Ivan a auzit că, la facultate, nu este obligatoriu să te duci la toate cursurile. Aşa că el a decis să-şi prelungească vacanţa, deşi anul şcolar începuse. Şi aşa a şi făcut!

Dar, desigur, există şi reversul medaliei - la fel ca şi la liceu, în orice universitate există examene. Mai exact, între materiile lui Ivan sînt exact N examene. Ele pot varia în dificultate, aşa încît două examene pot acorda număr diferit de puncte. Ivan nu e obligat să dea toate examenele, dar notele adunate la teste sînt importante, pentru că sînt parte din nota finală. El şi-a dat rapid seama că are nevoie de cel puţin T puncte din toate examenele, astfel încît în final să obţină o notă bună. El ştie sigur că poate să adune cel puţin T puncte din toate examenele, dar suspectează că s-ar putea să fie mai multe feluri de a le obţine. Cu cît mai multe feluri sînt, cu atît mai mult timp liber are - Ivan va putea să aleagă ce examen să dea şi ce nu. În acest fel el va avea mai multe opţiuni cum să-şi distribuie distracţiile - de exemplu la ce concerte să meargă, sau ce meciuri de fotbal. Ivan este complet sigur pe abilităţile sale, aşa încît dacă dă un examen, el ia scor maxim.

Cerinţă

Nu-l lăsaţi pe Ivan să se întrebe prea multă vreme în cîte feluri poate să adune cel puţin T puncte. Scrieţi un program care-i găseşte acest număr.

Date de intrare

Primul rînd al fişierului de intrare points2.in va conţine doi întregi pozitivi, N şi T. Pe rîndul următor se vor afla N întregi pozitivi despărţiţi de un singur spaţiu, care reprezintă punctele la fiecare examen.

Date de ieşire

În fişierul de ieşire points2.out veţi scrie un singur întreg - numărul de moduri în care Ivan poate să aleagă ce examene să dea şi care nu, astfel încît suma punctelor adunate să fie cel puţin T.

Restricţii

  • 1 ≤ N ≤ 36
  • punctele la examene sînt întregi pozitivi ≤ cu 1013
  • În 20% din teste numerele de pe rîndul doi al fişierului de intrare vor fi ≤ 1000.

Exemplu

points2.inpoints2.outExplicaţie
4 6
1 2 5 4
9
Sînt nouă feluri în care Ivan poate sa aleagă care examen să dea şi care nu,
astfel încît suma punctelor adunate să fie cel puţin 6: (primul şi al treilea),
(al doilea şi al treilea), (primul, al doilea şi al treilea), (al doilea şi al
patrulea), (primul, al doilea şi al patrulea), (primul, al treilea şi al patrulea),
(al doilea, al treilea şi al patrulea), (primul, al doilea, al treilea şi al patrulea),
(al treilea şi al patrulea).
8 90
1000 2 5 79 12
3 1 3
166
 
Trebuie sa te autentifici pentru a trimite solutii. Click aici