 # JMARKET - Editorial

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

Cakewalk

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 + v << 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;
cin>>a>>a>>a;
sort(a, a+3);

cout<<(x-1)*a + a<<endl;
}
return 0;
}

1 Like