Help me Debugging my code

problem- Demonetisation

contest- BITFLIT

PROBLEM LINK:- https://www.codechef.com/BITF2016/problems/DMNTION

MY CODE :- https://www.codechef.com/viewsolution/12347310

RESULT :- WA

The contest is over now so please help me debugging it.

@neget Your logic is correct but you are taking answer as int, just change it to long long int and it will get AC. Although, according to the limits, the maximum answer for a single test case can be 1000500000 which is well within the limit of int, but sometimes the test data might contain some larger test cases also. So, its a good practice to take final answer as long long int in such cases.

@neget Your code is correct but you forgot something. “long long int sum”.

When I remove all “if-else” conditions the result is AC and also time efficient. Check it out.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long int sum;
        long long int tc=0;

        for(int i=0;i<n;i++)
        {  
            cin>>sum;

            tc= tc+sum/100;
            sum=sum%100;
            tc=tc+sum/50;
            sum=sum%50;
            tc=tc+sum/20;
            sum=sum%20;
            tc=tc+sum/10;
            sum=sum%10;
            tc=tc+sum/5;
            sum=sum%5;
            tc=tc+sum/3;
            sum=sum%3;
            tc=tc+sum/2;
            sum=sum%2;
            tc=tc+sum;
        }
    cout<<tc<<endl;
    }
return 0;
}

@neget
Your code to the problem can be simplified has in poste by @only4. But you would still recieve WA. It would fail some test cases.

How many minimum coins of 1,4,9 would you need to make an amount of 12?

According to your code: 9+1+1+1(=4)

Actual Answer: 4+4+4 (=3) which would be the correct answer


Editorial for DMNTION can be found here

To implement this problem, there is a concept of Dynamic Programming aka DP. It is very important concept in dynamic programming. Check out the below link to know more about dp:

https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/

https://www.codechef.com/wiki/tutorial-dynamic-programming

1 Like
//