Question Name:Pebbles Game

#include <bits/stdc++.h>
using namespace std;
int col[100005];
long double f(long long int x1, long long int y1, long long int x2, long long int y2)
{
 return sqrtl(powl(x1-x2,2) + powl(y1-y2,2));
}
int main()
{
 int t;
 scanf("%d", &t);
 while(t--)
 {
  int n,m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i)
  {
   scanf("%d", &col[i]);
  }
  sort(col, col+n);
  long double temp_ans = 0;
  temp_ans+=f(col[0],col[1],col[0],col[n-1]);
  temp_ans+=f(col[0],col[n-1],col[n-2],col[n-1]);
  temp_ans+=f(col[n-2],col[n-1],col[n-1],col[n-2]);
  temp_ans+=f(col[n-1],col[n-2],col[n-1],col[0]);
  temp_ans+=f(col[n-1],col[0],col[1],col[0]);
  temp_ans+=f(col[1],col[0],col[0],col[1]);
  long long int fans = ceill(temp_ans);
  fans*=m;
  printf("%lld\n", fans);
 
 }
 return 0;
}
  • Problem Description
    Given 2N 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).

    Input Format:

    First line consists of an integer T denoting the number of test cases. The First line of each test case consists of two space separated integers denoting N and M.

    The next line consists of N space separated integers, where the ith integer is A[i], and denotes that we have been given exactly 2 pebbles of color equal to A[i]. It is guaranteed that A[i]!=A[j], if i!=j

    Output Format:

    Print the minimum cost as asked in the problem in a separate line for each test case.

    Constraints:

    1<=T<=50
    3<=N<=10^5
    1<=M<=10^5
    1<=A[i]<=10^6 

    where 1<=i<=N
  • Test Case 1
    Input (stdin)1
    3 5
    1 2 3
    Expected Output35
  • Test Case 2
    Input (stdin)1
    2 8
    1 2 6
    Expected Output24

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.