USACO: Ski Course Design

Problem Link : http://train.usaco.org/usacoprob2?a=tffkkLavmsp&S=skidesign


/*
PROG: skidesign
LANG: C++
*/

#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 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));}
/*------------------------------------------------*/


int main()
{
    freopen("skidesign.in","r",stdin);
    freopen("skidesign.out","w",stdout);
    int n,x;
    sf(n);
    vector<int>v;
    loop(i,n) sf(x),v.pb(x);
    ll ans=INT_MAX;

    for(int i=1; i<=83; i++)
    {
        ll temp=0;
        for(int j=0; j<n; j++)
        {
            if(v[j]<i) temp+=sqr(i-v[j]);
            else if(v[j]>i+17) temp+=sqr(v[j]-i-17);
        }
        ans=min(ans,temp);
    }
    cout<<ans<<endl;
    return 0;
}


Advertisements

USACO : Wormholes

Problem Link : http://train.usaco.org/usacoprob2?a=tffkkLavmsp&S=wormhole


/*
PROG: wormhole
LANG: C++
*/


#include <iostream>
#include <fstream>
using namespace std;
#define MAX_N 12

int N, X[MAX_N+1], Y[MAX_N+1];
int wife[MAX_N+1];
int next_on_right[MAX_N+1];

bool cycle_exists(void)
{
    for (int start=1; start<=N; start++)
    {
        int pos = start;
        for (int count=0; count<N; count++)
            pos = next_on_right[wife[pos]];
        if (pos != 0) return true;
    }
    return false;
}

int solve(void)
{
    int i, total=0;
    for (i=1; i<=N; i++)
        if (wife[i] == 0) break;

    // everyone paired?
    if (i > N)
    {
        if (cycle_exists()) return 1;
        else return 0;
    }

    // try pairing i with all possible other wormholes j
    for (int j=i+1; j<=N; j++)
        if (wife[j] == 0)
        {
            // try pairing i & j, let recursion continue to
            // generate the rest of the solution
            wife[i] = j;
            wife[j] = i;
            total += solve();
            wife[i] = wife[j] = 0;
        }
    return total;
}

int main(void)
{
    ifstream fin("wormhole.in");
    fin >> N;
    for (int i=1; i<=N; i++) fin >> X[i] >> Y[i];
    fin.close();

    for (int i=1; i<=N; i++) // set next_on_right[i]...
        for (int j=1; j<=N; j++)
            if (X[j] > X[i] && Y[i] == Y[j]) // j right of i...
                if (next_on_right[i] == 0 ||
                        X[j]-X[i] < X[next_on_right[i]]-X[i])
                    next_on_right[i] = j;

    ofstream fout("wormhole.out");
    fout << solve() << "\n";
    fout.close();
    return 0;
}


UVa 714 – Copying Books


/*
User ID: turing_13
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=655
*/

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#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 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));}
/*------------------------------------------------*/

int n,k,ara[510];
bool visited[510];

int func(ll mid)
{
    ms(visited,0);
    int cnt=0;
    for(int i=n-1;i>=0;)
    {
        ll sum=0;
        while(i>=0 && sum+ara[i]<=mid)
        {
            sum+=ara[i];
            i--;
        }
        if(sum==0)
            return k+1;
        cnt++;
        visited[i]=1;
    }
    return cnt;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll sum=0;
        sff(n,k);
        loop(i,n)
        {
            sf(ara[i]);
            sum+=ara[i];
        }

        ll lo=1,hi=sum,mid;
        while(lo<hi)
        {
            mid=lo+(hi-lo)/2;
            if(func(mid)<=k)
                hi=mid;
            else
                lo=mid+1;
        }

        int cnt=func(hi);
        for(int i=0;i<n && cnt<k;i++)
        {
            if(!visited[i])
                visited[i]=1,cnt++;
        }

        loop(i,n)
        {
            if(i)
                pf(" %d",ara[i]);
            else
                pf("%d",ara[i]);
            if(visited[i])
                pf(" /");
        }
        pf("\n");
    }
    return 0;
}

UVa 12032 – The Monkey and the Oiled Bamboo


/*
User ID: turing_13
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3183
*/

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#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 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));}
/*------------------------------------------------*/

int n;
ll ara[100005];

bool func(int mid)
{
    for(int i=1;i<=n;i++)
    {
        if(ara[i]-ara[i-1]>mid) return false;
        if(ara[i]-ara[i-1]==mid) mid--;
    }
    return true;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll lo=10000000000,hi=-10000000,mid;
        sf(n);
        REP(i,1,n+1)
        {
            sf(ara[i]);
            lo=min(lo,ara[i]);
            hi=max(hi,ara[i]);
        }
        while(lo<hi)
        {
            mid=lo+(hi-lo)/2;
            if(func(mid))
                hi=mid;
            else
                lo=mid+1;
        }
        PRINT_CASE;
        pf("%d\n",hi);
    }
    return 0;
}

UVa 11413 – Fill the Containers


/*
User ID: turing_13
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2408
*/

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#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 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));}
/*------------------------------------------------*/

int n,m;
int ara[100000];

int func(ll mid)
{
    int cnt=0;
    ll sum=0;
    for(int i=0;i<n;)
    {
        sum=0;
        while(i<n && sum+ara[i]<=mid)
        {
            sum+=ara[i];
            i++;
        }
        if(cnt>m)
            return cnt;
        cnt++;
    }
    return cnt;
}

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

    while(sff(n,m)==2)
    {
         ll lo=1, hi=0,mid;
        loop(i,n) sf(ara[i]),hi+=ara[i];

        while(lo<hi)
        {
            mid=lo+(hi-lo)/2;
            if(func(mid)<=m)
                hi=mid;
            else
                lo=mid+1;
        }
        pf("%lld\n",hi);
    }
    return 0;
}

USACO : Combination Lock

Problem Link : http://train.usaco.org/usacoprob2?a=4Hh6zP8GJZV&S=combo


/*
PROG: combo
LANG: C++
*/

#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 oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define getint2(a,b) scanf("%d%d",&a,&b)
#define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;
int n;
bool check1(int a, int b)
{
    if(abs(a-b)<=2) return 1;
    if(abs(a-b)>=n-2) return 1;
    return 0;
}

bool check(int a1,int b1,int c1,int a2,int b2,int c2)
{
    return (check1(a1,a2) && check1(b1,b2) && check1(c1,c2));
}
int main()
{
    freopen("combo.in","r",stdin);
    freopen("combo.out","w",stdout);
    int a,b,c,x,y,z;
    int cnt=0;
    cin>>n;
    cin>>a>>b>>c>>x>>y>>z;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(check(i,j,k,a,b,c)||check(i,j,k,x,y,z))
                    cnt++;
    cout<<cnt<<endl;
    return 0;
}



USACO: Prime Cryptarithm

Problem Link : http://train.usaco.org/usacoprob2?a=dOLJGJAE7bv&S=crypt1


/*
TASK: crypt1
LANG: C++
*/

#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 oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define getint2(a,b) scanf("%d%d",&a,&b)
#define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;
int ara[11];
bool mp[11];

int main()
{
    freopen("crypt1.in","r",stdin);
    freopen("crypt1.out","w",stdout);

    int n;
    cin>>n;
    loop(i,n)
        {
            cin>>ara[i];
            mp[ara[i]]=1;
        }
    int cnt=0;
    loop(a,n)
    loop(b,n)
    loop(c,n)
    {
        int abc=ara[a]*100+ara[b]*10+ara[c];
        if( abc/1000 !=0)
            continue;
        int p1,p2;
        loop(d,n)
        {
            p1=abc*ara[d];
            if( p1/1000 !=0)
            continue;
            int temp1=p1;
            bool test=0;
            while(temp1)
            {
                if(mp[temp1%10]==1)
                {
                    temp1/=10;
                }
                else
                {
                    test=1;
                    break;
                }
            }
            if(test)
                continue;
            loop(e,n)
            {
                p2=abc*ara[e];
                if( p2/1000 !=0)
                continue;
                int temp2=p2;
                bool test=0;
                while(temp2)
                {
                    if(mp[temp2%10]==1)
                    {
                        temp2/=10;
                    }
                    else
                    {
                        test=1;
                        break;
                    }
                }
                if(test)
                    continue;
                int ans=p1+p2*10;
                while(ans)
                {
                    if(mp[ans%10]==1)
                        ans/=10;
                    else
                    {
                        test=1;
                        break;
                    }
                }
                if(test==0)
                    cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}