U dalekoj zemlji Bajtoviji, održali su se redovni parlamentarni izbori. Nakon što je izborna komisija proglasila rezultate, potrebno je formirati vladu. Svakoj od stranaka koje su prešle cenzus je dodeljen odredeni broj mesta za poslanike u parlamentu. Vladu može formirati jedna stranka ili koalicija stranaka, s tim što ukupan broj poslanika koje stranka, odnosno koalicija, poseduje mora biti viši od polovine svih mesta u parlamentu. Kompanija koja se bavi predviđanjima političkih dogadaja želi da zna na koliko se načina može formirati postizborna koalicija.

Ulaz:

(Ulazni podaci se nalaze u datoteci vlada.in) U prvom redu datoteke se nalazi prirodan broj N, broj stranaka koje su prešle cenzus. U narednih N redova se nalazi N brojeva (u svakom redu po jedan), svaki pokazuje koliko je koja stranka dobila mesta u skupštini

Izlaz:

(Izlazne podatke upisati u datoteku vlada.out) U prvi i jedini red datoteke treba ispisati broj načina da se formira vladajuća koalicija.

Ograničenja:

• 1 ≤ N ≤ 20
• brojevi mesta koje su stranke dobile u parlamentu nisu veći od 200,
• vremensko ograničenje za izvršavanje programa je 1 s.

Primer 1:

4
10
20
30
40

7

Primer 2:

2
50
51

2

#include <cstdlib>
#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("vlada.p9.in");
ofstream fout("vlada.p9.out");
int n;
const int MAXN = 20;
int p[MAXN];
bool in[MAXN];
int sum;

void input() {
     fin >> n;
     sum = 0;
     for (int i = 0; i < n; i++) {
         fin >> p[i];
         sum += p[i];
     }
}
long solve(int s) {
     if (s < n) {
                 in[s] = false;
                 long total = solve(s+1);
                 in[s] = true;
                 total += solve(s+1);
                 return total;
     } 
     int sum1 = 0;
     for (int i = 0; i < n; i++)
         if (in[i])
            sum1 += p[i];
     if (sum1 > sum/2)
        return 1;
     else
         return 0;
}
int main(int argc, char *argv[])
{
    input();
    for (int i = 0; i < n; i++)
        in[i] = false;
    long res = solve(0);
    cout << n;
    fout << res << "\n";
    fout.close();
    system("PAUSE");
    return EXIT_SUCCESS;
}