# Chef and Division 3 DIVTHREE SOLUTION Code Chef

Page Contents

## Chef and Division 3 DIVTHREE SOLUTION Code Chef

Chef wants to host some Division-3 contests. Chef has N setters who are busy creating new problems for him. The ith setter has made Ai problems where 1≤i≤N.Chef and Division 3 DIVTHREE SOLUTION

A Division-3 contest should have exactly K problems. Chef wants to plan for the next D days using the problems that they have currently. But Chef cannot host more than one Division-3 contest in a day.

Given these constraints, can you help Chef find the maximum number of Division-3 contests that can be hosted in these D days?

Input:

The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains three space-separated integers – N, K and D respectively.

The second line of each test case contains N space-separated integers A1,A2,…,AN respectively.

Output:

For each test case, print a single line containing one integer ― the maximum number of Division-3 contests Chef can host in these D days.

Constraints

1≤T≤103

1≤N≤102

1≤K≤109

1≤D≤109

1≤Ai≤107 for each valid i

Subtask #1 (40 points):

N=1

1≤A1≤105

Subtask #2 (60 points): Original constraints

Sample Input:

5

1 5 31

4

1 10 3

23

2 5 7

20 36

2 5 10

19 2

3 3 300

1 1 1

Sample Output:

0

2

7

4

1

Explanation:

• Example case 1: Chef only has A1=4 problems and he needs K=5 problems for a Division-3 contest. So Chef won’t be able to host any Division-3 contest in these 31 days. Hence the first output is 0.
• Example case 2: Chef has A1=23 problems and he needs K=10 problems for a Division-3 contest. Chef can choose any 10+10=20 problems and host 2 Division-3 contests in these 3 days. Hence the second output is 2.
• Example case 3: Chef has A1=20 problems from setter-1 and A2=36 problems from setter-2, and so has a total of 56 problems. Chef needs K=5 problems for each Division-3 contest. Hence Chef can prepare 11 Division-3 contests. But since we are planning only for the next D=7 days and Chef cannot host more than 1 contest in a day, Chef cannot host more than 7 contests. Hence the third output is 7.Chef and Division 3 DIVTHREE SOLUTION

## Solution

Program Python:

```try:
T=int(input())
for _ in range(T):
N,K,D = map(int,input().split())
arr = list(map(int,input().split()))

if(sum(arr)<K):
print(0)
else:
res=sum(arr)//K
if res>D:
print(D)
else:
print(res)

except:
pass
```

Program C++:

```#include <iostream>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t--) {
int n;
long k,d;
cin>>n>>k>>d;
long long total = 0;
long A[n] = { 0 };
for(int i=0;i<n;i++) {
cin>>A[i];
total += A[i];
}
// long long max = k * d;
long days = total / k;
if (days > d) {
cout<<d<<endl;
} else {
cout<<days<<endl;
}
}
return 0;
}
```

Program Java:

```import java.util.*;
import java.lang.*;
import java.io.*;
class div3
{
public static void main (String[] args) throws java.lang.Exception
{
try
{
Scanner scn=new Scanner(System.in);
int t=scn.nextInt();
for(int l=0;l<t;l++)
{
int n=scn.nextInt();
int k=scn.nextInt();
int d=scn.nextInt();
int tprob=0;
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=scn.nextInt();
tprob+=a[i];
}
int days=tprob/k;
if(d<days)
System.out.println(d);
else
{
System.out.println(days);
}

}
}
catch(Exception e)
{}

}
}```