Codechef January Challenge 2021 Division 3 : Chef and Division 3

Chef and Division 3 | Problem Code: DIVTHREE

Question Link : https://www.codechef.com/JAN21C/problems/DIVTHREE

Video Link : https://youtu.be/ItN6GMcuqmA

Chef wants to host some Division-3 contests. Chef has N$N$ setters who are busy creating new problems for him. The ith$i^{th}$ setter has made Ai$A_i$ problems where 1≤i≤N$1\le i\le N$.

A Division-3 contest should have exactly K$K$ problems. Chef wants to plan for the next D$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$D$ days?

Input:

• The first line of input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains three space-separated integers - N$N$, K$K$ and D$D$ respectively.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ 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$D$ days.

Constraints

• 1≤T≤103$1\le T\le {10}^3$
• 1≤N≤102$1\le N\le {10}^2$
• 1≤K≤109$1\le K\le {10}^9$
• 1≤D≤109$1\le D\le {10}^9$
• 1≤Ai≤107$1\le A_i\le {10}^7$ for each valid i$i$

Subtasks

Subtask #1 (40 points):

• N=1$N=1$
• 1≤A1≤105$1\le A_1\le {10}^5$

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$A_1=4$ problems and he needs K=5$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$0$.

• Example case 2: Chef has A1=23$A_1=23$ problems and he needs K=10$K=10$ problems for a Division-3 contest. Chef can choose any 10+10=20$10+10=20$ problems and host 2$2$ Division-3 contests in these 3 days. Hence the second output is 2$2$.

• Example case 3: Chef has A1=20$A_1=20$ problems from setter-1 and A2=36$A_2=36$ problems from setter-2, and so has a total of 56$56$ problems. Chef needs K=5$K=5$ problems for each Division-3 contest. Hence Chef can prepare 11$11$ Division-3 contests. But since we are planning only for the next D=7$D=7$ days and Chef cannot host more than 1$1$ contest in a day, Chef cannot host more than 7$7$ contests. Hence the third output is 7$7$.

Solution Code : IN C++

#include <bits/stdc++.h>  // This will work only for g++ compiler. 

#define for0(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing

#define for1(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing

#define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i) // closed interver from l to r r inclusive

#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i) // reverse 0 based.

#define forr1(i, n) for (int i = (int)(n); i >= 1; --i) // reverse 1 based

//short hand for usual tokens

#define pb push_back

#define fi first

#define se second

// to be used with algorithms that processes a container Eg: find(all(c),42)

#define all(x) (x).begin(), (x).end() //Forward traversal

#define rall(x) (x).rbegin, (x).rend() //reverse traversal

// traversal function to avoid long template definition. Now with C++11 auto alleviates the pain.

#define tr(c,i) for(__typeof__((c)).begin() i = (c).begin(); i != (c).end(); i++)

// find if a given value is present in a container. Container version. Runs in log(n) for set and map

#define present(c,x) ((c).find(x) != (c).end())

//find version works for all containers. This is present in std namespace.

#define cpresent(c,x) (find(all(c),x) != (c).end())

// Avoiding wrap around of size()-1 where size is a unsigned int.

#define sz(a) int((a).size())

#define LL long long

using namespace std;

// Shorthand for commonly used types

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef long long ll;

typedef vector<ll> vll;

typedef vector<vll> vvll;

typedef double ld;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    LL int n,t,k,d,a[100000],sum;

    cin>>t;

    while(t){

        cin>>n>>k>>d;

        for0(i, n) cin>>a[i];

        for0(i, n) sum+=a[i];

        int j =sum/k;

        if(j>=d) cout<<d<<"\n";

        else cout<<j<<"\n";

        sum=0;

        t--;

    }

    return 0;

}

Author:smit_adm

Date Added:30-12-2020

Time Limit:1 secs

Source Limit:50000 Bytes

Languages:CPP14, C, JAVA, PYTH 3.6, PYTH, CS2, ADA, PYPY, PYP3, TEXT, CPP17, PAS fpc, RUBY, PHP, NODEJS, GO, TCL, HASK, PERL, SCALA, kotlin, BASH, JS, PAS gpc, BF, LISP sbcl, CLOJ, LUA, D, R, CAML, rust, ASM, FORT, FS, LISP clisp, SQL, swift, SCM guile, PERL6, CLPS, WSPC, ERL, ICK, NICE, PRLG, ICON, PIKE, COB, SCM chicken, SCM qobi, ST, NEM, SQLQ