Algorithm
Problem link- https://www.spoj.com/problems/ACPC11B/
ACPC11B - Between the Mountains
Did you try to ride a telepherique (cable car)? It is a lot of fun. Our company is trying to build a new telepherique line between two high mountains and you will be invited for a free ride. The trick to get your free ride is to help the company in building the telepherique line.
The company wants to build two platforms, one on each mountain. The line will extend between these two platforms. The suitable points for holding a platform in each mountain were determined, and the altitudes of these points were reported.
One of the talented engineers suggested that the company can save a lot of energy if the two stations have the same altitude or at least have altitudes which are as close to each other as possible. Your job is to select two points, one at each mountain, from those suitable points, so that the altitude difference between the two points is as little as possible.
Input
Your program will be tested on one or more test cases. The first line of the input will be a single integer T , the number of test cases (1 ≤ T ≤ 100). Follows 2T lines containing the test cases, each on a pair of lines.
Each of the two lines in a case describe the altitudes of suitable points to build a platform on one mountain. Each line starts with an integer N , the number of reported altitudes (1 ≤ N ≤ 1,000), followed by N integers, which represent the altitudes reported from this mountain. Any altitude value will be between 1 and 1,000,000, inclusive.
Output
For each test case, output, on a single line, a single number representing the minimum
altitude difference between two suitable platform points, one at each mountain.
Example
Input: 2 8 1 3 5 7 9 7 3 1 8 2 4 6 8 10 8 6 2 8 2 3 5 10 9 3 2 1 7 1 2 6 12 13 3 2 Output: 1 0
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
int m;
scanf("%d",&m);
int temp=m;
long a[m];
while(m--){
scanf("%ld",&a[m]);
}
sort(a,a+temp);
int n;
scanf("%d",&n);
int temp1=n;
long b[n];
while(n--){
scanf("%ld",&b[n]);
}
sort(b,b+temp1);
long int minabs=1000000;
//cout<<minabs<<endl;
for(int i=0;i<temp;i++){
for(int j=0;j<temp1;j++){
minabs=min(minabs,abs(a[i]-b[j]));
//cout<<minabs<<endl;
}
}
printf("%ld\n",minabs);
}
return 0;
}Input
8 1 3 5 7 9 7 3 1
8 2 4 6 8 10 8 6 2
8 2 3 5 10 9 3 2 1
7 1 2 6 12 13 3 2
Output
0
#2 Code Example with Java Programming
Code -
Java Programming
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,a,tc;
scanf("%d",&tc);
while(tc--){
scanf("%d",&n);
vector<int> v1(n);
for(int i=0; i<n; i++) scanf("%d",&v1[i]);
scanf("%d",&m);
vector<int> v2(m);
for(int i=0; i<m; i++) scanf("%d",&v2[i]);
sort(v1.begin(), v1.end());
int ans = INT_MAX;
for(int i=0; i<m; i++){
int id = lower_bound(v1.begin(), v1.end(), v2[i]) - v1.begin();
if(id>0) ans= min(ans, abs(v1[id-1] - v2[i]));
if(id==n) continue;
ans= min(ans, abs(v1[id] - v2[i]));
}
printf("%d\n",ans);
}
}Input
8 1 3 5 7 9 7 3 1
8 2 4 6 8 10 8 6 2
8 2 3 5 10 9 3 2 1
7 1 2 6 12 13 3 2
Output
0
#3 Code Example with C Programming
Code -
C Programming
#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;
}Input
8 1 3 5 7 9 7 3 1
8 2 4 6 8 10 8 6 2
8 2 3 5 10 9 3 2 1
7 1 2 6 12 13 3 2
Output
0
Demonstration
SPOJ Solution-ACPC11B Between the Mountains- Solution in C, C++, Java, Python ,ACPC11B,SPOJ Solution