PROBLEM LINK:
Practice
Setter: Charan Narukulla
Tester: Abhilash Movva
DIFFICULTY:
Easy
PREREQUISITES:
Math,Sorting
PROBLEM:
You are going to your college via bike/scooter/car. You need to increase your speed to reach the college as soon as possible. Your speed right now is divided into N parts with their values S(i) (given). You can increase your speed X number of times by increasing any value by S(i)/2. Consider floor value if the speed is odd. You always try to increase the speed very few times and speed to be high. You can’t change the speed more than N times and can’t change the same speed again. Finally, you need to maintain the total speed ≥40 to reach the college on time. Print minimum number of times you need to change the speed, total speed, YES if you can reach the college on time else NO.
EXPLANATION:
Take the speed divisions and sort them in descending order. This gives us the minimum number of changes needed. Increase each value by S(i)/2 and add excess value obtained to the sum of the speeds. if sum of the speeds is ≥40 initially the number of changes =0. break the process until this condition is met. if this condition never become true for the given set of speeds then its not possible to reach on time.
Setter's Solution
//ADD headers here
using namespace std;
int main() {
// your code goes here
int T;
cin>>T;
while(T–){
int N;
cin>>N;
int speed[N];
int totalspeed=0;
for(int i=0;i<N;i++){
cin>>speed[i];
totalspeed+=speed[i];
}
if(totalspeed>=40){
std::cout << 0<<" "<<totalspeed<<" "<<"YES" << std::endl;
}
else{
sort(speed,speed+N,greater<int>());
int X=0;
for(int i=0;i<N;i++){
int ic=speed[i]/2;
X++;
totalspeed+=ic;
if(totalspeed>=40)
break;
}
if(totalspeed>=40)
std::cout << X<<" "<<totalspeed<<" YES" << std::endl;
else
std::cout << X<<" "<<totalspeed<<" NO" << std::endl;
}
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t–){
int n,sum=0;
cin >> n;
int s[n];
for(int i=0; i<n; i++){
cin >> s[i];
sum += s[i];
}
if(sum>=40){
cout << “0” << " " << sum << " " << “YES\n”;
}
else{
sort(s, s+ n, greater());
int cnt=0;
for(int i=0; i<n; i++){
int t = s[i] / 2;
if(t%2!=0) floor(t);
sum+=t;
cnt++;
if(sum>=40) break;
}
if(sum>=40) cout << cnt << " " << sum << " " << “YES\n”;
else cout << cnt << " " << sum << " " << “NO\n”;
}
}
return 0;
}