CodeChef Starters 30 Division 4 (Rated) Gift Shop and Coupon Problem Code: GFTSHP Solution

 

Problem Link:  https://www.codechef.com/problems/GFTSHP

 Solution in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int  n,t,i,r,k,s,c,f,d;

    cin>>t;

    while(t--)

    {

        s=r=f=0;

        cin>>n>>k;

        int a[n+9];

        for(i=0; i<n; i++)

            cin>>a[i];

        sort(a,a+n);

        if(n>1)

        {

            {

                for(i=0; i<n; i++)

                {

                    s+=a[i];

                    if(s>=k)

                    {

                        s-=a[i];

                        f=1;

                        break;

                    }

                    else

                        r++;

                }

                if(a[r]%2==1)

                    d=a[r]/2+1;

                else

                    d=a[r]/2;

                s=s+d;

                if((s<=k)&&(f==1))

                    cout<<r+1<<endl;

                else

                    cout<<r<<endl;

            }

        }

        else if(n==1)

        {

            if(a[0]%2==1)

            {

                d=a[0]/2+1;

                if(d<=k)

                    cout<<"1"<<endl;

                else

                    cout<<"0"<<endl;

            }

            else

            {

                d=a[0]/2;

                if(d<=k)

                    cout<<"1"<<endl;

                else

                    cout<<"0"<<endl;

            }

        }

    }

}