USACO: Barn Repair

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


/*
PROG: barn1
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;

bool test(int a,int b)
{
    return a>b;
}

int main()
{
    freopen("barn1.in","r",stdin);
    freopen("barn1.out","w",stdout);
    int sum=0,ans=0,m,s,c;
    int ara[300],len[300];
    cin>>m>>s>>c;
    loop(i,c)
    {
        cin>>ara[i];
    }
    ms(len,0);
    sort(ara,ara+c);
    int maxx=ara[c-1];
    int minx=ara[0];
    int cnt=0;
    sum=maxx-minx+1;

    for(int i=1;i<c;i++)
    {
        len[cnt++]=ara[i]-ara[i-1]-1;
    }

    sort(len,len+cnt,test);

    loop(i,m-1)
    {
        ans+=len[i];
    }
    cout<<sum-ans<<endl;
    return 0;
}

Advertisements

USACO : Mixing Milk

Problem Link : http://train.usaco.org/usacoprob2?a=ZjtQpZMHmbg&S=milk


/*
PROG: milk
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;
vector<pii>v;

int main()
{
    freopen("milk.in","r",stdin);
    freopen("milk.out","w",stdout);
    int n,m,ans=0,a,b;
    getint2(n,m);
    loop(i,m)
    {
        getint2(a,b);
        v.pb(MP(a,b));
    }
    
    sort(all(v));

    for(int i=0;i<SZ(v);i++)
    {
        if(n==0)
            break;
        if(n<=v[i].ss)
        {
            ans+=(n*v[i].ff);
            break;
        }
        else
        {
            ans+=(v[i].ss*v[i].ff);
            n-=v[i].ss;
        }
    }
    cout<<ans<<endl;
    v.clear();
    return 0;
}


Light OJ 1048 – Conquering Keokradong


/*
Link : http://www.lightoj.com/volume_showproblem.php?problem=1048
*/

#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)
#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[2000],n,m;

bool test(int x)
{
    int t=x;
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(x<ara[i]) return 0;
        if(t-ara[i]>=0) t-=ara[i];
        else
        {
            cnt++;
            t=x-ara[i];
        }
        if(cnt>m) return 0;
    }
    return 1;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sc("%d",&t);


    TEST_CASE(t)
    {
        int sum=0,maxx=-1;
        getint2(n,m);
        n++;
        for(int i=1; i<=n; i++)
        {
            getint(ara[i]);
            maxx=max(maxx,ara[i]);
            sum+=ara[i];
        }

        int l,r,mid;
        l=min(maxx,sum);
        r=max(maxx,sum);

        while(l<r)
        {
            mid=(l+r)/2;
            if(test(mid))
                r=mid;
            else
                l=mid+1;
        }
        while(!test(mid)) mid++;
        m++;
        PRINT_CASE;
        pf("%d\n",mid);
        int temp=0;
       l=n;
        for(int i=1; i<=l; i++)
        {
            temp+=ara[i];
            n--;
            m--;
            if(temp+ara[i+1]<=mid && n>m)
            {
                int j=i+1;
                temp+=ara[j];
                n--;
                while(temp+ara[j+1]<=mid && n>m)
                {
                    j++;
                    temp+=ara[j];
                    n--;
                }
                i=j;
            }
            pf("%d\n",temp);
            temp=0;
        }
    }
    return 0;
}

Here is another solution…


#include <bits/stdc++.h>
using namespace std;

int d[1024];
int main()
{
    int t, tc = 0, n, i, j, k, hi, lo, mid, sum;
    scanf ("%d", &t);
    while (tc < t)
    {
        tc++;
        scanf ("%d%d", &n,&k);
        n++;
        k++;
        hi = 0;
        lo = 0;
        for (i = 0; i < n; i++)
        {
            scanf ("%d", &d[i]);
            hi += d[i];
        }

        while (hi >= lo)
        {
            mid = (hi+lo)/2;
            for (i = 1, j = 0; i <= k ; i++)
            {
                sum = 0;
                for (; j < n; j++)
                {
                    if (sum+d[j]>mid) break;
                    sum += d[j];
                }
            }
            if (j < n) lo = mid+1;
            else hi = mid-1;
        }

        printf ("Case %d: %d\n", tc, lo);
        for (i = k, j = 0; i > 0; i--)
        {
            sum = 0;
            for (; n-j >= i; j++)
            {
                if (sum+d[j] > lo) break;
                sum += d[j];
            }
            printf ("%d\n",sum);
        }
    }
    return 0;
}


Light OJ 1389 – Scarecrow


/*
Link: http://www.lightoj.com/volume_showproblem.php?problem=1389
*/


#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <string>
#include <map>

#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)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#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;

/* Bits operation */
int Set(int n,int pos)  { return n = n | 1<<pos;}
bool check(int n,int pos) { return n & 1<<pos;}
int Reset(int n, int pos) { return n=n & ~(1<<pos);}
/*----------------*/

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    char ara[110];
    int t;
    cin>>t;
    TEST_CASE(t)
    {
        int n;
        cin>>n;
        sc("%s",ara);
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(ara[i]=='.')
                ans++,i+=2;
        }
        PRINT_CASE;
        cout<<ans<<endl;
    }
    return 0;
}

Light OJ 1016 – Brush (II)


/*
Link: http://www.lightoj.com/volume_showproblem.php?problem=1016
*/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <string>
#include <map>

#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)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#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;

vector<ll>v;
int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    getint(t);
    TEST_CASE(t)
    {
        int n,w;
        ll a,b;
        sc("%d %d",&n,&w);
        loop(i,n)
        {
            sc("%lld %lld",&a,&b);
            v.pb(b);
        }
        sort(all(v));
        int ans=1;
        a=v[0];
        for(int i=1; i<n; i++)
        {
            if(v[i]-a>w)
            {
                ans++;
                a=v[i];
            }
        }
        PRINT_CASE;
        pf("%d\n",ans);
        v.clear();
    }
    return 0;
}