CPP Program Interesting Sequences – Adhoc Problems

by
  • Professor Jain has a class full of notorious students. To get anything done from them is a herculean task. Prof Jain wanted to organize a test. He gave this responsibility to Aahad. Aahad did an excellent job of organizing the test. As a reward, the professor gave him a sequence of numbers to play with. But Aahad likes playing with “interesting” sequences of numbers, which are sequences that have equal elements.
  • Now, the problem is Prof Jain has a sequence with elements, and that sequence isn’t always “interesting”. To ensure the sequence has equal elements, Prof Jain has 2 options:
    1. Choose two elements of the sequence. DECREASE the first element by 1 and INCREASE the second element by 1. This operation costs ‘k’ coins.
    2. Choose one element of an array and INCREASE it by 1. This operation costs ‘l’ coins.
  • What’s the minimum number of coins Prof Jain needs to turn his sequence into an “interesting” sequence for Aahad?

Input Format:

  • The first line of input contains three space-separated integers: n, k, and l. Integer n is the size of the array. Integer k is the number of coins needed to perform the first operation. Integer l is the number of coins needed to perform the second operation.
  • The second line contains n integers: (a1, a2, a3… an) representing sequence.

Constraints:

1 <= n, k, l <= 1000
1 <= ai <= 1000
Time Limit: 1 second

Output Format:

  • In a single line, print one integer number: the minimum number of coins required to make an “interesting” sequence.

Sample Test Cases:

Sample Input 1:

4 1 2
3 4 2 2

Sample Output 1:

3

Explanation Output 1:

  • The professor has a sequence with 4 elements. To perform the first operation, they must pay 1 coin, and to perform the second operation, they must pay 2 coins. The optimal strategy is:
  • Perform the second operation on the fourth element. Now the sequence is {3, 4, 2, 3}. This costs 2 coins.
  • Perform the first operation on the second and third elements. The sequence is now “interesting”, and it looks like {3, 3, 3, 3}. This costs 1 coin.
  • The total amount of coins needed is 2 + 1 = 3.

Sample Input 2:

3 2 1
5 5 5

Sample Output 2:

0

Explanation Output 2:

The given sequence is already “interesting”. The professor would spend 0 coins.

Sample Input 3:

5 2 1
1 2 3 4 5

Sample Output 3:

6

Explanation Output 3:

  • The professor has a sequence with 5 elements. To perform the first operation, they must pay 2 coins, and to perform the second operation, they must pay 1 coin. The optimal strategy is:
  • Perform the first operation on the first and last element. Now the sequence is {2, 2, 3, 4, 4}. This costs 2 coins.
  • Perform the first operation again on the first and last elements. Now the sequence is {3, 2, 3, 4, 3}. This costs 2 coins.
  • Perform the first operation on the second and second last element. Now the sequence is {3, 3, 3, 3, 3}. This costs 2 coins.
  • The total amount of coins needed is 2 + 2 + 2 = 6.

Code:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;
long long cost_calculator(vector<long long>v, long long k, long long l, long long n, long long number)
{
	long long increment = 0;
	long long decrement = 0;
	for(long long i=0; i<n; i++)
	{
		if(v[i]>number)
		{
			decrement += v[i] - number;
		}
		else if(v[i]<number)
		{
			increment += number - v[i];
		}
	}
	if(decrement>increment)
	{
		return INT_MAX;
	}
	return (decrement * k) + ((increment - decrement)*l);
}
int main()
{
	long long n, k, l;
	cin >> n >> k >> l;
	vector<long long>v;
	for(long long i=0; i<n; i++)
	{
		long long element;
		cin >> element;
		v.push_back(element);
	}
	long long minimum=9999999, maximum=-1;
	for(long long i=0; i<n; i++)
	{
		if(v[i]<minimum)
		{
			minimum = v[i];
		}
		if(v[i]>maximum)
		{
			maximum = v[i];
		}
	}
	long long cost = INT_MAX;
	for(long long i=minimum; i<=maximum; i++)
	{
		cost = min(cost, cost_calculator(v, k, l, n, i));
	}
	cout << cost;
}
Code language: C/AL (cal)

Leave a Comment