Problema 3 admitere informatica Iasi 2012.

#include <iostream>
#include <string.h>

using namespace std;

int a[100] = {3,2,6,7,1,-9,8,2,-15,2,4,3};

int m[100], M[100];
int b=700, x[100], n=12, inf=-100, sup=100;
int gasit=0;


int minn(int nm, int am[], int bm, int infm, int supm, int km){
    int minim=2000000000;
    for(int jj=infm; jj<=supm; jj++)
    {
        int sum=0;
        for(int i=km; i<nm-1; i++)
            sum += am[i]*jj;
        if (sum < minim) minim=sum;
    }
    return minim;
}

int maxx(int nm, int am[], int bm, int infm, int supm, int km){
    int maxim=-2000000000;
    for(int jj=infm; jj<=supm; jj++)
    {
        int sum=0;
        for(int i=km; i<nm-1; i++)
            sum += am[i]*jj;
        if (sum > maxim) maxim=sum;
    }
    return maxim;
}

int verifica(int k)
{
    int sum=0;
    for(int i=0;i<k;i++)
        sum+=(a[i]*x[i]);
    if (sum+m[k]>b) return 0;
    if (sum+M[k]<b) return 0;
    return 1;
}


void afisare(){

    int sum=0;
    for(int i=0;i<n;i++)
        sum+=(a[i]*x[i]);
    if(sum==b){
            for(int i=0;i<n;i++)
                cout << a[i]<<"*"<<x[i]<<" + ";
            gasit=1;
            cout << endl;
    }
}

void bkt(int k){
    if(k==n) afisare();
    else{
        for(int i=inf;i<=sup;i++){
            x[k]=i;
            if (verifica(k)) bkt(k+1);
        }
    }
}

int main()
{
    for(int i=0; i<n; i++)
        m[i]=minn(n,a,b,inf,sup,i);
    for(int i=0; i<n; i++)
        M[i]=maxx(n,a,b,inf,sup,i);
    bkt(0);

    return 0;
}