In this HackerEarth Pebbles Game problem solution, we have given 2 * N pebbles of N different colors, where there exists exactly 2 pebbles of each color, you need to arrange these pebbles in some order on a table. You may consider the table as an infinite 2D plane.

The pebbles need to be placed under some restrictions :

You can place a pebble of color X, at a coordinate (X,Y) such that Y is not equal to X, and there exist 2 pebbles of color Y.
In short consider you place a pebble of color i at co-ordinate (X,Y). Here, it is necessary that  (i = X),(i != Y)  there exist some other pebbles of color equal to Y.

Now, you need to enclose this arrangement within a boundary , made by a ribbon. Considering that each unit of the ribbon costs M, you need to find the minimum cost in order to make a boundary which encloses any possible arrangement of the pebbles. The ribbon is sold only in units (not in further fractions).


HackerEarth Pebbles Game problem solution


HackerEarth Pebbles Game problem solution.

#include<bits/stdc++.h>
#define INF 1000000001
using namespace std;
#define ll long long
#define dd double
int main()
{
int t;
scanf("%d",&t);
while(t--){
ll n,i,m;
scanf("%lld %lld",&n,&m);
ll max1=0,max2=0,min1=INF,min2=INF;
for(i=0;i<n;i++)
{
ll temp;
scanf("%lld",&temp);
(min1>temp)?min2=min1,min1=temp:min2=min(min2,temp);
(max1<temp)?max2=max1,max1=temp:max2=max(max2,temp);
}
ll ans=0;
//cout<<max1<<" "<<max2<<" "<<min1<<" "<<min2<<endl;
ans=((max1-min2+max2-min1)<<1)+(ll)(ceil(((long double)(min2-min1+max1-max2))*sqrt(2)));
printf("%lld\n",ans*m);}
return 0;
}

Second solution

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350

using namespace std;

const int INF = 1e9;
const int N = 110000;

int tests;
int n, m;
double ans;
int ar[N];

int main(){
ios_base::sync_with_stdio(0);
//cin.tie(0);

cin >> tests;
for (; tests; --tests)
{
cin >> n >> m;
ans = 0;

for (int i = 0; i < n; i++)
{
cin >> ar[i];
}
sort(ar, ar + n);
ans = (ar[n - 1] - ar[1] + ar[n - 2] - ar[0]) * 2;
ans += sqrt(2.0)*(ar[1] - ar[0] + ar[n - 1] - ar[n - 2]);
long long Rounded = (ans + 1.0 - eps);
cout << Rounded*m << endl;
}

cin.get(); cin.get();
return 0;
}