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.

Powered By
CHP Adblock Detector Plugin | Codehelppro