UVA 990 - Diving for Gold solution

#include <bits/stdc++.h>
#define pb push_back
#define MAX 10006
#define mod 1000000009
#define read freopen("input.txt","r",stdin);
#define base 10
using namespace std;
typedef long long ll;
typedef unsigned long long llu;

int total,w,n;
int cost[1002],weight[1002],ary[1001];
vector<int>c,inde,final_c,final_inde;

void call(int i,int sum)
{

    if(i>=n)
    {
        int ss=0,f=0;
        for(int j=0; j<c.size(); j++) ss+=c[j];
        for(int j=0; j<final_c.size(); j++) f+=final_c[j];

        if(ss>f)
        {
            final_c=c;
            final_inde=inde;
        }
        return ;
    }

    if(sum+cost[i]<=total)
    {
        c.pb(weight[i]);
        inde.pb(i);
        call(i+1,sum+cost[i]);
        c.pop_back();
        inde.pop_back();
    }
    call(i+1,sum);
}

int main()
{
    //  read;
    // freopen("output.txt","w",stdout);
    bool flag=true;
    while(scanf("%d %d",&total,&w)==2)
    {

        if(!flag) printf("\n");
        flag=false;
        scanf("%d",&n);

        c.clear();
        inde.clear();
        final_c.clear();
        final_inde.clear();

        for(int i=0; i<n; i++) scanf("%d %d",&ary[i],&weight[i]);
        for(int i=0; i<n; i++) cost[i]=(ary[i]*w)+(2*(ary[i]*w));
        //  final_c.pb(0);

        call(0,0);
        int sum=0;

        if(final_inde.size()>0) for(int i=0; i<final_inde.size(); i++)sum+=weight[final_inde[i]];
        cout<<sum<<endl;
        cout<<final_inde.size()<<endl;

        if(final_inde.size()>0)
        {
            for(int i=0; i<final_inde.size(); i++)
            {
                cout<<ary[final_inde[i]]<<" "<<weight[final_inde[i]]<<endl;
            }
        }
        else cout<<0<<" "<<0<<endl;

    }

    return 0;
}

UVA 10664 - Luggage solution

#include <bits/stdc++.h>
#define pb push_back
#define MAX 10006
#define mod 1000000009
#define read freopen("input.txt","r",stdin);
#define base 10
using namespace std;
typedef long long ll;
typedef unsigned long long llu;

int n,len,s;
vector<int>ary;
int  dp[22][4002];

bool call(int i,int sum)
{
    if(sum==(s-sum)) return 1;
    if(dp[i][sum]!=-1) return dp[i][sum];
    if(i>=len) return 0;
    return dp[i][sum]=call(i+1,sum+ary[i])||call(i+1,sum);
}

int main()
{
   // read;
    int test;
    scanf("%d",&test);
    getchar();
    while(test--)
    {
        ary.clear();
       // flag=false;
        string str;
        getline(cin,str);
        stringstream st;
        st<<str;
        s=0;
        while(st>>n) ary.pb(n),s+=n;
        memset(dp,-1,sizeof(dp));
        len=ary.size();
        puts(call(0,0)==1?"YES":"NO");
    }

    return 0;
}

uva 10616 - Divisible Group Sums solution

#include <bits/stdc++.h>
#define pb push_back
#define MAX 10006
#define mod 1000000009
#define read freopen("input.txt","r",stdin);
#define base 10
using namespace std;
typedef long long ll;
typedef unsigned long long llu;

int n,Q,d,m,ary[300];
int dp[201][11][50];
int call(int i,int c,int sum)
{

    if(c==m)
    {
        if(sum) return 0;
        else return 1;
    }
    if(i>=n) return 0;
    if(dp[i][c][sum]!=-1) return dp[i][c][sum];

    return dp[i][c][sum]=call(i+1,c+1,(sum+ary[i])%d)+call(i+1,c,sum);
}



int main()
{
    // read;
    int cas=0;
    while(~scanf("%d %d",&n,&Q)&&n&&Q)
    {
        for(int i=0; i<n; i++) scanf("%d",&ary[i]);
        printf("SET %d:\n",++cas);

        for(int q=1; q<=Q; q++)
        {
            memset(dp,-1,sizeof(dp));
            scanf("%d %d",&d,&m);
            printf("QUERY %d: %d\n",q,call(0,0,0));
        }
    }


    return 0;
}

UVA solution 1213 - Sum of Different Primes

#include <bits/stdc++.h>
#define pb push_back
#define MAX 10006
#define mod 1000000009
#define read freopen("input.txt","r",stdin);
#define base 10
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
bool mark[MAX];
vector<int>prime,p;
int target,cnt,n;
ll dp[500][20][1200];
void sieve()
{
    for(int i=3; i<=sqrt(MAX); i+=2)
    {
        if(!mark[i]) for(int j=i*i; j<MAX; j+=i) mark[j]=true;
    }

    prime.pb(2);
    for(int i=3; i<MAX; i+=2) if(!mark[i]) prime.pb(i);

}

ll call(int i,ll sum,int c)
{

    if(sum>target) return 0;
    if(c==cnt)
    {
        if(sum==target) return 1;
        else return 0;
    }
    if(i>=n) return 0;
    if(dp[i][c][sum]!=-1) return dp[i][c][sum];

    return  dp[i][c][sum]=call(i+1,sum+p[i],c+1)+call(i+1,sum,c);

}


int main()
{
    // read;
    sieve();  // easy knapsack
    //cout<<prime.size()<<endl;
    // for(int i=0;i<5;i++) cout<<prime[i]<<endl;
    while(scanf("%d %d",&target,&cnt)&& target &&cnt)
    {
        memset(dp,-1,sizeof(dp));
        p.clear();
        for(int i=0; prime[i]<=target; i++) p.pb(prime[i]);
        n=p.size();
        printf("%lld\n",call(0,0,0));

    }





    return 0;
}

spoj NHAY - A Needle in the Haystack solution

#include <bits/stdc++.h>
#define pb push_back
#define MAX 1000006
#define mod 1000000009
#define read freopen("input.txt","r",stdin);
#define base 10
using namespace std;
typedef long long ll;
typedef unsigned long long llu;

llu ary[MAX],ah,bh[MAX];

int main()
{
   // read;
    ary[0]=1;
    for(int i=1; i<=MAX; i++) ary[i]=ary[i-1]*base;  //  using hashing
    string a,b;
    int lena,lenb;
    while(cin>>lena>>a>>b)
    {
        lenb=b.size();
        ah=0;
        memset(bh,0,sizeof(bh));
        for(int i=lena-1; i>=0; i--) ah=ah*base+a[i];
        for(int i=lenb-1; i>=0; i--) bh[i]=bh[i+1]*base+b[i];
        bool flag=false;
        if(lena<=lenb)
        {

            for(int i=0; i<=lenb-lena; i++)
            {

                llu c=bh[i]-(bh[i+lena]*ary[lena]);
                if(ah==c )
                {
                    printf("%d\n",i);
                    flag=true;
                }
            }
        }

        if(!flag) puts("");
    }

    return 0;
}

UVA solution 624 - CD

#include<bits/stdc++.h>
#define READ freopen("input.txt","r",stdin);
using namespace std;
typedef long long ll;
int target,n,ary[50];
vector<int>temp,res;
void call(int i,int sum,int c)
{
    if(i>=n)
    {

        int s=0,s2=0;
        for(int i=0; i<temp.size(); i++) s+=temp[i];
        for(int i=0;i<res.size();i++) s2+=res[i];

        if(s>=s2)
        {
            if(s==s2)
            {
                if(temp.size()>res.size()) res=temp;
            }
            else res=temp;
        }



        return ;
    }
    if(sum+ary[i]<=target)
    {
        temp.push_back(ary[i]);
        call(i+1,sum+ary[i],c+1);
        temp.pop_back();
        c--;
    }
    else call(i+1,sum,c);

    call(i+1,sum,c);

}

int main()
{
   // READ;
    while(scanf("%d %d",&target,&n)==2)
    {
        temp.clear();
        res.clear();
        for(int i=0; i<n; i++) scanf("%d",&ary[i]);
        call(0,0,0);
        int s=0;
        for(int i=0; i<res.size(); i++)
        {
            s+=res[i];
            printf("%d ",res[i]);
        }
        printf("sum:%d\n",s);
    }


    return 0;
}