PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author & Editorialist: Alei Reyes
Tester: Istvan Nagy
DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
Chef Ada is preparing N dishes (numbered 1 through N), the i-the dish requires a cooking time of C_i seconds.
Ada has a kitchen with two identical burners. To cook the i-th dish, she puts it in one of the burners, waits for C_i seconds, and then removes it from the burner. The dishes can be prepared in any order. Two dishes can be cooked simultaneously, however no two dishes can be in the same burner at the same time. When a dish is in a burner, it can’t be removed before it is completely cooked.
What is the minimum time to prepare all dishes?
QUICK EXPLANATION:
Brute force all possible ways of assigning each dish to a burner.
EXPLANATION:
The dishes will be splitted between the two burners. Let L be the sum of cooking times of all the dishes cooked in the first burner, similarly let R be the sum of cooking times of the second burner. The total time required to cook all dishes is T=min(L,R). If we denote by S the sum of cooking times of all dishes, then L+R=S and therefore T=min(L,S-L)
There are three possible ways of splitting the dishes, we can try all possibilities:
- all dishes are cooked in only one burner, this optimal when there is only one dish!
- one dish is cooked in the first burner (let’s say dish i), and the rest in the second burner. The cooking time is min(C_i,S-C_i).
- each burner cooks two dishes, let’s say dishes i and j are cooked in the first burner. The cooking time is min(C_i+C_j, S-(C_i+C_j))
SOLUTIONS:
Setter's Solution, first subtask
for _ in range(input()):
n = input()
c = map(int, raw_input().split())
s = sum(c)
print ((n+1)/2)*c[0]
Setter's Solution, full score
for _ in range(input()):
n = input()
c = map(int, raw_input().split(" "))
s = sum(c)
ans = s
for x in c:
ans = min(ans, max(x, s-x))
for i in range(n):
for j in range(i+1,n):
x = c[i] + c[j]
ans = min(ans, max(x, s-x))
print ans
Tester's Solution (C++)
int main(int argc, char** argv)
{
int T;
cin >> T;
forn(i, T)
{
int N, csum = 0, best = 1000;
cin >> N;
vector<int> C(N);
for (auto& ci : C)
{
cin >> ci;
csum += ci;
}
for (int j = 0; j < (1 << N); ++j)
{
int su = 0;
for (int k = 0; k < N; ++k)
{
if ((1 << k) & j)
su += C[k];
}
best = min(best, max(su, csum - su));
}
cout << best << endl;
}
return 0;
}
