# CHEFEZQ - Editorial

Author: Jatin Nagpal
Tester: Srikkanth
Editorialist: Srikkanth

Cakewalk

# PROBLEM:

For first n days, you get a number of queries, however you can answer maximum k queries per day.
Find the first day you get to have a break, i.e. you answer strictly less than k queries.

# EXPLANATION:

We can simulate the process for each day from 1 to n.
If we didn’t get a break in the first n days, we keep answering k queries for \lfloor\frac{q_r}{k}\rfloor days.
So answer in this case is \lfloor\frac{q_r}{k}\rfloor + 1 where q_r is total number of queries.

# TIME COMPLEXITY:

TIME: \mathcal{O}(n)
SPACE: \mathcal{O}(1)

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>

using namespace std;

#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;

#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)

clock_t start = clock();

const int N = 1e5 + 5;
int v[N], sumn = 0;

int n, k;
cin >> n >> k;
sumn += n;
assert(1 <= n && n <= 100000);
assert(1 <= k && k <= 100000000);
LL sumv = 0;
for (int i=0;i<n;++i) {
cin >> v[i];
assert(0 <= v[i] && v[i] <= 100000);
sumv += v[i];
}
assert(1 <= sumv && sumv <= 100000);
int days = 1, answer_me = v[0];
++days;
if (days <= n) answer_me += v[days-1];
}
cout << days << '\n';
}

void solve() {
int n, k;
cin >> n >> k;
sumn += n;
assert(1 <= n && n <= 100000);
assert(1 <= k && k <= 100000000);
for (int i=0;i<n;++i) {
cin >> v[i];
assert(0 <= v[i] && v[i] <= 100000000);
}
LL sum = 0;
for (int i=0;i<n;++i) {
sum += v[i];
if (sum < (i+1) * 1LL * k) {
cout << i+1 << '\n';
return;
}
}
cout << sum / k + 1 << '\n';
}

int main() {
FASTIO;
int T = 1;
cin >> T;
assert(1 <= T && T <= 100000);
for (int t=1;t<=T;++t) {
solve();
}
assert(sumn >= T && sumn <= 100000);
cerr << fixed << setprecision(10);
cerr << "Time: " << (clock() - start) / (CLOCKS_PER_SEC) << " secs\n";
return 0;
}

7 Likes

CHEF AND QUERIES: Full Explanation - Link

8 Likes
3 Likes

chef and easy queries video solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
int64_t t;
cin>>t;
while(t>0)
{
int64_t n,k,noOfQ,quesLeft=0,ctr=0;
cin>>n>>k;
if(n==1)
{
cin>>noOfQ;
cout<<(noOfQ/k)+1<<endl;
}
else
{
while(n>0)
{
ctr++;
cin>>noOfQ;
quesLeft+=noOfQ;
n–;
if(quesLeft < k)
{
cout<<ctr<<"\n";
break;
}
else
{
quesLeft-=k;
}
}
if(n==0 && quesLeft>=k)
{
cout<<ctr+1+(quesLeft/k)<<"\n";
}
if(quesLeft==0)
{
cout<<ctr<<endl;
}
}
t–;
}
return 0;
}

Can someone tell me if there’s anything that Im not covering in this code? I was only able to pass Subtask 2 for this one, and getting SIGFPE for Subtask 1… I checked about SIGFPE, but I wasn’t able to find any scenario where divide by zero was encountered.

Have I misunderstood a part of the problem?

#include<bits/stdc++.h>

#define ll long long int
#define vi vector<int>
#define pb push_back

using namespace std;

int solve(int arr[],int n,int k){
ll buffer = 0;
//    int days = 1;
for(int i = 0;i<n;i++){
if(arr[i]+buffer<k) return i+1;
else if(arr[i]>=k) buffer += arr[i]-k;
else if(arr[i] < k) buffer -= k-arr[i];
//        days++;
}
//days += buffer/k + 1;
return n + buffer/k + 1;

}

int main() {
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
int arr[n];
for(int i = 0;i<n;i++) cin>>arr[i];
cout<<solve(arr,n,k)<<"\n";
}
return 0;
}


I am failing testcase 2. Can someone explain where I am going wrong

You need to consider long long for variable arr array and days.

1 Like

Why my code is wrong.

#include <bits/stdc++.h>
#include <string>
#include <sstream>
#include <iostream>
#define rep(i,a,n) for(int i=int (a);i<int (n);i++)
#define OUT  freopen("output.txt", "w", stdout)
#define IN  freopen("input.txt", "r", stdin)
#define mem(a,b) memset((a),(b),sizeof(a))
#define NumofDigits(n) ((int)log10(n)+1)
#define NumofBits(n) ((int)log2(n)+1)
#define PI 3.14159265358979323846264
#define vii vector<pair<int,int>>
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi  vector<int>
#define vc  vector<char>
#define vl  vector<long>
#define nl  cout<<"\n"
#define pb  push_back
#define mp  make_pair
#define ll  long long
#define ss  second
#define ff  first
#define endl "\n"
#define sp  " "
using namespace std;

int main(){
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
vi a(n);
for(int i = 0; i < n; i++){
cin>>a[i];
}
ll b=0;
int c=-1;
for(int i = 0; i < n; i++){
b += a[i];
b = b-k;
if(b < 0){
c = i+1;
break;
}
}
if(c == -1){
c = n+b/k+1;
}
cout<<c<<endl;
}
}


It worked. Thanks a lot!

In depth explanation with fun : - YouTube

1 Like

In depth explanation, with key observations and caveats for testcase 2

Have a look here

#include <bits/stdc++.h>
using namespace std;
#define inf (long)1e7 + 6
#define ll long long
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void solve(){
ll n, k, x, sum = 0, ans = inf;
cin >> n >> k;
for(ll i = 0; i < n; ++i){
cin >> x;
sum += x;
if((sum / k) <= i)
ans = min(ans, i + 1);
}
ans = min(ans, (sum / k) + 1);
cout << ans << “\n”;
}

int main(){
FASTIO
int t=1;
cin >> t;
while(t–) solve();
return 0;
}

Someone, help me with the code i can’t understand where my code went wrong .It’s giving only partially correct

 # include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
ll  k,temp;
ll T,n;

cin>>T;

while(T--)
{
ll index=0,sum=0;
cin>>n;
cin>>k;
vector<int> arr;
for(int i=0;i<n;i++)
{
int temp;
cin>>temp;
arr.push_back(temp);

}
for(int i=0;i<n;i++)
{
sum+=arr[i]-k;
if(sum<0)
{
index=i;
break;
}
}
if(index!=0){
cout<<index+1<<endl;
}
else{
cout<<n+(sum/k)+1<<endl;
}

}
}


can someone tell me why my code is not passing the 1st tescase

I also did similar thing and still not able to pass subtask-1, did you got what mistake is there?.
I tried applying Floor (don’t know why) and naturally it didn’t work.

If it is the day 1 then ur index becomes 0 and then final answer will change (i.e n +( sum / k) + 1)

I am failing Subtask 1 with the error: RE (SIGFPE). What is wrong in my code?

#include <bits/stdc++.h>
using namespace std;

int main() {
long long int num_test;
long long int days,k;
long long int queries,i,day;

scanf("%lld",&num_test);
for(i=0;i<num_test;i++){
queries =0;
scanf("%lld %lld",&days,&k);

long long int test;
for (day=1;day<=days;day++){
scanf("%lld",&test);
if(queries < k -test){
printf("%lld\n",day);
// printf("here");
break;
}
queries = queries - k + test;
}
if (day>days){
long long int out = (queries/k)+1+days;
printf("%lld\n",out);

}
}
return 0;


}

1 Like
#include<bits/stdc++.h>


using namespace std;

int main() {
int total_testcases;
cin>>total_testcases;

int testcases=0;
//long long int sumn=0;
//long long int sumq=0;

while(testcases<total_testcases){
int n;
long long int k;
cin>>n;
cin>>k;
//assert(n>=1 && n<=100000);
//sumn+=n;
int i;
//assert(k>=1&&k<=100000000);
for(i=0;i<n;i++){
cin>>new_questions;
available_questions=carried+new_questions;
if(available_questions<k){
break;
}
else{
days++;
}

}

if(i==n){
days+=(carried/k);
}

//assert(1<=sumq&&sumq<=100000);
cout<<days<<endl;
testcases++;

}
//assert(total_testcases<=sumn&&sumn<=100000);
return 0;


}

Can someone help me with debugging my code ? I am getting a SIGFPE error. I cannot find any instance where i am dividing with 0. Also, i used long long data type for all the variables.

1 Like

#include
using namespace std;
int main() {
int t,n,k;
cin>>t;
while(t>0)
{
cin>>n>>k;
int a[n],days,que=0,i;
for(int i=0;i<n;i++)
{
int b;
cin>>b;
a[i]=b;
}
for( i=0;i<n;i++)
{
if(a[i]>=k)
{
que=a[i]-k;
a[i+1]=a[i+1]+que;
}
else
{
if(a[i]<k)
{
cout<<i+1;
}
}}
if(que>0)
{
days=que/k;
days=days+i+1;
cout<<days;

            }
t--;
}
return 0;


}
can someone will please tell me why its not running on codechef ide but correctly runs on code blocks?