Sunday 19 August 2012

UVa 442 - Matrix Chain Multiplication Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)
#define LL long long
#define MX 12
#define MOD 1000000007

struct Z{
    int row,col;
    char c;
};

main()
{
    int n,r,c;
    Z z,z1,z2;
    int pos1,pos2;
    string s;
    cin>>n;
    vector<Z>mat;
    stack<Z>mat2;
    //stack<Z>mat;
    while(n--)
    {
        cin>>z.c>>z.row>>z.col;
        mat.PB(z);
        mat2.push(z);
    }
    int matl=mat.size();
    while(cin>>s)
    {
        bool chk=true;
        int sl=s.length();
        stack<Z>stk;
        stk=mat2;
        LL sum=0;
        FOR(i,sl)
        {
            if(s[i]==')')
            {
                Z aa,bb;
                aa=stk.top();
                stk.pop();
                bb=stk.top();
                stk.pop();

                if(bb.col==aa.row)
                {

                    sum+=(bb.row*bb.col*aa.col);
                    z.c='x';
                    z.row=bb.row;
                    z.col=aa.col;
                    stk.push(z);
                }
                else
                {
                    chk=false;
                    break;
                }
            }

            else if(isalpha(s[i]))
            {
                FOR(j,matl)
                    if(mat[j].c==s[i])
                    {
                        z.c=mat[j].c;
                        z.row=mat[j].row;
                        //cout<<z.row<<endl;
                        z.col=mat[j].col;
                        //cout<<z.col<<endl;
                        stk.push(z);
                        break;
                    }
            }
        }
    if(chk)
        cout<<sum<<endl;
    else
        cout<<"error"<<endl;
    }
return 0;
}

Monday 13 August 2012

Spoj 4301. Tables Solution

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long n,k,s,cnt,a[2000],i,sum,ks;
    while(cin>>n>>k>>s)
    {
        ks=k*s;
        sum=0;
        for(i=0;i<n;i++)
        cin>>a[i];

        sort(a,a+n);

        for(i=1;i<=n;i++)
        {
            sum+=a[n-i];
            if(sum>=ks)
            break;
        }
        cout<<i<<endl;
    }
}

URAL 1014. Product of Digits Solution

#include<iostream>
using namespace std;
int main()
{
    long long i,q;
    string s;
    while(cin>>q)
    {
        if(q==0)
        {cout<<"10"<<endl;  continue;}
        if(q==1)
        {cout<<"1"<<endl;  continue;}

        s="";
        for(i=9;i>1;i--)
        {
            if(q>=i && q%i==0)
            {
                q/=i;
                s+=i+'0';
                i=10;
            }
        }
        if(q==1)
        {
            for(i=s.length()-1;i>=0;i--)
            cout<<s[i];
            cout<<endl;
        }
        else
        cout<<"-1"<<endl;
    }
}

URAL 1293. Eniya Solution

#include<iostream>
using namespace std;
int main()
{
    long long n,a,b;
    while(cin>>n>>a>>b)
        cout<<n*a*b*2<<endl;
}

URAL 1409. Two Gangsters Solution

#include<iostream>
using namespace std;
int main()
{
    int a,b,c;
    while(cin>>a>>b)
    {
        c=a+b-1;
        cout<<c-a<<" "<<c-b<<endl;
    }
}

Spoj 11. Factorial Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long


int main()
{
    int point1,point2,n,x1,y1,x2,y2,ans;
    while(cin>>n>>x1>>y1>>x2>>y2)
    {
        if(y1==0)
            point1=1;
        else if(x1==n)
            point1=2;
        else if(y1==n)
            point1=3;
        else if(x1==0)
            point1=4;

        if(y2==0)
            point2=1;
        else if(x2==n)
            point2=2;
        else if(y2==n)
            point2=3;
        else if(x2==0)
            point2=4;

        if((point1==point2) && (point1==1 || point1==3))
            {
              if(x1>x2)
                ans=x1-x2;
              else
                ans=x2-x1;
            }
        else if((point1==point2) && (point1==2 || point1==4))
            {
              if(y1>y2)
                ans=y1-y2;
              else
                ans=y2-y1;
            }
        else if(point1==1 && point2==2)
            ans=y2+n-x1;
        else if(point1==2 && point2==1)
            ans=y1+n-x2;
        else if(point1==2 && point2==3)
            ans=n-x2+n-y1;
        else if(point1==3 && point2==2)
            ans=n-x1+n-y2;
        else if(point1==3 && point2==4)
            ans=x1+n-y2;
        else if(point1==4 && point2==3)
            ans=x2+n-y1;
        else if(point1==4 && point2==1)
            ans=x2+y1;
        else if(point1==1 && point2==4)
            ans=x1+y2;
        else if((point1==1 && point2==3) || (point1==3 && point2==1))
            ans=min(3*n-x1-x2, n+x1+x2);
        else if((point1==2 && point2==4) || (point1==4 && point2==2))
            ans=min(3*n-y1-y2, n+y1+y2);

        cout<<ans<<endl;
    }
return 0;
}

Spoj 4038. Counting The Way of Bracket Replacement Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MOD 100000

bool moduloUsed;
LL memo[200+10][200+10];
string s;

LL func(int left, int right)
{
    int i, valid;
    if(left>right)  return 1;

    if(memo[left][right]!=-1)   return memo[left][right];

    LL ret=0;

    for(i=left+1;i<=right;i+=2)
    {
        if(s[left]=='(' && s[i]==')') valid=1;
        else if(s[left]=='{' && s[i]=='}') valid=1;
        else if(s[left]=='[' && s[i]==']') valid=1;
        else if(s[left]=='?' && s[i]==')') valid=1;
        else if(s[left]=='?' && s[i]=='}') valid=1;
        else if(s[left]=='?' && s[i]==']') valid=1;
        else if(s[left]=='(' && s[i]=='?') valid=1;
        else if(s[left]=='{' && s[i]=='?') valid=1;
        else if(s[left]=='[' && s[i]=='?') valid=1;
        else if(s[left]=='?' && s[i]=='?') valid=3;
        else    valid=0;

        ret+=valid*func(left+1,i-1)*func(i+1,right);

        if(ret>MOD)
        {
            moduloUsed=true;
            ret%=MOD;
        }
    }
return memo[left][right]=ret;
}


int main()
{
    LL ans,length;

    while(cin>>length>>s)
    {
        SET(memo);
        ans=func(0,length-1);
        if(!moduloUsed)
        cout<<ans<<endl;
        else
        printf("%05lld\n",ans);
    }

return 0;
}

URAL 1146. Maximum Sum Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
#include<queue>
using namespace std;
#define clr(a) memset(a,0,sizeof(a))
#define PB push_back
#define pi acos(-1.0)
#define eps 1e-9
long sum[120][120];

int main()
{
long n,a,b,c,d,arr[120][120];
long max,temp;
cin>>n;
        {
            max=-100000000;
            for(a=1;a<=n;a++)
                for(b=1;b<=n;b++)
                    cin>>arr[a][b];

            for(a=1;a<=n;a++)
                for(b=1;b<=n;b++)
                    for(c=1;c<=a;c++)
                        for(d=1;d<=b;d++)
                            sum[a][b]+=arr[c][d];

            for(a=1;a<=n;a++)
                for(b=1;b<=n;b++)
                    for(c=1;c<=a;c++)
                        for(d=1;d<=b;d++)
                            {
                                temp=sum[a][b]-sum[a][d-1]-sum[c-1][b]+sum[c-1][d-1];
                                //cout<<sum[a][b]<<" "<<sum[a][d]<<" "<<sum[c][b]<<" "<<sum[c][d]<<endl;
                                //cout<<temp<<endl;
                                if(temp>max)
                                max=temp;
                            }
            cout<<max<<endl;


                }

            //clr(sum);

return 0;
}

URAL 1079. Maximum Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long




int main()
{
    int tc,a[100000],mx,n,i;
    a[0]=0;
    a[1]=1;

    for(i=2;i<100000;i+=2)
    {
        a[i]=a[i/2];
        a[i+1]=a[i/2]+a[i/2+1];
    }
    //cin>>tc;
    while(cin>>n)
    {
        if(n==0) break;
        //cin>>n;
        mx=0;
        for(i=1;i<=n;i++)
            if(a[i]>mx)
                mx=a[i];
        cout<<mx<<endl;

    }
return 0;
}

Spoj 3693. Maximum Sum Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 110000

struct Node{
    LL mx,sum;
};

Node nd[MX*4];

int lazy_value[4*MX];
bool lazy[4*MX];

void update_node(int idx, int st, int ed, LL val)
{
    lazy[idx]=1;
    lazy_value[idx]=val;

    nd[idx].mx=val;
    nd[idx].sum=val;
}

void update_lazy(int idx, int st, int ed)
{
    if(st==ed)    return;

    int mid=(st+ed)/2;

    update_node(2*idx, st, mid, lazy_value[idx]);
    update_node(2*idx+1, mid+1, ed, lazy_value[idx]);
    lazy[idx]=lazy_value[idx]=0;
}

void insert(int idx, int st, int ed, int s, int e, LL val)
{
    if(st==s && ed==e)
    {
        update_node(idx, st, ed, val);
        return;
    }

    //if(lazy[idx]) update_lazy(idx, st, ed);

    int mid=(st+ed)/2;
    if(e<=mid) insert(idx*2, st, mid, s, e, val);
    else insert(idx*2+1, mid+1, ed, s, e, val);
    /*else
    {
        insert(idx*2, st, mid, s, mid, val);
        insert(idx*2+1, mid+1, ed, mid+1, e, val);
    }*/
    //mx[idx]=max(mx[idx*2], mx[idx*2+1]);
    nd[idx].mx = max(nd[idx*2].mx, nd[idx*2+1].mx);
    nd[idx].sum = max3(nd[idx*2].sum, nd[idx*2+1].sum, nd[idx*2].mx + nd[idx*2+1].mx);
    //n[idx].sum = max(n[idx.sum], ;
    return;
}

Node query(int idx, int st , int ed, int s, int e)
{
    if(st==s && ed==e) return nd[idx];

    //if(lazy[idx]) update_lazy(idx, st, ed);

    int mid=(st+ed)/2;
    if(mid>=e)  return query(2*idx, st, mid, s, e);
    else if(s>mid)  return query(2*idx+1, mid+1, ed, s, e);
    else    //return max(query(idx*2, st, mid, s, mid), query(idx*2+1, mid+1, ed, mid+1, e));
    {
        Node ret,a,b;
        a = query(idx*2, st, mid, s, mid);
        b = query(idx*2+1, mid+1, ed, mid+1, e);

        ret.mx = max(a.mx, b.mx);
        ret.sum = max3(a.sum, b.sum, a.mx + b.mx);

        return ret;
    }
}

int main()
{
    int n, i, q, cnt, st, ed;
    LL val;
    char c;
   // string s_line;

    //cin>>n;
    scanf("%d",&n);

    for(i=1;i<=n;i++)
        {
            //cin>>val;
            scanf("%lld",&val);
            insert(1, 1, n, i, i, val);
        }

    //cin>>q;
    scanf("%d",&q);


    while(q--)
    {
        getchar();
        //cin>>c;
        //cin>>st>>ed;
        scanf("%c%d%",&c,&st);

        if(c=='U')
        {
                scanf("%lld",&val);
                insert(1, 1, n, st, st, val);
        }

        else
        {
            scanf("%d",&ed);
            printf("%lld\n",query(1, 1, n, st, ed).sum);
                //cout<<<<endl;

        }
    }

    return 0;
}

Period (Spoj 263, UVa 1328, UVaLive 3026, Regionals 2004 >> Europe - Southeastern)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 1000010

string pattern;
int failur[MX],length_b,cnt;

void FailureFunction()
{
    int i=1,j=0;
    failur[0]=0;
    while(i<length_b)
    {
        if(pattern[i]==pattern[j])
        {
            j++;
            failur[i]=j;
            i++;
        }
        else if(j>0)
            j=failur[j-1];
        else
        {
            failur[i]=0;
            i++;
        }
    }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t,kk=1;
    while(cin>>length_b && length_b)
    {
        cin>>pattern;
        CLR(failur);
        FailureFunction();
        cout<<"Test case #"<<kk++<<endl;

        for(int i=1; i<length_b; i++)
        {
            int miss_matched=i+1-failur[i];
            if((i+1)%miss_matched==0)
                if((i+1)/miss_matched>1)
                    cout<<i+1<<" "<<(i+1)/miss_matched<<endl;
        }
        cout<<endl;
    }
    return 0;
}

Spoj 3921. The Great Ball Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 10000010
#define MOD 1000000007


struct Z{
    int time;
    bool chk;
    bool operator < (const Z &p) const{
    if(time==p.time)
        return chk<p.chk;
    return time>p.time;
    }
};


main()
{
    int t,n,tm,i;
    cin>>t;
    while(t--)
    {
        priority_queue<Z>pq;
        Z TM;
        int cnt=0, mx=0;
        cin>>n;
        for(i=0;i<n*2;i++)
            {
                cin>>tm;
                TM.time=tm;
                if(i%2==0)
                    TM.chk=true;
                else
                    TM.chk=false;
                pq.push(TM);
            }

        for(i=0;i<n*2;i++)
            {
                TM=pq.top();

                if(TM.chk)
                    {
                        cnt++;
                        mx=max(cnt,mx);
                    }
                else
                    cnt--;
                pq.pop();
            }
        //cout<<pq.top().time<<endl;
        cout<<mx<<endl;
    }
}