Light OJ : 1331 – Agent J

0

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

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

double angle (double a, double b, double c)
{
    return acos((a*a+b*b-c*c)/(2*a*b));
}
int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    TEST_CASE(t)
    {
        double r1,r2,r3;
        cin>>r1>>r2>>r3;
        double a,b,c;
        a=r1+r2;
        b=r3+r2;
        c=r3+r1;
        double s=(a+b+c)/2;
        double area = sqrt(s*(s-a)*(s-b)*(s-c));
        area-=angle(a,b,c)/2*r2*r2;
        area-=angle(a,c,b)/2*r1*r1;
        area-=angle(b,c,a)/2*r3*r3;
        PRINT_CASE;
        pf("%lf\n",area);
    }
    return 0;
}

Light OJ – 1311 – Unlucky Bird

0

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

#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 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 main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    double v1,v2,v3,a1,a2,t1,t2;
    cin>>t;
    TEST_CASE(t)
    {
        cin>>v1>>v2>>v3>>a1>>a2;
        PRINT_CASE;
        t1=v1/a1;
        t2=v2/a2;
        double ans1=((v1*t1)-.5*a1*t1*t1)+((v2*t2)-.5*a2*t2*t2);
        double ans2=max(t1,t2)*v3;
        pf("%lf %lf\n",ans1,ans2);
    }
    return 0;
}


USACO (Complete Search) : Transformations

0

Problem Link : http://train.usaco.org/usacoprob2?a=SeMATkWVe9o&S=transform


/*
PROG: transform
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)
#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;

class Matrix
{

    char ara[11][11];
    int n;
public:
    void set_n(int x)
    {
        n=x;
    }
    int get_n()
    {
        return n;
    }

    friend istream& operator>>(istream & in, Matrix &xx);
    friend ostream& operator<<(ostream & in, Matrix &xx);

    bool operator==(Matrix xx)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                if(ara[i][j]!=xx.ara[i][j])
                    return false;
            }
        return 1;
    }

    friend Matrix Rotate_90(Matrix xx);
    friend Matrix Rotate_180(Matrix xx);
    friend Matrix Rotate_270(Matrix xx);
    friend Matrix Rotate_270(Matrix xx);
    friend Matrix Reflex(Matrix xx);
};

istream& operator>>(istream &in, Matrix &xx)
{
    for(int i=0; i<xx.n; i++)
        for(int j=0; j<xx.n; j++)
        {
            in>>xx.ara[i][j];
        }
    return in;
}

ostream& operator<<(ostream& in, Matrix &xx)
{
    for(int i=0; i<xx.n; i++,cout<<endl)
        for(int j=0; j<xx.n; j++)
        {
            in<<xx.ara[i][j]<<" ";
        }
    return in;
}

Matrix Rotate_90(Matrix xx)
{
    Matrix temp;
    temp.n=xx.n;
    for(int i=0; i<xx.n; i++)
        for(int j=0; j<xx.n; j++)
        {
            temp.ara[i][j]=xx.ara[xx.n-j-1][i];
        }
    return temp;
}

Matrix Rotate_180(Matrix xx)
{
    Matrix temp=Rotate_90(xx);
    Matrix temp1=Rotate_90(temp);
    return temp1;
}

Matrix Rotate_270(Matrix xx)
{
    Matrix temp=Rotate_90(xx);
    Matrix temp1=Rotate_180(temp);
    return temp1;
}

Matrix Reflex(Matrix xx)
{
    Matrix temp;
    temp.n=xx.n;
    for(int j=0; j<xx.n; j++)
        for(int i=xx.n-1,k=0; k<xx.n; k++,i--)
        {
            temp.ara[j][k]=xx.ara[j][i];
        }
    return temp;
}

int main()
{
    freopen("transform.in","r",stdin);
    freopen("transform.out","w",stdout);
    Matrix a,b,c;
    int ans=7;
    int x;
    cin>>x;
    a.set_n(x);
    b.set_n(x);
    cin>>a;
    cin>>b;
    if(b==Rotate_90(a))
        ans=min(ans,1);
    else if(b==Rotate_180(a))
        ans=min(ans,2);
    else if(b==Rotate_270(a))
        ans=min(ans,3);
    Matrix d;
    d.set_n(a.get_n());
    d=Reflex(a);
    if(b==d)
        ans=min(ans,4);
    for(int i=0; i<3; i++)
    {
        d=Rotate_90(d);
        if(b==d)
            ans=min(ans,5);
    }
    if(a==b)
        ans=min(ans,7);
    cout<<ans<<endl;
    return 0;
}

USACO (Complete Search) : Milking Cows

0

problem Link : http://train.usaco.org/usacoprob2?a=SeMATkWVe9o&S=milk2


/*
PROG: milk2
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)
#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<pii>v;
int main()
{
    freopen("milk2.in","r",stdin);
    freopen("milk2.out","w",stdout);


    pii a;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a.ff>>a.ss;
        v.pb(a);
    }
    int x,y,ans1=0,ans2=0;
    sort(all(v));
    x=v[0].ff;y=v[0].ss;
    ans1=y-x;
    for(int i=1;i<SZ(v);i++)
    {
        if(v[i].ff<=y)
            {
                if(y<v[i].ss)
                    y=v[i].ss;
            }
        else
        {
            ans2=max(ans2,v[i].ff-y);
            ans1=max(ans1,y-x);
            x=v[i].ff;
            y=v[i].ss;
        }
    }

    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}

USACO (Ad Hoc) : Broken Necklace

0

/*
Link :http://train.usaco.org/usacoprob2?a=SeMATkWVe9o&S=beads
*/

/*
PROG: beads
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)
#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;


int main()
{
    freopen("beads.in","r",stdin);
    freopen("beads.out","w",stdout);
    string str;
    int cnt,ans=0;
    int n;
    cin>>n>>str;
    for(int i=0;i<n;i++)
    {
        char color='w';
        bool taken_half=0;
        char current_color;
        cnt=0;
        for(int j=0;j<n;j++)
        {
            current_color=str[(i+j)%n];
            if(current_color!='w')
            {
               if(color=='w')
               {
                   color=current_color;
               }
               else if(color!=current_color)
               {
                   if(taken_half)
                    break;
                   else
                   {
                       taken_half=1;
                       color=current_color;
                   }
               }
            }
            cnt++;
        }
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}

Light OJ 1294 – Positive Negative Sign

0

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

/*
MMP""MM""YMM   db      `7MN.   `7MF'`7MMM.     ,MMF' .g8""8q.`YMM'   `MM'
P'   MM   `7  ;MM:       MMN.    M    MMMb    dPMM .dP'    `YM.VMA   ,V
     MM      ,V^MM.      M YMb   M    M YM   ,M MM dM'      `MM VMA ,V
     MM     ,M  `MM      M  `MN. M    M  Mb  M' MM MM        MM  VMMP
     MM     AbmmmqMA     M   `MM.M    M  YM.P'  MM MM.      ,MP   MM
     MM    A'     VML    M     YMM    M  `YM'   MM `Mb.    ,dP'   MM
   .JMML..AMA.   .AMMA..JML.    YM  .JML. `'  .JMML. `"bmmd"'   .JMML.
*/

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

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    getint(t);
    TEST_CASE(t)
    {
        ll n,m;
        cin>>n>>m;
        PRINT_CASE;
        cout<<m*(n/2)<<endl;
    }
    return 0;
}

Light OJ 1261 – K-SAT Problem

0

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

#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 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);
    vector<int>v[32];
    bool ara[32];
    int t;
    getint(t);
    TEST_CASE(t)
    {
        ms(ara,0);
        int n,m,k,p,num;
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)
        {
            v[i].pb(0);
            for(int j=1;j<=k;j++)
            {
                cin>>num;
                v[i].pb(num);
            }
        }

        cin>>p;
        loop(i,p)
        {
            cin>>num;
            ara[num]=1;
        }

        bool test1=0,test2=0;
        for(int i=1;i<=n;i++)
        {
            test1=0;
            for(int j=1;j<=k;j++)
            {
                if(v[i][j]>0 && ara[v[i][j]])
                    test1=1;
                if(v[i][j]<0 && !ara[-v[i][j]])
                    test1=1;
            }
            if(test1==0)
                test2=1;
        }
        PRINT_CASE;
        if(test2)
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
        loop(i,n+1)
            v[i].clear();
    }
    return 0;
}


UVa 136 – Ugly Numbers

0

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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

int main()
{
    double a,b,c,k,ara[2000];
    int count=0;
    for(a=0; a<31; a++)
        for(b=0; b<31; b++)
            for(c=0; c<31; c++)
            {
                k=pow(2,c)*pow(3,b)*pow(5,a);
                if(k>1000000000)
                {
                    k=0;
                      break;
                }
                else
                {
                    ara[count]=k;
                    count++;
                }
            }
    sort(ara,ara+count);
    printf("The 1500'th ugly number is %.lf.\n",ara[1499]);
    return 0;
}

UVa 113 – Power of Cryptography

0

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

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    double n,p;
    while(scanf("%lf %lf", &n,&p)==2)
    {
        printf("%.lf\n", pow(p,1/n));
    }
    return 0;
}

UVa 102 – Ecological Bin Packing

0

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

#include <bits/stdc++.h>

#define ll long long
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)

using namespace std;

int main()
{
    ///freopen("input.txt","r",stdin);
    ///freopen("output.txt","w",stdout);
    long long a1,a2,a3,b1,b2,b3,c1,c2,c3,ans,i,j,k,l;
    while(cin>>a1>>b1>>c1>>a2>>b2>>c2>>a3>>b3>>c3)
    {
        j=(a2+a3+c1+c3+b1+b2);
        k=j;
        l=1;
        j=(a2+a3+b1+b3+c1+c2);
        if(j<k)
        {
            k=j;
            l=2;
        }
        j=(c2+c3+a1+a3+b1+b2);
        if(j<k)
        {
            k=j;
            l=3;
        }
        j=(c2+c3+b1+b3+a1+a2);
        if(j<k)
        {
            k=j;
            l=4;
        }
        j=(b2+b3+a1+a3+c1+c2);
        if(j<k)
        {
            k=j;
            l=5;
        }
        j=(b2+b3+c1+c3+a1+a2);
        if(j<k)
        {
            k=j;
            l=6;
        }
        if(l==1)
            cout<<"BCG "<<k<<endl;
        else if(l==2)
            cout<<"BGC "<<k<<endl;
        else if(l==3)
            cout<<"CBG "<<k<<endl;
        else if(l==4)
            cout<<"CGB "<<k<<endl;
        else if(l==5)
            cout<<"GBC "<<k<<endl;
        else if(l==6)
            cout<<"GCB "<<k<<endl;
    }
    return 0;
}