Gangs of Dholakpur-Cumulative Weight Problem

In the school of Dholakpur the gang having the greatest number of cumulative weight dominates.

Currently Kalia’s gang dominates with cumulative weight M.Since, Kalia’s gang is abusive so, Bheem decides to end this and establish peace in the school.

Bheem can only defeat Kalia if the cumulative weight of his team is strictly greater than that of cumulative weight of Kalia’s team.

The cumulative of weight of Bheem’s team is N, which is smaller than M.

So, he secretly conducts auditions to recruit one more member to his gang in order to defeat Kalia.

The auditioning L student’s weight(w) is represented by the array A.

Given L,N,M and A find the number of possible ways in which Bheem can choose single student to become the dominant gang.

SAMPLE INPUT

1

5 6 11

1 3 5 7 9

SAMPLE OUTPUT

2

Explanation

Input:

The first line contains the number of test cases T.

Following T lines contains 3 numbers L, N, M and the next line contains the array A of size L.

Output:

Print the total number of possible ways in which Bheem can choose a student to become the dominant gang. If there is no such possible way print 0.

Constraints:

0<=T<=100

0<=L,N,M<=10^4

Sample Input

1

5 6 11

1 3 5 7 9

Output

2

Explanation

Weight of Bheem’s team is 6 and that of Kalia’s team is 11. In order to outweigh Kalia’s team, Bheem’s team needs a student whose weight when added to the current weight of Bheem’s team, makes Bheem’s team the dominant one.

So, the students with weight 7 or 9 can be selected because after selecting them, the weight of Bheem’s team will be 13 or 15 respectively, which is strictly greater than 11, i.e. the weight of Kalia’s Team.

Time Limit:3.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

SOURCE CODE in Python : :

for i in range(input()):
        l,n,m=map(int,raw_input().split())
        arr=sorted(map(int,raw_input().split()))
        for j in range(l):
                if arr[j] > m-n:
                        break
        print l-j

SOURCE CODE in C++ : :

#include<iostream>
using namespace std;
 
int main()
{
    int t,l,m,n,num;
    
    cin>>t;
 
for(int j=1;j<=t;j++)
{
    cin>>l;
    cin>>n;
    cin>>m;
    int count=0;
    for(int i=0;i<l;i++)
    {
 
       cin>>num;
       if((n+num)>m)
       {
           count++;
       }
 
    }
 
    cout<<count<<endl;
}
 
 
 
    return 0;
 
}

OUTPUT : :

>>> 
================= RESTART: C:\Users\First.py =================
2
5 6 11
1 3 5 7 9
2

7 3 4
1 2 3 4 5 6 7 
6
>>>

5 1 vote

Article Rating