PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY
Cakewalk
PREREQUISITES
None
PROBLEM
Given order details for two days, delivery charge and cost of a coupon which waives the delivery charges on orders worth \geq 150 rupees, determine whether it is beneficial to apply coupon or not.
QUICK EXPLANATION
Compute the cost with and without coupon and compare them.
EXPLANATION
Since we are checking whether buying coupon is beneficial or not, all we need to do is to compute the cost with and without coupon. It is useful to apply coupon only if the cost including coupon cost is strictly less than the total cost without coupon.
Since all the items on same day are delivered together, we only care about sum of cost of items. So let’s denote A = A_1+A_2+A_3 and B = B_1+B_2+B_3 be the order cost of first and second day.
Cost without coupon is easy to compute. Order of first day is worth A rupees and delivery charges D, so cost for first day is A+D. Cost for second day is B+D. Hence, total cost, if coupon is not purchased is A+B+2*D
Cost with coupon firstly includes coupon cost C. Order costs remain unaffected with coupon, so order costs A and B remain same.
- If none of A and B is \geq 150, then delivery cost is added twice.
- If exactly one of A and B is \geq 150, then delivery cost is added once.
- If both A and B are \geq 150, then delivery cost is not added.
Hence, the order cost when coupon is purchased is C+A+B+x where x denote the number of orders with cost <150 rupees.
So now we have cost in both cases, so we can compare them and determine whether it is beneficial to purchase coupon or not.
Follow up
Suppose you are given order amounts for N days, coupon cost C and delivery cost D. A coupon is valid only for K days. Find the minimum cost, if coupon can be bought any number of times, any day.
TIME COMPLEXITY
The time complexity is O(1) per test case.
The memory complexity is O(1) per test case.
SOLUTIONS
Setter's Solution
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
public static void main(String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
int T=Integer.parseInt(br.readLine().trim());
StringBuilder sb=new StringBuilder();
while (T-->0)
{
String[] s=br.readLine().trim().split(" ");
int D=Integer.parseInt(s[0]);
int C=Integer.parseInt(s[1]);
s=br.readLine().trim().split(" ");
int A1=Integer.parseInt(s[0]);
int A2=Integer.parseInt(s[1]);
int A3=Integer.parseInt(s[2]);
s=br.readLine().trim().split(" ");
int B1=Integer.parseInt(s[0]);
int B2=Integer.parseInt(s[1]);
int B3=Integer.parseInt(s[2]);
int X=C+((A1+A2+A3)>=150?0:D)+((B1+B2+B3)>=150?0:D);
int Y=2*D;
sb.append(X<Y?"YES\n":"NO\n");
}
System.out.println(sb);
}
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <limits>
#ifdef HOME
#define NOMINMAX
#include <windows.h>
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
// if(g == '\r')
// continue;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
std::mt19937 rng(0x15c51);
template<typename T>
T getRandom(T from, T to)
{
std::uniform_int_distribution<T> distribution(from, to);
return distribution(rng);
}
int main(int argc, char** argv)
{
#ifdef HOME
if (IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
// int Tc = 100000;
// printf("%d\n", Tc);
// forn(tc, Tc)
// {
// printf("%d %d\n", getRandom(1, 100), getRandom(1, 100));
// printf("%d %d %d\n", getRandom(1, 100), getRandom(1, 100));
// printf("%d %d %d\n", getRandom(1, 100), getRandom(1, 100));
// }
//
// return 0;
#endif
int T = readIntLn(1, 100000);
forn(tc, T)
{
int D = readIntSp(1, 100);
int C = readIntLn(1, 100);
int A1 = readIntSp(1, 100);
int A2 = readIntSp(1, 100);
int A3 = readIntLn(1, 100);
int B1 = readIntSp(1, 100);
int B2 = readIntSp(1, 100);
int B3 = readIntLn(1, 100);
int v1 = A1 + A2 + A3 + B1 + B2 + B3 + D + D;
int v2 = A1 + A2 + A3 + B1 + B2 + B3 + C;
if (A1 + A2 + A3 < 150)
v2 += D;
if (B1 + B2 + B3 < 150)
v2 += D;
if (v2 < v1)
printf("YES\n");
else
printf("NO\n");
}
assert(getchar() == -1);
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class COUPON2{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int D = ni(), C = ni();
int A = ni()+ni()+ni();
int B = ni()+ni()+ni();
int withoutCoupon = A+B+D+D;
int withCoupon = C + A+B+ (A >= 150?0:D) + (B >= 150?0:D);
pn(withCoupon < withoutCoupon ?"YES":"NO");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new COUPON2().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
VIDEO EDITORIAL:
Feel free to share your approach. Suggestions are welcomed as always. 
