# Adjusting time limit(Chef and Demonetisation Problem Code: CHFMOT18)

how should i optimize my code so it doesn’t the exceed time limit?

I already replaced cin and cout with printf and scanf. Still the time limit is exceeding.

2 Likes

Your code is terrible. It’s really slow. Try to come up with a O(1) solution (pretty simple).
Greedily choose coins. If S is odd, you HAVE to use a coin of denomination 1. Now subtract 1 from S if it is odd. Now you will have an even S. You can be greedy and choose \text{floor}\Big(\dfrac{S}{N}\Big) coins of denomination N (since it’s even). Now remove \text{floor}\Big(\dfrac{S}{N}\Big) \times N from S. Now S will be even (parity won’t change) and will be in [0, \ n). So we only need 1 more coin if S is not 0.

Code
#include <bits/stdc++.h>

using namespace std;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, s, ans = 0;
cin >> s >> n;
if (s & 1)
{
++ans;
--s;
}
ans += (s/n);
ans += (s%n!=0);
cout << ans << '\n';
}
}

1 Like

Oo, Sorry. I will be careful next time.

Sorry for my terrible code. I have just started, don’t have much practice and experience. Thank you for your explanation. I will try to understand as much as i can.

I got it. Thank you.