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:

2 Likes

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.

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. :partying_face: :partying_face: