The easiest segment tree problem. Lightoj-1082

1082 - Array Queries  

First read about Segment tree in English or In Bangla ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-১.

 Implemented in C:

#include<stdio.h>
#define mx 100009
int arr[mx];
int tree[mx*3];
void init(int NowNode,int L,int R) /** Building segment tree **/
{
    if(L==R)
    {
        tree[NowNode]=arr[L];
        return;
    }
    int left = NowNode*2;
    int right = NowNode*2+1;

    int mid = (L+R)/2;

    init(left,L,mid);
    init(right,mid+1,R);
    if(tree[left]<tree[right])
        tree[NowNode]=tree[left];
    else
        tree[NowNode]=tree[right];
}

int Query(int NowNode,int L,int R,int p,int q) /** Query **/
{
    if(p>R|| q<L)
    {
        return 9999999;
    }
    if(L>=p && R<=q)
        return tree[NowNode];

    int left = NowNode*2;
    int right = NowNode*2+1;
    int mid = (L+R)/2;
    int p1 = Query(left,L,mid,p,q);

    int p2 = Query(right,mid+1,R,p,q);
    if(p1<p2)
        return p1;
    else
        return p2;
}


int main()
{
    int n,j,m,k,p,q;
    int i,test;

    scanf("%d",&test);
    for(j=1;j<=test;j++)
    {
        getchar();
        scanf("%d%d",&n,&m);

        for(k=1;k<=n;k++)
        {
            scanf("%d",&arr[k]);
        }
        init(1,1,n);
        printf("Case %d:\n",j);
        for(k=1;k<=m;k++)
        {
            scanf("%d%d",&p,&q);
             printf("%d\n",Query(1,1,n,p,q));
        }
    }
    return 0;
}

Lightoj-1212 - Double Ended Queue

 
The simple deque implementation problem.

C++ Code (STL deque).

#include<bits/stdc++.h>
#define file freopen("lightoj.txt","rt",stdin)
using namespace std;

int main()
{
  //  file;
    deque<int>d;
    string str;
    int n,m,a,val,test;
    cin>>test;
    for(int j=1; j<=test; j++)
    {
        d.clear();

        printf("Case %d:\n",j);
        cin>>n>>m;

        for(int i=1; i<=m; i++)
        {
            cin>>str;
            if(str=="pushLeft")
            {
                cin>>a;
                if(d.size()<n)
                {
                    d.push_front(a);
                    cout<<"Pushed in left: "<<a<<endl;
                }
                else
                    cout<<"The queue is full"<<endl;
            }
            else if(str=="pushRight")
            {
                cin>>a;
                if(d.size()<n)
                {
                    d.push_back(a);
                    cout<<"Pushed in right: "<<a<<endl;
                }
                else
                    cout<<"The queue is full"<<endl;

            }
            else if(str=="popLeft")
            {

                if(!d.empty())
                {
                    val = d.front();
                    d.pop_front();
                    cout<<"Popped from left: "<<val<<endl;
                }
                else
                    cout<<"The queue is empty"<<endl;
            }
            else
            {
                if(!d.empty())
                {
                    val = d.back();
                    cout<<"Popped from right: "<<val<<endl;
                    d.pop_back();
                }
                else
                    cout<<"The queue is empty"<<endl;
            }
        }
    }
    return 0;
}

Lightoj 1305 - Area of a Parallelogram.

N:B Please don't copy source code.Try to find out the geometrical logic and work hard.

There are 2 or more solution of this problem. I have mentioned one by commenting by uses matrix formula for finding area of quadrilateral.

Or read again the problem.

 C program:

#include<stdio.h>
int main()
{

    double Ax,Ay,Bx,By,Cx,Cy,x,y;
    double a,b,c,ans,s,d,h;
    int i,test;
    scanf("%d",&test);
    for(i=1; i<=test; i++)
    {
        scanf("%lf %lf %lf %lf %lf %lf",&Ax,&Ay,&Bx,&By,&Cx,&Cy);
        x=Ax+Cx-Bx;
        y=Ay+Cy-By;
        a=sqrt((Ax-Bx)*(Ax-Bx)+(Ay-By)*(Ay-By));
        b=sqrt((x-Ax)*(x-Ax)+(y-Ay)*(y-Ay));
        c=sqrt((x-Bx)*(x-Bx)+(y-By)*(y-By));
        s=(a+b+c)/2.0;
        d = sqrt(s*(s-a)*(s-b)*(s-c));
       // ans = .5*fabs((Ax*By+Bx*Cy+Cx*y+x*Ay)-(Ax*y+x*Cy+Cx*By+Bx*Ay));/** Matrix solution **/

        printf("Case %d: %.0lf %.0lf %.0lf\n",i,x,y,2*d);
    }
    return 0;
}