UVa 10296 – Jogging Trails

0

Problem Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1237


Solution Idea:
—————–
Light OJ: 1086 – Jogging Trails is a similar problem. The main idea behind this problem is Chinese Postman Problem.

For details about this theorem is described in book Competitive programming 3 by Steven Halim.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
int Set(int N,int pos)
{
    return N=N | (1<<pos);
}
int reset(int N,int pos)
{
    return N= N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}
/*------------------------------------------------*/

ll g[16][16];
int degree[16];
ll dp[1<<16];
int n,m;

void floyed_warshal()
{
    for(int k=0; k<n; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                if(g[i][j]>g[i][k]+g[k][j])
                    g[i][j]=g[i][k]+g[k][j];
            }
}

ll func(int mask)
{
    if(mask==0) return 0;
    ll &ret=dp[mask];
    if(ret!=-1) return ret;
    int pos=0;
    for(int i=0; i<n; i++)
        if(check(mask,i))
        {
            pos=i;
            break;
        }
    ret=INT_MAX;
    for(int i=pos+1;i<n;i++)
    {
        if(check(mask,i))
        {
            int temp_mask=mask;
            temp_mask=reset(temp_mask,pos);
            temp_mask=reset(temp_mask,i);
            ret=min(ret,g[pos][i]+func(temp_mask));
        }
    }
    return ret;
}

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int t;
//    sf(t);
//    TEST_CASE(t)
    while(sf(n) && n)
    {
        sf(m);
//        sff(n,m);
        ll ans=0;
        for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) g[i][j]=INT_MAX;
        ms(degree,0);
        for(int i=0; i<m; i++)
        {
            ll a,b,c;
            sfffl(a,b,c);
            a--;
            b--;
            g[a][b]=min(g[a][b],c);
            g[b][a]=min(g[b][a],c);
            degree[a]++;
            degree[b]++;
            ans+=c;
        }

        floyed_warshal();

        int mask=0;

        for(int i=0; i<n; i++)
            if(degree[i]%2)
                mask=Set(mask,i);


//        PRINT_CASE;
        ms(dp,-1);
        printf("%lld\n",ans+func(mask));
    }

    return 0;
}

SPOJ KALTSUM – k Alternating Sum

0

Problem Link : http://www.spoj.com/problems/KALTSUM/

Solution Idea:

Break the problem into two cases: When k is greater than sqrt(n) and when k is less tahn or equal sqrt(n). Deal with them in different ways.

Case 1: For any k>sqrt(N) there will be less than sqrt(N) alternating segment. If you have an array, having cumulative sum, you can get the sum of a contiguous segment in O(1). So you can just loop over the alternating parts and get the sum in O(sqrt(N)) for a single query.

Case 2: Now when k <= sqrt(n), you need to do some preprocessing.

let arr[k][i] be the "k alternating sum" of a subarray which starts at position i and keeps alternating untill it reaches a position x such that if you add another segment of size k then it will go out of the array. [ This array can be computed in O(N) , and as you're doing it for every k < sqrt(n), the total complexity is O(N * sqrt(N))] With the help of this array, you can answer every query having k < sqrt(N) in O(1).

This solution idea is from this link.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

ll dp[318][100005];
ll csum[100005];
ll ara[100005];

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n,q;

    sff(n,q);
    for(int i=1;i<=n;i++)
    {
        sfl(ara[i]);
        csum[i]=csum[i-1]+ara[i];
    }

    int root=ceil(sqrt(n));

    for(int i=1;i<=root;i++)
    {
        ll temp=0,sub=0;
        for(int j=n;j>=1;j--)
        {
            temp+=ara[j];
            if(j+i>n)
                sub=0;
            else
                sub=ara[j+i];
            temp-=sub;

            if(j+i-1>n)
                dp[i][j]=0;
            else
                dp[i][j]=temp-dp[i][j+i];
        }
    }
//
//    for(int i=1;i<=root;i++,cout<<endl)
//        for(int j=1;j<=n;j++)
//        cout<<dp[i][j]<<" ";

    while(q--)
    {
        int a,b,k;
        sfff(a,b,k);
        ll ans=0;
        if(k>root)
        {
            for(int i=a,j=0;i<=b;i+=k,j++)
            {
                if(j%2==0)
                    ans+=csum[i+k-1]-csum[i-1];
                else
                    ans-=csum[i+k-1]-csum[i-1];
            }
            pf("%lld\n",ans);
        }
        else
        {
            int turn=(b-a+1)/k;
            if(turn%2==1)
                pf("%lld\n",dp[k][a]+dp[k][b+1]);
            else
                pf("%lld\n",dp[k][a]-dp[k][b+1]);
        }
    }


    return 0;
}


1217 – Neighbor House (II)

0

Problem Link : http://lightoj.com:81/volume/problem/1217


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n;
int ara[1001];

int    dp[1001][1001][3];
bool xxxxx[1001][1001][3];
int yy=1;

int func(int idx, int last, int state)
{

    if(idx>n)
    {
        if(state==0 && last!=n)
            return ara[1];
        return 0;
    }

    int &ret=dp[idx][last][state];
    bool &cas=xxxxx[idx][last][state];
    if(cas) return ret;
    cas=1;

////    if(ret!=-1) return ret;

    int p=0,q=0;

    if(idx==1)
    {
        p=ara[1]+func(idx+2,idx,1);
        q=func(idx+1,last,state);
    }
    else if(idx==2)
    {
        p=ara[2]+func(idx+2,idx,2);
        q=func(idx+1,0,state);
    }
    else if(idx==n)
    {
        if(last!=n-1 && state!=1)
            p=ara[n]+func(idx+2,idx,state);
        q=func(idx+1,last,state);
    }
    else
    {
        p=ara[idx]+func(idx+2,idx,state);
        q=func(idx+1,last,state);
    }

    return ret=max(p,q);


}

int main()
{

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        sf(n);
        for(int i=1; i<=n; i++) sf(ara[i]);
//        ms(dp,-1);
//        yy++;
        ms(xxxxx,0);
        PRINT_CASE;
        printf("%d\n",func(1,0,0));

    }

    return 0;
}

Light OJ: 1421 – Wavio Sequence

0

Problem Link : http://lightoj.com:81/volume/problem/1421


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int ara[100006];
int lis[100005];
int lds[100005];
int temp[100005];

void LIS(int n)
{
    loop(i,n+5) temp[i]=infinity;
    temp[0]=-infinity;
    int len=0;
    for(int i=0; i<n; i++)
    {
        int lo=0,hi=len;
        while(lo<=hi)
        {
            int mid=(lo+hi)/2;
            if(temp[mid]<ara[i])
                lo=mid+1;
            else
                hi=mid-1;
        }
        temp[lo]=ara[i];
        lis[i]=lo;
        if(lo>len) len++;
    }
}

void LDS(int n)
{
    loop(i,n+5) temp[i]=infinity;
    temp[0]=-infinity;
    int len=0;
    for(int i=0; i<n; i++)
    {
        int lo=0,hi=len;
        while(lo<=hi)
        {
            int mid=(lo+hi)/2;
            if(temp[mid]<ara[i])
                lo=mid+1;
            else
                hi=mid-1;
        }
        temp[lo]=ara[i];
        lds[i]=lo;
        if(lo>len) len++;
    }
}


int main()
{

//     freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int n;
    int t;
    sf(t);
    TEST_CASE(t)
    {
        sf(n);
        loop(i,n) sf(ara[i]);
        LIS(n);
        reverse(ara,ara+n);
        LDS(n);
//        loop(i,n) cout<<lis[i]<<" ";
//        cout<<endl;
//        loop(i,n) cout<<lds[i]<<" ";
//        cout<<endl;
        reverse(lds,lds+n);
        int ans=0;
        for(int i=0; i<n; i++)
        {
            ans=max(ans,(2*min(lis[i],lds[i]))-1);
        }
        PRINT_CASE;
        printf("%d\n",ans);
    }

    return 0;
}


Light OJ: 1326 – Race

0

Problem Link : http://lightoj.com:81/volume/problem/1326

Solution Idea:

Let’s define dp(i) as the number of ways in which a race with “i” horses can finish.

Suppose we have “i” horses at the race and we will choose k of them for the first place, leaving “i – k” for the second (or higher) place. The process to count the number of ways to choose horses for the second place is equals to the original problem. This is the reason why we use dp.

(This Solution idea is from Manuel Pinda)


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              10056
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

ll dp[1003][1003];
ll ans[1003];

ll nCr(int n, int r)
{
    if(r==1) return n;
    if(n==r) return 1;

    ll &ret=dp[n][r];

    if(ret!=-1) return ret;

    return ret=(nCr(n-1,r-1)%MOD+nCr(n-1,r)%MOD)%MOD;
}

ll func(int n)
{
    if(n==0) return 1;
    if(ans[n]!=-1) return ans[n];

    ll ret=0;

    for(int i=1;i<=n;i++)
    {
        ret+=(nCr(n,i)*func(n-i))%MOD;
        ret%=MOD;
    }

    return ans[n]=ret;
}

int main()
{

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int t;
    sf(t);

    ms(dp,-1);
    ms(ans,-1);

    TEST_CASE(t)
    {
        int n;
        sf(n);
        PRINT_CASE;

        printf("%lld\n",func(n));

    }

    return 0;
}


Light OJ: 1095 – Arrange the Numbers

0

Problem Link : http://lightoj.com:81/volume/problem/1095


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

ll fact[1005];

ll dp[1005][1005];

ll nCk(int n, int k)
{
    if(k==1) return n;
    if(n==k) return 1;

    if(dp[n][k]!=-1) return dp[n][k];

    return dp[n][k]= (nCk(n-1,k-1)+nCk(n-1,k))%MOD;
}


int main()
{

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    fact[0]=1;

    for(ll i=1; i<1002; i++) fact[i]=(fact[i-1]*i)%MOD;

    int t;
    sf(t);
    ms(dp,-1);

    TEST_CASE(t)
    {
        ll n,m,k;
        sfffl(n,m,k);
        ll ans=nCk(m,k);

        int nn=n-k;

        ll ans1=fact[n-k];

        for(int i=1; i<=(m-k); i++)
        {
            if(i%2==1)
                ans1-= (nCk(m-k,i)*fact[nn-i])%MOD;
            else
                ans1+= (nCk(m-k,i)*fact[nn-i])%MOD;
            ans1=(ans1+MOD)%MOD;
        }

        PRINT_CASE;

        printf("%lld\n",(ans*ans1)%MOD);


    }


    return 0;
}

Light OJ: 1127 – Funny Knapsack

0

Problem Link : http://lightoj.com:81/volume/problem/1127



#include <bits/stdc++.h>
 
#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define CASE_PRINT      cout<<"Case "<<z<<": ";
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long
 
using namespace std;
 
 
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/
 
/*-----------------------Bitmask------------------*/
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
 
ll ara[50];
ll l[65536],r[65536];
 
int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        ms(l,0);
        ms(r,0);
        ll n,w;
        sffl(n,w);
        loop(i,n)
        {
            sfl(ara[i]);
        }
 
        int m1=n/2;
//        if(m1==0) m1++;
        int m2=(n-m1);
 
        int mask= 1<<(m1);
        int aa=mask;
        loop(i,mask)
        {
            loop(j,m1)
            if(check(i,j))
            {
                l[i]+=ara[j];
            }
        }
 
        mask=1<<(m2);
        int bb=mask;
        loop(i,mask)
        {
            loop(j,m2)
            {
                if(check(i,j))
                    r[i]+=ara[m1+j];
            }
        }
 
 
        sort(r,r+bb);
 
        ll ans=0;
 
        loop(i,aa)
        {
            if(w-l[i]>=0)
            ans+= upper_bound(r,r+bb,w-l[i])-r;
        }
 
        PRINT_CASE;
        pf("%lld\n",ans);
    }
    return 0;
}