PROBLEM LINK:
Setter: Daanish Mahajan
Tester: Alexander Morozov
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
CAKEWALK
PREREQUISITES:
PROBLEM:
We have an array of ages for N people. Anyone whose age is \ge 80 or \le 9 is considered to be at risk. Per day, you can only vaccinate up to D people and on each day you cannot vaccinate both categories of people (those who are at risk and those who are not at risk). The task is to find the minimum number of days to vaccinate all N people.
QUICK EXPLANATION:
First find the minimum numbers of days to vaccinate all the people who are at risk, then find the same for all the people who are not at risk and add the results to get the required answer.
EXPLANATION:
Since on a particular day we can’t vaccinate both risky people and non-risky people, let us treat both the cases separately and finally add both the results to get the final answer.
-
First count the number of people who are at risk. Let the count be R . Since on each day we can give vaccine to atmost D people, the minimum number of days required to vaccinate all the risky people wll be \Bigl\lceil \dfrac{R}{D} \Bigr\rceil .
-
The number of people who are not at risk will be N-R . Similar to the above case, the minimum number of days required to vaccinate all the non-risky people will be \Bigl\lceil \dfrac{N-R}{D} \Bigr\rceil .
-
Therefore, the minimum number of days required to vaccinate all N people will be
\Bigl\lceil \dfrac{R}{D} \Bigr\rceil + \Bigl\lceil \dfrac{N-R}{D} \Bigr\rceil .
TIME COMPLEXITY:
O(n) for each testcase.
SOLUTION:
Editorialist's solution (C++)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, d;
cin >> n >> d;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int risk = 0, not_risk = 0;
for (int i = 0; i < n; i++)
{
if (a[i] >= 80 || a[i] <= 9)
risk++;
else
not_risk++;
}
int ans = (risk / d) + (risk % d > 0) + (not_risk / d) + (not_risk % d > 0);
cout << ans << endl;
}
return 0;
}
Setter's solution (Java)
import java.util.*;
import java.io.*;
public
class Main
{
static PrintWriter out;
static InputReader in;
public
static void main(String args[]) throws IOException
{
out = new PrintWriter(System.out);
// out = new PrintWriter(new FileWriter("/home/daanish/CP/codechef/LearningTeam/Testing/2020/Long/Dec/2/out.txt"));
in = new InputReader();
new Main();
out.flush();
out.close();
}
Main()
{
solve();
}
final int maxd = (int)1e5;
final int maxn = (int)1e4;
void solve()
{
int t = in.nextInt();
while (t-- > 0)
{
int n = in.nextInt(), d = in.nextInt();
int c1 = 0, c2 = 0;
for (int i = 0; i < n; i++)
{
int x = in.nextInt();
if ((x >= 0 && x <= 9) || (x >= 80 && x <= 100))
c2++;
else if (x > 9 && x < 80)
c1++;
}
if (c1 + c2 != n || n > maxn || n < 0 || d > maxd || d < 0 || t > 9 || t < 0)
System.out.println("wrong test no: " + t);
out.println(((c2 + d - 1) / d + (c1 + d - 1) / d));
}
}
public
static class InputReader
{
BufferedReader br;
StringTokenizer st;
InputReader() throws IOException
{
br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new FileReader("/home/daanish/CP/codechef/LearningTeam/Testing/2020/Long/Dec/2/in.txt"));
}
public
int nextInt()
{
return Integer.parseInt(next());
}
public
long nextLong()
{
return Long.parseLong(next());
}
public
double nextDouble()
{
return Double.parseDouble(next());
}
public
String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
}
}
return st.nextToken();
}
}
}
VIDEO EDITORIAL:
Please comment below if you have any questions, alternate solutions, or suggestions.