Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel:

Exemplu

reteta1.in

4 5
2 1 3
2 2 2 3
1 1 1
1 3 4 1 2
1 1 3
8 20 2 16

reteta1.out

45.0

Explicație

Soluţia s-a obţinut prin folosirea primei şi celei de a patra reţete. O altă soluţie, dar de cost mai mare, s-ar fi obţinut dacă se folosea reţeta a patra şi cea de a cincea.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("reteta1.in");
ofstream cout("reteta1.out");

int n , m , A[21] , X[21];
double mini = 10000001;

struct poz
{
    int c , n , a[21];
    double val;
}r[21];

int afisare(int k)
{
    for(int i = 1 ; i <= k ; i++)
        cout << X[i] << " ";
    cout << '\n';
}

void alegemin(int k)
{
    /*for(int i = 1 ; i <= k ; i++)
        cout << X[i] << " ";
    cout << endl;*/
    double v = 0;
    int ok = 0 , f[21] = {0};
    for(int i = 1 ; i <= k ; i++)
    {
        v += r[X[i]].val;
        for(int j = 1 ; j <= r[X[i]].n ; j++)
            f[r[X[i]].a[j]]++;
    }
    /*for(int j = 1 ; j <= n ; j++)
        cout << f[j] << " ";
    cout << endl;*/
    for(int j = 1 ; j <= n ; j++)
        if(f[j] != 1) ok = 1;
    if(ok == 0 && v < mini) mini = v;
}
void back(int k)
{
    for(int i = X[k - 1] + 1 ; i <= m ; i++)
    {
        X[k] = i;
        alegemin(k);
        back(k + 1);
    }
}

int main()
{
    cin >> n >> m;

    for(int i = 1 ; i <= m ; i++)
    {
        cin >> r[i].c >> r[i].n;
        for(int j = 1 ; j <= r[i].n ; j++)
            cin >> r[i].a[j];
    }

    for(int i = 1 ; i <= n ; i++)
        cin >> A[i];

    for(int i = 1 ; i <= m ; i++)
    {
        r[i].val = 0;
        for(int j = 1 ; j <= r[i].n ; j++)
            if(r[i].c == 1)
                r[i].val += A[r[i].a[j]];
            else
                r[i].val += A[r[i].a[j]] / 2.0;
    }
    back(1);
    cout << fixed << setprecision(1) << mini;
}