# PBinfo #2062 – piese1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Ion este un tânăr muzician și studiază chitara clasică. La un spectacol în aer liber, Ion a fost invitat să interpreteze câteva dintre piesele sale.  Ion are în repertoriu n piese, a căror durată este t[1], t[2], …, t[n] și ştie că timpul care-i va fi alocat nu poate depăşi T unităţi de timp.  Pentru alegerea pieselor, Ion este interesat să ştie câte variante distincte are de a interpreta cel puţin o piesă în spectacol, astfel încât durata totală a pieselor interpretate să nu depăşească T. Două variante sunt distincte dacă există cel puţin o melodie care se găseşte într-o variantă şi nu se găseşte în cealaltă variantă.

Cerința
Cunoscând n, T și duratele pieselor, determinaţi numărul de variante distincte pe care le are Ion de a interpreta piese astfel încât durata lor să nu depăşească T.

Date de intrare
Fișierul de intrare piese1.in conține pe prima linie numerele n şi T având semnificaţia din enunţ. Pe linia a doua se găsesc n numere naturale t[1], t[2], …, t[n], separate printr-un singur spaţiu, reprezentând duratele pieselor din repertoriul lui Ion.

Date de ieșire
Fișierul de ieșire piese1.out va conţine pe o singură linie un număr natural ce reprezintă numărul de variante distincte pe care le are Ion de a interpreta piese din repertoriul său, astfel încât  durata lor să nu depăşească T.

Restricții și precizări

2 ≤ n ≤ 30
1 ≤ x1, x2, ..., xn, T ≤ 1 000 000 000
Ordinea de prezentare a pieselor în spectacol nu este relevantă.

Exemplul 1:
piese1.in

3 2
4 3 5
piese1.out

0
Explicație
Nu există nicio variantă. Toate piesele durează mai mult de T unități de timp.

Exemplul 2:
piese1.in

4 6
2 4 5 1
piese1.out

8
Explicație
Sunt 8 variante posibile: 2, 4, 5, 1, 2+4, 2+1, 4+1, 5+1.

## Cod sursă C++

```cpp
/* 
	prof. Constantin Galatan
	Complexitate O(2^(n/2))
*/
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream fin("piese1.in");
ofstream fout("piese1.out");
int main()
{
	int n;
	long long  T;
	fin >> n >> T;
	vector<int> p(n);
	for (int i = 0; i < n; ++i)
		fin >> p[i];
	vector<long long>  x, y;
    int nx = n / 2;
    int ny = n - nx;
    for (int i = 0; i < (1 << nx); i++)
    {
		x.push_back(0);
		for (int j = 0; j < nx; j++)
			if ((1 << j) & i)            // daca setul i are bitul j
				x[x.size() - 1] += p[j];
    }
    for (int i = 0; i < (1 << ny); i++)
    {
		y.push_back(0);
		for (int j = 0; j < ny; j++)
			if ((1 << j) & i)
				y[y.size() - 1] += p[nx + j];
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
	int res = 0;
    for (int i = 0; i < x.size(); i++)
    {
		int l = 0, r = y.size() - 1, m, pos = 0;
		while (l <= r)
		{
			m = (l + r) / 2;
			if (x[i] + y[m] <= T)
			{
				pos = m;
				l = m + 1;
			}
			else
				r = m - 1;
		}
		if (x[i] <= T)    
			res += pos + 1;
    }
	fout << res - 1;
	fin.close();
	fout.close();
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2062)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2062/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2062/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)