# Problem Link

Author: Vaibhav Chaurasia

Editorialist: Rudransh Tripathi

# Difficulty

Cakewalk

# Prerequisites

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)
{
cout << "BAD EXPERIENCE"<< "\n";
}
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:
print("BAD EXPERIENCE")
else:
print("GOOD EXPERIENCE")
```