Saturday, 4 July 2015

ACPC11B

Standard

Between the Mountains

Link to the question : ACPC11B

HINT :

The question asks us to find the minimum difference between two mountains. This can be done with the naive solution, i.e, checking each element with every other element. The time limit allows us to do this.

RECOMMENDED QUESTION :

Try this question .

SOURCE CODE :

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int a[n],i;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        int m;
        scanf("%d",&m);
        int b[m];
        for(i=0;i<m;i++)
            scanf("%d",&b[i]);
        int diff=1000000,s,j;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(a[i]>b[j])
                    s= a[i]-b[j];
                else
                    s= b[j]-a[i];
                if(s<diff)
                    diff=s;


            }
        }
        printf("%d\n",diff);
    }
    return 0;
}

5 comments:

  1. Is there any other method to solve this problem

    ReplyDelete
    Replies
    1. This might be done using binary search but I have not tried it yet.

      Delete
  2. Replies
    1. Sort the altitudes of first mountain. Now for each altitude on the second mountain, lets call it x, do a binary search on the altitudes of first mountain and find the smallest altitude greater than equal to x and the largest altitude smaller than x. Take difference of both with x and store the minimum. The minimum value for all the x will be the answer.

      Delete
    2. Another approach can be found here :
      http://comproguide.blogspot.in/2013/12/minimum-difference-between-two-sorted.html

      Delete