PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Soumyadeep Pal
Tester: Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY
Cakewalk
PREREQUISITES
None
PROBLEM
Chef has 3 boxes of sizes A, B, and C respectively. He puts the boxes in bags of size D (A \leq B \leq C \leq D). Find the minimum number of bags the Chef needs so that he can put each box in a bag. A bag can contain more than one box if the sum of the sizes of boxes in the bag does not exceed the size of the bag.
QUICK EXPLANATION
- The number of required boxes never exceeds 3.
- One box is sufficient when A+B+C \leq D
- Two boxes are sufficient when A+B \leq D
EXPLANATION
First of all, We never need more than three boxes, as we can put each of the three boxes in one box of size D.
Hence, the number of boxes required is \leq 3. Let’s identify when 1 or 2 boxes are sufficient.
If the chef has only one bag, the only way all three boxes can be put inside is if and only if A+B+C \leq D, as total capacity must be at least the sum of sizes of boxes to be put inside.
Hence, now we need to identify when 2 boxes are sufficient. We have three boxes to pack, and two boxes to store them in, so we can see that two boxes would be packed in one box of size D and the third box would be stored in a separate box of size D.
There are only three ways to choose which box is in different boxes of size D. WLOG assume A was in one box and B and C are in the second box. We need to ensure A \leq D and B+C \leq D. We can try all three cases and if two boxes are sufficient in any case, we can pack those in two boxes of size D.
Otherwise, we have proven that they can be packed in 3 boxes but not in 2 boxes. Hence the minimum number of boxes needed must be 3.
Bonus
- Prove that condition A+B \leq D is sufficient to determine whether two boxes are sufficient or not.
Figure out why condition A+B+C \leq 2 \times D is not sufficient to guarantee that two boxes of size D can be used to keep the boxes of sizes A, B, and C. Find out a case.
TIME COMPLEXITY
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif
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) {
if (is_neg) {
x = -x;
}
deb(l, r, 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;
}
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, ' ');
}
///////////////////////////////////////////////////////////////////////
void solve() {
int a, b, c, d;
a = readIntSp(1, 100);
b = readIntSp(a, 100);
c = readIntSp(b, 100);
d = readIntLn(c, 100);
int ans = 3;
if (d >= a + b + c) ans = 1;
else if (d >= a + b) ans = 2;
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("ip1.txt", "r", stdin);
freopen("out1.txt", "w", stdout);
#endif
int t = readIntLn(1, 100);
while (t--) {
solve();
}
assert(getchar() == -1);
return 0;
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#ifdef HOME
#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;
}
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, ' ');
}
int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T = readIntLn(1, 100);
forn(tc, T)
{
int A = readIntSp(1, 100);
int B = readIntSp(A, 100);
int C = readIntSp(B, 100);
int D = readIntLn(C, 100);
if (A + B + C <= D)
printf("1\n");
else if (A + B <= D)
printf("2\n");
else
printf("3\n");
}
assert(getchar() == -1);
return 0;
}
Editorialist's Solution
import java.util.;
import java.io.;
class THREEBOX{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int A = ni(), B = ni(), C = ni(), D = ni();
if(A+B+C <= D)pn(1);
else if(A+B <= D)pn(2);
else pn(3);
}
//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 THREEBOX().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;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always.