1217 – Neighbor House (II)

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;
}

Advertisements

Light OJ: 1421 – Wavio Sequence

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

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: 1102 – Problem Makes Problem

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


#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[2000006];

ll bigmod(ll n, ll pow)
{
    ll ret=1;
    while(pow)
    {
        if(pow%2==1)
            {ret*=n; ret%=MOD;}
        n*=n;
        n%=MOD;
        pow/=2;

    }
    return ret;
}

int main()
{

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    fact[0]=1;
    for(ll i=1;i<2000005;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,k;

        sff(n,k);

        ll down=(fact[k-1]*fact[n])%MOD;

        down=bigmod(down,MOD-2);

        down=(fact[n+k-1]*down)%MOD;

        PRINT_CASE;

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



    }

    return 0;
}

Light OJ: 1095 – Arrange the Numbers

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;
}