PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Pranav Dev
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta
DIFFICULTY:
Simple
PREREQUISITES:
Sorting
PROBLEM:
Chef wants to impress Chefina by giving her the maximum number of gifts possible.
Chef is in a gift shop having N items where the cost of the i^{th} item is equal to A_{i}.
Chef has K amount of money and a 50 \% off discount coupon that he can use for at most one of the items he buys.
If the cost of an item is equal to X, then, after applying the coupon on that item, Chef only has to pay {\bf \left\lceil \frac{X}{2} \right\rceil} (rounded up to the nearest integer) amount for that item.
Help Chef find the maximum number of items he can buy with K amount of money and a 50 \% discount coupon given that he can use the coupon on at most one item.
EXPLANATION:
Let M be the maximum number of items that Chef will buy, and let \{i_1, i_2, \ldots i_M\} be the list of items that costs minimum among all possible list of items of size M. Also, let S = \sum_{\alpha = 1}^{M} A_{i_{\alpha}}
Observation 1: Chef will always use the discount coupon on the most expensive item. This is because the amount of money that Chef will pay will be S - discount, and as the price increases, the discount increases.
Observation 2: The list of items will have the M lowest priced items. To prove this, let us introduce a new item j in the list of items and remove i_\alpha such that A_{i_\alpha} < A_j. We can make 4 cases on {discount on A_{i_\alpha}, discount on A_{j}} and in each case, we can see that the original list results in less overall cost.
So we can first sort the items in the increasing order of price, and for each i such that 1 \leq i \leq N, check if we can take first i elements by applying discount on the i^{th} item. The largest feasible i will be our answer.
TIME COMPLEXITY:
O(N \cdot \log{N}) for each test case.
SOLUTION:
Editorialist's Solution
#define ll long long
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#include<bits/stdc++.h>
using namespace std ;
void solve()
{
ll n , k ;
cin >> n >> k ;
ll arr[n] ;
for(int i = 0 ; i < n ; i++)
cin >> arr[i] ;
sort(arr , arr+n) ;
ll sum = 0, ans = 0;
for(ll i = 0 ; i < n ; i++)
{
ll new_cost = (arr[i] + 1)/2 ; // ceil division
if(sum + new_cost <= k)
{
ans++ ;
sum += arr[i] ; // updating sum for next iteration
}
else
break ;
}
cout << ans << '\n' ;
return ;
}
int main()
{
ll t = 1 ;
cin >> t ;
while(t--)
{
solve() ;
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}