PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Abhinav Sharma
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
There are two types of vehicles in Chefland.
- Bus has a capacity of 100 people.
- Car has a capacity of 4 people.
There are N people who want to travel. You know that a single bus emits X units of smoke while a single car emits Y units of smoke.
You want to arrange some buses and cars to carry all these N people such that total smoke emitted is minimised. Output the minimised smoke value.
EXPLANATION:
Consider a batch of 100 people.
If we arrange buses for them, we would require only 1 bus and the total smoke emitted would be X units.
On the other hand, if all of them travel by car, we would need \frac{100}{4} = 25 cars. The total smoke emitted by cars would be 25 \cdot Y units.
It is optimal to use a bus for all these people only if X \leq 25 \cdot Y. Else, we use a car.
The total smoke emitted for the commute of these 100 people is min(X, 25 \cdot Y).
Note that for this batch 100 people, it is never optimal to use both the vehicles.
Why?
Let us assume we use 1 bus and C cars (C>0) for these 100 people. Note that using more than one bus would never be optimal as 1 bus has a capacity of 100 people.
Now, the total smoke emitted would be X + C\cdot Y. Since X + C\cdot Y >X, it is better to use only the bus instead of both bus and car.
We divide all the people into batches of 100 and calculate the answer for each batch.
For the remaining N' people (N'<100), we require either 1 bus or C = ceil(\frac{N'}{4}) cars. Minimum smoke emitted for the commute of these N' people is min(X, C \cdot Y).
The total answer would be the sum of answers of all batches of 100 people and the answer for the batch of remaining people (which is less than 100).
TIME COMPLEXITY:
If we calculate the answer for each batch of 100 people separately, the complexity would be O(\frac{N}{100}).
However since the answer for each batch of 100 people would be the same, we can calculate the answer in O(1) for each test case.
The time complexity is O(1) per test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int x, y;
cin>>x>>y;
int smoke = 0;
while(n>=100){
int busSmoke = x;
int carSmoke = 25*y;
smoke += min(busSmoke, carSmoke);
n -= 100;
}
if(n>0){
int cars = ceil(n/4.0);
int carSmoke = cars * y;
int busSmoke = x;
smoke += min(busSmoke, carSmoke);
}
cout<<smoke<<endl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
cin >> T;
while(T--){
int n,x,y;
cin>>n>>x>>y;
int ans = 10*x;
rep(i,10){
ans = min(ans, i*x+((max(0,n-100*i)+3)/4)*y);
}
cout<<ans<<el;
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int x, y;
cin>>x>>y;
int smoke = 0;
//for batches of 100
int buses = n/100;
int cars = buses * 25;
int busSmoke = buses * x;
int carSmoke = cars * y;
smoke = min(busSmoke, carSmoke);
n = n%100;
//for all people left
if(n>0){
int cars = ceil(n/4.0);
int carSmoke = cars * y;
int busSmoke = x;
smoke += min(busSmoke, carSmoke);
}
cout<<smoke<<endl;
}
return 0;
}
