JMARKET - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Janmansh Agarwal
Tester: Takuki Kurokawa
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Cakewalk

PREREQUISITES:

Greedy

PROBLEM:

Janmansh is at the fruit market to buy fruits for Chingari. There is an infinite supply of three different kinds of fruits with prices A, B and C.

He needs to buy a total of X fruits having at least 2 different kinds of fruits. What is the least amount of money he can spend to buy fruits?

EXPLANATION:

  • It is always optimal to choose the fruit with the lowest price.
  • To have 2 different kinds of fruits, we can select exactly one fruit not having the lowest price.

Without the loss of generality, let us assume A \leq B \leq C.

To have the minimum price for buying X fruits having at least 2 different kinds of fruits, we can buy (X-1) fruits with cost A and 1 fruit with cost B.

Thus, the answer is (X-1)\cdot A + B (where A \leq B \leq C).

TIME COMPLEXITY:

Sorting 3 elements takes constant time. Thus, the time complexity is O(1) per test case.

SOLUTION:

Tester's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int x, a, b, c;
        cin >> x >> a >> b >> c;
        vector<int> v = {a, b, c};
        sort(v.begin(), v.end());
        cout << (x - 1) * v[0] + v[1] << endl;
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int x;
	    cin>>x;
	    
	    int a[3];
	    cin>>a[0]>>a[1]>>a[2];
	    sort(a, a+3);
	    
	    cout<<(x-1)*a[0] + a[1]<<endl;
	}
	return 0;
}
1 Like