GFTSHP - Editorial

The problem is that the round function is not doing what you assume. Check round(1.5) and round(2.5) interactively. You can get “half of integer x rounded up” with (x+1)//2 - the double slash is integer division (rounds down).

1 Like

Since you’ve solved it, here’s what I meant about putting the discounted-price test inside the while loop ‘if’:

  while j < n:
    if cost + sorted_prices[j] > k:
      if (cost + ((sorted_prices[j]  + 1) // 2) <= k):
        j += 1
      break
    cost += sorted_prices[j]
    j += 1

  print(j)

and then since use of the price is all inside the one loop you can iterate on the list:

  for a_price in sorted_prices:
    if cost + a_price > k:
      if cost + (a_price + 1)// 2 <= k:
        j += 1
      break
    cost += a_price
    j += 1

  print(j)

Hey, there is an error in your discount function.
First you did

x = a/2

then you are comparing x to a/2, which is essentially the same.
Even if you have initialized x as float, the value of a/2 would still be returned as an integer(rounded off), which then gets converted to float

My suggestion is to better use this:

int Discount(int a){
    int res = a/2;
    if(a%2)res++;
    return res;
}

Hey, the problem is that when you use the accumulate function, there can be an integer overflow since 10^9*10^5 is much greater than the limit of INT.

So either use long long, or better, remove that if condition. The code in the else block works perfectly fine and also covers the case that you have tried to cover in the if block.

can you please tell me where i am wrong ?
`
#include<bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;

while(t--){
    int n,k;
    cin>>n>>k;
    int arr[n];
    
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    sort(arr, arr+n);
    
    int max_amount_spent=0;
    int gift_count=0;
    int last_index_used=-1; 
    for(int i=0; i<n; i++){
        if((max_amount_spent+arr[i]) <=k){
            max_amount_spent=max_amount_spent+arr[i];
            gift_count++;
            last_index_used=i;
        }
    }
    
    if( (max_amount_spent + round(arr[last_index_used+1]/2)) <=k){
        cout<<gift_count+1<<endl;
    }
    else{
        cout<<gift_count<<endl;
    }
    
}
return 0;

}
`

what is wrong with the below code?

t=int(input())
for i in range(t):
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
sum=0
l=0
for i in A:
l=l+1
sum=sum+i
if l==len(A):
print(l)
break
elif sum>=K:
print(l)
break

indentation is correct in my code, here it is not copying correctly