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

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

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

you accidentely linked ur profile instead of code :stuck_out_tongue:


This is your code.
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.

#include <bits/stdc++.h>

using namespace std;

int main()
    int t;
    cin >> t;
    while (t--)
        int n, s, ans = 0;
        cin >> s >> n;
        if (s & 1)
        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. :partying_face: :partying_face: