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:
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;
}