Codeforces Round #271 (Div. 2) 474B Worms

Solution to Codeforces Round #271 (Div. 2) 474B Worms With Explanation

       Kindly comment if you have any other best solution or found any errors in my program.

Explanation:

        In this problem, all the worms in the packs are numbered consecutively. You have to find, in which pack the 'q'th worm resides. Binary search technique should be used as the bubble sort will give you a TLE.

Steps:

• Get the number of worms in each pack in an array.
• While getting worms in each pack maintain the sum of the all the worms till that particular pack in another array s[].
• Then sort array 'S' as the binary search works only on a sorted array.
• Then get the label of the juicy worm and search it in the array 'S' using binary search.
• Repeat until finish searching all the juicy worms in the array.

Program:

//    Accepted                                                                            592ms                             800KB

#include<iostream>
using namespace std;
int binarysearch(int low,int high,int q,int s[])
{
    int index;
    if(low>high)
        index=0;
    else
        {
    int mid=(low+high)/2;
    if(q==s[mid])
        index=mid+1;
    else{
            if(q<s[0])
               return 1;
    if((q>s[mid])&&(q<s[mid+1]))
        index=mid+2;
    else if(q<s[mid])
        index=binarysearch(low,mid-1,q,s);
    else
        index=binarysearch(mid+1,high,q,s);
    }
    }
    return index;
}
int main()
{
    int n,m;
    cin>>n;
    int a[n],sum=0,s[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum=sum+a[i];
        s[i]=sum;
    }
    cin>>m;

   while(m--)
   {
       int q;
       cin>>q;
       cout<<binarysearch(0,n,q,s)<<endl;;
   }
   return 0;
}

Codeforces Round #280 (Div. 2) 492B Vanya and Lanterns

Solution to Codeforces Round #280 (Div. 2) 492B Vanya and Lanterns With Explanation

         Kindly comment if you have any other best solution or found any errors in my program.


Explanation:

       In this problem, you need to find the light radius R of a lantern that is the distance covered by a lantern in a direction.
       Each lantern can cover twice the radius in the street. 

Steps:

• Get the position of lanterns in an array. 
• Then sort this array using sort function.
• Find the maximum distance between adjacent lanterns by walking through the sorted array and divide that max_distance by 2 to obtain the radius.
• Now the tricky part is comparing that radius with the position of lanterns at both ends.
• If the lanterns at both ends placed are at the exact starting and ending position of street, you can compare as it is.
• If they are not placed at the exact starting or end position, the 1st lantern has to cover all distance before it and last lantern should cover distance after it..
• So compare the max_distance with starting or ending position of lanterns.
• Then print it.

        

Program:

//    Accepted                                                                                            31ms                             4KB

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<iomanip>

using namespace std;

int main()

{

    int nl,l;

    int lb,rb;

    cin>>nl>>l;

    int a[nl],dia=0;

    float max_distance=0;

    for(int i=0;i<nl;i++)

        cin>>a[i];

        sort(a,a+nl);

        for(int i=1;i<nl;i++)

        {

            dia=a[i]-a[i-1];

            if(float(dia)>max_distance)

                max_distance=float(dia);

        }

        max_distance=max_distance/2;

        lb=a[0],rb=l-a[nl-1];

        if(float(lb)>max_distance)

            max_distance=float(lb);

        if(float(rb)>max_distance)

            max_distance=float(rb);

        printf("%.10f",max_distance);

        return 0;

}

Codeforces Round #223 (Div. 2) 381A Sereja and Dima

Solution to Codeforces Round #223 (Div. 2) 381A Sereja and Dima with explanation

           Kindly comment if you have any other best solution or found any errors in my program.

Explanation:
       This program uses greedy technique i.e. each player wants to take a card with high score.

Steps:

• Get the score of n cards in an array.

• Let i and j points to start and end of the array respectively.

• Then compare i and j to and choose the maximum of both.

• Add the choosen cards score to the corresponding player.

• The player turn can be identified by variable 'k' . If k is even player 1 turn, otherwise player 2 turn.

• Continue until i and j crosses each other.

Program:

//    Accepted                                                                                            31ms                             4KB

#include<iostream>

using namespace std;

int main()

{

    int n;

    cin>>n;

    int a[n];

    for(int i=0;i<n;i++)

        cin>>a[i];

    int i=0,j=n-1,max,k=0;

    int play1=0,play2=0;

    while(i<=j)

    {

        if(a[i]>=a[j])

        {

           max=a[i];

           i++;

        }

        else{

            max=a[j];

            j--;

        }

        if(k%2==0)

          play1=play1+max;

        else

          play2=play2+max;

     k++;

    }

    cout<<play1<<" "<<play2<<endl;

    return 0;

}