PROBLEM LINK:
Setter: Daanish Mahajan
Tester: Alexander Morozov
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Basic math, Ceiling function
PROBLEM:
We have two companies A and B. Company A produces V1 vaccines starting from day D1 and company B produces V2 vaccines starting from day D2. We are asked to find the minimum number of days required to produce P vaccines.
QUICK EXPLANATION:
Without loss of generality assume D1<D2. Let the required answer be d. Check two cases:
-
D1 \le d<D2
-
d \ge D2
Form mathematical expressions accordingly and find the minimum value of d.
EXPLANATION:
First of all if D1>D2, then swap D1 with D2 and V1 with V2. This clearly wonāt affect our final answer. Now check the following cases:
Case 1:
-
D1 \le d < D2
If this is the case, then the total vaccines produced by the end of d^{th} day will be
(d-d1+1) \cdot V1 . This must be greater than P. Then, we have (d-d1+1) \cdot V1 \ge P. On solving this, we get d \ge \Bigl\lceil \dfrac{P}{V1} \Bigr\rceil + D1 - 1 . Thus, minimum d will be \Bigl\lceil \dfrac{P}{V1} \Bigr\rceil + D1 - 1 . If this value of d \ge D2, we move on to the next case.
Case 2:
-
d \ge D2
If this is the case, then the total vaccines produced by the end of d^{th} day will be
(d-D1+1) \cdot V1 + (d-D2+1) \cdot V2 . This must be greater than P. Then, we have (d-D1+1) \cdot V1 + (d-D2+1) \cdot V2 \ge P. On solving this, we get
d \ge \Bigl\lceil \dfrac{P+(D1-1) \cdot V1+(D2-1) \cdot V2}{V1+V2} \Bigr\rceil . Thus, the minimum value of d will be the right side of the inequality .
TIME COMPLEXITY:
O(1) since we are just solving a bunch of inequalities.
SOLUTION:
Editorialist's solution (C++)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int D1, V1, D2, V2, P;
cin >> D1 >> V1 >> D2 >> V2 >> P;
if (D1 > D2)
{
swap(D1, D2);
swap(V1, V2);
}
int d = (P / V1) + (P % V1 > 0) + D1 - 1;
if (d < D2)
cout << d << endl;
else
{
int num = P + (D1 - 1) * V1 + (D2 - 1) * V2;
int den = V1 + V2;
d = (num / den) + (num % den > 0);
cout << d << 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/1/out5.txt"));
in = new InputReader();
new Main();
out.flush();
out.close();
}
Main()
{
solve();
}
void solve()
{
int d1 = in.nextInt(), v1 = in.nextInt(), d2 = in.nextInt(), v2 = in.nextInt(), p = in.nextInt();
if (d2 < d1)
{
d2 ^= d1;
d1 ^= d2;
d2 ^= d1;
v2 ^= v1;
v1 ^= v2;
v2 ^= v1;
}
int maxp = (d2 - d1) * v1;
if (maxp >= p)
{
out.println(d1 - 1 + (p + v1 - 1) / v1);
}
else
{
p -= maxp;
v1 += v2;
out.println(d2 - 1 + (p + v1 - 1) / v1);
}
}
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/1/in5.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 (English):
VIDEO EDITORIAL (Hindi):
Please comment below if you have any questions, alternate solutions, or suggestions.