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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#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;
void subtask() {
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];
while(answer_me > 0) {
int answer = min(answer_me, k);
if (answer < k) break;
++days;
answer_me -= k;
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();
// subtask();
}
assert(sumn >= T && sumn <= 100000);
cerr << fixed << setprecision(10);
cerr << "Time: " << (clock() - start) / (CLOCKS_PER_SEC) << " secs\n";
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.
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.
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;
int main() {
// your code goes here
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;
long long int available_questions=0,days=1,carried=0,answered=0,new_questions=0;
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{
answered=k;
carried=available_questions-answered;
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.
