# Editorial - TFTWN

Author: Vaibhav Chaurasia
Editorialist: Rudransh Tripathi

Cakewalk

Binary Search

# Problem

Aanchal likes to visit different restaurants and try the dishes they offer. One day she decides to visit this restaurant called The Food Town. There are N chefs working there and they take specific amount of time T to cook any of the dishes. Aanchal knows the time T_i (time taken by each chef to prepare a dish). Chefs can work simultaneously on different tables, and she can make any chef/chefs work for her to prepare required Q dishes. She notes the minimum time required to make all Q dishes. But she is a moody girl and does not like 3 or any of its multiples and considers it as bad timing. If the minimum time comes out to be bad, she rated her visit as BAD EXPERIENCE otherwise GOOD EXPERIENCE.

# Quick Explanation

Just use binary search.

# Explanation

You are given N chefs and asked the minimum time these chefs require to prepare Q dishes such that the i chef creates a dish in T{_i} time.
We check all the possible outcomes between 0 and 10^{18} using binary search.
For some value solution we use binary search, we are left with the task of checking whether we can create Q dishes in solution time. To do this, observe that it’s optimal for every chef to work simultaneously. Then, in solution time, chef i can create \lfloor{\frac{solution}{Ti}}\rfloor dishes.
Overall, the N chefs can prepare \sum_{i=1}^{N} \lfloor{\frac{solution}{Ti}}\rfloor dishes. If this solution \geq Q, then solution is valid. Finally, check divisibility by 3.

# Solution

C++ Solution
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {

ll n;
ll q;
cin >> n >> q;
vector<ll> vec(n);
for(ll i=0;i<n;i++)
{
cin >> vec[i];
}
ll lo=0,hi=1e18,ans=0;
while(lo <= hi)
{
ll mid = (lo + hi)/2;
ll temp=0;
for(ll i=0;i<n;i++)
{
temp+=(mid/vec[i]);
if(temp>=q)
{
break;
}
}
if(temp >=q)
{
ans=mid;
hi=mid-1;
}
else
{
lo=mid+1;
}
}
if(ans%3==0)
{
}
else
{
cout << "GOOD EXPERIENCE" << "\n";
}

return 0;
}

Python Solution
#Author: rt24
from math import floor
from sys import stdin, stdout

n, q = map(int, input().split())
ar = list(map(int, input().split()))

left = 1
right = int(1e18)

while left < right:
mid = (left + right) // 2
#print(str(mid) + " " + str(left) + " " + str(right))
ans = 0
for i in range (0, n) :
ans += min(mid // ar[i], 1e9)

if ans >= q:
right = mid
else:
left = mid + 1

#stdout.write(str(left))
if left % 3 == 0: